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

Ответ 1

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

Предложение 1

Я думал о совершенно другом подходе.
Действительно ли требуется разделить фигуру на 2 цифры, чтобы использовать ее в вашей программе САПР? Я ожидаю, что это тоже ОК, если вы можете описать его как одну фигуру в одном цикле (один список точек, образующих многоугольник).
Вам нужно найти линии, которые соединяют разные циклы фигуры и которые полностью находятся внутри фигуры, так что вы можете использовать их для комбинирования петель.

Я бы начал с сравнения пар сегментов разных циклов и поиска сегментов, которые ближе всего друг к другу. Начните сравнивать все сегменты внешнего контура со всеми сегментами всех внутренних петель.
Практически я бы реализовал его, сравнивая точки на внешнем контуре с сегментами внутренних петель и точками на внутреннем контуре с сегментами внешнего контура. И я бы оптимизировал, пропустив вычисления, если расстояние x или y больше, чем самое маленькое пройденное расстояние.
2 сегмента или ближайшая точка и сегмент предоставят вам линию, которая может использоваться для объединения петель (или разбить фигуру): линия из угла одной из них (или точки) перпендикулярна на другой сегмент. Недостатком является то, что вы добавляете новые узлы, но они эффективны и всегда правильны.
Как только вы найдете такую ​​линию, внутренний цикл, который подключен, и новая линия/сегмент могут быть объединены в один модифицированный внешний цикл, который включает новый сегмент дважды, чтобы закрыть новый цикл. Вы можете повторить процедуру, сравнив сегменты этого модифицированного внешнего контура с остальными другими внутренними контурами.
Когда все внутренние петли используются, у вас есть один цикл, описывающий весь рисунок.

Чтобы полностью разделить фигуру на 2 цифры, вам понадобится еще один дополнительный сегмент.
Но я думаю, что цикл, который у нас есть на данный момент, может использоваться в большинстве программ САПР для представления вашей фигуры. Это не нормализованная фигура, потому что она касается себя, но программы CAD обычно не заботятся об этом. Для CAD-программы идеально подходит для представления поверхности фигуры.

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

Комментарий к вашему ответу на предложение 1

У меня еще нет права комментировать ваш ответ, потому что у меня недостаточно кредитов, поэтому я добавлю комментарий к своему собственному ответу.

Я смотрю на ваш пример, который я неправильно истолковал, поэтому я адаптировал этот комментарий.

У вас есть 3 отверстия, поэтому первая часть алгоритма добавит 3 сегмента, которые вы показываете.

И да, у вас явно есть проблема для второй части алгоритма. Вам нужна 4-я строка, но в этом случае нет двух частей, которые разделены всеми тремя добавленными сегментами в обоих направлениях или я не вижу их в любом случае. Я предположил, что всегда будут две части нового цикла, которые будут разделены всеми новыми сегментами. Это предположение неверно, когда есть 3 отверстия или более.

Но я буду думать об этом дальше.

Предложение 2

Теперь я думаю о другом возможном алгоритме.

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

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

• Обнаружение всех пересечений нарисованной линии с отрезками фигуры, чтобы уменьшить линию до набора сегментов, которые полностью находятся внутри фигуры и соединяют различные петли фигуры. Оставьте любой сегмент, который начнет конец в том же цикле.
  Если дыра просто касается только найденных сегментов только в одной точке. Переместите один сегмент в точку того же самого отверстия, ближайшего к этой точке, чтобы избежать попадания фигуры с отверстием, касающимся наружу. Проверьте новые пересечения с измененным сегментом и разбейте их снова, если они найдены.
  Поиск всех пересечений требует сравнения строки, найденной со всеми сегментами фигуры, которая также является большим количеством вычислений, но вы можете пропустить вычисления, проверив, что линия пересекает ограничивающий прямоугольник вокруг сегмента перед вычислением пересечения. Я бы начал с вычисления пересечений с внешним циклом, чтобы как можно скорее создать ограничивающий прямоугольник для оставшейся части строки, потому что это также поможет проверить разделы, которые вам не нужно сравнивать для пересечений.
  Вы также можете оптимизировать, заменив каждый найденный сегмент сегментом, соединяющим самые близкие конечные точки подключенных сегментов (если еще не в точке соединения из двух сегментов). Это позволяет избежать создания дополнительных точек для новых фигур и увеличивает шанс избавиться от большего количества отверстий за один шаг. Но тогда вам нужно будет снова проверить новые пересечения и повторить эту оптимизацию, пока вы не найдете больше пересечений.
  И еще одна возможная оптимизация: проверьте, что точки отверстий, которые еще не были отрезаны, находятся близко к найденным сегментам и разбивают найденный сегмент на 2 сегмента, чтобы поймать это отверстие также на том же шаге. Как и предыдущая оптимизация, это также требует проверки новых пересечений.

• Используйте сегменты, чтобы разделить фигуру на 2 фигуры и повторить с шага 2 для каждой новой фигуры, в которой все еще есть отверстия.

Недостатком является то, что у вас может быть более двух цифр (max (n +1)/2 цифры с n - количество отверстий), но если у вас много отверстий, что приводит к множеству цифр, возможно, рекомбинируйте некоторые из них.

Ответ 2

Я использую этот ответ для визуализации моего комментария к @Stefan Mondelaers:

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

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

Я думаю, что вторая часть вашего алгоритма не работает.

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

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