# Perimiter Path from a Contiguous Discrete 2D Area

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

## 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 on other sites
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 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

##### 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 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 = 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 false

1. 1
Rutin
22
2. 2
3. 3
4. 4
5. 5

• 9
• 9
• 9
• 14
• 12
• ### Forum Statistics

• Total Topics
633308
• Total Posts
3011293
• ### Who's Online (See full list)

There are no registered users currently online

×