Un algorithme efficace pour tamponner une polyligne pour créer un polygone?

Question

J'ai besoin d'écrire du code qui tamponnera une ligne pour créer un polygone comme indiqué ci-dessous.

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

de suivre les étapes décrites, je peux créer des formes de polygones autour des lignes simples qui ne se croisent pas ou ont des courbes trop serrées, mais comme les lignes que je suis en train de tampon sont des pistes de l'ouragan squiggly swhirly, ce n'est vraiment pas assez bon.

Je sais qu'il existe une fonction dans SQL Server 2008 qui peut le faire, mais je crains que ce soit actuellement un non.

Quelqu'un peut-il me diriger dans la direction d'un algorithme plus complet que je peux suivre, ou toute information de fond qui pourrait me aider à cela?

Answer 1

Bien que cela s'appelle buffering dans GIS, apparemment les mathématiciens qui travaillent sur des algorithmes l'appellent le Minkowski sum. Googling trouvé this page par l'expert en algorithme Steven Skiena qui lie à plusieurs implémentations d'algorithmes et quelques livres. J'espère que cela t'aides!

L'une des implémentations d'algorithme auxquelles elle est liée en ce moment (mars 09) est CGAL, une bibliothèque C open source.