brister@td2cad.intel.com (James Brister) (09/11/89)
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-9713mitchell@cbmvax.UUCP (Fred Mitchell - QA) (09/15/89)
In article <BRISTER.89Sep11091622@aries.td2cad.intel.com> 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.
madhu@hubcap.clemson.edu (m a d h u) (09/15/89)
> In article <BRISTER.89Sep11091622@aries.td2cad.intel.com> 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...... > > > >James > In article <7918@cbmvax.UUCP>, mitchell@cbmvax.UUCP (Fred Mitchell - QA) writes: > 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. Yamaguchi Fujio, Tokieda Toshiya,"Bridge Edge and Triangulation approach in solid modeling," Frontiers in Computer Graphics, Proc. Computer Graphics Tokyo '84, edited by Tosiyasu L. Kunii, PP. 44-65, Springer-Verlag, 1985. This is probably what you should look at. madhu
dave@viper.Lynx.MN.Org (David Messer) (09/18/89)
In article <7918@cbmvax.UUCP> mitchell@cbmvax.UUCP (Fred Mitchell - QA) writes: >In article <BRISTER.89Sep11091622@aries.td2cad.intel.com> 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