Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!husc6!purdue!decwrl!granite!pjs
From: pjs@granite.dec.com (Philip J. Schneider)
Newsgroups: comp.graphics
Subject: Algorithm or pointers to references wanted
Message-ID: <242@granite.dec.com>
Date: 21 Jun 88 00:10:20 GMT
Organization: Digital Equipment, WSE group, Palo Alto, CA
Lines: 29


    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-3244