pjs@granite.dec.com (Philip J. Schneider) (06/21/88)
I need an algorithm to break up a self-intersecting polygon into
a set of convex polygons. A search through some of the "standard"
references and texts has yielded several algorithms that work on
non-convex polygons, but fail if the polygon is self-intersecting as well.
One solution to the problem might be to clip the polygon "against
itself", which would break it up into a set of non-intersecting polygons,
to which one could then apply an algorithm that worked only on non-self-
intersecting concave polygons. This obviously requires a good bit of
work, not to mention some slightly tedious bookkeeping to program.
This seems to me to be a rather elementary problem (i.e., someone else
must have come across it befor), so my guess is that someone out there
must either have solved it before him/herself, or knows where to start
looking for references. I expect a correct solution to the general
problem is not extremely elegant, but then again . . .
Any help, algorithms, code, or advice would be greatly appreciated.
Thanks in advance for your assistance!
- Philip Schneider
--
Philip J. Schneider | pjs@decwrl.dec.com
DEC Workstation Systems Engineering | pjs@granite.dec.com
100 Hamilton Avenue | (415)853-6538
Palo Alto, CA 94306 | (415)493-3244johnr@praxis.co.uk (John Richards) (06/24/88)
In article <242@granite.dec.com> pjs@granite.dec.com (Philip J. Schneider) writes: > > I need an algorithm to break up a self-intersecting polygon into >a set of convex polygons. A search through some of the "standard" >references and texts has yielded several algorithms that work on >non-convex polygons, but fail if the polygon is self-intersecting as well. > Have a look at: J.Nievergelt and F.P.Preparata, "Plane-sweep algorithms for intersecting geometric figures", Communications of the ACM 25(10), pp.739-747 (1982) They describe the class of plane-sweep algorithms which work by incrementally advancing a "front" across a plane in one direction, processing as you go. Their algorithm processes self-intersecting polygons and produces non-intersecting ones, though their terminology is different. John Richards