0

Let's say we have an arbitrary number of different sized rectangles randomly placed on a 2D Cartesian plane. For the sake of brevity, let's also say that none of these rectangles overlap each other.

Drawing a vector from the center of one of these rectangles, and moving to the center of another arbitrary rectangle, how can we return an array of rectangles which intersect this path?

My first thought is to:

  • Normalize the vector
  • Use linear interpolation to get each XY point along this vector, between V1 and V2 (where V1 = center of 1st rect, and V2 is center of 2nd rect)
  • Perform a "point in rect" check, for every existing rectangle that isn't the 1st and 2nd rects
  • Return the array of any rectangles found in the previous step

While this would likely work, is there a more optimal way of doing things? Perhaps some way of eliminating having to loop through every existing rectangle?

RectangleEquals
  • 1,825
  • 2
  • 25
  • 44
  • _Use linear interpolation to get each XY point along this vector, between V1 and V2 (where V1 = center of 1st rect, and V2 is center of 2nd rect)_ : this sounds bad because there are a lot of such points and that would make a lot of "point in rect". You should rather find the intersection of the line connecting the two centers with each of the 4 lines of each rectangle. That's already a huge improvment over your solution. For the maths see [here](https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection) – Jabberwocky Oct 25 '17 at 13:10
  • are the rectangles sides all parallel to the cartesian axes ? – Massimiliano Janes Oct 25 '17 at 13:10
  • @MassimilianoJanes If you are asking if any of the rectangles are rotated, the answer is no. All rects are just standard `X1,Y1`,`X2,Y2` (or `X1,Y1`,`W`,`H`) points on the plane – RectangleEquals Oct 25 '17 at 13:13
  • @RectangleEquals with my suggestion it would work with any rectangles even with any polygons. But if the rectangles are not rotated, the maths can probably be simplified. – Jabberwocky Oct 25 '17 at 13:14
  • @RectangleEquals you need to forget the rectangles. Your problem boils down to finding the intersection of two lines (one of which is either vertical or horizontal which simplifies the problem even further). To check if your line intersects with a rectangle you simple need to check if the line intersects with one of the 4 lines of the rectangle. – Jabberwocky Oct 25 '17 at 13:19
  • Googling naively "check if lines intersects rectangle" I found [this](https://stackoverflow.com/questions/16203760/how-to-check-if-line-segment-intersects-a-rectangle) – Jabberwocky Oct 25 '17 at 13:22
  • Is the request should be done once or several time (for other coordinates) ? Could you have precompute step or not ? – Jarod42 Oct 25 '17 at 13:26
  • @Jarod42 I'm not entirely sure I understand your question, but this calculation is not something I would like to perform every frame. The rects are fixed, and do not change position or size after being plotted. We are just interested in constructing an array of rectangles along a known path – RectangleEquals Oct 25 '17 at 13:31
  • @MichaelWalz I'm going to assume that your optimization is probably best. I found [this answer](https://stackoverflow.com/a/5514619/1500110) which appears quite similar. Would you mind posting an answer for me to mark? – RectangleEquals Oct 25 '17 at 13:39
  • Or at the very least, could someone mark this thread as duplicate, pointing to similar threads? – RectangleEquals Oct 25 '17 at 13:45
  • I meant that for example, you could create a triangulation (For example [Delaunay_triangulation](https://en.wikipedia.org/wiki/Delaunay_triangulation)) with owner rectangle. then from triangle iterate on direction of target, and add to result rectangle visited. So once triangulation is done (once), you got result in complexity "unrelated" to number of rectangles. – Jarod42 Oct 25 '17 at 18:00
  • Partitioning rectangles can also be an option, and then iterate only for a sub-group of rectangles to check intersection with line. – Jarod42 Oct 25 '17 at 18:02

0 Answers0