java - 如何在扫描线算法中检测正确的端点

Question

我想知道 Sweep line algorithm当我们使用从左到右扫描的扫描垂直线时，我们如何检测形状(圆形或矩形)的右端点？所以算法基本上是每当我们击中左端点然后插入到该形状的 y 间隔的区间树中，当我们击中任何形状的右端点时我们将它从区间树中删除。例如

    ArrayList<Circle> circles = new ArrayList<Circle>();
    BinarySearchTree<Interval> intervalTree = new BinarySearchTree<Interval>();

    //sort by x coordinate
    Collections.sort(circles, new Comparator<Circle>(){
          @Override
          public int compareTo(Circle c1, Circle c2){
                return c1.x - c2.x;
          }
    });        

    //here's where the sweep line begins
    for(int i = 0; i < circle.size(); i++)
    {
          //we hit the ith circle's left endpoint 
          Circle current = circle.get(i);

          //insert into the interval tree
          intervalTree.addInterval(new Interval(current.y, current.y+current.height));

    }

但是我们什么时候知道我们是否到达了 Circle 的右端点？我们需要另一个 HashMap 吗？

Answer 1

public enum EventType {
    START,
    END;
}

public class EventPoint implements Comparable<EventPoint> {
    public EventType type;
    public double x;
    public Circle circle;
    public Interval interval;

    public EventPoint(EventType type, double x,
            Circle circle, Interval interval) {
        this.type = type;
        this.x = x;
        this.circle = circle;
        this.interval = interval;
    }

    /**
     * Compare this EventPoint with another. This is used by the priority
     * queue to determine the "minimum" event.
     */
    public int compareTo(EventPoint other) {
        return Double.compare(x, other.x);
    }

    /** Creates a start event, with a circle. */
    public static EventPoint start(double x, Circle circle) {
        return new EventPoint(START, x, circle, null);
    }

    /** Creates an end event, with an interval. */
    public static EventPoint end(double x, Interval interval) {
        return new EventPoint(END, x, null, interval);
    }
}

PriorityQueue<EventPoint> events = new PriorityQueue<EventPoint>();
BinarySearchTree<Interval> intervalTree = new BinarySearchTree<Interval>();

// Initialize all the start events, and include the corresponding circle.    
for (Circle c : circles) {
    events.add(EventPoint.start(c.x, c));
}

while (!events.isEmpty()) {

    // Remove the minimum (leftmost) event from the queue
    EventPoint ep = events.poll();

    switch (ep.type) {

        case START:
            Circle current = ep.circle;
            // (Look for intersections in the interval tree...)

            // Create an interval and add it to the interval tree
            Interval interval = new Interval(current.y, current.y +
                    current.height);
            intervalTree.add(interval);

            // Add an end-event to the queue, and include the interval for
            // later removal.
            events.add(EventPoint.end(current.x + current.width, interval));

            break;

        case END:
            // Remove the interval from the interval tree.
            intervalTree.remove(ep.interval);
            break;
    }
}