search

jbuckmccready / CavalierContours

2D polyline library for offsetting, combining, etc.
MIT License
421 stars 79 forks source link

Internal offset of a small closed rectangle #7

Closed lscandella closed 4 years ago

lscandella commented 4 years ago

Hello JBuck and thanks for your excellent work. I'm looking forward for your stable release. I worked as well on Liu paper and was not able to make it work.

Having said that, I found a bizarre result on a simple case. I have a rectangle defined by (x,y,bulge): 0,0,0 120,0,0 120,40,0 0,40,0 isClosed = true

and asked for the internal offset with offset value = 30. I was expecting an empty list of curves, but a curve was return and it was:

x=22 y=22 bulge=0 x=98 y=22 bulge=0 x=98 y=18 bulge=0 x=22 y=18 bulge=0 isClosed=true

Keep in mind that there is a high probability that I misused your code...

Thanks. Bye

jbuckmccready commented 4 years ago

@lscandella Thanks for the bug report.

Short response and fix: I committed a fix and added the test case you posted here, here is the commit for reference: https://github.com/jbuckmccready/CavalierContours/commit/7ecb19fd79e881cf0072b1f783a7de72262d23bd.

More detailed response and background: The offset algorithm generates a raw offset curve for which all self intersects are found. In the event that there are no self intersects (as in the example you posted) I previously had the algorithm check that each vertex position was a valid offset distance from the input curve. This is fairly expensive computation and for my particular use case I was already needing to calculate the areas. So what I did was check that the sign of the area of the offset polyline matched the sign of the area of the input polyline (the sign flips in the collapsed case as the direction of the polyline changes). If the signs didn't match then I discarded the result (it was collapsed).

What I have done to fix the issue is only test that one of the vertexes on the raw offset polyline is a valid offset distance from the input polyline. This should always work for detecting collapsed cases and only involves checking one point. Note however if the input polyline is very small (nearly a singular point) then due to float thresholding in the distance check it may fail to properly detect the inversion. If you need to handle such cases I still recommend checking that the sign of the areas match between the input polyline and offset polyline.

Let me know if you have any other issues or questions.

lscandella commented 4 years ago

JBuck, perfect! Thanks!