JOIN
 Revision History
 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 My Post History  |  My Watches  |  User Settings Forums Marathon Matches Marathon Match 23 Re: Post your approach Revision History (1 edit)
 Re: Post your approach (response to post by radeye) 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 radeye) 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).