CODEWITHSUNDEEP
c++calgorithm
jmasterx
jmasterx

Reputation: 54193

How Do Vector drawing applications do this?

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

Upvotes: 1

Views: 257

Answers (2)

R.. GitHub STOP HELPING ICE
R.. GitHub STOP HELPING ICE

Reputation: 215627

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.

Upvotes: 0

caf
caf

Reputation: 239361

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.

Upvotes: 3

Related Questions