Xref: utzoo comp.graphics:7491 sci.math:7864 Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!uunet!cbmvax!mitchell From: mitchell@cbmvax.UUCP (Fred Mitchell - QA) Newsgroups: comp.graphics,sci.math Subject: Re: Polygon Triangulation. (?) Message-ID: <7918@cbmvax.UUCP> Date: 14 Sep 89 23:04:56 GMT References: Reply-To: mitchell@cbmvax.UUCP (Fred Mitchell - QA) Distribution: comp Organization: Commodore Technology, West Chester, PA Lines: 30 In article brister@td2cad.intel.com (James Brister) writes: >I have a little problem...... :-) > >Given a sequence of vertices that represent the points on a polygon. I need to >(somehow) reduce this into two (or more) smaller polygons that have a (new) >common edge. For example given the square (0,0) (1,0) (1,1) (0,1) I'd like to >produce the two polygons (triangles) (0,0) (0,1) (1,1) and (0,0) (1,1) (0,1). >The problem is that I have no way of knowing before I am given the list of >vertices whether the polygon is concave or convex (or how many vertices I'm >going to get). So I can't just arbitrarily choose a pair of vertices and create >a new edge. I can't even be sure that the polygon isn't self intersecting (i.e. >a figure-eight-type shape). This doesn't seem like a very easy problem (I've >scratched my head over this for a while), and my graphics text books don't >cover this sort of problem at all. Can anyone suggest where I should look for >ideas on how to reduce complex polygons to simpler ones? Thanks. > >James I have run across this problem myself. I have created a way to test for concavity, but its rather tricky and I have not fully implemented it yet. But one way you can test for concavity is to measure the angles between each subsequent pair of lines. If they are all less than 180 degrees, then your object is convex. Of course, the trick is testing for <180, and what I've done is to take both the sin of the angle and test for the sign. They should be all positive (or zero) for all angles, or all negative if the points are rotating in the opposite direction. To get the sin of the angle involves a bit of vector math which can be found in any book on vector algebra.