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

StackOverflow https://stackoverflow.com/questions/1418831

Вопрос

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

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

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

Это было полезно?

Решение

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

y-monoyone-partitioning у-monoyone-разбиение

Время выполнения равно 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 очень полезен для ответов на вопросы ...

Другие советы

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

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

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

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

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

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

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

Boost имеет некоторую функциональность вороной: http://www.boost.org/doc/ ЛИЭС / 1_55_0 / ЛИЭС / многоугольник / док / voronoi_basic_tutorial.htm

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

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

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

Может быть полезно немного подробнее о желаемом вводе и выводе.

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

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

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

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

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

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

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

<Ол>
  • Сортируйте уши, или если это слишком медленно
  • Выберите ухо наугад.

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

    Лицензировано под: CC-BY-SA с атрибуция
    Не связан с StackOverflow
    scroll top