Open path clipping

[helviett]

Hello! One of the usage of polygon clipping is Nesting algorithms. I use Nesting with No Fit Polygons in order to tightly pack polygonal sprites into atlases. Clipper v1 is used as a clipping library and it's functional, fast and I've accomplished great results with it. However I can't handle well edge cases of nesting.

In the NFP Nesting in order to pack polygon you have to determine region in container where you can place polygon by using Inner Fit Polygon. Then you narrow region by taking difference with NFPs of other polygons. There can be two edge cases:

• Region before narrowing is a single point
• Region before narrowing is a segment

A single point edge case is easily handled just implementing point in polygon predicate. I've decided to handle segment edge case with open path clipping but unfortunetely it's is an undefined behaviour according to Clipper documentations. Even a simple example as taking a difference of segment and nothing gives different behaviour: it returns original segment for horizontal segment and nothing for vertical segment.

I wish such edge cases could be handled in a determinist way e.g. providing an option to make border inclusive or exclusive (so we consider polygon to be open or closed set of points). May be it can be achieved by requiring a strict order e.g. left to right, bottom to top. Is it even possible to achieve or underlying algorithms have some limitations?

[AngusJohnson]

Hi Dimitrii.
I'm afraid I'm not sure I understand your question. I understand you're clipping open paths and you're encountering problems when the subject inputs are either 1. a single point, or 2. a segment.

Regarding clipping single points, I'm pretty sure Clipper currently eliminates these during clipping but I could easily change this if this is causing problems for library users.

Regarding segment clipping, I suspect you're alluding to situations where these segments are exactly aligned with clipping paths (ie on the edges of the clipping path). Is this the problem? In these cases then yes, whether these segments are included or excluded from the solutions is currently undefined. This is something I'm working on now, so that these segments will always be including in solutions. (I've mostly got this implemented, but I'll only include this new behaviour when I'm sure it can be done without any significant impact on general clipping performance.)