Perimiter Path from a Contiguous Discrete 2D Area
Author
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]
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?
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?
Author
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
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
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 =)
optimized correctly, im sure this will be sufficiently snappy =)
some pseudo code which may not be completely correct, but should get you started.
also, should offer linear complexity.
also, should offer linear complexity.
reference_point = (3, 6)Region = points[5]intersections = 0x_minimum = left side of bounding box around Regionfor 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 falseThis topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
