JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
Post your approach | Reply
My basic algorithm has three stages:

1) Find a point in the polygon
2) Expand it to a triangle
3) Pick a likely side and see if there is more polygon beyond it

I mostly choose lines and do binary searches for the polygon boundary along those lines. For each vertex I create, I keep the in point (the closest one to the boundary that is inside the polygon) and the out point (the closest one outside the polygon). Everything is based around the fact that with a convex polygon, you can't have a line go from inside the polygon to outside and then back in. I use this to find the largest triangle that could have a given side of my current polygon as its base. I also use it to move my in and out points closer to the polygon boundary without using more queries (well, sometimes I query the midpoint if it seems the best thing to do).

My code is available here: PolygonArea_jdmetz.cpp And it is pretty well commented.

It gets 4.9842 on average over 100000 cases.
Subject Author Date
Post your approach jdmetz Oct 3, 2007 at 12:01 PM EDT
Re: Post your approach narri Oct 3, 2007 at 12:03 PM EDT
Re: Post your approach stevetrov Oct 3, 2007 at 12:05 PM EDT
Re: Post your approach RatonulBolnav Oct 3, 2007 at 12:07 PM EDT
Re: Post your approach vexorian Oct 3, 2007 at 12:07 PM EDT
Re: Post your approach anastasov.bg Oct 3, 2007 at 12:19 PM EDT
Re: Post your approach venco Oct 3, 2007 at 12:21 PM EDT
Re: Post your approach Dale_Mellor Oct 3, 2007 at 12:31 PM EDT
Re: Post your approach radeye Oct 3, 2007 at 12:41 PM EDT
Re: Post your approach venco Oct 3, 2007 at 1:04 PM EDT
Re: Post your approach gedluk Oct 3, 2007 at 1:15 PM EDT
Re: Post your approach paranoia Oct 3, 2007 at 1:12 PM EDT
Re: Post your approach temur Oct 3, 2007 at 3:57 PM EDT
Re: Post your approach Fory Oct 4, 2007 at 12:33 AM EDT
Re: Post your approach BeachedWhale Oct 3, 2007 at 1:18 PM EDT
Re: Post your approach gsais Oct 3, 2007 at 1:38 PM EDT
Re: Post your approach jdmetz Oct 3, 2007 at 2:00 PM EDT
Re: Post your approach paranoia Oct 4, 2007 at 2:42 AM EDT
Re: Post your approach ecv Oct 3, 2007 at 3:10 PM EDT
Re: Post your approach restricteur Oct 3, 2007 at 1:49 PM EDT
Re: Post your approach TheRaven Oct 3, 2007 at 2:13 PM EDT
Re: Post your approach jdmetz Oct 3, 2007 at 4:25 PM EDT
Re: Post your approach TheRaven Oct 3, 2007 at 4:55 PM EDT
Re: Post your approach hagman Oct 3, 2007 at 2:38 PM EDT
Re: Post your approach ecv Oct 3, 2007 at 3:35 PM EDT
Re: Post your approach Psyho Oct 3, 2007 at 3:12 PM EDT
Re: Post your approach RatonulBolnav Oct 3, 2007 at 4:07 PM EDT
Re: Post your approach gsais Oct 3, 2007 at 4:26 PM EDT
Re: Post your approach paranoia Oct 3, 2007 at 4:35 PM EDT
Re: Post your approach TheRaven Oct 3, 2007 at 5:03 PM EDT
Re: Post your approach jdmetz Oct 3, 2007 at 8:42 PM EDT
Re: Post your approach TheRaven Oct 3, 2007 at 10:56 PM EDT
Re: Post your approach Rustyoldman Oct 5, 2007 at 9:48 PM EDT
Re: Post your approach vlad_D Oct 5, 2007 at 2:43 PM EDT
Re: Post your approach paranoia Oct 5, 2007 at 4:47 PM EDT
Re: Post your approach vlad_D Oct 7, 2007 at 3:46 PM EDT
Re: Post your approach paranoia Oct 7, 2007 at 4:24 PM EDT
Re: Post your approach vlad_D Oct 7, 2007 at 5:04 PM EDT
Re: Post your approach Rustyoldman Oct 5, 2007 at 10:49 PM EDT
Re: Post your approach Rustyoldman Oct 9, 2007 at 2:58 AM EDT
Re: Post your approach murrayr Oct 3, 2007 at 3:56 PM EDT
Re: Post your approach jdmetz Oct 3, 2007 at 4:23 PM EDT
Re: Post your approach murrayr Oct 3, 2007 at 4:54 PM EDT
Re: Post your approach jdmetz Oct 3, 2007 at 9:04 PM EDT
Re: Post your approach radeye Oct 3, 2007 at 4:58 PM EDT
Re: Post your approach hagman Oct 5, 2007 at 9:18 AM EDT
Re: Post your approach hagman Oct 5, 2007 at 9:06 AM EDT
Re: Post your approach IdNotFound Oct 3, 2007 at 11:50 PM EDT
Re: Post your approach Olathe Oct 4, 2007 at 6:52 AM EDT
RSS