An effective algorithm for buffering a polyline to

问题:

I need to write some code that will buffer a line to create a polygon as shown below.

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

From following the steps outlined, I can create polygon shapes around simple lines that do not cross themselves or have too tight curves, but as the lines I'm trying to buffer are squiggly swhirly hurricane tracks, it's really not good enough.

I know there's a function in SQL Server 2008 that can do this, but I'm afraid that's currently a no go.

Can anyone point me in the direction of a more complete algorithm I can follow, or any background info that could help me figure this out?

回答1:

Although this is called buffering in GIS, apparently the mathematicians who work on algorithms call it the Minkowski sum. Googling found this page by algorithm expert Steven Skiena that links to several algorithm implementations and some books. Hope this helps!

One of the algorithm implementations it links to right now (March 09) is CGAL, an open source C library.