Нечёткие (fuzzy) операции над полигонами. Посоветуйте либу.

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

• PolyBoolean
• Boolean
• Computational Geometry Algorithms Library (CGAL)
• Clippoly
• Generic Polygon Clipper (GPC)
• LEDA
• Clipper (очень быстрая и активно разрабатываемая, вроде как)
• Boost.Geometry AKA Generic Geometry Library (GGL)
• Java Topology Suite (JTS)
• Geometry Engine - Open Source (GEOS) (порт JTL на C++)
• TerraLib
• Wykobi

Вот найденные тесты и сравнения:

• http://www.angusj.com/delphi/clipper.php#features
• http://www.complex-a5.ru/polyboolean/comp.html
• http://svn.osgeo.org/osgeo/foss4g/benchmarking/geometry_libraries/README.txt (я, правда, не вдуплил, где там результаты)

Прочая информация:

• http://en.wikipedia.org/wiki/Boolean_operations_on_polygons
• http://barendgehrels.blogspot.com/search/label/boolean%20operations

Вот ещё вроде бы как что-то прямо по теме (насчёт чисел с плавающих запятой и геометрии): http://barendgehrels.blogspot.com/2011/01/precision-cause-of-spikes.html

Сейчас башка не варит и не осиляю, надо поспать.

Алсо, Boost.Geometry это очень перпективная и хорошая либа, с которой удобно работать вкупе с Qt: http://geometrylibrary.geodan.nl/x01__qt__example_8cpp-example.html

И, в завершение, интересное сообщение о GGL vs Clipper

Right now we have already yet another implementation of polygon clipping accepted to boost as part of the new Boost.Geometry (formerly GGL) library that is not numerically robust, and not algorithmically optimal. However, it has much better chances than an optimal Vatti sweepline implementation of successfully producing an output because sweepline is a somewhat tempermental algorithm and numerical errors are often fatal conditions, whereas the Boost.Geometry algorithm tolerates them better. My expectation is that for large cases your implementation should be faster than the Boost.Geometry algorithm, but more likely to fail due to numerical errors. Your algorithm could find a home in boost itself as a «strategy» for polygon clipping that can be passed into the Boost.Geometry generic interface. If that interests you I suggest you join the Boost.Geometry project and mailing list and pursue contributing your code. I expect that your participation would be welcomed by the other member of the project, certainly I welcome it. It is possible to make a floating point implementation of Vatti, such as yours, numerically robust and that is something we could pursue as a community in the Boost.Geometry project.

+ http://lists.boost.org/boost-users/2010/08/61287.php

Clipper быстрее GPC. GPL быстрее Boost.Geomtry.

Правда, мне скорость не важна. Но, между прочим, проекту Clipper и года нету, он появился где-то в прошлом марте-апреле.

>«Смазанные» (fuzzy)

Нечёткие. Т.е. на основе нечётких множеств.

Спасибо за перевод термина. А я мучился. Хотя не догадался в engcom посмотреть, ведь там:

неточный; нечёткий; в po-файлах переводов системы gettext применяется для обозначения переводов возможно не соответствующих оригинальному предложению;

Clipper fuzzy логику не поддерживает: https://sourceforge.net/projects/polyclipping/forums/forum/1148419/topic/4101283

При чем здесь нечеткие операции вообще? Если я сравниваю числа с плавающей точкой через fabs(a-b) < EPS, я что, уже работаю в рамках нечеткой логики?

> Если я сравниваю числа с плавающей точкой через fabs(a-b) < EPS, я что, уже работаю в рамках нечеткой логики?

Нечёткая логика здесь не при чём. fabs(a-b) < EPS принято называть fuzzy compare, вот я и применил данный термин.

вот, например — http://tcllib.sourceforge.net/doc/fuzzy.html

или qFuzzyCompare в кьюте.