<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>Message</TITLE>
<META http-equiv=Content-Type content="text/html; charset=us-ascii">
<META content="MSHTML 6.00.2800.1276" name=GENERATOR></HEAD>
<BODY text=#000000 bgColor=#ffffff>
<DIV><SPAN class=978593917-16032004><FONT face=Arial color=#0000ff
size=2>Alex:</FONT></SPAN></DIV>
<DIV><SPAN class=978593917-16032004></SPAN> </DIV>
<DIV><SPAN class=978593917-16032004><FONT face=Arial color=#0000ff size=2>From
your original post, it sounds like you are buffering fairly "twisty" linestrings
(e.g. rivers of Europe). The way buffering works is this
(roughly): The offset curve is computed as a series of offsets from
the line segments of the linestring together with rounded "fillets" for the
sharp corners. If the linestring winds about a bit, the offset curve
starts self-intersecting (and the wider the buffer width, the more
self-intersections occur). The complex part of buffering is handling these
self-intersections, by discarding the pieces of the offset curve that lie inside
the buffer. This code runs more or less proportionally to the number of
self-intersections. </FONT></SPAN></DIV>
<DIV><SPAN class=978593917-16032004><FONT face=Arial color=#0000ff
size=2></FONT></SPAN> </DIV>
<DIV><SPAN class=978593917-16032004><FONT face=Arial color=#0000ff
size=2>It's more complex than that in reality, but basically the "windier"
the buffer the longer it will take to compute.</FONT></SPAN></DIV>
<DIV><SPAN class=978593917-16032004><FONT face=Arial color=#0000ff
size=2></FONT></SPAN> </DIV>
<DIV><SPAN class=978593917-16032004><FONT face=Arial color=#0000ff
size=2>Martin</FONT></SPAN></DIV>
<DIV> </DIV>
<DIV> </DIV>
<DIV align=center><FONT face=Arial size=2>Martin Davis, Senior Technical
Architect<BR><STRONG><FONT color=#0000ff>Vivid Solutions
Inc.</FONT></STRONG><BR><EM>Suite #1A-2328 Government Street Victoria, B.C. V8T
5G5<BR>Phone: (250) 385 6040 - Local 308 Fax: (250) 385 6046</EM></FONT></DIV>
<BLOCKQUOTE dir=ltr
style="PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #0000ff 2px solid; MARGIN-RIGHT: 0px">
<DIV></DIV>
<DIV class=OutlookMessageHeader lang=en-us dir=ltr align=left><FONT
face=Tahoma size=2>-----Original Message-----<BR><B>From:</B> Alexander Pucher
[mailto:pucher@atlas.gis.univie.ac.at] <BR><B>Sent:</B> March 16, 2004 5:17
AM<BR><B>To:</B> PostGIS Users Discussion<BR><B>Subject:</B> Re:
[postgis-users] Buffer Performance<BR><BR></FONT></DIV><FONT
face="Helvetica, Arial, sans-serif">Hi all,<BR><BR>Martin, sounds clear to me,
but what's the deal with the intersection? >From my experience, when I
buffer 50 line segments, I get 50 buffers (i.e 50 "rows"). So no intersection
is made between the several buffers, as far as I can see. Please correct me if
I'm wrong.<BR><BR>reagrds,<BR>alex.<BR></FONT><BR>Martin Davis wrote:
<BLOCKQUOTE
cite=mid5A94289A9268514C8D6C0F1FF44BA0274F4F4E@venus.VividSolutions.com
type="cite">
<META content="MSHTML 6.00.2800.1276" name=GENERATOR>
<DIV><SPAN class=204313117-12032004><FONT face=Arial color=#0000ff
size=2>The performance difference is probably due to the difference in the
buffer widths. In general, larger buffer widths require longer to
compute than smaller ones. This is due to the greater interaction
(intersections) between the offset curves computed to build the buffer
curve.</FONT></SPAN></DIV>
<DIV> </DIV>
<DIV> </DIV>
<DIV align=center><FONT face=Arial size=2>Martin Davis, Senior Technical
Architect<BR><STRONG><FONT color=#0000ff>Vivid Solutions
Inc.</FONT></STRONG><BR><EM>Suite #1A-2328 Government Street Victoria, B.C.
V8T 5G5<BR>Phone: (250) 385 6040 - Local 308 Fax: (250) 385
6046</EM></FONT></DIV>
<BLOCKQUOTE
style="PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: rgb(0,0,255) 2px solid; MARGIN-RIGHT: 0px">
<DIV class=OutlookMessageHeader lang=en-us dir=ltr align=left><FONT
face=Tahoma size=2>-----Original Message-----<BR><B>From:</B> Alexander
Pucher [<A class=moz-txt-link-freetext
href="mailto:pucher@atlas.gis.univie.ac.at">mailto:pucher@atlas.gis.univie.ac.at</A>]
<BR><B>Sent:</B> Friday, March 12, 2004 3:39 AM<BR><B>To:</B> PostGIS
Users Discussion<BR><B>Subject:</B> [postgis-users] Buffer
Performance<BR><BR></FONT></DIV><FONT
face="Helvetica, Arial, sans-serif">Hi,<BR><BR>did some buffer performance
testing with a table that holds about 2100 multilinestrings (river network
of europe).<BR><BR>'select buffer(the_geom,5) from river;'<BR><BR>takes
about 7 seconds to execute, whereas<BR></FONT><FONT
face="Helvetica, Arial, sans-serif"><BR>'select buffer(the_geom,15000)
from river' <BR><BR>takes a couple of minutes...<BR><BR>The 'river' table
is not indexed, if this might be of importance ?!?<BR><BR>'explain
select....' <BR><BR>shows similar output for both queries:<BR><BR>QUERY
PLAN<BR>-----------------------------------------------------------<BR> Seq
Scan on river (cost=0.00..139.51 rows=2051 width=32)<BR>(1
row)<BR><BR><BR>What's the reason for the difference in execution time,
depending on the buffer size?<BR>Is there a way to speed up </FONT><FONT
face="Helvetica, Arial, sans-serif">execution time of </FONT><FONT
face="Helvetica, Arial, sans-serif">such queries??<BR><BR>Best
regards,<BR>alex.<BR></FONT><FONT
face="Helvetica, Arial, sans-serif"><BR></FONT></BLOCKQUOTE><PRE wrap=""><HR width="90%" SIZE=4>
_______________________________________________
postgis-users mailing list
<A class=moz-txt-link-abbreviated href="mailto:postgis-users@postgis.refractions.net">postgis-users@postgis.refractions.net</A>
<A class=moz-txt-link-freetext href="http://postgis.refractions.net/mailman/listinfo/postgis-users">http://postgis.refractions.net/mailman/listinfo/postgis-users</A>
</PRE></BLOCKQUOTE></BLOCKQUOTE></BODY></HTML>