PolyGon in PolyGon

[THEROB]

Can anyone tell me how to check if one 2D polygon is within another. This function needs to be as quick as possible so preferably C++.

Thanks

Rob

[thinktank]

Don't know if it is of any help..but give it a look.

http://astronomy.swin.edu.au/pbourke...ry/insidepoly/

[THEROB]

Thanks for the reply - but I need to check for an entire polygon inside another polygon. I can't check each point to see if it is inside or out of the other polygon - because while all the points may be inside - a line connecting 2 points may fall outside.

Any other sites???

Thanks

Rob

[kedaman]

A line is totally inside a polygon if doesn't cross any of it's sides, and a line to one of it's end points from an arbitary point outside (preferably vertical) crosses an odd amount of the polygons sides. A whole polygon is inside another if none of it's sides crosses any of the other polygon's and one of the corners can be verified to be inside the polygon using the method I mentioned

[THEROB]

Cheers - any sample code?

Rob

[kedaman]

Something like this:

bool is=false;//inside/intersection

for (lineiterator i2=plg2.first;i2<pl2.last;i2++){

is^=
((
(plg1.first.first.x>i2.first.first.x
)^(
plg1.first.last.x>i2.first.last.x
))&&(
i2.first.first.y+(i2.first.last.y-i2.first.first.y)/(plg1.first.first.x-i2.first.first.x)*(i2.first.last.x-i2.first.first.x)
)

}
if (!is) return false;

for (lineiterator i1=plg1.first;i1<pl1.last;i1++)
for (i2=plg2.first;i2<pl2.last;i2++)
if(is=i1.iscross(i2)) break;

return is;

[THEROB]

Thanks - I am using Borland so I don't have that lineiterator object - however I'll work it out.

Thanks

Rob

[kedaman]

lineiterator doesn't come with as a component in any library, i just invented it for the use of acting as a line and as a iterator in the polygon, the iterator would point to a specific corner in the polygon (and iterate to next corner with ++ operator) while the line part of the interface would provide that corner point first and the next corner point last as two end points of a line.

[THEROB]

Thanks - I think I have the bones of a C++ function that will do it.

Just on another point - if I wanted to place a grid over a polygon and then I just want returned the grid sections that are entirely inside the polygon - do you know how that would work??

Do you know what I mean?

Thanks

Rob

[kedaman]

Yep, it's called Bresenham algoritm