What are the algorithms for finding equidistant rectangles?

Question

JavaScript

I'm looking for an algorithm or library to draw connection lines between equidistant rectangles. I need to implement this feature in an editor written in javascript. All rectangles can be dragged and the algorithm should be as efficient as possible.
The end result of the implementation can be seen in some editors such as Keynote or PowerPoint.


Important: the algorithm must calculate the points at which the rectangle will be equidistant relative to the nearest siblings. Thus, when dragging close to an equidistant point, it will be possible to magnetize the edge of the rectangle to that point.
I tried to implement the following algorithm:

1. Finding all rectangles along the x and y axes relative to the dragged (selected) rectangle
   
2. Divide the found sets into subsets: "top", "bottom", "left", "right" and find the nearest rectangle to the selected rectangle in each subset
   
3. calculate the distances (D) between the dragged and the nearest rectangle
   
4. Repeat the procedure from step 1 for the rectangles found in step 2. But instead of looking for the nearest one, look for a rectangle at distance D
   
5. Repeat step 4 recursively until rectangles at distance D are found
   

I can't calculate the equidistance points for the magnetize feature when dragging a rectangle. I'm also concerned about performance, since all calculations and sorting must be done on the "ondrag" event (multiple times per second).
Is there a way to optimize my algorithm?

Answer 1

Your algorithm just needs to be tweaked a bit.
1) find the nearest top (left/bottom/right) of those that have overlap.
2) repeat the operation, finding the next one on top. Take the distance between them as d.
3) keep going up. If the next closest one is also at distance d, draw a gap. If not, it will stop.
4) Knowing the nearest rectangle from point 1) and the distance d - you can retreat down and you have a magnetization point.
You can speed up the algorithm a bit. First, in one pass, select all the rectangles that are above the given one, but intersect with it along the X axis. Sort them from bottom to top by the bottom border. Now in paragraphs 1,2,3 it is necessary to consider only one next rectangle from the list.
If there are intersections, then you can either throw out the rectangles that intersect with the current one, or stop as if there is no next rectangle.
To speed it up even more, when you have a lot of rectangles on the screen, you can store them in a quad tree and pull out rectangles from it that overlap with the given one and above it in the correct order. But most likely just going through the list of all rectangles will be enough.

Answer 2

Build a grid to which you want to "magnetize" and when approaching it - push in the right direction.
Examples can be googled like this

Answer 3

(?<!<|\/)body