How Do Vector drawing applications do this?

Question

In Illustrator, you can drag a rectangle and it will select all objects in it. It does beyond a bounding box test since it ensures its touching an actual part of the polygon. How does it efficiently do this then? (A C or C++ implementation would be preferable)

Thanks

Answer 1

If you want to check if any part of polygon P is within a rectangle R, then you can do this:

• If any vertex of P is within R, then return TRUE;
• If any vertex of R is within P, then return TRUE;
• If any edge of P (line between adjacent vertexes) intersects an edge of R, then return TRUE.
• Otherwise, return FALSE.

Answer 2

You could also just construct the intersection of the rectangle with the object (a function which programs like Illustrator already have for many other purposes) and check that it's non-empty. More efficient algorithms are available (see caf's answer), but mine has the one advantage that it requires no additional code.