JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Marathon Matches Marathon Match 23 Post your approach [ 1 2 3 4 ]    NEXT >
 Post your approach | Reply My basic algorithm has three stages:1) Find a point in the polygon2) Expand it to a triangle3) Pick a likely side and see if there is more polygon beyond itI 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 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.1Step 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 doingVaring 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 point2. Using binary search, go from that point to the left, right, up and down andfind the the intersections with the polygon edges3. Expand the polygon edges one by one, in the order of their size, untilthere all the edges are greater than a given threshold. We expand an edge byapplying binary search from its middle point to the direction perpendicular toit4. 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 36. 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 edge2) Take each vertex and expand it away from the centroid3) 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.
 Forums Marathon Matches Marathon Match 23 Post your approach Previous Thread  |  Next Thread [ 1 2 3 4 ]    NEXT >