Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
[ 1 2 3 4 ]    NEXT >
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.
Re: Post your approach (response to post by jdmetz) | Reply
My strategy is based off a few theorems stemming from the fact that we are looking at a convex polygon (proofs are left to the reader):
Let points inside the polygon be good points, all other points are bad points
T1) Any point on the line segment AB, where A and B are good points, are themselves good (we shall call this a good segment)
T2) The convex hull of a set of good points must also be good (we shall call this a good polygon)
T3) There must be exactly one 'border' between a good point and a bad point
T4) (The major theorem) Given a good segment AB and a bad point C, draw two infinite rays starting from C in the direction of vectors AC and BC ...every point in the area between the two rays you just drew is also bad (including the rays themselves) <-- this allows rapid elimination of areas
T5) (Another big one) Given a good segment AB on a good polygon, draw one infinite ray from any point on AB in a direction headed outward. There must be a border point somewhere on the ray (possibly on AB itself), after which all points are bad <--- this allows binary search

How I used these could have been better, but anyway:

1) Pick and test random points until you have three successful points.
By far the weakest part of my algorithm...if I didn't find three points after N measurements, I did a variety of things, none of which worked well
2) Repeat the following until N measurement overall have been done:
a) Find the convex hull of all good points (using Graham scan)
b) Take each vertex and find the area gain I would get if i extend that vertex out from the centroid. Take each midpoint of each side of the hull and extend it perpendicularly and see the area gain. Pick the point with the most possible area gain.
c) call isInside with this point of maximal potential gain, update arrays of good and bad points
3) (This led from 2444->2469) Now take the midpoints of each segment of the convex hull, and extend it perpendicularly one last time. Find the area of this new polygon. Return the average of the area of the new polygon and the convex hull (almost always the true area was somewhere in this range).
4) (This stunningly led to 2469->2479) Take one or two thousand results....plug the real (not absolute differences) into Excel (not 2007!) and graph as a function of N. Fit a curve to the data (logarithmic worked well for me) and put the result (which is a function of N) as a fudge factor to your answer....
5) (2479->2481) Return the weighted average between the smaller area and 6 times the larger area.
Fudge, indeed, is yummy. I hope this is the start of a bunch of good marathons for me!

EDIT: wow, my approach is somewhat similar to jdmetz's....except that I always include the midpoint in my deliberations as to which point to attempt an extension from, which is probably wasteful in some cases
Example results:
0) 4.990047963928504
1) 4.9913226200532925
2) 4.970696142925412
3) 4.9928553256184856
4) 4.982272505400221
5) 4.907782431935212
6) 4.963737267020377
7) 4.993254406561572
8) 4.998868686733182
9) 4.981794885452505
Re: Post your approach (response to post by jdmetz) | Reply
The idea behind my approach was to find a point in the polygon and then discover it by performing binary search from that point in different directions.
This method gives us a nice simple formula to calculate the area.

N.b. each binary search is performed until the difference between the upper and lower bounds is 0.1

Step 1: Find the polygon:
Try (5:5) then random points until we find the polygon. If we dont find the poly return a guess of 1.

Step 2:
perform binary searches toward the left and right (from our discovered point) to find two points on the edge of the polygon.
choose the point half way between these points for the start of all our binary searches.
perofrm BSs towards the top and bottom from our new chosen point.

Step 3:
Now we have found 4 points on the edge of the polygon we can continue to discover the rest of the shape.
We want to perform more binary searches that bisect two adjacent discovered points.
For each possible new search we look at the last two points and the next two points and calculate the uncertainty in the total area from this gap.
This allows us to perform searchs in the places that will be the most useful.I.e. perform searches to discover corners rather than straight lines.
Each new BS is initialised with the max and min posible values based on information from the exising BSs.
This is performed until we run out of enquires.

Things I never got around to doing
Varing the precision of the BS based on the number of enquires we have been given.
Using a more structured search to find those small polygons.
Using a better method to find a point within a polygon or using more than one internal point to start BSs on.
Re: Post your approach (response to post by jdmetz) | Reply
My approach is similar.

1. Start with a grid size of 64x64 and find an inside point
2. Using binary search, go from that point to the left, right, up and down and
find the the intersections with the polygon edges
3. Expand the polygon edges one by one, in the order of their size, until
there all the edges are greater than a given threshold. We expand an edge by
applying binary search from its middle point to the direction perpendicular to
4. Repeat
pick the best unknown point and query it
until there are either no more unknown points or no more queries left

The "best" point is the one that will minimize the total number of unknown points if we would know its value. This is computed as the minimum between
a) the number of currently unknown points that are situated inside the outer "cone" created by the point we want to query and the convex hull of the inside points found so far, if the query will be negative (point is outside)
b) the number of unknown points that will be added to the convex hull of all the inside points found so far, if the query will be positive (point is inside)

If multiple points are tied for "best", pick a random one among them.

5. If there are queries left, than expand the grid (to 128x128, 256x256, or 512x512 depending on how many queries are left) and repeat from step 3

6. Estimate the area, using the following formula:

area ~= (n_inside_points + n_unknown_points_adjacent_to_inside_points/2)*grid_cell_size.
Re: Post your approach (response to post by jdmetz) | Reply
1) Find one, two or four points inside the polygon (depends on available M ) Take average, this is the center of the polygon.
2) Then I do 4 binary searches to find the points to where the polygon intersects with a cross that got the "center of the polygon" as center.

3) I keep the 4 points in an array and then start a loop:
- while there are enough M to do tests:
- pick the two consecutive points in the array that got the largest distance.
- Try to find the intersection from center to the middle angle between those points.
- Add new point to the array.

4) When it ends I take the convex hull and calculate area.

2359.25 points in preliminar tests.
Re: Post your approach (response to post by jdmetz) | Reply
My approach is:

1) Construct a triangle by checking random points.
2) Use binary search from the centre of the convex polygon, constructed by now and find a boundary point. Centre is defined to be the average of all the points of the convex polygon, which I have found.
3) Repeat 2 until there are queries left.

This approach got 2251.59 on the 500 full submission test cases.
Re: Post your approach (response to post by jdmetz) | Reply
I maintain two sets of points - inside, and outside.
Each outside point assumes a sector of outside area to preserve convexity of the polygon.
Both sets are non-redundant, so for the inside points I keep only vertexes of their convex hull, and for the outside points I remove all points covered by outside sector of another point.
This gives me minimal and maximal areas of the polygon.
Then I randomly choose a new query in unknown area (not inside, or outside) such that it will maximize possible reduction of the unknown area for two outcomes - if the new point is inside or not.
At the end I return some value between minimal and maximal areas depending on total number of queries (at .5-.8).
There is a problem of rare cases when all queries missed the polygon.
In this cases I return 71/M - as it gives the best approximation.
My average is about 4.982.
Re: Post your approach (response to post by venco) | Reply
My approach was identical to venco's except in determining where to sample between the inside and outside polygons: I rolled a big ball around the perimeter of the inside polygon, and if the ball did not intersect the outside polygon I used the centre of the ball as the next sample point. If I could not find any such sample points I would reduce the size of the ball a small amount and repeat, thus always sampling the biggest open area between the two polygons.

This unfortunately only got me 36th place provisionally. The main reason it performed so badly I think is that it didn't sample sharp corners very well, unless there were plenty of sampling opportunities available.

Oh well, another day...
Re: Post your approach (response to post by venco) | Reply
Mine's pretty much exactly the same as venco's.

Interestingly, I found if I increased the number of sample points from 1000 per guess to 2000 per guess, when trying to maximize the possible reduction of the unknown area, this caused my solution to perform *worse*.

It turns out that maximizing min(area-reduction-if-true, area-reduction-if-false) is suboptimal, as these points have a significantly greater than 50% chance of being "true".

I didn't understand this until too late to incorporate any changes into my code. So I just grabbed one of my earlier submissions and resubmitted it.

Also, the curve fitting at the end may have helped a great deal (or hurt, depending on how well you did it).

Oh, I had a reasonable approach to finding the first two points; the first point I tried to maximize the distance to the closest prior guess and the edges, and this worked pretty well. For the second point, I tried to maximize the distance to the closest prior guess, while ensuring that the closest prior guess was indeed the point we had already found inside the polygon. After I had two points inside the polygon, I could proceed with my normal inside/outside work.
Re: Post your approach (response to post by radeye) | Reply
I have found that maximizing min(gain_if_in, 2*gain_if_out) is better, but not much.
As for number of samples, I didn't see significant difference, but 160 in my last submission is a bit better than 40 in earlier.
I think reducing randomness is the way to enhance our approach. My current code produces large number of hull and outside points at the end, way more than number of real polygon vertexes.
Re: Post your approach (response to post by radeye) | Reply
Mine was very similar to many already posted:
* find some points in the polygon
* expand the convex hull of those points by querying points that give new information (i.e. aren't inside the known convex hull and don't cause the new convex hull to contain known outside points)

I choose new points in 3 different ways in my final solution (all references are to the convex hull of the inside points):
1) Pick the midpoint of an edge and expand along the normal of that edge
2) Take each vertex and expand it away from the centroid
3) Take each vertex and expand it along an edge it sits on (i.e. pick an edge and stretch it in one or the other direction)

The expansion distance is calculated by doing a binary search to find the maximum distance the point can be expanded without including a known outside point, then expanding half of this distance.

To calculate the distance at the very end I return a value interpolated between the area of the inner convex hull and that convex hull "blown up like a balloon" (without querying) until it's touching the outside points.

I also tried generating points based on possible corners expanded away from the nearest point on the convex hull, where a possible corner is any extrapolated intersection of two edges that is considered interesting (gives new information).

Edit: I forgot to mention that I pick the point that maximizes the area of the inside hull should the point be inside. There's probably a much better way to do this.
Re: Post your approach (response to post by venco) | Reply
probably this coefficient of gain_if_out should be equal to (1-in_f)/in_f, where in_f - the average fraction of area inside the polygon. I don't know how much that exactly is, but 0.33 (giving 2) is probably a good guess...
Re: Post your approach (response to post by jdmetz) | Reply
My approach was to build an integer grid of size MxM. Then I would find a point within the polygon and then another. Using the fact the any two points in the polygon where known to be within the polygon I would not query those again. Also I would do binary searches to find the edges in relation to each point. Find the edge from point A(x,y) to A'(x,0), A''(x,M)...etc for each side of the grid and the four corners. Then I would take some other points along the edges.

After I queried M times I would use 3 coins to find the polygon with the points I had and then just take the determinant of the points to find the area.
Re: Post your approach (response to post by jdmetz) | Reply
I didn't submit anything this time because of lack of time (hey, I'm finally upgrading to Linux after 15 years of being trapped in Windows!). Anyway, I want to share my unfinished approach as it has an idea I haven't seen posted by anyone yet.

In the first phase, I generate a lot (50K) of convex polygons according to the test generator (but I skip all those few polygons that would take a long time to generate). Then I search for a query point that would return false/true for ~50% of the sample polygons. After the query, all the sample polygons that are not consistent with the feedback are removed; if the number of sample polygons is lower than 1K (which happens very quickly as we're removing one half on each query) then new polygons are generated by randomly "mutating" the existing samples such that they are still concave and consistent with the feedbacks.

The second phase starts once the "diversity" of the samples drops below a certain threshold value (as measured by the std. dev. of the areas of the samples). This phase is very similar to what have been posted already: find the query point that maximizes {area discarded if false, area accepted if true}. As radeye has already pointed out, I also found that this binary search was sub-optimal, in the sense that the entropy gain was lower than 1-bit per query.

The third phase is the one that I didn't have the time to implement; it started once all queries were exhausted and would consisted in randomly generating (as the time limit allowed) valid concave polygons between the minimum convex hull and the outside points, and returning the average area as the result.

I found that the first phase was near-optimal (before diversity dropped), and much better than random sampling of points. For example, it found on average (over 1000 cases) the first "inside point" using ~2 queries, which is indeed the expected value for 1-bit entropy queries (on the other hand, random sampling used more than twice as much queries to find each of the first 3 inside points).

@jdmetz: nice idea to use a genetic algorithm to tune your estimation parameters (that's commented on the source). Do you have a generic framework for doing this, or is it an ad-hoc solution? (edit - why I've the feeling I've asked this before???)

edit - convex => concave... d'oh!
Re: Post your approach (response to post by jdmetz) | Reply
This is the first time that I post my approach. I think it's a nice approach even if the result was bad.

1- find a point in the polygon which is not on the edge:
I find that point by starting from the center of the square and moving like a snake (in spiral) folowing the integer points until covering all the square. (I think the probability that a plygon does not contain such a point is very near to zero :) ).
When I find this first point I see the four points around it in the directions N,E,S and W with a distance of 0.5 .
Then I take the average of these points (not the centeral point)

2- find the polygon edge points in "all" directions by BS:
I start by pi/2 (four points), then pi/4 (8 points) and so on until 8192 points (which is impossible :) and I skip points that are aleady checked.
I think that my error is that I give to each new BS a determined quota of idInside calls.
after each full rotation I build my own polygon and eliminate some vertices from it by convexity (si I gain more area)

I also imroved my algorithm by imroving the binary search: if a point is not in the polygon for sure (by convexity) then try a closer point to my central point.

An other time thanks to the author of the problem, it was really a nice one.
[ 1 2 3 4 ]    NEXT >