Re: Polygon interact other polygon

Replies are listed 'Best First'.
Re^2: Polygon interact other polygon by pg (Canon) on Oct 24, 2004 at 17:15 UTC
"How to find the intersection of 2 lines has a well known solution," Well, just to add a bit detail here: line is the extension of a line segment on both ends. Two line intersect each other, does not mean that the two original line segments intersect. Your solution is fine, other than that we have to add one more step: after you get the point of intersection, you have to go back and check whether the intersection point is on both original line segments.	[reply]
Re^3: Polygon interact other polygon by zentara (Archbishop) on Oct 25, 2004 at 13:08 UTC
You are right, but I didn't go into detail because I figured it would be obvious to do x-y bounds checking. I'm not really a human, but I play one on earth. flash japh	[reply]
Re^2: Polygon interact other polygon by tilly (Archbishop) on Oct 25, 2004 at 17:37 UTC
That won't catch the case where one polygon is entirely inside the other.	[reply]
Re^3: Polygon interact other polygon by zentara (Archbishop) on Oct 26, 2004 at 12:52 UTC
Good point. That is a case where the line segments need to be extended to infinity, before checking for intersection. Then using that in conjunction with the known x and y maximum and minimums, one should be able to figure out if one is inside another. It's an interesting problem. I can see a set of nested loops. You can probably do some "pre-filtering" of the line segment extreme endpoints, to determine which type of tests to perform. If all extreme endpoints of one polygon fall between the extreme endpoints of the other, and there is no intersection detected between segments.....??? Sounds like homework now. I'm not really a human, but I play one on earth. flash japh	[reply]
Re^4: Polygon interact other polygon by tilly (Archbishop) on Oct 26, 2004 at 14:47 UTC
Not so easy. Imagine a polygon that tracks out a big "C, then turns around and makes that into a strip. The other is a small circle in the middle of the C. Looking at extreme endpoints it would look like the first contains the other but it doesn't. I'd suspect that nailing down all possible cases could be very hard. Without knowing the standard algorithm, my natural approach would be to try to find intersections. If there are none then take the polygon with the point with the largest x-value, take any point of the other polygon, pull out my complex analysis and calculate a winding number by numerical integration. (In that calculation you're viewing the point `(x,y)` is treated as the complex number `x + yi`.) If that comes out non-zero (within the tolerance of rounding errors), then the one is inside the other. Otherwise not.	[reply] [d/l] [select]
Re^5: Polygon interact other polygon by zentara (Archbishop) on Oct 27, 2004 at 12:10 UTC


There's more than one way to do things
	PerlMonks