|
Does anyone know a mathematical formula (which can be translated to C #) to check if a polygon is inside another polygon?
|
|
|
|
|
Regular polygons (where all the angles or equal) or irregular?
Needless to say, irregular ones are the PITA...especially where they are the containing polygon.
Just to confirm how much of a PITA irregular polygons are, here's a discussion that may may like to read (though you'll probably wish you hadn't)
The Polygon Containment Problem[^]
modified 28-Jan-13 14:17pm.
|
|
|
|
|
There are irregular polygons.
|
|
|
|
|
If polygon A is inside polygon B, then:
1. Every vertex of A will be inside B, and
2. No edge of A will intersect an edge of B.
So you need two subroutines: One to detect if a point is in a polygon, and one to detect if two line segments intersect each other.
Test all points of A to see if they're in B. If one isn't, then B doesn't contain A. Then test all edges of A to see if any intersect an edge of B. If none do, then polygon A is inside polygon B.
|
|
|
|
|
Yes you are right, but this is a very costly routine, and it might be performed more than 1000 times during the opening of a shapefile.
|
|
|
|
|
So you need efficiency too. Ok, calculate the bounding rectangles of both polygons. If the bounding rectangles don't overlap, neither polygon contains the other, so you can skip the more expensive test.
If they do overlap, check if each polygon contains points of the other in the overlap region. If polygon B contains some points of polygon A, but not others, then B doesn't contain A.
|
|
|
|