Эффективный алгоритм буферизации полилинии для создания многоугольника?

Question

Мне нужно написать некоторый код, который буферизует строку для создания многоугольника, как показано ниже.

http://www.sli.unimelb.edu.au/gisweb/BuffersModule/Buff_line.htm

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

Я знаю, что в SQL Server 2008 есть функция, которая может это делать, но я боюсь, что в настоящее время это не пойдет.

Может ли кто-нибудь указать мне направление более полного алгоритма, которым я могу следовать, или какую-либо справочную информацию, которая может помочь мне понять это?

Answer 1

Хотя в ГИС это называется буферизацией , очевидно, математики, работающие над алгоритмами, называют это суммой Минковского . Поиск в Google обнаружил эксперт по алгоритму Стивен Скиена, который ссылается на несколько реализаций алгоритма и некоторые книги. Надеюсь это поможет!

Одной из реализаций алгоритма, на которую он ссылается прямо сейчас (09 марта), является CGAL , библиотека C с открытым исходным кодом.