Polygon interact other polygon

animal_x has asked for the wisdom of the Perl Monks concerning the following question:

Hi guys, I need a function that check if one polygon interact(intersect,touch or inside) other polygon. thanks

Comment on Polygon interact other polygon

Replies are listed 'Best First'.
Re: Polygon interact other polygon by borisz (Canon) on Oct 24, 2004 at 11:49 UTC
See: Algorithms with Perl. The Chapter you are interested in is free: Geometric Algorithms. Boris	[reply]
Re: Polygon interact other polygon by tall_man (Parson) on Oct 24, 2004 at 22:27 UTC
The module Math::Geometry::Planar contains a GpcClip function that can find the intersection of two polygons. Your test will be that the intersection is not empty.	[reply]
Re^2: Polygon interact other polygon by animal_x (Initiate) on Oct 25, 2004 at 07:59 UTC
Thanx The shortest answer and exactly what i needed.	[reply]
Re: Polygon interact other polygon by bart (Canon) on Oct 24, 2004 at 21:12 UTC
There's a nice simple algorithm to check if a point is inside a polygon: the principle is this: draw a line from it to any point outside the polygon (for example with an X that is larger than any X for all the polygon vertices), and count how many edges it crosses. Iff this number is even, the point is outside of the polygon. There are problematic cases where your test line goes straight through a vertex. You could think up an elaborate advanced scheme, taking the direction of the crossing into account, and counting such a crossing as +0.5 or -0.5 depending on its direction; or you could simply try again with a different line. Combine this with tests on whether any edges from the polygons actually cross, and the basis is set.	[reply]
Re: Polygon interact other polygon by zentara (Archbishop) on Oct 24, 2004 at 13:56 UTC
From just thinking about the problem, my first thought, is if it's polygons, then you should have the equations of the line segments which make up it's sides. All you have to do is see if any segment from polygon1 intersects any segment from polygon2. How to find the intersection of 2 lines has a well known solution, called "simultaneous equations". I'm not really a human, but I play one on earth. flash japh	[reply]
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
Re^5: Polygon interact other polygon by zentara (Archbishop) on Oct 27, 2004 at 12:10 UTC
Re: Polygon interact other polygon by FoxtrotUniform (Prior) on Oct 24, 2004 at 21:35 UTC
Are we talking 2d polygons, or 3d? In 2d the problem is quite simple; in 3d, not so much. `--` Yours in pedantry,`F o x t r o t U n i f o r m` "Lines of code don't matter as long as I'm not writing them." -- merlyn	[reply]

Back to Seekers of Perl Wisdom