5
$\begingroup$

I'm creating an SVG editor.

I have a simple selection tool that appears when I click and move my mouse from a blank area in my SVG.

My SVG is populated with rectangles that can have a rotation applied to.

  • I have the X and Y position applied to a translate function.
  • Width and height are easy to calculate based on a scale factor and original dimensions of my rectangle(s).
  • My rotation angle is applied in a rotate function

I know about the point in polygon algorithm but I don't know how to calculate the points of my (rotated) rectangles.

My question is how can I verify if my selection area is over one or more of these rectangles and if the PIP algorithm is the best, how can I calculate the points of my rectangle(s)?

Here is the kind of render I'm trying to have: selection

$\endgroup$
1
$\begingroup$

In pseudocode

For each rectangle:
    If the rectangle overlaps the selection area, highlight the rectangle

This is all that is required for a correctly working approach, but there are a number of other things you might need to take into account if this approach performs too slowly. I recommend implementing the simple approach, and once it works correctly you can make gradual improvements if it is not sufficiently smooth and responsive (this may not be necessary unless you have a large number of rectangles or restrictive hardware/software).

Determining whether a rectangle overlaps the selection rectangle

As you point out, using the point in polygon algorithm is impractical for this purpose - each rectangle is made up of an infinite number of points. So we need a completely different approach.

One way to check if a candidate rectangle overlaps the selection rectangle is to check for the following two cases:

  • Check if any edge of the candidate rectangle intersects an edge of the selection rectangle.
  • Check if either the candidate rectangle or the selection rectangle is completely contained within the other.

If either of these are true, there is some overlap. If neither of these are true, there is no overlap.

The complete containment check is simplified by the fact that the selection rectangle is never rotated - always remaining aligned to the x and y axes:

  • To check if a candidate rectangle is completely contained within the selection rectangle, check that all 4 of its corners are between the x boundaries of the selection rectangle, and between the y boundaries of the selection rectangle.
  • To check if a candidate rectangle completely contains the selection rectangle, check that it has one corner outside the bounds of the selection rectangle in each of the 4 orthogonal directions (left, right, up, and down). If so, it either contains the selection rectangle completely, or one or more of the edges intersect (but edge intersection was checked for in the previous stage, so we're only checking for complete containment if we already know there is no edge intersection).

Line segment intersection

To check whether any of the edges of a candidate rectangle intersects with any of the edges of the selection rectangle, you can either use a general line segment intersection algorithm and apply it to each pair of candidate edge and selection edge, or you can take advantage of the fact that the selection rectangle is never rotated,as follows:

Parallel case

If the candidate rectangle has edges parallel to the x and y axes (that is, it is rotated by 0, 90, 180 or 270 degrees), check each of its edges:

If the edge is vertical, check if its x position is between the x coordinates of the selection rectangle, and if one of the following holds then there is an intersection:

  • The y coordinate of one of its end points is between the y coordinates of the selection rectangle AND the y coordinate of the other end point is not.
  • The end points are both outside the y coordinates of the selection rectangle but in opposite directions.

Similarly, if the edge is horizontal, check if its y position is between the y coordinates of the selection rectangle, and if one of the following holds then there is an intersection:

  • The x coordinate of one of its end points is between the x coordinates of the selection rectangle AND the x coordinate of the other end point is not.
  • The end points are both outside the x coordinates of the selection rectangle but in opposite directions.

Non-parallel case

Check each of the edges of the candidate rectangle as follows:

First find the points of intersection of the infinite line on which the candidate edge lies, with the infinite lines forming the boundaries of the selection rectangle.

If either of the intersections with the y boundaries of the selection rectangle has an x coordinate between the x boundaries of the selection rectangle, then there is an intersection of one of the horizontal line segment edges of the selection rectangle with the candidate infinite line (so potentially with the candidate line segment too).

Similarly, if either of the intersections with the x boundaries of the selection rectangle has a y coordinate between the y boundaries of the selection rectangle, then there is an intersection of one of the vertical line segment edges of the selection rectangle with the candidate infinite line (so potentially with the candidate line segment too).

To then check if there is an intersection with the candidate line segment, check if one of the following is true:

  • An intersection with the y boundary of the selection rectangle is between the x boundaries of the selection rectangle AND between the y coordinates of the candidate line segment.
  • An intersection with the x boundary of the selection rectangle is between the y boundaries of the selection rectangle AND between the x coordinates of the candidate line segment.

Examples of refinements if speed is unsatisfactory

  • Acceleration data structures such as a grid or space partitioning hierarchy so that not every rectangle needs to be checked.
  • Only checking the changed parts of the selection (usually one corner of the selection stays fixed while the opposite corner moves).
  • Tracking which rectangles are already selected to reduce the checking required each time the selection changes:
    • No need to check unselected rectangles if the selection has purely shrunk.
    • No need to check already selected rectangles if the selection has purely grown.
    • It will only be necessary to check both selected and unselected rectangles if the selection has grown in one direction and shrunk in the other.
$\endgroup$
  • $\begingroup$ Thanks for your answer. I was checking more for the formula to get to know which points are inside my rotated rectangle, based on X, Y position, width and height and also rotation angle (centered). Thx $\endgroup$ – JSmith Jun 30 '17 at 14:50
  • $\begingroup$ I've just done it. Thx $\endgroup$ – JSmith Jun 30 '17 at 21:00
  • $\begingroup$ Can you edit your answer please? $\endgroup$ – JSmith Jul 1 '17 at 15:16
  • $\begingroup$ Edited following the edit to the question. $\endgroup$ – trichoplax Jul 3 '17 at 12:26
  • 1
    $\begingroup$ That's an hell of an edit. I wish I could upvote more. $\endgroup$ – JSmith Jul 3 '17 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.