If I have a polyline made up of any number of vertexes, what is an efficient algorithm for tracing around the boundary of this polyline?
There are 4 situations to consider:
- The polyline does not intersect itself and has no colinear edges.
- The polyline does not intersect itself but has an interior or exterior loop.
- The polyline has self intersections in a bowtie shape.
- The polyline has self intersections which form interior loops.
An example of each (all are closed):
- Vertex List = (5,3) (10,3) (10,7) (5,7)
- Vertex list = (0,0) (3,0) (3,3) (1,3) (1,2) (2,2) (2,3) (0,3)
- Vertex list = (5,3) (10,7) (10,3) (5,7)
- Vertex list = (0,0) (3,0) (3,4) (1,4) (1,2) (2,2) (2,3) (0,3)
In this case a convex hulling algorithm really is not appropriate, because I wish to preserve any concavities in the shape.
To clarify, the bow tie shape should not be crossed over, and a simple area calculation should yield an area for this shape (i.e. the two triangles end up logically wound in the same direction).
Not only does this algorithm have to work (which is the first priority) it should be fast enough to run on hundreds of thousands of polylines in a few seconds.
In addition, the algorithm has to be able to handle any combination of the four cases.