From: dragovic@halcyon.com (Jeff Dragovich) Newsgroups: sci.math.num-analysis Subject: Re: Algorithm for polygon around N arbitrary (x,y) points Date: Tue, 31 Oct 1995 20:09:23 In article <4766ki\$p7u@cliffy.lfwc.lockheed.com> "Mike I. Jones" writes: >From: "Mike I. Jones" >Subject: Algorithm for polygon around N arbitrary (x,y) points >Date: 31 Oct 1995 22:06:10 GMT >Howdy to all, >Could anyone furnish an algorithm or cite references for generating an enclosing >polygon (i.e., an outline) around a set of N arbitrarily distributed (x,y) points? >I have experimented with several different ways, but I can't seem to find a general >algorithm. >Thanks for any responses. >Mike You speak of the convex hull algorithm. Look in "Algorithms in C", by Robert Sedgewick. Off the top of my head, one possible solution might go something like this: [1] Find the point with the lowest Y coordinate. Let's call it P1. [2] Next, find the point (lets call it P2) such that the line between P1 and P2 makes the smallest angle with respect to the X axis. [3] Next, find the point P3 such that the angle created by P1-P2-P3 is the largest. Continue with step 3 until you return to P1. Enjoy. Jeff Dragovich ============================================================================== From: lefranc@lsh01.univ-lille1.fr (Marc Lefranc) Newsgroups: sci.math.num-analysis Subject: Re: Algorithm for polygon around N arbitrary (x,y) points Date: 2 Nov 1995 08:36:38 GMT [inclusion of previous post deleted -- djr] Although the convex hull will do, this is not necessarily the only way. There can be cases where points lie inside a highly non convex region and one would want a tighter enclosing than given by the convex hull. I would be highly interested in getitng pointers to such algorithms. As for the convex hull, one standard route is via a Delaunay tesselation. For instance, look at netlib in the voronoi directory (the Delaunay tesselation is the dual of the Delaunay one). Marc. -- ________________________________________________________________________ | Marc Lefranc, Laboratoire de Spectroscopie Hertzienne (URA CNRS 249) | | Bat P5, UFR de Physique | | Universite des Sciences et Technologies de Lille | | F-59655 Villeneuve d'Ascq CEDEX (FRANCE) | | e-mail: lefranc@lsh.univ-lille1.fr ; FAX : (+33) 20 33 70 20 | |______________________________________________________________________|