>>And a buffer for a point would be nothing but a circle.

>Yes, but that's not a polygon. If you take a line
>segment, and you take the set of points that at
>distance d, you get two half circles joined by two
>line segments - not a polygon either.

Interesting. Why is that, may I ask? As far as I can see (and I've been working in the GIS field for about 20 yrs believing it to be so), a circle is indeed a polygon as much as a buffer of line is. Btw, in your description above, the buffer is of a single straight-line segment. Of course, a line can be made of any number of line segments, or arcs. A line is nothing but a series of x,y pairs that don't end up where they started. While a polygon is the same as above except the first and the last pair are the same.

In any case, the problem actually is surprisingly hard. That is because of all the different manners in which a polygon or a line can be configured. One has to determine the inside vs. the outside worlds wrt the polygon (of course, for buffering, one would want to remain on the outside), which can differ based on the slope of that particular line segment and the direction of one's travel (clockwise vs. counter-clockwise). Then there is the thorny issue of vertices, as brought up above.

When all is said and done, it has to be fast.

Now, I know there are algorithms out there... well established, because the solution exists in commercial software. I am simply unable to find references to the darn algorithms in published literature so I can start exploring the possibility of building one as an open source solution.

In reply to Re^2: polygon buffering algorithms by punkish
in thread polygon buffering algorithms by punkish

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.