quickDecomp sometimes returns incorrect results altough isSimple() returns true

[Livor]

Hi,

I use matter-js, which uses poly-decomp for decomposition of concave shapes. And from what I can tell they use it correctly.
As I understand decomposition should work if isSimple() returns true, correct me if I'm wrong.

my stringified dataset:
[[0,-79.44508550870114],[10,-99.0834989573238],[20,-128.29964750979318],[30,-185.09029800617753],[40,-134.0195021932894],[50,-139.5227157326003],[60,-215.58025321809043],[70,-6.122609059449391],[80,-236.07719042816427],[90,-226.24259910699942],[100,-238.8041580583293],[110,-140.12907455932222],[120,-52.898053692856664],[130,-116.1611158499016],[140,-182.81279630844563],[150,-57.05993977865975],[160,-93.0145040380496],[170,-234.66429450441535],[180,-36.42968890750706],[190,-163.89528934984702],[200,0],[0,0]]

and result as returned by poly-decomp:
[[[40,-134.0195021932894],[10,-99.0834989573238],[20,-128.29964750979318]],[[20,-128.29964750979318],[30,-185.09029800617753],[40,-134.0195021932894]],[[50,-139.5227157326003],[60,-215.58025321809043],[70,-6.122609059449391]],[[118.85126572145955,0],[0,0],[0,-79.44508550870114],[10,-99.0834989573238],[40,-134.0195021932894],[50,-139.5227157326003],[110,-140.12907455932222],[120,-52.898053692856664]],[[130,-116.1611158499016],[140,-182.81279630844563],[150,-57.05993977865975]],[[160,-93.0145040380496],[170,-234.66429450441535],[180,-36.42968890750706]],[[180,-36.42968890750706],[190,-163.89528934984702],[200,0],[185.00906723012366,0]],[[185.00906723012366,0],[118.85126572145955,0],[120,-52.898053692856664],[130,-116.1611158499016],[160,-93.0145040380496],[180,-36.42968890750706]]]

The error is apparent as the vector [100, -238.8041580583293] does not show up in the result...

I also added images that showcase how it should, and how it actually does, look like. (for this I simply cut the shape into stripes)

[schteppe]

I'm not 100% sure why this happens, but it must be related to precision. I tried scaling your data a bit and now it works fine.

You can reproduce this by pasting the below code in the console on the demo page.

path=[[0,-79.44508550870114],[10,-99.0834989573238],[20,-128.29964750979318],[30,-185.09029800617753],[40,-134.0195021932894],[50,-139.5227157326003],[60,-215.58025321809043],[70,-6.122609059449391],[80,-236.07719042816427],[90,-226.24259910699942],[100,-238.8041580583293],[110,-140.12907455932222],[120,-52.898053692856664],[130,-116.1611158499016],[140,-182.81279630844563],[150,-57.05993977865975],[160,-93.0145040380496],[170,-234.66429450441535],[180,-36.42968890750706],[190,-163.89528934984702],[200,0],[0,0]].map((point)=>[3*point[0]+100,1*point[1]+500]); decomp.makeCCW(path); polys=decomp.quickDecomp(path); mousedown=true; render();

To fix the issue, scale your data by a factor of 3 in the x direction, alternatively scale it by 1/3 in the y direction.

I managed to reduce the input data a little bit, might be useful if someone (me?) gets time over to debug this:

path=[[0,-134],[50,-139],[60,-215],[70,-6],[80,-236],[110,-120],[110,0],[0,0]].map((point)=>[2*point[0]+100,1*point[1]+500]); decomp.makeCCW(path); polys=decomp.quickDecomp(path); mousedown=true; render();

I didn't write the original algorithm myself, so I can't immediately tell where things start to go wrong.

[schteppe]

Fiddled a little bit more with this. I added a polygonCanSee(poly, i, j) check to here, and it fixed the simpler case I posted above, but it broke some other cases and didn't fully work for the full data set you initially posted.
The "bug" is mentioned in the original C++ repo, on this link (case 5).

[schteppe]

Ok, I think I've fixed it... The check on the line I mentioned above is now

if (d < closestDist && (Math.abs(i-j)<=2 || polygonCanSee(poly, i, j))) {

and it seems to work. Your input data works, and the tests run. And the freehand drawing in the demo seems to produce the same results as before with about the same speed. Unfortunately there are very few unit tests so I cannot check if something else broke...

[Livor]

thanks for the effort, it might take me some time but I will test it when possible.

in my little project I play around with a genetic algorithm and randomly generated data (the above is supposed to evolve into a ramp someday), and it triggered the bug about 2-3 out of 10 times maybe more. Therefore I think it can be considered fixed for now if it doesn't show up for me again...

[schteppe]

Awesome, thanks!
If you want to test it right now, you might need to rebuild the library locally. (I only update and commit the build/ directory when releasing)

[schteppe]

I tried reflecting your data along both X and Y and for some reason it doesn't work... I guess this bug needs some more love

[Livor]

if by reflecting you mean to mirror, it might be the order (clockwise vs counter clockwise). I have a faint memory that might matter

[schteppe]

Yeah, mirror, sorry.
It wasn't the order really, it was my fix... Math.abs(i-j)<=2 was supposed to check the distance between the given indices but of course that doesn't work if one of them is in the beginning of the polygon and the other is in the end of the polygon. Anyway, it's fixed now!

[schteppe]

I found a new edge case in my fix and fixed it once more... this time I feel a little bit more confident about it. The polygonCanSee function was not really doing what I thought it was so I made a different one.
Also made it more simple to try a polygon in the demo app: now it works to just run setPath([p0,p1,...]) in the console. It also renders point indices, steiner points (red), and reflex vertices (blue).

[schteppe]

Since I'm pretty confident the bug is fixed, I'll close the issue for now. Re-open it if you find other cases where the algorithm fails.

[schteppe]

And huge thanks for your input!