Split weakly-simple-polygon to true simple polygon or polygons

Question

I want to divide weakly-simple polygons into simple polygons.

Background

The use case is to simplify polygons that are Simplified (Unioned) using Javascript Clipper. Javascript Clipper's as well as original Clipper's SimplifyPolygon() function removes self-intersections and combines common edges, but it cannot produce true simple polygons. The output is used in three.js, which has TriangulateShapes() which needs polygons to be simple. Three.js accepts polygon structures that have one contour and zero or multiple holes.

Input, weakly-simple polygons

Weakly-simple polygons cannot have sequential-duplicate-vertices (true duplicate points), nor holes (islands) nor self-intersections (edge crossing over other edge), but there can be non-sequential-multiple-vertices (vertices that have exactly the same coordinate but not as sequential). The input polygon can have either CW or CCW winding order, which means that CW input is outer polygon and CCW is a hole. The input is either CW or CCW polygon.

The input is an array of polygon points eg.:

// This is a true example of weakly-simple polygon:

var input = [{"X":270,"Y":520},{"X":130,"Y":490},{"X":210,"Y":250},{"X":60,"Y":170},{"X":130,"Y":490},{"X":20,"Y":410},{"X":60,"Y":300},{"X":60,"Y":20},{"X":780,"Y":40}, {"X":680,"Y":180},{"X":460,"Y":130},{"X":210,"Y":250},{"X":320,"Y":100},{"X":220,"Y":80}, {"X":210,"Y":250},{"X":520,"Y":250},{"X":680,"Y":180},{"X":770,"Y":480},{"X":540,"Y":470}, {"X":520,"Y":250},{"X":380,"Y":280},{"X":430,"Y":390},{"X":540,"Y":470},{"X":270,"Y":520},{"X":330,"Y":350},{"X":210,"Y":250}];

This is the above input polygon as an image:

And here are the points numbered, where you can easily see what points are duplicates:

As you see, the above polygon can be divided in multiple ways, eg.:
- One outer polygon with five holes - five outer polygons of which one has one hole

Output, simple polygons as a exPolygon structure

Simple polygon is a polygon that have no self-intersections, no duplicate coordinates whether they were sequential or non-sequential, no holes. The output's simple polygon can have CW or CCW winding order. CW means outer and CCW holes.

The output can have (and in many times there will be) holes, but in certain cases the output has no holes. The output has always at least one outer polygon, but there can be also multiple outer polygons that have zero or more holes.

The output should be an array of exPolygon objects that have properties "outer" and "holes". "outer" is an array of point objects, "holes" is an array of arrays of point objects. If "holes" is populated, the holes in it have to be holes of "outer" polygon in the exPolygon object.

The example of output:

// This is an example of output, but the points are random:

[ { "outer": [{"X":54,"Y":4},{"X":2,"Y":50},{"X":30,"Y":5},{"X":10,"Y":50}],
    "holes": [ [{"X":0,"Y":8},{"X":60,"Y":13},{"X":21,"Y":2},{"X":3,"Y":1}],
               [{"X":21,"Y":2},{"X":50,"Y":2},{"X":6,"Y":1}] ] },
  { "outer": [{"X":54,"Y":4},{"X":2,"Y":50},{"X":30,"Y":5},{"X":10,"Y":50}],
    "holes": [ [{"X":0,"Y":8},{"X":60,"Y":13},{"X":21,"Y":2},{"X":3,"Y":1}],
               [{"X":21,"Y":2},{"X":50,"Y":2},{"X":6,"Y":1}] ] },
  { "outer": [{"X":54,"Y":4},{"X":2,"Y":50},{"X":30,"Y":5},{"X":10,"Y":50}],
    "holes": [] }
];

Output's "outer" polygons are CW, and "holes" are CCW.

There is no limit for counts of points in polygons, count of exPolygons objects nor count of holes.

Here are other examples of weakly simple polygons:

Example of division

Here is an example of input polygon:

Here is how it could be divided:

Some other polygons can have multiple possible alternatives of ouput depending where are the pseudo-duplicate-points.

---

My question

How the polygons can be divided this way and the desired output structure achieved? I'm not asking full code (but if you have some spare time and want to show that it is possible). Thoughts of possible algorithms are also welcome.

---

I have searched hours a solution and tried to find an algorithm.

In case you want to try a solution, I have here a code which I have used to find the duplicates: http://jsbin.com/unuyev/7/edit. It shows the polygon in SVG and shows the points as red circles and an array index of each point (after pressing button "Run with JS").

Here is the same, but with 12 example polygons (change pindex in Javascript window to change the polygon): http://jsbin.com/unuyev/4/edit

---

EDIT: Javascript Clipper 6 is available now and there is support for StrictlySimple. But according to the documentation "There's currently no guarantee that polygons will be strictly simple since 'simplifying' is still a work in progress". I have tested StrictlySimple and it fails in certain cases: Orientation problems and lack of rotation invariance. We hope these are fixed soon and StrictlySimple works as expected.

---

Answer 1

There may be something that I'm missing, but this looks like a classic problem of finding the articulation vertex of a graph. Essentially you're trying to find the weakest point in a graph such that when you cut the graph at that point, you end up with two separate graphs. So in your example, if you cut the polygon at that vertex, you end up with multiple polygons. You can represent your polygons quite easy as a graph, with each vertex representing a graph vertex, and the polygon edges as graph edges.

If I had to solve the problem, this is the approach that I would take. You can check out the following resources:

• Articulation vertices from the Algorithm Design Manual - This is your best bet. He explains the algorithm in simple terms and also gives you C code that you can easily translate into JavaScript. If I had to start writing an algorithm, this is where I would start.
• Biconnected component
• Detection of Articulation Points (search for "articulation")

UPDATE

I'll try and give you a brief overview of the problem and the solution to point you in the right direction. An implementation of this algorithm using graphs will necessarily go into graph-algorithm terminologies, so if you are not familiar with graphs, you might want to read up on them.

The brute-force approach in your case would be to traverse the graph, temporarily delete each vetex and then see if the graph is connected when doing a DFS/BFS traversal on the modified graph. This is not very efficient and will run in quadratic time O(n(m + n)). But there is a linear-time algorithm that is based on classifying the edges of the resultant DFS tree that is formed from a DFS traversal.

In a DFS tree that doesn't contain any back-edges (edges connecting a "lower" node to a node "higher" in the tree [assuming "higher" nodes are those closer to the root]) leaf nodes are not articulation nodes, since deleting any one of them will still leave the graph connected. However, deleting any of the internal nodes will disconnect any nodes that follow it from the root.

Deleting the root of the tree depends on whether it has one or more children. If it has just one child, then it's more-or-less a leaf and so deleting it will have no effect. However, deleting a root node that has more than one child will disconnect the graph.

But in a general graph, you can have back-edges and so deleting any of the nodes in between will not disconnect the graph. So figuring out the articulation vertices boils down to figuring out which sections of the tree are linked to ancestor nodes by back edges (i.e., figuring out the "reachable ancestor" of a vertex).

In the page I linked to from the Algorithm Design Manual, Skiena describes three cases where a vertex can be an articulation vertex (root, bridge, and parent cut-nodes). Using the algorithm he describes, you can figure out if the vertex you are processing, meets any of those conditions. If it does, it is an articulation node.

Hopefully this helps you get started!