Переместите прямоугольники, чтобы они не перекрывались

Question

Это наполовину запрограммированный вопрос, наполовину математика.

У меня есть несколько прямоугольников, которые представлены в виде четырех угловых точек.Это настоящие прямоугольники, пересечения двух наборов параллельных линий, где каждая линия в каждом наборе находится под прямым углом к ​​обеим линиям в другом наборе (просто чтобы нам было понятно.)

Для любого набораn ящиков, как я могу эффективно рассчитать, куда их перемещать (наименьшее расстояние), чтобы они не перекрывали друг друга?

Я работаю в javascript здесь.Вот данные:

//an array of indefinite length of boxes
//boxes represented as arrays of four points
//points represented as arrays of two things, an x and a y, measured in
//pixels from the upper left corner

var boxes = [[[504.36100124308336,110.58685958804978],[916.3610012430834,110.58685958804978],[916.3610012430834,149.58685958804978],[504.36100124308336,149.58685958804978]],[[504.4114378910622,312.3334473005064],[554.4114378910622,312.3334473005064],[554.4114378910622,396.3334473005064],[504.4114378910622,396.3334473005064]],[[479.4272869132357,343.82042608058134],[516.4272869132358,343.82042608058134],[516.4272869132358,427.82042608058134],[479.4272869132357,427.82042608058134]],[[345.0558946408693,400.12499171846],[632.0558946408694,400.12499171846],[632.0558946408694,439.12499171846],[345.0558946408693,439.12499171846]],[[164.54073131913765,374.02074227992966],[264.54073131913765,374.02074227992966],[264.54073131913765,428.02074227992966],[164.54073131913765,428.02074227992966]],[[89.76601656567325,257.7956256799442],[176.76601656567325,257.7956256799442],[176.76601656567325,311.7956256799442],[89.76601656567325,311.7956256799442]],[[60.711850703535845,103.10558195262593],[185.71185070353584,103.10558195262593],[185.71185070353584,157.10558195262593],[60.711850703535845,157.10558195262593]],[[169.5240557746245,23.743626531766495],[231.5240557746245,23.743626531766495],[231.5240557746245,92.7436265317665],[169.5240557746245,92.7436265317665]],[[241.6776988694169,24.30106373152889],[278.6776988694169,24.30106373152889],[278.6776988694169,63.30106373152889],[241.6776988694169,63.30106373152889]],[[272.7734457459479,15.53275710947554],[305.7734457459479,15.53275710947554],[305.7734457459479,54.53275710947554],[272.7734457459479,54.53275710947554]],[[304.2905062327675,-3.9599943474960035],[341.2905062327675,-3.9599943474960035],[341.2905062327675,50.04000565250399],[304.2905062327675,50.04000565250399]],[[334.86335590542114,12.526345270766143],[367.86335590542114,12.526345270766143],[367.86335590542114,51.52634527076614],[334.86335590542114,51.52634527076614]],[[504.36100124308336,110.58685958804978],[916.3610012430834,110.58685958804978],[916.3610012430834,149.58685958804978],[504.36100124308336,149.58685958804978]],[[504.4114378910622,312.3334473005064],[554.4114378910622,312.3334473005064],[554.4114378910622,396.3334473005064],[504.4114378910622,396.3334473005064]],[[479.4272869132357,343.82042608058134],[516.4272869132358,343.82042608058134],[516.4272869132358,427.82042608058134],[479.4272869132357,427.82042608058134]],[[345.0558946408693,400.12499171846],[632.0558946408694,400.12499171846],[632.0558946408694,439.12499171846],[345.0558946408693,439.12499171846]],[[164.54073131913765,374.02074227992966],[264.54073131913765,374.02074227992966],[264.54073131913765,428.02074227992966],[164.54073131913765,428.02074227992966]],[[89.76601656567325,257.7956256799442],[176.76601656567325,257.7956256799442],[176.76601656567325,311.7956256799442],[89.76601656567325,311.7956256799442]],[[60.711850703535845,103.10558195262593],[185.71185070353584,103.10558195262593],[185.71185070353584,157.10558195262593],[60.711850703535845,157.10558195262593]],[[169.5240557746245,23.743626531766495],[231.5240557746245,23.743626531766495],[231.5240557746245,92.7436265317665],[169.5240557746245,92.7436265317665]],[[241.6776988694169,24.30106373152889],[278.6776988694169,24.30106373152889],[278.6776988694169,63.30106373152889],[241.6776988694169,63.30106373152889]],[[272.7734457459479,15.53275710947554],[305.7734457459479,15.53275710947554],[305.7734457459479,54.53275710947554],[272.7734457459479,54.53275710947554]],[[304.2905062327675,-3.9599943474960035],[341.2905062327675,-3.9599943474960035],[341.2905062327675,50.04000565250399],[304.2905062327675,50.04000565250399]],[[334.86335590542114,12.526345270766143],[367.86335590542114,12.526345270766143],[367.86335590542114,51.52634527076614],[334.86335590542114,51.52634527076614]]]

Эта скрипка показывает поля, нарисованные на холсте полупрозрачно для ясности.

Answer 1

Вы можете использовать жадный алгоритм. Это будет далеко от оптимального, но может быть «достаточно хорошим». Вот эскиз:

 1 Sort the rectangles by the x-axis, topmost first. (n log n)
 2 for each rectangle r1, top to bottom
       //check for intersections with the rectangles below it.
       // you only have to check the first few b/c they are sorted 
 3     for every other rectangle r2 that might intersect with it 
 4         if r1 and r2 intersect //this part is easy, see @Jose's answer
 5             left = the amount needed to resolve the collision by moving r2 left
 6             right = the amount needed to resolve the collision by moving r2 right
 7             down = the amount needed to resolve the collision by moving r2 down

 8             move r2 according to the minimum value of (left, right down)
               // (this may create new collisions, they will be resolved in later steps)
 9         end if

10     end
11 end

Примечание шаг 8 может создать новое столкновение с предшествующим прямоугольником, которое не будет разрешено должным образом. Гектометр Вам может понадобиться иметь при себе некоторые метаданные о предыдущих прямоугольниках, чтобы избежать этого. Думая ...

Answer 2

Предполагая, что поля выровнены по осям x и y, как в вашем комментарии, сначала я бы изменил представление каждого прямоугольника на 4 точки: верхнюю, правую, нижнюю, левую и сохранил бы их как точки на прямоугольнике. Во-вторых, давайте упростим задачу до «Учитывая n прямоугольников, где находится ближайшая точка, куда прямоугольник r может переместиться, чтобы он не перекрывал другие прямоугольники»? Это значительно упрощает проблему, но также должно обеспечить достойное решение. Таким образом, мы имеем нашу функцию:

function deOverlapTheHonkOuttaTheRectangle(rectangle, otherRectangles){
    ..
}

Теперь каждый другой прямоугольник будет запрещать определенный диапазон движения для исходного прямоугольника. Таким образом, вы рассчитываете все эти запрещенные ходы. Из них вы можете рассчитать форму запрета, которая перекрывает источник и друг друга. Например, допустим, что rect1 запрещает сдвиг -3px to 5px вправо и 4px to 10px вверх, а rect2 запрещает -4px to 1px вправо и -2px to 5px вверх. rect1 не рассматривался до появления rect2, так как он перекрывает начало координат и rect1. Начиная с rect2, вы получите [[-4, -2],[1,-2],[1,5],[-4,5]]. Цифра в прямоугольнике 1 дает [[-4, -2],[1,-2],[1,4],[5,4],[5,10],[-3,10],[-3,5],[-4,5]] (см. Изображение ниже для пояснения). Вы продолжаете строить их для каждого перекрывающегося запрещенного прямоугольника. После того как вы рассмотрели все прямоугольники, вы можете использовать формулу расстояния от начала координат, чтобы получить наименьшее расстояние, на которое вы можете переместить прямоугольник и переместить его.

Наконец, вы повторите этот процесс для всех оставшихся прямоугольников.

Answer 3

Имейте в виду блочную модель, учитывая любые два прямоугольника, которые вы должны вычислить для ширины и высоты двух блоков, добавляя их соответствующие поля, отступы и границы (добавьте их слева / справа от них, чтобы обнаружить столкновение по оси x,и сверху / снизу для обнаружения столкновения по оси y), затем вы можете рассчитать расстояние между элементами 1 и 2, добавив результат к их соответствующей координатной позиции, например ((positionX2 + totalWidth2) - (positionX1 + totalWidth1)), чтобы вычислитьстолкновение вдоль оси X.Если оно отрицательное, они перекрываются.Как только вы это знаете, если они не будут перекрываться, перемещая их, вы можете переместить их как обычно, в противном случае вам придется вычесть количество пространства, которое они перекрывают, из значения, которое вы хотите переместить.

Посколькусреда - это 2D-плоскость, это должно быть довольно просто.С такой библиотекой, как jQuery, было бы шуткой, но даже в простом js это просто основная зависимость и вычитание.