Are they always convex?

Post #177,856

10/5/04 2:19:00 PM

Been a while since I did any serious graphics work, but how about:

1. Calculate (not draw) lines between all points.
2. Drop any lines which cross (at some point other than original vertices). That is, if two lines cross, drop both of them.
3. Calc points from remaining lines.

If there's a concave point, however, that won't work. One possibility for *that* problem would be to calc your triangles and drop any vertices which are contained within a triangle.

These are just ideas off the top of my head.

Post #177,868

by JayMehaffey

10/5/04 2:55:00 PM

Convex Hull

What I want is to find the smallest convex polygon that will fit around an essentially random set of points.

I figured was a well known problem, but it took me a while to find the proper geometric name for the problem, which is Convex Hull. Googling on that gives a lot of pages that address the problem.

Now I just have to pick an algorithm and implement it in PHP.

Not that it's going to be real easy. It's been so long since I have done anything like this I can't remember basic crud like checking if a point intersects a line.

Jay

Post #177,899

by ben_tilly

10/5/04 6:20:11 PM

Glad you said you found it

I thought about it, came up with one of the n log(n) algorithms, but now don't feel obliged to type it up. :-)

Cheers,
Ben

About the use of language: it is impossible to sharpen a pencil with a blunt axe. It is equally vain to try to do it with ten blunt axes instead. -- Edsger W. Dijkstra

Post #177,939

by static

10/5/04 11:42:53 PM

You need an algorithms book.

Like [link|http://www.amazon.com/exec/obidos/ASIN/0201314525/qid=1097033373/sr=2-1/ref=pd_ka_2_1/102-1952750-3300121|this one].

Wade.

Is it enough to love
Is it enough to breathe
Somebody rip my heart out
And leave me here to bleed

Is it enough to die
Somebody save my life
I'd rather be Anything but Ordinary
Please

-- "Anything but Ordinary" by Avril Lavigne.

Post #177,942

by ChrisR

10/5/04 11:53:02 PM

NIST DADS

The [link|http://www.nist.gov/dads/|NIST] page lists the [link|http://www.nist.gov/dads/HTML/optimalPolygonTriangProb.html|optimal polygon triangulation problem] but it unfortunately has no current definition.

Post #177,950

by JayMehaffey

10/6/04 12:31:33 AM

I have that one

Buried somewhere under the pile of stuff from moving. But I've read it more then once, and I don't think it address this specific question anyway.

Jay

Post #177,953

by altmann

10/6/04 1:05:42 AM

Wierd

There is a chapter on Convex Hulls in my copy of the C++ version: [link|http://www.amazon.com/exec/obidos/tg/detail/-/0201510596/qid=1097038850/sr=1-6/ref=sr_1_6/102-2463306-3277769?v=glance&s=books|http://www.amazon.co...?v=glance&s=books] but it looks like he's expanded the book into 5 volumes for later editions and left some older content out.

--
Chris Altmann

Post #177,955

by static

10/6/04 1:46:21 AM

I have the C++ one, too.

And I remember the chapter on Convex Hulls. That's why I recommended it.

Wade.

Is it enough to love
Is it enough to breathe
Somebody rip my heart out
And leave me here to bleed

Is it enough to die
Somebody save my life
I'd rather be Anything but Ordinary
Please

-- "Anything but Ordinary" by Avril Lavigne.

Welcome to IWETHEY!