# What is a good algorithm for tracing around the edge of a 2D polyline

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:

1. The polyline does not intersect itself and has no colinear edges.
2. The polyline does not intersect itself but has an interior or exterior loop.
3. The polyline has self intersections in a bowtie shape.
4. The polyline has self intersections which form interior loops.

An example of each (all are closed):

1. Vertex List = (5,3) (10,3) (10,7) (5,7)
2. Vertex list = (0,0) (3,0) (3,3) (1,3) (1,2) (2,2) (2,3) (0,3)
3. Vertex list = (5,3) (10,7) (10,3) (5,7)
4. Vertex list = (0,0) (3,0) (3,4) (1,4) (1,2) (2,2) (2,3) (0,3)

Visually: In this case a convex hulling algorithm really is not appropriate, because I wish to preserve any concavities in the shape.

Results:

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.

• Apr 23 '14 at 5:37
• Is it for rendering the outline on screen (I which case a shader can solve this in screen space)? And thousands of simple poly lines, or also poly lines with thousands of vertices? Apr 23 '14 at 6:02
• It is for computing the overlap between two potentially overlapping shapes. Basically these shapes are going to be the result of offsetting a number of regular 2D polygons, which may be concave. The polygons may have hundreds of vertexes, but probably not thousands. Apr 23 '14 at 6:03
• Were you able to solve this @Stephen Jan 12 '20 at 10:06