Составление списка крайних кругов на плоскости

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

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

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

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


person shal    schedule 06.01.2021    source источник
comment
у вас есть списки центральных точек и диаметров для приведенных выше примеров, а также для результатов, это поможет тем, кто хочет попробовать какой-то код.   -  person Paddy3118    schedule 06.01.2021
comment
Да, это массив {x,y}, все диаметры одинаковы. Но это можно сделать на любом языке, так что вы хотите, чтобы я подготовил, сниппет на js?   -  person shal    schedule 06.01.2021
comment
Я программист Python, но список JSON был бы в порядке.   -  person Paddy3118    schedule 06.01.2021


Ответы (2)


Это, возможно, слишком консервативно, но, конечно, никакие диски не будут выпущены.

  1. Вычислите триангуляцию Делоне в центрах окружностей. Лучше всего использовать высококачественную библиотеку, потому что вырожденные случаи и тесты с плавающей запятой сложно сделать правильно.

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

  3. Все точки, инцидентные этим граням, соответствуют внешним дискам.

person David Eisenstat    schedule 06.01.2021
comment
О, да! Это сработало! Отличное решение, большое спасибо! - person shal; 08.01.2021
comment
@shal Я немного изменил алгоритм, чтобы избежать странных особых случаев, связанных с изменением плоского графа. - person David Eisenstat; 08.01.2021

Я не совсем уверен, что у меня есть ответ на ваш вопрос, но я собрал два быстрых примера, используя Tinfour Библиотека триангуляции Делоне (написана на Java). Мне пришлось оцифровывать ваши точки вручную, поэтому я не всегда попадал в центр.

На первом рисунке показано, что граница триангуляции Делоне представляет собой выпуклый многоугольник. Это легко построить, просто добавьте вершины (центры кругов) в класс Tinfour IncrementalTin, а затем запросите у него ограничивающий многоугольник. Практически любая библиотека Делоне поддерживает это. Так что вам не обязательно нужен Tinfour.

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

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

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

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

person Gary Lucas    schedule 08.01.2021
comment
Спасибо, я реализовал аналогичный подход в TypeScript, основываясь на рекомендации Дэвида Эйзенстата выше. - person shal; 12.01.2021