Учитывая список многоугольников, построить Полигон с отверстиями - PullRequest
Новая
       3

Учитывая список многоугольников, построить Полигон с отверстиями

0 голосов
/ 17 января 2011

Для многоугольника, очки даются против часовой стрелки.Для лунок, точки приведены по часовой стрелке.Итак, учитывая список многоугольников, как построить весь многоугольник с отверстиями?

Вот несколько предварительных условий для списка многоугольников:

  1. Один многоугольник может содержать несколько отверстий, ноотверстие должно содержаться внутри многоугольника.
  2. отверстие не может содержать один или несколько многоугольников.
  3. Все отверстия должны быть расположены внутри многоугольника, а не вне его
  4. Отверстия отверстияребро может касаться многоугольников.
  5. И все многоугольники и отверстия не должны пересекаться с другими многоугольниками / отверстиями, хотя они могут касаться друг друга.
  6. Многоугольник / отверстие могут быть либо выпуклыми или вогнутый.

Как разработать алгоритм, который строит многоугольники с отверстиями?

Я ищу общий алгоритм, поэтому приветствуется любой код в виде C #, C ++ и matlab.

Редактировать: это мой ввод (в C #) 

public class PolygonWithHoles
{
   public List<Point> OuterBoundary;
   public List<List<Point>> Holes;
}


//input: a list of point list. If the point list constructs a polygon in Counter clock wise, then it is a general polygon, else it is a holes
public List<PolygonWithHoles> ConstuctPolyHoles(List<List<Point>> Polys)
{
}

1 Ответ

2 голосов
/ 18 января 2011

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

Более надежный подход должен основываться на алгоритме линии сканирования, где вершины сначала сортируются в соответствии с их значениями x и y.Линия сканирования (или развертки) затем перемещается, например.слева направо.Затем алгоритм обычно поддерживает список линий, пересекающих линию сканирования, добавляя строку, когда ее левая вершина «попадает» на строку сканирования, и удаляя ее, когда ее правая вершина достигает линии.

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

После нахождения всех пересечений можно надежно идентифицировать контуры и отверстия.

Этот подход используется в следующих проектах:

Существуют другие, и на следующем сайте (который продвигает библиотеку PolyBoolean) сравниваются наиболее важные из них: http://www.complex -a5.ru / polyboolean / comp.html .

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

Удачи!

...