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

Question

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

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

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

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

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

Answer 1

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

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