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
woolstar@cit-vax.Caltech.Edu (John D Woolverton) (09/16/89)
>>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. While looking at a polygon and trying to figure out where to start, we hit apon some neet tricks. To find a good corner to start with, go through all the points, and find the most extreme point in either axis (greatest x or y), and this angle will convex. By taking the cross product of the two sides this point is part of, and comparing it to the other cross products, you can tell which angles are convex, and which are concave. This makes cutting up the polygon easier. (But still not trivial) I speak from experience on this, as I am right in the middle, of writing a program to break up concave polygons into smaller convex polygons. A friend supposedly wrote a utility to break up polygons into triangles only, but that is too far for me. (So the debugging goes on...) John d Woolverton, video bits woolstar@csvax.caltech.edu
sumane@anaconda.stanford.edu (Thilaka Sumanaweera) (09/17/89)
Assuming the polygon vertices are ordered so that they can be treated as contours, one can use Delaunay Triangulation to divide both convex and concave polygons into triangles. (This can be extended with minor modifications for non-simple (self-intersecting) polygons.) Delaunay triangulation gives a set of triangles having the polygon-vertices as corners and whose union is the convex hull of the polygon-vertices. Triangles outside the polygon can be eliminated using the fact that the polygon-vertices are oriented. This will yield a set of triangles, whose union is the given polygon. If you want a simple algorithm to implement 2D Delaunay triangulation, I can give some pointers. Thilaka
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
gcchou@sdrc.UUCP (jin chou) (09/19/89)
In article <11820@polya.Stanford.EDU>, sumane@anaconda.stanford.edu (Thilaka Sumanaweera) writes: > [Stuff deleted] > Delaunay triangulation gives a set of triangles having > the polygon-vertices as corners and whose union is the > convex hull of the polygon-vertices. Triangles outside > the polygon can be eliminated using the fact that the > polygon-vertices are oriented. This will yield a set > of triangles, whose union is the given polygon. > But the edges of the given polygon may not be in the set of edges of the Delaunay triangulation. It is not clear how you can handle these efficiently. > [Stuff deleted] > Thilaka Jin Chou
sumane@anaconda.stanford.edu (Thilaka Sumanaweera) (09/19/89)
This is in response to the following message: ***************************************************************************** In article <11820@polya.Stanford.EDU>, sumane@anaconda.stanford.edu (Thilaka Sumanaweera) writes: > [Stuff deleted] > Delaunay triangulation gives a set of triangles having > the polygon-vertices as corners and whose union is the > convex hull of the polygon-vertices. Triangles outside > the polygon can be eliminated using the fact that the > polygon-vertices are oriented. This will yield a set > of triangles, whose union is the given polygon. > But the edges of the given polygon may not be in the set of edges of the Delaunay triangulation. It is not clear how you can handle these efficiently. > [Stuff deleted] > Thilaka Jin Chou ***************************************************************************** This problem can be get around by introducing new points ( O(N) ) on the original edges as explained in the following: (N = No of points.) Shape Reconstruction from Planar Cross Sections - Jean-Daniel Boissonnat, Journal of Computer Vision, Graphics and Image Processsing 44, pp 1-29, 1988 This algorithm can introduce new points with the time complexity O(N log N). Thilaka