Re: [Lib2geom-devel] Maximum distance between curves

[Krzysztof K. <twe...@gm...>]

2015-04-07 22:28 GMT+02:00 Nathan Hurst <nj...@nj...>:
> I've attached a collection of cases that mentalguy came up with (along
> with an algorithm which is not too dissimilar to what you are
> proposing :)

Seems to me that Mental's idea for boolops was based on the
Weiler-Atherton algorithm, which uses the invariant that the inside is
always in the direction of on of the normals (the left one or the
right one). I use a modified Greiner-Hormann algorithm, which assumes
that shapes have even-odd winding and does not need the uncrossing
step. I have a suspicion that my modified version may also work for
nonzero winding shapes, but I'll have to verify this.

I also know of a modification of this algorithm that correctly solves
all possible degenerate cases for polygons, but it doesn't generalize
to curves.

Regards, Krzysztof