Polygon Self-Intersection 2
- Author:
- Ryan Hirst
- Topic:
- Intersection, Polygons, Vectors
I have adopted a consistent set of definitions.
The next step is to find all the points of self-intersection:
To begin, I intersect each distinct pair of lines, and see if the intersections fall on the edges of the polygon. How many calculations will this take? Since the points are connected, the intersections of adjacent segments are already given by the vertices.
Define the coincident case in the same way (they intersect at the common endpoint).
Then, discarding adjacent edges,
Edge may intersect
Edge k= 2, 3, ... n-2 may intersect
Each intersection time has the form , where a,b, c are vectors in the plane.
I have then to calculate this many intersection times:
(n-3) +[(n-3)/2 pairs of (n-2)]
An running time, but a very lightweight one.
The point here is to give the intersections. Optimization later.
Now, to tackle the problem of disambiguating the polygon. The figure in blue is still pretend: GGB does not know how to consistently measure or display its interior. Let us see how this determination can be made. Anticipating my first plan of attack, I have tracked the intersection times of each point, and kept a running list of the pairs of intersecting segments. I believe that the Boolean inside/outside condition, together with the closed path of vertices will immediately provide a procedure.
Onward.