Ниже приведен пример изображения, если у меня есть точка белой точки в середине, и я хочу найти ближайшее возможное местоположение для синего круга (который, очевидно, находится в том месте, где я его поместил), если все красные круги уже существуют , Как я могу найти это место?
Производительность для меня не является серьезной проблемой для этого приложения.
design
design-patterns
algorithms
performance
geometry
Ботанический
источник
источник
Ответы:
Это не общее решение, так как есть несколько ситуаций, когда оно не обеспечит положение синего круга с кратчайшим расстоянием до белой точки. Например, если у вас есть 100 красных шаров, сгруппированных вместе, и белая точка находится далеко от этой группы красных шаров, то ни один из красных шаров не будет иметь никакого влияния на положение синего круга, который может быть центрирован на белой точке. , Также он не покажет все детали расчетов. В любом случае, для подмножества конфигураций, где решение (синий круг) касается двух красных кругов, должно работать следующее:
1) пусть R - радиус синего круга
2) сделать цикл по всей паре красных кругов, да Я знаю, что это O (n2).
3) для каждой пары окружностей i, j с центрами в (xi, yi) и (xj, yj) с соответствующими радиусами ri и rj вычислите квадрат расстояния между парой окружностей
4) поставить все пары окружностей, которые
в список.
5) пройти список, найдя 2 решения окружностей радиуса R, касающихся обеих окружностей i и j. Для этого используйте эти уравнения вместе с этим изображением
с помощью вышеуказанной информации вы можете найти (X1ij, Y1ij) и (X2ij, Y2ij) центры 2 окружностей, касающихся окружностей i и j. Для каждого кандидата синий круг обведите все красные кружки и посмотрите, не перекрываются ли они. Если они действительно сбросят это, если нет, проверьте расстояние до белого круга. Если вы оставите тот с меньшим расстоянием, думаю, у вас будет решение, когда вы закончите обход списка пар окружностей. Алгоритм выглядит как O (n3).
источник
Ближайшее размещение к точке будет либо в точке, либо касанием круга.
поэтому сначала проверьте точку, а затем обведите новый круг по краю каждого существующего круга, рассчитав расстояние от точки и, если вы перекрывались, и отслеживая точку минимального расстояния. Остановитесь, когда пройдете каждый круг.
то есть. отметьте все точки на зеленых линиях плюс белый кружок. где зеленая линия представляет собой круг с радиусом красного плюс синий
вам нужно проверить всю зеленую линию, а не только пересечения, чтобы охватить эти крайние случаи.
Очевидно, что размер шага вашего обхода будет важен с точки зрения производительности. Но поскольку вы заявляете, что производительность не является проблемой, выберите значение, соответствующее разрешению вашего выходного значения. то есть плавать, долго?
уточнение:
Мое предложение состоит в том, чтобы перебрать все точки вокруг каждого круга, проверяя их на совпадение со всеми остальными кругами в каждой точке. нет хитрости
Если в примере на картинке указано количество кругов и разрешение, это не должно быть проблемой для стандартного ПК.
у нас есть 20 кругов среднего радиуса 200, так что примерно 20 * 2 π * 200 точек * 20 испытаний на пересечение = 4800000 итераций
Замечания:
Подобные итеративные подходы несовершенны тем, что размер шага, в данном случае разрешение вашего вывода, может сильно повлиять на результат.
Скажем, у меня есть два красных круга на расстоянии 2 пикселя и синий круг с радиусом 1 пиксель, чтобы сжать их между собой. Очевидно, что с любым из двух пикселей в качестве центра синего круга он будет перекрывать один из красных. но очевидно, что есть место для круга, если центр находится между двумя пикселями.
Отсюда мой комментарий с вопросом о разрешении вывода. который вы сказали, может быть что угодно.
Вы также можете решить уравнение одновременности для каждой пары окружностей, радиус которых увеличивается на радиус синего круга.
это даст вам точки, где синий круг будет касаться обоих красных кругов более точно, чем итерация.
Тем не мение. Есть несколько условий, когда, если вы только сделаете это, вы получите неправильный ответ или не получите ответа. то есть.
1 или нет кругов
2 или более кругов, но с заданной точкой далеко и за их пределами.
много кругов, но с целевой точкой близко к поверхности
источник
Этот план содержит рабочий код,
концепция
Даны кружки C1, C2 .... Cn
и координаты окружности Cn - это Cnx, Cny и радиус - это Cr
и радиус необходимого круга R
если синий круг находится в положении X, Y и если он не конфликтует ни с какими другими кругами, следующие уравнения верны
меняя первое уравнение,
так что уравнения можно переписать как,
Реализация
начать с координаты белой точки (Xw, Yw),
первой найденной координатой, удовлетворяющей всем уравнениям, является местоположение синего круга
источник
расширенный круг является одним из кругов с радиусом, расширенным на r
Есть некоторая дополнительная работа, если O не находится в центре круга. Итак, прямо сейчас предположим, O == C0
Вычислите все пересечения всех окружностей с C0, используя их соответствующие радиусы плюс r , т.е. пересекайте протяженные окружности с расширенным C0. Если пересечений нет, то точка, которую вы ищете, находится где-нибудь на C0, если есть пересечения, для каждого пересечения проверьте, находится ли она внутри другого расширенного круга (вы можете ограничиться кругами, которые имели пересечения с C0). Возьмите первое пересечение, которое не находится в другом расширенном круге как P, могут быть другие.
Если между расширенными окружностями и C0 нет пересечений, которые не находятся внутри другого расширенного круга, вычислите пересечения всех расширенных кругов друг с другом. Затем проверьте эти пересечения в порядке расстояния до O, снова, если любое из пересечений находится в пределах другого расширенного круга, если да, отбросьте, если нет, это ваш результат.
Если вы предполагаете, что представите, что обведите все круги, которые указывают на возможное местоположение вашего синего круга, объединение всех расширенных кругов укажет область, которой ваш синий круг не может быть. Точка, которую вы ищете, является ближайшей точкой, которой нет в этом союзе. Если на C0 есть какая-либо точка, не входящая в это объединение, которая является решением, если C0 полностью покрыта, то P должен находиться на пересечении между двумя другими расширенными окружностями, и он должен находиться в области, которая не покрыта этот союз (т.е. не в расширенном круге ).
Это O (n ^ 2), есть несколько способов улучшить это, хотя, сетка может использоваться, чтобы уменьшить усилие парного поиска, также я думаю, сортируя круги по их близости к O, (расстояние между два круга, уменьшенные по радио), поможет ограничить пространство поиска для поиска покрытия и пересечения
источник
Возможные решения LookUp
Поиск актуальных решений среди возможных решений
Теперь у вас есть набор точек, которые являются возможными решениями , переберите их и проверьте для каждого.
NB: я не говорю, что реализация алгоритма должна быть точно описана. Вы можете попытаться улучшить производительность, используя динамическое программирование или пропуская возможные решения, если очевидно, что они не будут работать.
источник