1

スイープ ライン アルゴリズムでは、左から右にスキャンするスイープ垂直線を使用するときに、形状 (円または長方形) の右端点をどのように検出するのか疑問に思っています。したがって、アルゴリズムは基本的に、左の端点に到達するとその形状の 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 の適切な終点に到達したかどうかはいつわかりますか? そのために別のハッシュマップが必要ですか?

4

1 に答える 1

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;
    }
}
于 2012-10-28T16:49:38.347 に答える