Incorrect Polygon Decomposition (Snoeyink-Keil)

[voces]

Compiled to JavaScript and the following polygon is decomposing incorrectly:

[   {x: 0,   y: 0},
    {x: 300, y: 280},
    {x: 200, y: 300},
    {x: 150, y: 350},
    {x: 0,   y: 400},
    {x: 400, y: 400},
    {x: 400, y: 0}     ]

One of the resulting sub-polygons seems to be missing the corner vertex. In the following image, the red represents the original polygon while the purple represents new polygons:

[azrafe7]

Definitely a bug, thanks for reporting it!

Not sure yet if my port is faulty, or there's a problem in the original implementation (http://www.cs.ubc.ca/~snoeyink/demos/convdecomp/MCDDemo.html). In any case it's not going to be easy too to track down.

Can you please try if preprocessing your polys so that the first vertex is always the top-right-most one makes it work correctly?

(meaning something like this)

    var testPoly = [
        {x: 0,   y: 0},
        {x: 300, y: 280},
        {x: 200, y: 300},
        {x: 150, y: 350},
        {x: 0,   y: 400},
        {x: 400, y: 400},
        {x: 400, y: 0 }
    ];

    var topRightIdx = 0;
    var p = testPoly[0];
    for (i in 1...testPoly.length) {
        var q = testPoly[i];
        if (q.y < p.y || (q.y == p.y && q.x > p.x)) {
            topRightIdx = i;
            p = q;
        }
    }
    if (topRightIdx != 0) {
        var newTail = testPoly.splice(0, topRightIdx);
        testPoly = testPoly.concat(newTail);
    }

And even if that works out, I'd really appreciate if you report back with more failing cases. As that would surely help me in isolating the bug.

Thanks!

[voces]

That did fix the provided polygon, but I found a very similar case:

[ {x: 500, y: 0},
  {x: 0,   y: 0},
  {x: 0,   y: 500},
  {x: 200, y: 400},
  {x: 500, y: 500},
  {x: 350, y: 150},
  {x: 400, y: 100},
  {x: 200, y: 100},
  {x: 100, y: 400},
  {x: 100, y: 100}  ]

As an image:

I believe it's the same issue. If I remove the first three and last vertex, it results in an error. If I do the same but order it as suggested (top-right first), it works fine.

[azrafe7]

I've probably found the culprit. It's on my side (not the original impl.) and involves how I'm reconstructing the polys based on the diagonals the algo finds (around here).

Working on it... it'll require some thinking and tinkering though.

[azrafe7]

Hey @voces, I just pushed a commit that aims to fix these issues, can you please try if it works for you?

[voces]

Awesome, that fixed it. After this 1650-point test, I'm mostly convinced it works for random shapes.

[azrafe7]

That's great to hear! \o/

Please report back if you encounter any other issues with it.

Can you test if big polys like this work correctly regardless of orientation (so both in cw or ccw order)?

(Not directly related but, as a next step, I'm going to ditch my current EarClipper impl. and port the one from mapbox, which seems way more robust and flexible than my current code)

[azrafe7]

For clarity I'd also add that there should be no need to "align" to the top-right vertex (was just a thing I needed for investigating the issue).

Closing this now, but please file another one if you have any more problems with it.