Xref: utzoo comp.graphics:7451 sci.math:7851 Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!tut.cis.ohio-state.edu!gem.mps.ohio-state.edu!ginosko!uunet!zephyr.ens.tek.com!tektronix!reed!pzbaum!omepd!mipos3!td2cad!brister From: brister@td2cad.intel.com (James Brister) Newsgroups: comp.graphics,sci.math Subject: Polygon Triangulation. (?) Message-ID: Date: 11 Sep 89 16:16:22 GMT Sender: news@td2cad.intel.com Distribution: comp Organization: Intel Corp., Santa Clara, CA, USA Lines: 23 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 -- ------------------------------------------------------------------------------- James Brister "Is the set of all respectable sets respectable?" UUCP: {amdcad,decwrl,hplabs,oliveb,pur-ee,qantel}!td2cad!brister ARPA: brister%td2cad.intel.com@relay.cs.net CSNET: brister@td2cad.intel.com VOICE: (408) 765-9713