search

kallaballa / libnfporb

Implementation of a robust no-fit polygon generation in a C++ library using an orbiting approach
GNU General Public License v3.0
106 stars 31 forks source link

Edge case false positive degenerate case #22

Closed Naimad1CZ closed 3 years ago

Naimad1CZ commented 3 years ago

When having those 2 polygons: POLYGON((20 10,20 30,30 30,30 10,40 20,40 30,30 40,60 40,60 80,0 80,20 40,10 30,10 20)) POLYGON((50 30,50 20,60 20,60 30)) The resulting NFP consists of 1 big loop (correct) and 1 degenerate point (wrong).

image

I can see why it's selected - all vertices of polygon B (sliding polygon) are touching vertices of the polygon A, but everything else (except one edge) from polygon B is directly inside the polygon A.

kallaballa commented 3 years ago

The paper i based this on is incomplete when it comes to edge-cases with parallel lines. i tried to improvise but wasn't able to cover it all. -> a91f1ae12ba28455e54c076e9be757b9be888201 seems to work except for this issue

kallaballa commented 3 years ago

I am on it :)

kallaballa commented 3 years ago

fixed