Comments (11)
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.
from poly-decomp.js.
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).
from poly-decomp.js.
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...
from poly-decomp.js.
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...
from poly-decomp.js.
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)
from poly-decomp.js.
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
from poly-decomp.js.
if by reflecting you mean to mirror, it might be the order (clockwise vs counter clockwise). I have a faint memory that might matter
from poly-decomp.js.
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!
from poly-decomp.js.
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).
from poly-decomp.js.
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.
from poly-decomp.js.
And huge thanks for your input!
from poly-decomp.js.
Related Issues (14)
- Duplicate point not removed HOT 1
- clockwise order info HOT 2
- Easily returns a concave poly instead of array of convex polys HOT 3
- Shapes return an empty array HOT 1
- Could support a polygon with some holes ? HOT 5
- infinite loop in decomp HOT 2
- Does it decompose polygons with holes? HOT 4
- update dependencies?
- Self overlapping polygon
- Online demo can't run 'Peaks'
- Latest decomp version does not return proper results for path.
- Edge Case Issue - Caused by unsafe initilization of lowerIndex/upperIndex vars in QuickDecomp
- QuickDecomp method extension?
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from poly-decomp.js.