Найти ближайший подходящий для круга

12

Ниже приведен пример изображения, если у меня есть точка белой точки в середине, и я хочу найти ближайшее возможное местоположение для синего круга (который, очевидно, находится в том месте, где я его поместил), если все красные круги уже существуют , Как я могу найти это место?

Производительность для меня не является серьезной проблемой для этого приложения.

введите описание изображения здесь

Ботанический
источник
1
каково значение черного круга? Вы можете поместить синий круг по этому?
Эван
2
Таким образом, чтобы быть ясным, вы хотите место, где вы можете поместить синий круг так, чтобы он был наименьшим возможным расстоянием от белой точки, не перекрывая другие круги?
Роберт Харви
3
Связанный: Упаковка Круга
Роберт Харви
2
Будут ли все круги касаться какого-либо другого круга хотя бы в одном месте?
Роберт Харви
3
Связанные: stackoverflow.com/questions/10666116 и stackoverflow.com/questions/5509151 . Также возможно актуально: stackoverflow.com/a/19375601
Роберт Харви

Ответы:

4

Это не общее решение, так как есть несколько ситуаций, когда оно не обеспечит положение синего круга с кратчайшим расстоянием до белой точки. Например, если у вас есть 100 красных шаров, сгруппированных вместе, и белая точка находится далеко от этой группы красных шаров, то ни один из красных шаров не будет иметь никакого влияния на положение синего круга, который может быть центрирован на белой точке. , Также он не покажет все детали расчетов. В любом случае, для подмножества конфигураций, где решение (синий круг) касается двух красных кругов, должно работать следующее:
1) пусть R - радиус синего круга
2) сделать цикл по всей паре красных кругов, да Я знаю, что это O (n2).
3) для каждой пары окружностей i, j с центрами в (xi, yi) и (xj, yj) с соответствующими радиусами ri и rj вычислите квадрат расстояния между парой окружностей

d_ij^2=(xi-xj)^2+(yi-yj)^2  

4) поставить все пары окружностей, которые

dij^2<R^2

в список.

5) пройти список, найдя 2 решения окружностей радиуса R, касающихся обеих окружностей i и j. Для этого используйте эти уравнения вместе с этим изображением две синие кружочки-кандидаты на пару красных кружочков

a = R+ri  
b = R+rj  
c = dij  
α = arccos((b^2+c^2-a^2)/(2bc)  

с помощью вышеуказанной информации вы можете найти (X1ij, Y1ij) и (X2ij, Y2ij) центры 2 окружностей, касающихся окружностей i и j. Для каждого кандидата синий круг обведите все красные кружки и посмотрите, не перекрываются ли они. Если они действительно сбросят это, если нет, проверьте расстояние до белого круга. Если вы оставите тот с меньшим расстоянием, думаю, у вас будет решение, когда вы закончите обход списка пар окружностей. Алгоритм выглядит как O (n3).

мандрил
источник
не работает, когда есть только один круг
Ewan
или два круга, но с целевой точкой за пределами обоих
Ewan
проблема в том, что вы не можете быть уверены, что у вас есть все крайние случаи
Ewan
также. Есть уникальные решения для этих случаев
Ewan
Вам необходимо записать все предположения, при которых решение будет правильным, или хотя бы указать все пограничные случаи. Некоторые из них могут быть очевидными, а некоторые нет. Например, это не сработает, если можно нарисовать линию, которая отделяет белую точку от всех красных кругов, а белая точка находится на расстоянии меньше R от ближайшего круга.
Влад
2

Ближайшее размещение к точке будет либо в точке, либо касанием круга.

поэтому сначала проверьте точку, а затем обведите новый круг по краю каждого существующего круга, рассчитав расстояние от точки и, если вы перекрывались, и отслеживая точку минимального расстояния. Остановитесь, когда пройдете каждый круг.

то есть. отметьте все точки на зеленых линиях плюс белый кружок. где зеленая линия представляет собой круг с радиусом красного плюс синий

возможные центральные точки

вам нужно проверить всю зеленую линию, а не только пересечения, чтобы охватить эти крайние случаи.

случаи одного круга

Очевидно, что размер шага вашего обхода будет важен с точки зрения производительности. Но поскольку вы заявляете, что производительность не является проблемой, выберите значение, соответствующее разрешению вашего выходного значения. то есть плавать, долго?

уточнение:

Мое предложение состоит в том, чтобы перебрать все точки вокруг каждого круга, проверяя их на совпадение со всеми остальными кругами в каждой точке. нет хитрости

Если в примере на картинке указано количество кругов и разрешение, это не должно быть проблемой для стандартного ПК.

у нас есть 20 кругов среднего радиуса 200, так что примерно 20 * 2 π * 200 точек * 20 испытаний на пересечение = 4800000 итераций

Замечания:

Подобные итеративные подходы несовершенны тем, что размер шага, в данном случае разрешение вашего вывода, может сильно повлиять на результат.

Скажем, у меня есть два красных круга на расстоянии 2 пикселя и синий круг с радиусом 1 пиксель, чтобы сжать их между собой. Очевидно, что с любым из двух пикселей в качестве центра синего круга он будет перекрывать один из красных. но очевидно, что есть место для круга, если центр находится между двумя пикселями.

Отсюда мой комментарий с вопросом о разрешении вывода. который вы сказали, может быть что угодно.

Вы также можете решить уравнение одновременности для каждой пары окружностей, радиус которых увеличивается на радиус синего круга.

это даст вам точки, где синий круг будет касаться обоих красных кругов более точно, чем итерация.

Тем не мение. Есть несколько условий, когда, если вы только сделаете это, вы получите неправильный ответ или не получите ответа. то есть.

1 или нет кругов

2 или более кругов, но с заданной точкой далеко и за их пределами.

много кругов, но с целевой точкой близко к поверхности

Ewan
источник
2
То, что ему нужно накрутить край синего круга вокруг других кругов, легко понять. Трудная часть состоит в том, чтобы выяснить уравнения / расчеты, чтобы сделать это.
Роберт Харви
1
действительно? просто (x-x1) ^ 2 + (y-y1) ^ 2 = (r + r1) ^ 2
Эван
2
И тогда вам придется делать все это снова, когда вы пробуете следующий пункт. Я знаю, что ОП сказал, что производительность не была проблемой, но она должна завершиться до тепловой смерти вселенной.
Роберт Харви
2
Единственный способ узнать, получите ли вы десять голосов, - это опубликовать свой код C # и посмотреть, что произойдет.
Роберт Харви
2
я думаю, что произойдет, если ОП
Эван
1

Этот план содержит рабочий код,

концепция

Даны кружки C1, C2 .... Cn

и координаты окружности Cn - это Cnx, Cny и радиус - это Cr

и радиус необходимого круга R

если синий круг находится в положении X, Y и если он не конфликтует ни с какими другими кругами, следующие уравнения верны

(C1x - X)^2 + (C1y - Y)^2 > (C1r + R)^2
(C2x - X)^2 + (C2y - Y)^2 > (C2r + R)^2
....
(Cnx - X)^2 + (Cny - Y)^2 > (Cnr + R)^2

меняя первое уравнение,

C1x^2 - 2C1x*X + X^2 + C1y^2 - 2C1y*Y + Y^2 > C1r^2 + 2C1r*R + R^2
X^2 + Y^2 - 2C1x*X - 2C1y*Y > C1r^2 + 2C1r*R + R^2 - C1x^2 - C1y^2

так что уравнения можно переписать как,

X^2 + Y^2 - 2C1x*X - 2C1y*Y > C1r^2 + 2C1r*R + R^2 - C1x^2 - C1y^2
X^2 + Y^2 - 2C2x*X - 2C2y*Y > C2r^2 + 2C2r*R + R^2 - C2x^2 - C2y^2
....
X^2 + Y^2 - 2Cnx*X - 2Cny*Y > Cnr^2 + 2Cnr*R + R^2 - Cnx^2 - Cny^2

Реализация

начать с координаты белой точки (Xw, Yw),

    var isValidLocation = function(x,y,r){
       var valid = true;
       for (var i = 0; i< circles.length; i++){
          var circle = circles[i];
          valid = valid && ((x*x + y*y - 2*circle.x*x - 2*circle.y*y) > (circle.radius*circle.radius + 2*circle.radius*r + r*r - circle.x*circle.x - circle.y*circle.y));
       }
       return valid;
      };

      var find = function(Xw,Yw,Rw){
        var radius = 0;
        while(true){
          for (var x=-1 * radius ;x <= radius; x++) {
            for (var y=-1 * radius;y <= radius; y++) {
               if (isValidLocation(Xw + x,Yw + y, Rw)){
                 drawCircle(Xw + x,Yw + y,Rw,"#0000FF");
                 return;
               }
            }   
          } 
          radius++;
        }
     }; 

первой найденной координатой, удовлетворяющей всем уравнениям, является местоположение синего круга

Низко летящий пеликан
источник
Может кто-нибудь объяснить, что не так с этим подходом?
пеликан
Это трудно читать. Используйте несколько хороших имен и абстракций. Это убило бы вас, чтобы добавить диаграмму?
candied_orange
Насколько я вижу, этот подход пытается найти только допустимые места размещения для синего круга, но не самое близкое возможное местоположение. Это можно исправить, однако, подход также делает (скорее всего, неверным) предположение, что существует только конечное число координат целочисленных значений.
Док Браун
Он начинается с координаты белой точки и обходит ее, расширяя сетку поиска. Из-за этого он не столкнется ни с одной ситуацией, когда у него бесконечное число координат. В конце концов он найдет совпадающую координату.
пеликан
1
... для правильного решения в целочисленных координатах вам нужно использовать увеличивающийся радиус и сделать пространство поиска окружностью этого радиуса вокруг белой точки. И хотя OP пишет, что эффективность не является его задачей, было бы, тем не менее, хорошей идеей не проверять каждую уже протестированную пару координат в каждом цикле снова и снова.
Док Браун
0
  • О , это то, что ты пытаешься быть рядом с
  • P - точка, которую вы ищете (центр синего круга
  • r - радиус синего круга
  • C0 .. Cn - центры всех кругов, которые ограничивают размещение синего цвета на
  • расширенный круг является одним из кругов с радиусом, расширенным на r

    Есть некоторая дополнительная работа, если O не находится в центре круга. Итак, прямо сейчас предположим, O == C0

Вычислите все пересечения всех окружностей с C0, используя их соответствующие радиусы плюс r , т.е. пересекайте протяженные окружности с расширенным C0. Если пересечений нет, то точка, которую вы ищете, находится где-нибудь на C0, если есть пересечения, для каждого пересечения проверьте, находится ли она внутри другого расширенного круга (вы можете ограничиться кругами, которые имели пересечения с C0). Возьмите первое пересечение, которое не находится в другом расширенном круге как P, могут быть другие.

Если между расширенными окружностями и C0 нет пересечений, которые не находятся внутри другого расширенного круга, вычислите пересечения всех расширенных кругов друг с другом. Затем проверьте эти пересечения в порядке расстояния до O, снова, если любое из пересечений находится в пределах другого расширенного круга, если да, отбросьте, если нет, это ваш результат.

Если вы предполагаете, что представите, что обведите все круги, которые указывают на возможное местоположение вашего синего круга, объединение всех расширенных кругов укажет область, которой ваш синий круг не может быть. Точка, которую вы ищете, является ближайшей точкой, которой нет в этом союзе. Если на C0 есть какая-либо точка, не входящая в это объединение, которая является решением, если C0 полностью покрыта, то P должен находиться на пересечении между двумя другими расширенными окружностями, и он должен находиться в области, которая не покрыта этот союз (т.е. не в расширенном круге ).

Это O (n ^ 2), есть несколько способов улучшить это, хотя, сетка может использоваться, чтобы уменьшить усилие парного поиска, также я думаю, сортируя круги по их близости к O, (расстояние между два круга, уменьшенные по радио), поможет ограничить пространство поиска для поиска покрытия и пересечения

Харальд Шейрих
источник
0

Возможные решения LookUp

  1. Проверьте, является ли белая точка решением самой. Он охватывает случай с 0 красными кружками и тривиальный случай, когда красные круги находятся далеко от белой точки.
  2. Один красный круг.
    1. Белая точка - это центр круга. Возможные решения - бесконечное число точек на окружности, центр которой в белой точке, а радиус равен сумме радиуса синих кругов и диаметра красного круга. Давайте назовем это зеленым кругом .
    2. Белая точка где-то еще. Есть только одно возможное решение на линии, которая соединяет белую точку и центр красного круга, это радиус синего круга от точки, где красный круг пересекает линию к белой точке.
  3. Два или более красных кружка.
    1. Давайте возьмем красные кружочки один за другим и поищем возможные решения для каждого из них индивидуально в соответствии с пунктом 2 (один кружок).
    2. Для каждой пары красных кругов давайте проверим, можно ли нарисовать синий круг, касаясь обоих красных. Т.е. если расстояние между их центрами равно или меньше суммы их радиусов плюс диаметр синего круга. Если вы можете, то у вас есть два (или один, если красные кружки находятся точно на расстоянии одного синего круга) возможных решений .

Поиск актуальных решений среди возможных решений

Теперь у вас есть набор точек, которые являются возможными решениями , переберите их и проверьте для каждого.

  1. Если точка на самом деле является решением. Ни один красный круг не должен иметь центр ближе, чем его радиус к этой точке.
  2. Если он ближе к белой точке, чем решение, найденное ранее.
  3. Если у вас есть зеленый кружок (пункт 2.1)
    • Если среди отдельных точек нет решения, которое принадлежит зеленому кругу, то зеленый круг является ответом.
    • Если у вас есть индивидуальные решения на зеленом круге, и вам нужно какое-то решение, просто возьмите одно из них.
    • Если у вас есть отдельные решения на зеленом круге и вам нужно все неограниченное количество решений, то вам нужно решить еще одну проблему. Вам нужно вырезать из зеленого круга все дуги, определенные парой отдельных решений из каждого красного круга.

NB: я не говорю, что реализация алгоритма должна быть точно описана. Вы можете попытаться улучшить производительность, используя динамическое программирование или пропуская возможные решения, если очевидно, что они не будут работать.

Влад
источник