[Algorithms] Weiler Atherton Implementation (2D polygon clipping)

[<pie...@fr...>]

Hello,

I am implementing the Weiler Atherton algorithm as it really matches my n=
eeds
for some physic dev:
- concave with holes polygon clipped with concave with holes polygon
- the algorithm outputs 2 lists: inside polygons and outside polygons
- ability to use results as inputs for several passes

You can find the original article here :
http://www.cs.drexel.edu/~david/Classes/CS430/HWs/p214-weiler.pdf


The general cases works really good but it is getting harder with the
pathological cases when some intersections points happens to be the same =
as
some polygon points:
- 2 non parallel edges intersect on one end of one edge
- 2 non parallel edges intersect on one end of one edge which is also an =
end of
the other edge
- 2 parallel edges intersect on two points which are end of edges

I tried different ways to treat them (insert intersection nodes or not) b=
ut
nothing really works for the moment.

The paper is quite "vague" about it :
"If care is taken in placement of intersections where the subject and cli=
p
polygon contours are identical in the x-y plane, no degenerate polygons w=
ill be
produced by the clipping process"

Then the text makes two assertions :
"These two types of intersections will be found to alternate along any gi=
ven
contour and the number of intersections will always be even"

I cant satisfy these two assertions with the different approaches i tried=
 for
the pathological cases...

Anyone has experimented these issues ? Any help is welcome.

Thanks,
--
Pierre Loic Herve