Каким будет алгоритм проверки того, что круг, подобный синему внизу, ПОЛНОСТЬЮ содержится в области других кругов (круговые круги). Я хочу TRUE для синего круга и FALSE для красного кругаАлгоритм проверки того, полностью ли окружен круг в области других кругов.
Вход для всех кругов - их координаты и их радиус.
Это кажется простым (EDIT: а не является): если каждая точка каждой дуги данной окружности содержится, по меньшей мере, одной из других кругов, то весь круг содержится. Затем вам нужно будет найти все пересечения (algorithm to detect if a Circles intersect with any other circle in the same plane) и выполнить проверку для всех дуг, заданных этими пересечениями. Если какая-либо «внутренняя» точка дуги A1-A2 круга A для заданных двух пересечений с кругом B (дуга B1-B2, где точки A1 = B1 и A2 = B2) содержится в круге B, то вся дуга содержащихся в круге B и наоборот. Пожалуйста, поправьте меня, если я ошибаюсь.
EDIT: Хорошо, я уже знаю, что я ошибался, как показала maxim1000. Это сложнее, чем я думал. Я думаю о том, чтобы добавить что-то к моему ответу, но я не уверен, является ли это решением. Я надеюсь, что это поможет. А именно: я думаю об определении общей площади пересечений между нашим кругом и другими. Мы находим все разделенные пересечения внутри нашего круга - все части, которые содержат те же точки, которые разделены всеми пересекающимися дугами, - и находят их области. Ву суммируйте их. Если он равен площади нашего круга, то наш круг содержится в других кругах. Определение этой области может быть проблемой само по себе, но, как я уже сказал, это может привести к правильному направлению. Дайте мне подумать тоже ..
EDIT: Через некоторое время мышления. Определение всех областей в (нескольких) пересекающихся кругах - это просто вопрос добавления или вычитания треугольников или ... хм ... как их называть? ... желтые части, как здесь на картинке :)
Я не думаю, что есть простое решение.
Я хотел бы обратиться к этому, взяв каждый круг по очереди и выполняя логическое вычитание всех других кругов. (Круги, которые достаточно далеко - R0 + R1 < D12 - не будут мешать.)
После того, как куски были съедены, круг становится криволинейным многоугольником из круговых дуг или множеством таких полигонов, быть сломанным. Многоугольник может быть представлен списком кругов, которые вносят дугу его контура, а конечные точки дуг определяются общим пересечением двух последовательных соседей или окружности цели и соседа. Обратите внимание, что один и тот же сосед может появляться несколько раз.
Чтобы сделать вещи немного больше, полигоны могут иметь отверстия, которые вам также необходимо представлять.
Тогда важной операцией является вычитание круга из криволинейного многоугольника. Вам нужно обнаружить дуги, которые полностью находятся внутри нового круга, и те, которые пересекают его. После получения оставшихся частей дуг вам необходимо перестроить оставшиеся дуги и новые (ы).
Я думаю, что все эти операции могут быть построены из одного примитива, который находит часть дуги (определяемую тремя кругами), которая находится внутри диска.
Вот неочищенный раствор:
Для каждого края отслеживайте созданный круг.
Для каждого ограничивающего ребра Е каждой области R вы найдете, возьмите окружность С, что Е принадлежит. Если С не T (красный) - то есть Е-синий, проверьте точки на других кромках R находятся внутри C:
в приведенной выше схеме, С содержит B, поэтому R покрыта; но C не содержит, так что не покрывает S
Боковые случаи:
Этот алгоритм высоко неэффективна, и я не уверен на 100%, если есть какие-либо более вырожденные случаи; если у кого есть какие-либо предложения, пожалуйста, дайте мне знать.
Рассмотрите большой круг, и его граница полностью покрыта небольшими кругами. Центр большого круга определенно не будет покрыт небольшими кругами. И если я правильно понимаю вопрос, это касается кругов с их интерьером. – maxim1000
Правильно. Белые круги соответствуют области, а другой круг может перекрывать эту область или ее часть. Это то, что мне нужно проверить. – oscarm
Да, вы правы! Хорошая точка зрения. Голосуйте! : D – forestgril