1

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:

The shapes to trace the outline of.

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).

This is what the resultant shapes should look like

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.

  • 1
  • 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? – Kris Van Bael 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. – Stephen Apr 23 '14 at 6:03
3

Here is a rough outline of an algorithm which might probably solve your problem:

  1. dissolve the polygon into non-intersecting lines, forming a planar graph

  2. once you have the planar graph, construct the outer hull by adapting the classic gift wrapping algorithm to this graph

Step 1 could be implemented in a simple, but not very efficient manner, by making a intersection test for each pair of edges (giving a running time of O(#Edges²)). A more sophisticated implementation could utilize a sweep line approach. You have to be careful to move your sweep line not just to the coordinates of the existing vertices, but also take care for intersecting points, parallel lines etc. and split the existing lines accordingly. After this step, there should be no crossing or overlaying lines any more.

Step 2 is a simple modification of the classic "convex hull" algorithm: just start with an outer vertice of your graph, move from one vertice to the next adjacent vertice picking the connecting edge with the "smallest angle". Make sure that step 1 passes you the planar graph in a data structure which will allow you to pick all edges connected to a given vertice very quickly.

Hope this helps.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.