From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: comp.graphics.algorithms
Subject: Re: Algorithm to split a polygon that intersect itself!
Date: 24 May 1997 05:35:15 GMT

In article <33830017.2558@lsc.ca>, Jocelyn Denis  <jdenis@lsc.ca> wrote:

>I'm wondering if it already exists an algorithm that would be able to
>split a polygon that intersect itself into several polygons.

What do you want the algorithm to produce in a case like this:

*--------------------------------------*
|A                                     |B
|                                      |
|             E*------*F               |
|               \    /                 |
|                \  /                  |
|                 \/                   |
|                 /\D                  |
|                /  \                  |
|G              /    \                 |
*--------------/      \----------------*C

Do you want  ABCEFG  converted to:  ABCDEFDG,  ABCDFEDG, ABCDFEDG union DEF,
ABCDFEDG union DFE, ABCDG union DEF (or DFE), ABCDG, ...

All are reasonable requests. Perhaps clarifying your intention will help
formulate an algorithm. (If you're still unclear on what you want, play
the same game but with  F  much further to the right; this gives even
more options when  F  is past  BC.)

dave