Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic

Re^4: Polygon interact other polygon

by tilly (Archbishop)
on Oct 26, 2004 at 14:47 UTC ( #402614=note: print w/replies, xml ) Need Help??

in reply to Re^3: Polygon interact other polygon
in thread Polygon interact other polygon

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.

Replies are listed 'Best First'.
Re^5: Polygon interact other polygon
by zentara (Archbishop) on Oct 27, 2004 at 12:10 UTC
    Complex numbers?....don't know if it would work but it sounds impressive. Sort of like jumping into hyper-space to do some calculation.

    My first thought would be to calculate the "area-points" of each polygon, and see if any points intersect, but your integration above probably does this in a clean manner.

    I'm not really a human, but I play one on earth. flash japh

Log In?

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://402614]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (3)
As of 2023-09-29 23:27 GMT
Find Nodes?
    Voting Booth?

    No recent polls found