Jump to content
  • Advertisement
Sign in to follow this  
TheAdmiral

Perimiter Path from a Contiguous Discrete 2D Area

This topic is 3317 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I have a little problem that I'd like solved as efficiently as possible. It seems like quite a common task and so I was hoping that somebody here knows of a standard routine. Suppose I have a 2D, bounded, regular Cartesian grid of points. Within this grid is defined a 'zone of control'; imagine the border of a country for instance. The only query operation available is a boolean test that tells me if any given point is within this zone or not. If I can guarantee that the area of 'controlled' points is contiguous, but not necessarily convex, how can I efficiently compute the closed path that represents the zone's perimeter? I can see half a dozen ways to do this but they're all fairly messy and O(n3) or worse. Considering that the grid can get pretty big and I'm hoping to perform the computation in a single frame (but only occasionally) I'd like something snappy. Thanks Admiral Ps: It's good to be back and see so many familiar names [smile]

Share this post


Link to post
Share on other sites
Advertisement
maybe this?
http://en.wikipedia.org/wiki/Convex_hull
then make a polygon out of the resulting points, and use half-space functions or linear inequalities to determine if the point is inside?

Share this post


Link to post
Share on other sites
CPPNick,

That's close, but what I'm after is kind of the converse. Rather than the smallest convex hull containing the area, I want the largest (in terms of area enclosed) potentially concave closed curve that fits inside it.

Thanks all the same
Admiral

Share this post


Link to post
Share on other sites
ok, i've got an idea. When scan converting a polygon for drawing, the test to see whether or not an area is inside a polygon, is if the scanline has crossed an odd number of edges, then the given pixel is inside the polygon. so maybe you could pick a certain axis, and test for intersection between (a line along that axis, through your point of reference) and (each edge of the bounding concave polygon). if there is an odd number of intersections, then your point is inside the polygon.


optimized correctly, im sure this will be sufficiently snappy =)

Share this post


Link to post
Share on other sites
some pseudo code which may not be completely correct, but should get you started.
also, should offer linear complexity.


reference_point = (3, 6)
Region = points[5]
intersections = 0
x_minimum = left side of bounding box around Region
for each edge of Region // edge = point[0] to point[1], ect..
{
if(reference_point is inside bounding box)
{
find intersection with line from(3, 6)to(x_minimum, 6)
if(intersection.y (>) edge.y1 && intersection.y (<) edge.y2)
intersections++
}
}
return (intersections mod% 2) //yields 1 or 0, true or false



Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!