Sunday, April 02, 2006

Polygon intersection.

1> We need to decompose the two polygons into nodes and edge which make up the graph.
2> Combine the nodes and edges from those two polygons into one big graph, which is the initial graph we need to deal with.
3> Applies the sweep line intersection algorithm to get all the intersection points between the egdes from two polygons. The invariant is that the part of the overlay above the sweep line has been computed correctly.
4> If the event involves only edges from one of the two subdivsions, that is all; The event point is a vertex that can be re-used. If the event involves the edges from both subdivisions, we must link the doubly-connected edge lists of the two original subdivisions at the intersection point.
5> When an edge e passes through another polygon at point v, the edeg e must be replaced by two edges e1 and e2. The two half-edges become four half-edges. We create two new half-edge records whith v as the origin. The new edge e1 is represented by one new (with v as its origin) and one existing half-edge (with e's end point as its origin), and the same holds for e2.
6>
6-a> Link the edges at the end node of original edge e.
The most important part is that we have to link those edges with Prev() and Next() pointers. The Next() pointers of the two new half-edges each copy the Next() pointers of the old half-edge that is not its twin. The half-edges to which these pointers point must also update their Prev() pointer and set it to the new half edges().
6-b> Link the edge at the point v.
Consider the half edge for e1 that has v as its destiantion, it must be linked to the first half-edge, seen clockwise from e1, with v as its origin. The half edge for e1 with v as its origin must be linked to the first counterclockwise half-edge with v as its destination.
GISResearch

No comments: