Code conundrum

Hamster_style

Hey guys,

So, for those of you out there who are inclined towards programming, I have a particular problem.

I have a 2 dimensional image array in memory and a set of points (x, y) which define an abritrary well behaved polygon in this array. This is not a pathological polygon, ie, it doesn't cross itself or anything ugly like that. Rather; it's a simple shape that encloses a single continuous area.

So, my question is, what's an efficient way to take this list of vertices, and use this to grab all of the information in the area that is enclosed? The operation I need to do is add this area in one array to another array with identical dimensions, on the same locations. Graphically, you can just think of me adding values in a section of an image to another identically sized image.

Does anyone have any algorithms in mind that work well for this, or am I going to have to just grind through this along each edge of the polygon?

If anyone has any experience using IDL with FITS files, that's what I'm using right now.

Cathode

If execution speed isn't an issue, there are quite a few algorithms for determining if a point lies in a triangle on a 2-dimensional plane (google is your friend), any one of which you could just evaluate on a per-pixel basis to see if the pixel in question gets added to the destination image, iterating through all the pixels one by one. You can also reduce the number of pixel-in-triangle tests performed by first calculating the smallest rectangle that fits around the polygon in question and culling all pixels that don't lie inside this rectangle, which will always be faster than calculating if they lie inside the triangle.

Marty

Interesting question. I'd advise against checking to see if points lie in triangles made by your vertices...it scales badly with the number of vertices you have and it doesn't work if your polygon isn't convex.

Legionnaired

Wikipedia Say: http://pmaillot.chez.com/2dpclip/2dpclip.htm

Powerpuppies

Just spitballing here, but couldn't you move vertically from the topmost vertex to the bottommost, determining the left-right edges of the polygon for each row? Something like finding the nearest 'left' vertices above and below the row, then using slope to calculate the left edge of the polygon, then finding the nearest 'right' vertices above and below the row and using slope to calculate the right edge of the polygon?

I'm not going to put in the effort to actually solve the problem, but it seems like it wouldn't be too bad to loop row by row and figure left-right boundaries. Especially if you separated the boundary finding from the pixel checking.

Doc

Powerpuppies wrote: »

Just spitballing here, but couldn't you move vertically from the topmost vertex to the bottommost, determining the left-right edges of the polygon for each row? Something like finding the nearest 'left' vertices above and below the row, then using slope to calculate the left edge of the polygon, then finding the nearest 'right' vertices above and below the row and using slope to calculate the right edge of the polygon?

I'm not going to put in the effort to actually solve the problem, but it seems like it wouldn't be too bad to loop row by row and figure left-right boundaries. Especially if you separated the boundary finding from the pixel checking.

That's probably how I'd do it. Just find the two intercepts per row and grab all the pixels between them. It should be really easy, provided that it's convex and you sort your points first.

If it can be concave, split it into two or more convex shapes and do them separate.

Hamster_style

Powerpuppies I was thinking of an approach similar to yours...just going row by row and checking ends. Reading your description of the method filled in the necessary holes in my thinking in order to code this fairly easily. Thanks!

While I'll probably implement the above tomorrow, I'm still going to check out these algorithms that people mentioned, just to see what there is that's out there in terms of speed and robustness.

Thanks for the help everyone!