Xref: utzoo comp.graphics:7530 sci.math:7888 Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!uwvax!umn-d-ub!umn-cs!nis!viper!dave From: dave@viper.Lynx.MN.Org (David Messer) Newsgroups: comp.graphics,sci.math Subject: Re: Polygon Triangulation. (?) Message-ID: <2710@viper.Lynx.MN.Org> Date: 18 Sep 89 00:26:21 GMT References: <7918@cbmvax.UUCP> Reply-To: dave@viper.Lynx.MN.Org (David Messer) Distribution: comp Organization: Lynx Data Systems, Eagan, MN Lines: 24 In article <7918@cbmvax.UUCP> mitchell@cbmvax.UUCP (Fred Mitchell - QA) writes: >In article brister@td2cad.intel.com (James Brister) writes: >> >>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). > >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. If you take the cross-product of two 2d vectors (i.e. [X1 Y1 0] x [X2 Y2 0] ) the sign of the resultant vector is positive if the angle is <= 180 degrees and negative otherwise. Cross-product is the similest way that I know of to determine this. -- Remember Tiananmen Square. | David Messer dave@Lynx.MN.Org -or- | Lynx Data Systems ...!bungia!viper!dave