Ищу библиотеку Polygon Geometry с конкретными возможностями

Question

Я делаю обзор библиотек полигональных / геометрических алгоритмов, реализованных в Objective C, C или C ++ (в таком порядке предпочтений).У меня есть очень специфические потребности, поэтому я решил попросить сообщество выяснить, знает ли кто-нибудь тот, который соответствует некоторым или всем из них, так как я бы предпочел использовать одну библиотеку / API для всех своих нужд.Это то, что мне нужно сделать:

1. Пересечение 2 полигонов
2. Определить, являются ли два полигона конгруэнтными (т.е. одинаковой формы и размера, хотя они могут вращаться или зеркально отображаться))
3. 2-мерная упаковка в бункер выпуклых многоугольников (так называемая резка листов - или упаковка в бункер с открытым концом, поэтому я максимально использую полосу материала фиксированной ширины)
4. То же, что # 3но для вогнутых многоугольников
5. Возможность взять набор отрезков, некоторые из которых имеют общие конечные точки, а некоторые пересекают друг друга и превратить его в набор многоугольников
6. То же, что и # 5но с добавленной способностью обнаруживать многоугольники с отверстиями и разбивать их на 2 многоугольника (по крайней мере один из которых будет вогнутым)
7. Бонус: любое или все из перечисленных выше с замкнутыми формами, состоящими из линий и кривых

Они расположены в порядке приоритета, и я могу обойти их отсутствие (мое приложение просто становится менее полезным).так, например, если бы у меня была библиотека, которая делала только 1 и 2, я бы нашла это более полезной, чем библиотека, которая делала 3-7.

Answer 1

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

Очень полезная библиотека, которую я знаю на C ++: CGAL . Он покрывает некоторые ваши потребности, но не все.

Answer 2

Некоторые вещи, которые вам нужны, охватываются GEOS .

Пространственные отношения между геометриями (пересекаются, касаются, перекрываются, находятся внутри, содержат и т. Д.), Реализованы GEOS довольно хорошо.

Я не знаю, встроены ли 3-7 (вы можете объединить строки (5)).

Что касается 7, GEOS не моделируеткривые (только точки, которые образуют линии или многоугольники).Единственные замкнутые фигуры, которые вы можете определить в GEOS, - это многоугольники.