IWETHEY v. 0.3.0 | TODO
1,095 registered users | 0 active users | 0 LpH | Statistics
Login | Create New User
IWETHEY Banner

Welcome to IWETHEY!

New 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
New 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
New 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.

New 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.
New 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
New 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
New 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.

     Mininum Convex Polygon around Points? - (JayMehaffey) - (16)
         Are they always convex? - (FuManChu) - (7)
             Convex Hull - (JayMehaffey) - (6)
                 Glad you said you found it - (ben_tilly)
                 You need an algorithms book. - (static) - (4)
                     NIST DADS - (ChrisR)
                     I have that one - (JayMehaffey) - (2)
                         Wierd - (altmann) - (1)
                             I have the C++ one, too. - (static)
         Start with center of mass - (drewk)
         Re: Mininum Convex Polygon around Points? - (deSitter) - (6)
             Yep, that would be a formal statement - (JayMehaffey) - (5)
                 Re: Yep, that would be a formal statement - (deSitter) - (2)
                     If he doesn't remember highschool math... - (ben_tilly) - (1)
                         He's Jay - he'll figure it out -NT - (deSitter)
                 You don't need to compute angles - (ben_tilly) - (1)
                     Actually ended up using vector math - (JayMehaffey)

Pain is merely nature's way of hurting you.
64 ms