Algorithm to find the contour of a polygon!

Algorithm to find the contour of a polygon!

Post by Jocelyn Deni » Fri, 23 May 1997 04:00:00



Hi,

I'm wondering if it already exists an algorithm that would be able to
rebuild a polygon that intersect itself into a polygon that doesn't
intersect itself.

Example:      

A)             C
               +
              / \  
             /   \  
      A +---+-----+ B
        |  /
        | /
        |/
        +
        D

B)             C
               +
              / \  
             /   \  
      A +---+-----+ B
        |  /
        | /
        |/
        +
        D

Instead of a polygon that intersect itself, I've got a polygon that
doesn't intersect itself. The polygon A has the following sequence:
A,B,C,D compares to the resulting one who has: A,C,B,D.

So, I would like to found an algorithm which is able to do this kind of
operation.

Any suggestion will be appreciated!
Thanks!

                         \\\|///
                       \\  - -  //

----------------------oOOo-(_)-oOOo-------------------------------
 Jocelyn Denis              |         _/     _/_/_/   _/_/_/      
 Analyste programmeur       |        _/    _/       _/            
 Programmer Analyst         |       _/     _/_/_/  _/            

 http://www.lsc.ca          |     _/_/_/ _/_/_/   _/_/_/ 2+1 INC.
------------------------------Oooo--------------------------------
                       oooO   (   )
                      (   )    ) /
                       \ (    (_/
                        \_)

 
 
 

Algorithm to find the contour of a polygon!

Post by Carl Burk » Fri, 23 May 1997 04:00:00



> Hi,

> I'm wondering if it already exists an algorithm that would be able to
> rebuild a polygon that intersect itself into a polygon that doesn't
> intersect itself.

[snip]

If you want to retain the same shape, you need to insert
a new vertex where edges AB and CD intersect (vertex E)
and output the two polygons ADE, BCE.
What I've been using for that is a simplified version
of Weiler's algorithm for polygon set operations (check Siggraph
proceedings from either 1980 or 1981 for the paper, I forget which
year it was right now.)

If you instead want to correct an accidental edge crossing,
maybe a convex hull algorithm will do what you want.  This will
not in general keep the same shape if the polygon is not convex
to start with, but it would work for the simple example to gave.

Hope this helps.

--
Carl Burke