Date: Fri, 1 Nov 96 04:37:14 UT
From: [Permission pending]
To: rusin@washington.math.niu.edu
Subject: Re: [Q] subdividing concave polygons into convex

Dear Dave,

I am desperately looking for an efficient algorithm to divide a concave
polygon to a set of triangles.  I browsed through the internet and found
you comment on this matter.  I have no problems to understand your 
method in finding concave vertices, however, I seem to have a little bit
difficulty in following your method to divide the concave polygons.  See,
if you start at a concave vertex P(i) "-", and assuming P(i+1) is convex
(i.e. "+" corner).  The area of triangle P(i), P(i+1), P(i+2), P(i) certainly 
will have the same sign as the whole polygon does, so it should cover at
least part of the polygon.  The proplem is, however, that the above 
mentioned triangle does not necessarily lie in the polygon.  Part of this
triangle could actually be outside the polygon!  If you try to think of a
polygon of shape "S", then you will find an example of that.  Am I making
any sense to you here, or am I simply not follow your method right?
Please drop me a mail.  

Thanks in advance.

[Permission pending]

==============================================================================

Date: Mon, 25 Nov 96 16:19:32 CST
From: rusin (Dave Rusin)
To: [Permission pending]
Subject: Re: [Q] subdividing concave polygons into convex

>I am desperately looking for an efficient algorithm to divide a concave
>polygon to a set of triangles.  I browsed through the internet and found
>you comment on this matter.  I have no problems to understand your 
>method in finding concave vertices, however, I seem to have a little bit
>difficulty in following your method to divide the concave polygons.  See,
>if you start at a concave vertex P(i) "-", and assuming P(i+1) is convex
>(i.e. "+" corner).  The area of triangle P(i), P(i+1), P(i+2), P(i) certainly 
>will have the same sign as the whole polygon does, so it should cover at
>least part of the polygon.  The proplem is, however, that the above 
>mentioned triangle does not necessarily lie in the polygon.  Part of this
>triangle could actually be outside the polygon!  If you try to think of a
>polygon of shape "S", then you will find an example of that.  Am I making
>any sense to you here, or am I simply not follow your method right?

Yes, I see the problem (I think): you wish to cut off triangle  ABC  and you
object that doing so will give  a triangle not completely contained in the
polygon:

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

I guess I hadn't thought of that. OK, how about this: Draw the segment from
A to B. Allow the lower endpoint to travel along  BC. Stop as soon as
you hit another vertex (in the diagram above, this will be  E). Draw
the segment  AE. You have now got a subdivision of the original polygon.
This can then be iterated until you get a decomposition into triangles.

I concede this adds a lot of computation time, since you must now
compare  N  vertices at each stage rather than just  3 or so. But I
don't see any other way around it (well, maybe you can be a little more
efficient: once you've checked that the points  D, E, and F don't get in
your way you don't need to continue since the remaining points are
more than  180 degrees around from the ray  AB. But this just cuts down
half the possible points).

By the way you do have to be careful to compute more than just angles:
in the figure below, you want to draw your first segment at  AE, not at  AX:

Z------W
|       \
|        \
|   C     D  F--G
|   |\    | /   |
|   | \   |/    |
|   |  \  E  A  |
|   |   \   / \ |
|   |    \ /   \|
Y---X     B     H


Thanks for alerting me to the bug. Probably this kind of thing is well
known, just not to me. Let me know if you find something more efficient.
I apologize for taking so long to respond.

dave