C ++ 2D библиотека тесселяции?

Question

У меня есть несколько выпуклых многоугольников, сохраненных как вектор точек STL (более или менее). Я хочу тесселяция их очень быстро, желательно на довольно равномерные по размеру части, без "осколков".

Я собираюсь использовать его, чтобы взорвать некоторые объекты на маленькие кусочки. Кто-нибудь знает хорошую библиотеку для тесселяции многоугольников (разбить их на сетку из более мелких выпуклых многоугольников или треугольников)?

Я смотрел на некоторые из них, которые уже нашел в Интернете, но даже не могу заставить их скомпилировать. Эти академические типы не учитывают простоту использования.

Answer 1

CGAL имеет пакеты для решения этой проблемы. Лучше всего будет использовать пакет 2D Polygon Partitioning . Например, вы можете сгенерировать y-монотонное разбиение многоугольника (работает и для невыпуклых многоугольников), и вы получите что-то вроде этого:

Время выполнения O (n log n).

С точки зрения простоты использования это небольшой пример кода, который генерирует случайный многоугольник и разбивает его на части (на основе этого примера руководства ):

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Partition_traits_2<K>                         Traits;
typedef Traits::Point_2                                     Point_2;
typedef Traits::Polygon_2                                   Polygon_2;
typedef std::list<Polygon_2>                                Polygon_list;
typedef CGAL::Creator_uniform_2<int, Point_2>               Creator;
typedef CGAL::Random_points_in_square_2<Point_2, Creator>   Point_generator;   


int main( )
{
   Polygon_2    polygon;
   Polygon_list partition_polys;

   CGAL::random_polygon_2(50, std::back_inserter(polygon),
                      Point_generator(100));

   CGAL::y_monotone_partition_2(polygon.vertices_begin(),
                                polygon.vertices_end(),
                                std::back_inserter(partition_polys));

   // at this point partition_polys contains the partition of the input polygons
   return 0;
}

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

Answer 2

poly2tri выглядит как действительно хорошая легкая библиотека C ++ для 2D триангуляции Делоне.

Answer 3

Как упомянуто в комментарии выше в balint.miklos, пакет triangle Шевчука довольно хорош. Я сам использовал это много раз; он хорошо интегрируется в проекты и имеет интерфейс triangle ++ C ++. Если вы хотите избежать осколков, то разрешите треугольнику добавлять (внутренние) точки Штейнера, чтобы создать качественную сетку (обычно ограниченную соответствующую триангуляцию Делоне).

Answer 4

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

Края вороной являются пунктирными линиями на этом рисунке и являются своего рода дополнением триангуляции Делоне. Все точки острого треугольника притупляются:

Boost имеет некоторую функциональность voronoi: http://www.boost.org/doc/libs/1_55_0/libs/polygon/doc/voronoi_basic_tutorial.htm

Следующий шаг - создание многоугольников вороной. Voro ++ http://math.lbl.gov/voro++/ ориентирован на 3D, но в других местах предполагается, что примерно 2d структура будет работать, но будет намного медленнее, чем программное обеспечение, ориентированное на 2D вороной. Другой пакет, который выглядит намного лучше, чем случайный проект для сирот на домашней странице, - https://github.com/aewallin/openvoronoi.

Похоже, OpenCV, используемый для поддержки, делает что-то в этом направлении, но это устарело (но c-api все еще работает?). cv :: distTransform по-прежнему поддерживается, но работает с пикселями и генерирует пиксельные выходные данные, а не вершины и структуры данных краевых многоугольников, но может быть достаточным для моих нужд, если не для вас.

Я обновлю это, как только узнаю больше.

Answer 5

Если вы не хотите встраивать весь GCAL в свое приложение - возможно, это проще реализовать.

http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml

Answer 6

Если у вас выпуклые многоугольники, и вы не слишком зациклены на качестве, то это действительно просто - просто сделайте стрижку ушей . Не волнуйтесь, это не O (n ^ 2) для выпуклых многоугольников. Если вы будете делать это наивно (то есть вы будете обрезать уши, когда найдете их), тогда вы получите треугольный веер, который немного затягивает, если вы пытаетесь избежать осколков. Две тривиальные эвристики, которые могут улучшить триангуляцию:

1. Сортировка ушей, или если это слишком медленно
2. Выберите ухо наугад.

Если вам нужен более надежный триангулятор, основанный на стрижке ушей, проверьте FIST .

Answer 7

Немного больше информации о желаемом входе и выходе может быть полезным.

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

---

Хорошо, я сделал неверное предположение - я предполагал, что марширующие квадраты будут больше похожи на марширующие кубы. Оказывается, это совсем другое, и совсем не то, что я имел в виду ..: |

В любом случае, чтобы прямо ответить на ваш вопрос, я не знаю ни одной простой библиотеки, которая делает то, что вы ищете. Я согласен с юзабилити CGAL. ​​

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

С другой стороны, вы могли бы сделать подразделение в стиле кошачьего кларка, но пропустить сглаживание. Алгоритм в основном заключается в добавлении точки в центр тяжести и в середину каждого ребра. Затем для каждого угла исходного многоугольника вы создаете новый меньший многоугольник, который соединяет среднюю точку ребра, предшествующую углу, углу, средней точке следующего ребра и центроиду. Это мозаичное пространство, и у него будут углы, похожие на ваш входной многоугольник.

Итак, множество вариантов, и мне нравятся мозговые штурмы, но я до сих пор не знаю, для чего вы планируете использовать это. Это для создания разрушаемых сеток? Вы делаете какую-то обработку сетки, которая требует меньших элементов? Пытаетесь избежать артефактов затенения Гуро? Это что-то, что работает как предварительный процесс или в реальном времени? Насколько важна точность? Чем больше информации, тем лучше предложения.