Content deleted Content added
mNo edit summary |
mNo edit summary |
||
Line 32:
* In the first phase, pairwise intersections between edges of the polygons are computed. Additional vertices are inserted into both polygons at the points of intersection; an intersection vertex holds a pointer to its counterpart in the other polygon.
* In the second phase, each intersection is marked as either an ''entry intersection'' or an ''exit intersection''. This is accomplished by evaluating the even–odd rule at the first vertex and then traversing the polygon and marking the intersections with alternating flags (the next intersection after an entry intersection must be an exit intersection).
* In the third phase, the result is generated. The algorithm starts at an unprocessed intersection and picks the direction of traversal based on the entry/exit flag: for an entry intersection it traverses forward, and for an exit intersection it traverses in reverse. Vertices are added to the result until the next intersection is found; the algorithm then switches to the corresponding intersection vertex in the other polygon and picks the traversal direction again using the same rule. If the next intersection has already been processed, the algorithm finishes the current component of the output and
The algorithm is not restricted to polygons and can handle arbitrary [[parametric curve]]s as segments, as long as there is a suitable pairwise intersection procedure.
| |||