On Sep 14, 7:22 am, KirAsh4 <[email protected]> wrote: > Anyone got a clipping algorithm to check whether a Polyline goes > through a (circle) Polygon? I don't want to reinvent the wheel if I > don't have to. > > I have all the vertexes of the Polyline defined. I have all the > points used to create the circle Polygon. Do I have to trace each > Polyline and check each individual vertex, see if it falls inside of > the circle? Seems a bit of an overhead there ...
You're right that it's computationally expensive, whereas a human can simply look at the situation to determine whether the lines intersect. Humans are optimised to avoid computation; computers are optimised for computing (surprising, that!) The problem is simply defined, however. Each segment of your polyline is a straight line. Each segment of your polygon boundary is a straight line. If the segments intersect, the line crosses the shape. Note: it's not sufficient to examine vertices, because you could have a straight line segment larger than the polygon -- the line could cross it but have both ends outside it. Checking vertices wouldn't catch that; you need to examine the lines themselves. Each line segment can be defined as an equation, y=ax+b. Each segment of the polygon boundary can be similarly defined: y'=cx'+d. If there is a solution to those simultaneous equations which lies within both MBRs of the segments, the segments cross and the line intersects the shape. Andrew --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Google Maps API" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/google-maps-api?hl=en -~----------~----~----~----~------~----~------~--~---
