Concave polygon problem

Concave polygon problem

Post by James Macrop » Sat, 02 Jun 1990 22:28:00



I have been  looking for an  algorithm to convert  a (possibly)  concave
polygon into a set  of convex polygons  that cover the  same area.   The
algorithm need not be  optimal, but should do  a reasonable job, and  be
fast.

I have been unable to find such a  beast, but I know that it must  exist
somewhere.

Any ideas or references would be much appreciated.
------
Jim Macropol
Contel Federal Systems          (818)706-5202

 
 
 

Concave polygon problem

Post by Ted Nels » Sun, 03 Jun 1990 00:35:00



>I have been  looking for an  algorithm to convert  a (possibly)  concave
>polygon into a set  of convex polygons  that cover the  same area.   The
>algorithm need not be  optimal, but should do  a reasonable job, and  be
>fast.

I found a nice, simple one to degenerate into horizontal trapezoids.  You
can find it in ACM Trans Graphics Vol 3, No 2, April 1984, pp 153-174
called "Triangulating Simple Polygons and Equivalent Problems." by Fournier
and Montuno.  Don't be thrown by the title, the algorithm you want is
presented completely in the first 5 pages.

-- Ted.

 
 
 

Concave polygon problem

Post by Hansye S. Dulimar » Sat, 02 Jun 1990 23:52:00



>I have been  looking for an  algorithm to convert  a (possibly)  concave
>polygon into a set  of convex polygons  that cover the  same area.   The
>algorithm need not be  optimal, but should do  a reasonable job, and  be
>fast.

>I have been unable to find such a  beast, but I know that it must  exist
>somewhere.

>Any ideas or references would be much appreciated.
>------
>Jim Macropol
>Contel Federal Systems              (818)706-5202


Since triangle is a CONVEX polygon, we can decompose the general polygon
to a number of triangles. I don't have such algorithms / program to do that
but I just want to give you an idea of decomposing the polygon:

Let say that we have N-side polygon (which also implies N points in the
polygon). To simplify the notation let us label all points with
p1,p2,...,pN (start from a point in the polygon and go to the next adjacent
point in ONE direction : clockwise / counterclockwise)

procedure Decompose (N);
  comment - "decompose a N-side polygon into triangles"
begin
  (1) Pick the first point to start the decomposition (p1)
  (2) Contruct a triangle from point (p1, p2 and pN-1).
      After "removing" this triangle from the polygon we are left with
      a polygon with (N-2) sides
  (3) if the remaining polygon is still concave we still have to apply
      further decomposition. [We can do this by calling recursively to
      Decompose (N-2);]
end;

Do you get the idea ?

 
 
 

Concave polygon problem

Post by Mark Ha » Sat, 02 Jun 1990 02:50:00




>>I have been  looking for an  algorithm to convert  a (possibly)  concave
>>polygon into a set  of convex polygons  that cover the  same area.
>Since triangle is a CONVEX polygon, we can decompose the general polygon
>to a number of triangles. I don't have such algorithms / program to do that
>but I just want to give you an idea of decomposing the polygon:

>Let say that we have N-side polygon (which also implies N points in the
>polygon). To simplify the notation let us label all points with
>p1,p2,...,pN (start from a point in the polygon and go to the next adjacent
>point in ONE direction : clockwise / counterclockwise)

>procedure Decompose (N);
>  comment - "decompose a N-side polygon into triangles"
>begin
>  (1) Pick the first point to start the decomposition (p1)
>  (2) Contruct a triangle from point (p1, p2 and pN-1).
>      After "removing" this triangle from the polygon we are left with
>      a polygon with (N-2) sides
>  (3) if the remaining polygon is still concave we still have to apply
>      further decomposition. [We can do this by calling recursively to
>      Decompose (N-2);]
>end;

>Do you get the idea ?

                   P4
                  *-------------------------------*
                 /                                 \
                /                                   \
               *  P3                                 \
                \                                     \
                 \                                     \
                  * P2                                  \
                  |                    *(inside)         *
                  |                                     /
                  * P1                                 /
                 /                                    /
                /                                    /
               * Pn-1                               /
                \                                  /
                 \  Pn-2                          /
                  *------------------------------*

    One problem with your algorithm: It fails for concave polygons.
  (Which is what it is needed for.) The triangle defined by points
  P1, P2, Pn-1 does not have to be in the polygon at all.

    Did I miss something?

 - mark

 
 
 

Concave polygon problem

Post by Jeffrey Mullig » Sat, 02 Jun 1990 20:06:00



Quote:> procedure Decompose (N);
>   comment - "decompose a N-side polygon into triangles"
> begin
>   (1) Pick the first point to start the decomposition (p1)
>   (2) Contruct a triangle from point (p1, p2 and pN-1).
>       After "removing" this triangle from the polygon we are left with
>       a polygon with (N-2) sides

If the interior angle at p1 is greater than 180 degrees, then the
triangle into which you have "decomposed" the polygon actually lies
outside of the original polygon.  Testing this angle is not sufficient,
either:

               P2
               .
             ./
           . /
         .  /
       .   /
  P1 .    .  P3
       .   \
         .  \
           . \
             .\
               .

               P4

Here the angle at P1 is < 180, but triangle P1 P2 P4 contains area
outside the polygon.

Quote:> Do you get the idea ?

More half-baked speculation follows; hit 'n' now if you're
waiting for the literature citation.

A little doodling has convinced me that it is difficult to devise
an algorithm that will do this without testing that the cutting
segment lies entirely within the polygon.  An effective way to
reduce the search space, however, would seem to be to restrict
possible cutting segments to those having endpoint(s) which do
not lie on the convex hull.

--


        NASA/Ames Research Ctr., Mail Stop 239-3, Moffet Field CA, 94035
        (415) 694-6290

 
 
 

Concave polygon problem

Post by Mr. Fu » Sat, 02 Jun 1990 21:58:00


 >
 >> procedure Decompose (N);
 >>   comment - "decompose a N-side polygon into triangles"
 >> begin
 >>   (1) Pick the first point to start the decomposition (p1)
 >>   (2) Contruct a triangle from point (p1, p2 and pN-1).
 >>       After "removing" this triangle from the polygon we are left with
 >>       a polygon with (N-2) sides
 >
 >If the interior angle at p1 is greater than 180 degrees, then the
 >triangle into which you have "decomposed" the polygon actually lies
 >outside of the original polygon.  Testing this angle is not sufficient,
 >either:
 >
 >               P2
 >               .
 >             ./
 >           . /
 >         .  /
 >       .   /
 >  P1 .    .  P3
 >       .   \
 >         .  \
 >           . \
 >        .\
 >          .
 >
 >               P4
 >
 >Here the angle at P1 is < 180, but triangle P1 P2 P4 contains area
 >outside the polygon.
 >
 ...
 >
 >A little doodling has convinced me that it is difficult to devise
 >an algorithm that will do this without testing that the cutting
 >segment lies entirely within the polygon.  An effective way to
 >reduce the search space, however, would seem to be to restrict
 >possible cutting segments to those having endpoint(s) which do
 >not lie on the convex hull.

I recently wrote a tessellation program for a class that used a
"slice triangles along the perimeter"-type of algorithm.  The way
I tested for situations like the above was to check that the edge
that I wanted to add didn't intersect any other edges.  As long as one
is careful to define what "intersect" means, especially at the endpoints
of an edge, this works.  Implemented in a straightforward manner, this test
is O(n) for each added segment.

In my program, I walkled all the way around the contour checking for
non-intersecting segments, then I added the shortest such segment.  This
made the resulting tessellation better (i.e. fewer long skinny
triangles).

Doing things like this results in a reasonable algorithm that produces
acceptable triangular tesselations (where "reasonable" and "acceptable"
mean this:  I got a good grade for the program).  It's probably not
the fastest algorithm, and it certainly doesn't produce an optimal
tessellation.  (In my class, two people came up with programs that
produced optimal tessellations.  I believe that they both ran in
O(n^5).)  The algorithm outlined above has an execution
time of O(n^3) (both worst case and typical).

An observation:  I think that the original poster was looking for a
program that would tessellate a concave polygon into a number of
convex polygons.  Tessellating into triangles is probably the simplest
way to go, but he could probably do better by tesselating into something
else (like general convex polygons).

By the way, I still have the source code (in C) for my tessellation
program.  If anyone wants it, drop me an e-mail line.  If you
find any bugs, I do NOT want to know :-)

Bill Foote

..!ucbvax.Berkeley.EDU!miro!foote

 
 
 

Concave polygon problem

Post by dr.m.h. overma » Sat, 02 Jun 1990 14:07:00


The problem of triangulating a polygon is well-known in computational
geometry. See e.g. Preparata and Shamos: Computational Geometry, an
introduction, published by Springer-Verlag for some algorithms. Given a
n-vertex polygon the theoretically most efficient algorithm runs in time
O(n loglog n) but I would not encourage you to implement it. A simple method
partitions the polygon into monotone polygons (each horizontal line intersects
it only once) and next triangulate these. It does not require you to add
vertices in the interior and runs in time O(n log n). See the above
book for a clear description.

--
--------------------------------------------------------------------------------
Mark Overmars                                                  |\/|
Dept. of Comp. Science, University of Utrecht,                 |  |ark
P.O. Box 80.089, 3508 TB Utrecht, the Netherlands    E-mail: hp4nl!ruuinf!markov