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 |
|______________________________________________________________________|