Quantcast

Buffer operation performance

classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Buffer operation performance

michaelm-2
Hi,

I noticed that OpenJUMP Buffer plugin performance decreases dramatically
if a large buffer size is used :
For a map with  rivers having vertices every few meters, I get :

buffer =  25 m :     7 s
buffer =  50 m :    16 s
buffer = 100 m :    48 s
buffer = 200 m : 2m 59 s

The plugin uses the BufferOp class. I have no idea why a large buffer
should take longer than a small one, and I don't know if there is a
better way to compute a buffer.

Any idea ?

Michaël

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Buffer operation performance

Paul Ramsey
Simplify your geometry before buffering. The larger the buffer
distance, the less effect the internal vertices have on the final
geometry, and the more aggressively you can simplify.

P.

On Thu, Jul 24, 2008 at 2:18 PM, Michael Michaud
<[hidden email]> wrote:

> Hi,
>
> I noticed that OpenJUMP Buffer plugin performance decreases dramatically if
> a large buffer size is used :
> For a map with  rivers having vertices every few meters, I get :
>
> buffer =  25 m :     7 s
> buffer =  50 m :    16 s
> buffer = 100 m :    48 s
> buffer = 200 m : 2m 59 s
>
> The plugin uses the BufferOp class. I have no idea why a large buffer should
> take longer than a small one, and I don't know if there is a better way to
> compute a buffer.
>
> Any idea ?
>
> Michaël
>
> _______________________________________________
> jts-devel mailing list
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
>
_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Buffer operation performance

Martin Davis
In reply to this post by michaelm-2
The reason for this is that as the buffer size gets bigger, the "raw
offset curve" that is initially created prior to extracting the buffer
outline gets more and more complex.  Concave angles in the input
geometry result in perpendicular "closing lines" being created, which
usually intersect other offset lines.  The longer the perpendicular
line, the more other lines it intersects, and hence the more noding and
topology analysis has to be performed.  (I haven't found any good way of
building the raw offset curve to avoid or reduce this problem - if
anyone has any ideas I'd be interested to hear them).

There's several ways that I've tried to reduce this problem:

- compute the buffer in a series of steps, using an increasing series of
buffer distances which add up to the desired distance.  Each successive
buffer gets smoother, which makes the subsequent buffers run faster.  It
may only be necessary to iterate say 3 times to get a good result.  The
trick of course is to pick the right distances.

- simplify the input geometry using DP, and a tolerance of say 2% of the
buffer distance

- A better way of simplifying I've been experimenting with only
simplifies *outwards*.  This does 2 things - it reduces concavity (which
is the source of the problem), and it avoid "losing" convex protrubances
(which DP can often delete or alter).  Convex protrubances are the
primary influence on the shape of the resulting buffer, so it is
important to preserve them.  (Currently this code is in alpha only - but
I can provide it if anyone's interested)

Martin

Michael Michaud wrote:

> Hi,
>
> I noticed that OpenJUMP Buffer plugin performance decreases
> dramatically if a large buffer size is used :
> For a map with  rivers having vertices every few meters, I get :
>
> buffer =  25 m :     7 s
> buffer =  50 m :    16 s
> buffer = 100 m :    48 s
> buffer = 200 m : 2m 59 s
>
> The plugin uses the BufferOp class. I have no idea why a large buffer
> should take longer than a small one, and I don't know if there is a
> better way to compute a buffer.
>
> Any idea ?
>
> Michaël
>
> _______________________________________________
> jts-devel mailing list
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
>

--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Buffer operation performance

michaelm-2
Hi Martin,

Thanks for the precise answer.
I do not know a good buffer algorithm but I made some further tests
which show there is place for improvements with the excellent stuff you
recently added.

I created a simple linestring : length = 25000 m, number of segments = 1000

Trying to create a buffer at a distance of 10000 m ended with a
heapspace exception (took more than 256 Mo !) after more than 4 mn of
intensive computation !

The other way is :
- decompose into segments : less than 1 s
- create individual buffers : openjump says 8 s but I think it includes
redrawing
- cascaded union of resulting buffer : 6 s (less than 50 Mo)

hope that helps

Michael



Martin Davis a écrit :

> The reason for this is that as the buffer size gets bigger, the "raw
> offset curve" that is initially created prior to extracting the buffer
> outline gets more and more complex.  Concave angles in the input
> geometry result in perpendicular "closing lines" being created, which
> usually intersect other offset lines.  The longer the perpendicular
> line, the more other lines it intersects, and hence the more noding
> and topology analysis has to be performed.  (I haven't found any good
> way of building the raw offset curve to avoid or reduce this problem -
> if anyone has any ideas I'd be interested to hear them).
>
> There's several ways that I've tried to reduce this problem:
>
> - compute the buffer in a series of steps, using an increasing series
> of buffer distances which add up to the desired distance.  Each
> successive buffer gets smoother, which makes the subsequent buffers
> run faster.  It may only be necessary to iterate say 3 times to get a
> good result.  The trick of course is to pick the right distances.
>
> - simplify the input geometry using DP, and a tolerance of say 2% of
> the buffer distance
>
> - A better way of simplifying I've been experimenting with only
> simplifies *outwards*.  This does 2 things - it reduces concavity
> (which is the source of the problem), and it avoid "losing" convex
> protrubances (which DP can often delete or alter).  Convex
> protrubances are the primary influence on the shape of the resulting
> buffer, so it is important to preserve them.  (Currently this code is
> in alpha only - but I can provide it if anyone's interested)
>
> Martin
>
> Michael Michaud wrote:
>> Hi,
>>
>> I noticed that OpenJUMP Buffer plugin performance decreases
>> dramatically if a large buffer size is used :
>> For a map with  rivers having vertices every few meters, I get :
>>
>> buffer =  25 m :     7 s
>> buffer =  50 m :    16 s
>> buffer = 100 m :    48 s
>> buffer = 200 m : 2m 59 s
>>
>> The plugin uses the BufferOp class. I have no idea why a large buffer
>> should take longer than a small one, and I don't know if there is a
>> better way to compute a buffer.
>>
>> Any idea ?
>>
>> Michaël
>>
>> _______________________________________________
>> jts-devel mailing list
>> [hidden email]
>> http://lists.refractions.net/mailman/listinfo/jts-devel
>>
>

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Buffer operation performance

Paul Ramsey
That's diabolical. Your certificate of membership in the League of
Evil is on the way.

Awesome.

P.

On Sat, Jul 26, 2008 at 1:15 AM, Michael Michaud
<[hidden email]> wrote:

> Hi Martin,
>
> Thanks for the precise answer.
> I do not know a good buffer algorithm but I made some further tests which
> show there is place for improvements with the excellent stuff you recently
> added.
>
> I created a simple linestring : length = 25000 m, number of segments = 1000
>
> Trying to create a buffer at a distance of 10000 m ended with a heapspace
> exception (took more than 256 Mo !) after more than 4 mn of intensive
> computation !
>
> The other way is :
> - decompose into segments : less than 1 s
> - create individual buffers : openjump says 8 s but I think it includes
> redrawing
> - cascaded union of resulting buffer : 6 s (less than 50 Mo)
>
> hope that helps
>
> Michael
>
>
>
> Martin Davis a écrit :
>>
>> The reason for this is that as the buffer size gets bigger, the "raw
>> offset curve" that is initially created prior to extracting the buffer
>> outline gets more and more complex.  Concave angles in the input geometry
>> result in perpendicular "closing lines" being created, which usually
>> intersect other offset lines.  The longer the perpendicular line, the more
>> other lines it intersects, and hence the more noding and topology analysis
>> has to be performed.  (I haven't found any good way of building the raw
>> offset curve to avoid or reduce this problem - if anyone has any ideas I'd
>> be interested to hear them).
>>
>> There's several ways that I've tried to reduce this problem:
>>
>> - compute the buffer in a series of steps, using an increasing series of
>> buffer distances which add up to the desired distance.  Each successive
>> buffer gets smoother, which makes the subsequent buffers run faster.  It may
>> only be necessary to iterate say 3 times to get a good result.  The trick of
>> course is to pick the right distances.
>>
>> - simplify the input geometry using DP, and a tolerance of say 2% of the
>> buffer distance
>>
>> - A better way of simplifying I've been experimenting with only simplifies
>> *outwards*.  This does 2 things - it reduces concavity (which is the source
>> of the problem), and it avoid "losing" convex protrubances (which DP can
>> often delete or alter).  Convex protrubances are the primary influence on
>> the shape of the resulting buffer, so it is important to preserve them.
>>  (Currently this code is in alpha only - but I can provide it if anyone's
>> interested)
>>
>> Martin
>>
>> Michael Michaud wrote:
>>>
>>> Hi,
>>>
>>> I noticed that OpenJUMP Buffer plugin performance decreases dramatically
>>> if a large buffer size is used :
>>> For a map with  rivers having vertices every few meters, I get :
>>>
>>> buffer =  25 m :     7 s
>>> buffer =  50 m :    16 s
>>> buffer = 100 m :    48 s
>>> buffer = 200 m : 2m 59 s
>>>
>>> The plugin uses the BufferOp class. I have no idea why a large buffer
>>> should take longer than a small one, and I don't know if there is a better
>>> way to compute a buffer.
>>>
>>> Any idea ?
>>>
>>> Michaël
>>>
>>> _______________________________________________
>>> jts-devel mailing list
>>> [hidden email]
>>> http://lists.refractions.net/mailman/listinfo/jts-devel
>>>
>>
>
> _______________________________________________
> jts-devel mailing list
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
>
_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Buffer operation performance

Martin Davis
In reply to this post by michaelm-2
Very interesting, Michael.  This "partitioned buffering" approach seems
pretty viable as well.  (It would also parallel nicely in a multi-core
environment!)

One limitation is that it's harder (or maybe impossible) to provide
different join styles using PB - but that is probably a minor price to pay.

Now, the challenge is to establish when to use the various approaches.  
Is it always better to use PB?  Or is there some cutover point between
the current buffer algorithm and PB?  This is one thing which has held
me back from offering these other options in JTS.  The choice of which
method to use really needs to be performed automatically by the library.

Can you send me your test dataset?


Michael Michaud wrote:

> Hi Martin,
>
> Thanks for the precise answer.
> I do not know a good buffer algorithm but I made some further tests
> which show there is place for improvements with the excellent stuff
> you recently added.
>
> I created a simple linestring : length = 25000 m, number of segments =
> 1000
>
> Trying to create a buffer at a distance of 10000 m ended with a
> heapspace exception (took more than 256 Mo !) after more than 4 mn of
> intensive computation !
>
> The other way is :
> - decompose into segments : less than 1 s
> - create individual buffers : openjump says 8 s but I think it
> includes redrawing
> - cascaded union of resulting buffer : 6 s (less than 50 Mo)
>
> hope that helps
>
> Michael
>
>
>
> Martin Davis a écrit :
>> The reason for this is that as the buffer size gets bigger, the "raw
>> offset curve" that is initially created prior to extracting the
>> buffer outline gets more and more complex.  Concave angles in the
>> input geometry result in perpendicular "closing lines" being created,
>> which usually intersect other offset lines.  The longer the
>> perpendicular line, the more other lines it intersects, and hence the
>> more noding and topology analysis has to be performed.  (I haven't
>> found any good way of building the raw offset curve to avoid or
>> reduce this problem - if anyone has any ideas I'd be interested to
>> hear them).
>>
>> There's several ways that I've tried to reduce this problem:
>>
>> - compute the buffer in a series of steps, using an increasing series
>> of buffer distances which add up to the desired distance.  Each
>> successive buffer gets smoother, which makes the subsequent buffers
>> run faster.  It may only be necessary to iterate say 3 times to get a
>> good result.  The trick of course is to pick the right distances.
>>
>> - simplify the input geometry using DP, and a tolerance of say 2% of
>> the buffer distance
>>
>> - A better way of simplifying I've been experimenting with only
>> simplifies *outwards*.  This does 2 things - it reduces concavity
>> (which is the source of the problem), and it avoid "losing" convex
>> protrubances (which DP can often delete or alter).  Convex
>> protrubances are the primary influence on the shape of the resulting
>> buffer, so it is important to preserve them.  (Currently this code is
>> in alpha only - but I can provide it if anyone's interested)
>>
>> Martin
>>
>> Michael Michaud wrote:
>>> Hi,
>>>
>>> I noticed that OpenJUMP Buffer plugin performance decreases
>>> dramatically if a large buffer size is used :
>>> For a map with  rivers having vertices every few meters, I get :
>>>
>>> buffer =  25 m :     7 s
>>> buffer =  50 m :    16 s
>>> buffer = 100 m :    48 s
>>> buffer = 200 m : 2m 59 s
>>>
>>> The plugin uses the BufferOp class. I have no idea why a large
>>> buffer should take longer than a small one, and I don't know if
>>> there is a better way to compute a buffer.
>>>
>>> Any idea ?
>>>
>>> Michaël
>>>
>>> _______________________________________________
>>> jts-devel mailing list
>>> [hidden email]
>>> http://lists.refractions.net/mailman/listinfo/jts-devel
>>>
>>
>
> _______________________________________________
> jts-devel mailing list
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
>

--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Buffer operation performance

michaelm-2
Hi,

> Very interesting, Michael.  This "partitioned buffering" approach
> seems pretty viable as well.  (It would also parallel nicely in a
> multi-core environment!)
Yes, but I'm not sure individual buffering takes much time compared to
union operation (it would need more precise measurements)
>
> One limitation is that it's harder (or maybe impossible) to provide
> different join styles using PB - but that is probably a minor price to
> pay.
Right, I did not think about it.
Partitioned buffering could be made available for "round" buffering only.
> Now, the challenge is to establish when to use the various
> approaches.  Is it always better to use PB?  Or is there some cutover
> point between the current buffer algorithm and PB?  This is one thing
> which has held me back from offering these other options in JTS.  The
> choice of which method to use really needs to be performed
> automatically by the library.
I agree that a single test is not enough to make decision. To complete
the test I'll try to measure the difference for
1 / 10 / 100 / 1000  segments
and for a buffer distance equals to
0.01x / 0.1x / 1x / 10x / 100x / 1000x the mean segment length
It would also be interesting to measure improvements for polygon buffering
> Can you send me your test dataset?
Here is the 1031 points wkt of the linestring (I tried a 10000 buffer) :

LINESTRING (
    168000 75099.09,
    168019.98 75079.81,
    168058.38 75051.63,
    168076.91 75045.01,
    168096.34 75039.38,
    168127.45 75021.15,
    168167.12 74999.39,
    168180.16 74991.79,
    168192.45 74982.57,
    168210.71 74972.38,
    168227.46 74964.28,
    168245.93 74951.24,
    168256.76 74941.96,
    168281.34 74925.48,
    168317.49 74903.93,
    168347.95 74893.42,
    168359.81 74886.5,
    168376.8 74873.61,
    168396.02 74862.35,
    168413.3 74857.15,
    168427.85 74850.68,
    168442.62 74840.26,
    168472.25 74826.59,
    168481.69 74819.74,
    168509.94 74810.66,
    168536.95 74796.66,
    168568.02 74785.98,
    168591.85 74776.06,
    168620.28 74763.11,
    168671.46 74735.14,
    168702.77 74718.98,
    168760.54 74684.78,
    168790.68 74665.69,
    168818.45 74651.59,
    168839.39 74639.33,
    168883.15 74612.66,
    168904.37 74597.07,
    168925.39 74585.69,
    168947.76 74575.73,
    168972.48 74562.28,
    168996.29 74552.47,
    169017.6 74547.3,
    169028.94 74543.14,
    169037.2 74537.14,
    169052.36 74529.73,
    169079 74518.34,
    169124.49 74504.73,
    169146.2 74496.7,
    169160.17 74490.57,
    169176.13 74483.44,
    169186.06 74479.41,
    169212.16 74474.08,
    169227.63 74467.66,
    169260.82 74439.9,
    169276.59 74427.91,
    169290.7 74415.52,
    169305.05 74405.76,
    169323.69 74389.86,
    169339.44 74377.81,
    169357.33 74366.16,
    169414.53 74321.51,
    169474.05 74282.78,
    169489.52 74270.72,
    169579.01 74223.09,
    169604.78 74210.14,
    169619.7 74199.66,
    169629.14 74195.23,
    169643.34 74192.88,
    169659.96 74185.19,
    169678.7 74177.96,
    169693.96 74170.68,
    169713.35 74162.96,
    169739.08 74156.44,
    169768.36 74152.97,
    169799.54 74148.44,
    169838.66 74144.65,
    169885.9 74150.01,
    169971.44 74167,
    170024.34 74173.38,
    170076.65 74178.2,
    170094.55 74180.82,
    170113.44 74185.45,
    170132 74188.82,
    170175.93 74192.59,
    170205.21 74192.5,
    170218.75 74191.32,
    170233.84 74190.88,
    170277.47 74190.61,
    170316.34 74191.58,
    170333.36 74190.76,
    170348.04 74190.9,
    170363.55 74188.79,
    170393.8 74188.48,
    170412.8 74190.33,
    170431.6 74191.32,
    170484.03 74196.25,
    170516.54 74191.7,
    170531.41 74190.82,
    170558.77 74188.35,
    170572.36 74182.24,
    170583.63 74178.45,
    170600.48 74171.3,
    170638.11 74160.2,
    170657.84 74153.73,
    170670.51 74148.4,
    170720.33 74125.39,
    170749.99 74113.62,
    170792.93 74100.61,
    170835.33 74092.07,
    170849.17 74088.43,
    170863.59 74083.87,
    170899.93 74068.73,
    170939 74058.28,
    170966.12 74049,
    170989.65 74044.69,
    171001.68 74041.17,
    171028.85 74030.8,
    171053.39 74019.23,
    171081.07 74007.94,
    171102.14 74002.15,
    171117.33 73997.16,
    171142.09 73992.68,
    171151.89 73991.51,
    171198.97 73979.07,
    171232.93 73972.48,
    171243.99 73969.27,
    171268.54 73966.34,
    171301.94 73958.88,
    171310.31 73958.18,
    171318.46 73959.11,
    171334.75 73959.34,
    171360.8 73955.36,
    171390.53 73952.29,
    171407.27 73951.84,
    171454.52 73946.27,
    171532.91 73942.72,
    171559.19 73942.74,
    171586.59 73941.28,
    171606.07 73941.02,
    171632.04 73942.05,
    171648.7 73941.96,
    171664.69 73940.23,
    171703.79 73932.17,
    171725.83 73923.91,
    171786.57 73908.02,
    171811.39 73902.01,
    171862.01 73883.19,
    171881.03 73877.34,
    171904.53 73869.1,
    171924.75 73861,
    171942.63 73855.66,
    171967.52 73846.29,
    171989.09 73837.11,
    172048.82 73819.06,
    172065.95 73811.98,
    172081.18 73803.66,
    172112.57 73792.61,
    172141.47 73781.54,
    172199.07 73754.61,
    172220.41 73746.36,
    172258.74 73737.64,
    172308.01 73719.25,
    172327.08 73714.16,
    172341.9 73711.22,
    172357.39 73706.04,
    172373.89 73699.51,
    172387.83 73695.45,
    172458.09 73667.62,
    172487.31 73654.97,
    172501.31 73647.79,
    172537.91 73627.37,
    172586.45 73599.14,
    172602.33 73591.61,
    172651.56 73576.46,
    172666.88 73571.13,
    172692.9 73558.6,
    172709.76 73549.34,
    172740.08 73534.5,
    172760 73523.41,
    172776.57 73511.27,
    172785.72 73506.09,
    172795.79 73501.6,
    172806.59 73500.89,
    172817.66 73498.13,
    172826.77 73492.83,
    172843.25 73480.68,
    172861.8 73468.4,
    172871.7 73463.21,
    172918.85 73435.31,
    172934.75 73420.57,
    172999.52 73375.23,
    173052.08 73332.33,
    173061.72 73326.05,
    173083.73 73320.93,
    173102.39 73312.88,
    173123.43 73301.81,
    173152.75 73282.68,
    173209.2 73242.11,
    173228.86 73230.1,
    173238.95 73224.75,
    173249.15 73217.87,
    173276.84 73196.72,
    173338.16 73146.47,
    173348.23 73139,
    173384.35 73114.23,
    173430.5 73084.55,
    173440.47 73076.9,
    173450.62 73072.16,
    173469.56 73061.59,
    173479.51 73055.68,
    173497.59 73042.86,
    173507.16 73038.03,
    173528.29 73029.23,
    173559.43 73019.59,
    173569.08 73014.36,
    173587.09 73001.77,
    173674.43 72947.17,
    173701.14 72928.72,
    173709.48 72921.58,
    173724.28 72906.98,
    173739.66 72893.97,
    173749.59 72890.25,
    173775.23 72869.71,
    173785.3 72863.62,
    173818.13 72836.11,
    173827.45 72829.13,
    173856.34 72812.25,
    173865.78 72805.46,
    173875.48 72801,
    173884.38 72795.17,
    173917.08 72767.14,
    173926.86 72762.21,
    173937.93 72763.44,
    173967.05 72749.76,
    173974.73 72741.71,
    173983.02 72734.67,
    173992.68 72727.88,
    174001.83 72722.59,
    174030.88 72707.71,
    174051.2 72698.45,
    174071.1 72687.2,
    174081.39 72683.5,
    174089.48 72685.37,
    174109.71 72677.64,
    174119.75 72678.34,
    174128.19 72671.13,
    174137.3 72664.75,
    174146.85 72659.03,
    174157.34 72654.76,
    174165.35 72648.08,
    174184.53 72637.86,
    174193.88 72633.25,
    174204.59 72631.67,
    174214.39 72625.59,
    174224.21 72621.86,
    174234.42 72616.88,
    174243.59 72610.11,
    174253.83 72605.56,
    174274.88 72598.13,
    174283.78 72592.38,
    174300.78 72576.21,
    174308.71 72569.51,
    174359.48 72528.51,
    174398.79 72492.94,
    174405.5 72484.28,
    174411.53 72474.83,
    174419.13 72466.61,
    174427.17 72459.43,
    174458.79 72425.51,
    174464.86 72417.51,
    174477.4 72397.91,
    174481.96 72388.65,
    174486.63 72377.13,
    174498.42 72343.67,
    174502.95 72333.07,
    174526.81 72283.89,
    174536.17 72262.58,
    174553.04 72234.6,
    174561.1 72226.58,
    174567.54 72216.87,
    174571.16 72206.15,
    174571.79 72195.91,
    174574.97 72185.45,
    174581.47 72175.77,
    174590.94 72156.19,
    174598.5 72148.42,
    174604.26 72138.96,
    174614.61 72119.31,
    174617.86 72109.68,
    174618.88 72098.83,
    174620.62 72088.92,
    174623.58 72079.08,
    174652.24 72019.39,
    174672.82 71980,
    174679.52 71957.62,
    174688.5 71937.78,
    174699.09 71920.14,
    174705.95 71911.18,
    174713.49 71904.44,
    174718.78 71894.98,
    174725.86 71874.85,
    174732.59 71864.99,
    174738.83 71856.73,
    174746.65 71848.06,
    174756.08 71841.4,
    174760.53 71831.95,
    174772.07 71813.16,
    174786.69 71793.3,
    174801.7 71775.1,
    174809.49 71766.29,
    174826.27 71749.24,
    174859.56 71717.58,
    174866.89 71709.21,
    174880.19 71691.3,
    174887 71683.71,
    174895.32 71676.12,
    174904.3 71671.55,
    174913.56 71664.66,
    174920.92 71656.83,
    174927.07 71648.48,
    174935.22 71640.33,
    174943.94 71634.84,
    174954.01 71631.94,
    174970.02 71616.71,
    174986.09 71603.63,
    174992.75 71595.93,
    174997.89 71586.08,
    175002.77 71574.24,
    175007.92 71566.95,
    175021.39 71554.85,
    175026.4 71547.19,
    175030.56 71538.06,
    175044.96 71517.18,
    175060.26 71493.05,
    175077.44 71472.78,
    175094.51 71455.41,
    175111.47 71442.59,
    175143.7 71420.42,
    175156.81 71408.96,
    175188.77 71371.82,
    175267.54 71302.71,
    175284.55 71286.73,
    175299.75 71269.13,
    175358.64 71206.84,
    175396.74 71163.01,
    175411.28 71150.26,
    175442.64 71127.33,
    175457.59 71115.13,
    175500.48 71075.17,
    175523.01 71052.94,
    175566.34 71002.67,
    175585.5 70982.26,
    175601.18 70968.3,
    175635.48 70940.41,
    175645.97 70928.51,
    175657.05 70917.56,
    175669.35 70907.51,
    175680.17 70899.55,
    175708.08 70884.05,
    175719.1 70875.15,
    175728.9 70865.65,
    175748.84 70840.67,
    175760.26 70828.78,
    175772.96 70816.86,
    175797.59 70795.41,
    175820.4 70771.58,
    175830.81 70758.94,
    175887.26 70702.46,
    175939.77 70657.23,
    175964.24 70638.02,
    175991.59 70619.95,
    176055.64 70575.16,
    176079.86 70557.44,
    176099.14 70540.66,
    176111.84 70528.48,
    176124.85 70521.62,
    176138.75 70516.52,
    176151.24 70509.62,
    176162.55 70497.52,
    176175.72 70481.45,
    176206.32 70435.37,
    176222.38 70407.62,
    176237.17 70375.68,
    176249.61 70346.63,
    176265.36 70306.53,
    176289.61 70252.4,
    176304.59 70228.36,
    176325.15 70199.27,
    176346.33 70164.59,
    176363.73 70134.77,
    176376.6 70110.47,
    176398.34 70074.51,
    176425.63 70037.09,
    176461.29 69993.33,
    176538.04 69890.48,
    176611.31 69795.95,
    176642.89 69757.61,
    176653.34 69740.97,
    176667.53 69705.46,
    176694.82 69587.45,
    176710.85 69542.86,
    176729.65 69499.4,
    176750.13 69456.2,
    176759.92 69440.95,
    176765.47 69440.79,
    176769.55 69437.84,
    176775.95 69428.35,
    176816.39 69344.34,
    176838.52 69303.52,
    176841.61 69288.41,
    176847.4 69271.24,
    176853.88 69257.39,
    176866.38 69224.77,
    176884.05 69191.75,
    176908.14 69156.34,
    176932.6 69124.48,
    176941.5 69109.01,
    176952.75 69087.58,
    176962.34 69066.66,
    177011.99 68975.48,
    177047.55 68904.3,
    177075.71 68857.75,
    177086.06 68846.79,
    177093.45 68840.28,
    177113.15 68819.4,
    177125.53 68803.37,
    177145.01 68774.81,
    177162.81 68744.93,
    177175.04 68722.96,
    177183.89 68711.15,
    177195.55 68697.11,
    177206.23 68681.8,
    177232.19 68640.09,
    177250.19 68607.22,
    177286.85 68548.09,
    177331.39 68483.17,
    177380.45 68419.09,
    177385.25 68410.57,
    177415.26 68372.12,
    177436.17 68348.33,
    177461.11 68318.37,
    177477.56 68301.44,
    177486.38 68290.59,
    177497.15 68278.98,
    177504.31 68271.41,
    177514.19 68263.47,
    177531.39 68251.34,
    177547.84 68236.75,
    177556 68228.1,
    177562.23 68220.36,
    177604.15 68155.74,
    177608.84 68145.94,
    177623.1 68120.44,
    177629.69 68105.2,
    177650.02 68073.08,
    177654.45 68065.11,
    177658.56 68050.95,
    177662.82 68042,
    177667.36 68024.84,
    177671 68015.54,
    177681.4 67994.43,
    177693.6 67949.74,
    177703.26 67919.53,
    177706.63 67911.94,
    177714 67899.68,
    177716.44 67893.18,
    177718.91 67884.28,
    177720.55 67871.14,
    177724.45 67851.53,
    177727.55 67839.84,
    177728.77 67829,
    177730.93 67818.94,
    177739.33 67800.24,
    177749.1 67785.58,
    177752.04 67778.56,
    177753.75 67770.32,
    177746.91 67735.03,
    177749.64 67718.67,
    177751.88 67673.54,
    177757.49 67617.74,
    177766.81 67556.29,
    177774.75 67524.5,
    177789.56 67484.51,
    177799.11 67451.34,
    177808.39 67423.01,
    177818.88 67380.1,
    177824.98 67359.84,
    177834.3 67337.45,
    177842.13 67315.31,
    177848.2 67276,
    177855.87 67246.99,
    177863.04 67223.1,
    177875.61 67190.41,
    177879.98 67179.07,
    177883.21 67166.85,
    177884.93 67160.33,
    177887.27 67151.44,
    177898.41 67109.32,
    177909.04 67078.94,
    177913.49 67064.05,
    177918.13 67052.99,
    177923.74 67042.42,
    177929.09 67035.22,
    177930.69 67029.22,
    177930.66 67018.64,
    177941.76 66972.23,
    177945.36 66939.94,
    177951.27 66907.91,
    177952.98 66901.54,
    177955.94 66887.96,
    177959.41 66872.07,
    177966.58 66851.6,
    177971.62 66836.37,
    177985.44 66786.6,
    177989.64 66763.17,
    177994.85 66733.27,
    178001.66 66699.61,
    178008.6 66667.66,
    178013.75 66647.23,
    178016.34 66636.11,
    178017.08 66605.55,
    178014.57 66554.14,
    178010.24 66506.37,
    178009.32 66465.24,
    178009.96 66441.56,
    178005.85 66419.82,
    178002.49 66387.67,
    177998.46 66338.04,
    177993.35 66326.83,
    177986.72 66324.9,
    177985.23 66322.04,
    177985.54 66319.15,
    177989.56 66306.9,
    177993.67 66298.82,
    177995.86 66291.86,
    177995.66 66289.33,
    177992.99 66284.06,
    177993.44 66281.23,
    177992.3 66260.72,
    177990.84 66248.64,
    177981.56 66172.16,
    177977.76 66141.43,
    177974.54 66123.9,
    177971.77 66108.86,
    177967.86 66094.01,
    177966.43 66092.26,
    177967.2 66087.09,
    177966.9 66082.9,
    177966.02 66080.43,
    177964.2 66078.21,
    177963.59 66075.21,
    177964.74 66064.46,
    177964.35 66055.86,
    177963.28 66052.01,
    177959.34 66029.13,
    177960.61 66022.97,
    177959.04 66018.46,
    177956.76 66015.2,
    177956.89 66012.74,
    177958.77 66009.48,
    177959.85 66004.68,
    177957.01 65995.03,
    177957.25 65986.78,
    177956.14 65982.15,
    177953.29 65979.39,
    177952.17 65976.64,
    177957.95 65969.74,
    177959.19 65962.62,
    177957.37 65900.17,
    177953.57 65856.26,
    177953.93 65817.35,
    177953.88 65813.27,
    177955.48 65807.19,
    177956.46 65799.14,
    177955.03 65777.69,
    177956.4 65734.55,
    177956.23 65719.34,
    177953.1 65713.03,
    177954.45 65705.09,
    177957.1 65697.01,
    177956.84 65685.15,
    177959 65679.49,
    177959.49 65671.26,
    177961.48 65638.16,
    177968.9 65592.02,
    177975.6 65560.06,
    177979.15 65534.98,
    177979.38 65495.95,
    177982.31 65407.44,
    177984.68 65358.91,
    177987.11 65325.67,
    177986.1 65293.15,
    177989.96 65264.47,
    177995.42 65209.31,
    178001.47 65168.9,
    178008.8 65113.21,
    178013.31 65003.86,
    178012.51 64952.06,
    178009.63 64847.94,
    178017.62 64682.43,
    178021.64 64541.27,
    178023.13 64396.67,
    178027.75 64137.61,
    178025.76 64028.45,
    178020.43 63910.8,
    178020.72 63849.5,
    178029.19 63778.85,
    178032.16 63763.6,
    178032.6 63749.92,
    178030.32 63733.73,
    178026.47 63721.29,
    178021.04 63709.32,
    178016.35 63702.9,
    178011.71 63699.25,
    178006.61 63698.96,
    178008.27 63678.14,
    178009.61 63661.41,
    178024.73 63657.03,
    178035.53 63651.2,
    178042.7 63644.43,
    178048.96 63635.33,
    178054.42 63625.44,
    178066.74 63513.4,
    178079.29 63350.15,
    178113.91 63043.92,
    178125.17 62967.61,
    178139.81 62861.77,
    178160.03 62739.24,
    178166.8 62690.71,
    178180.6 62598.21,
    178196.38 62478.9,
    178205.95 62429.83,
    178215.68 62390.38,
    178225.95 62355.56,
    178234.91 62330.13,
    178243.99 62312.58,
    178252.42 62300.17,
    178258.59 62293.76,
    178271.74 62267.81,
    178278.87 62259.41,
    178281.2 62257.11,
    178291.29 62241.06,
    178296.59 62234.42,
    178300.59 62233.22,
    178306.14 62233.23,
    178313.85 62230.84,
    178318.53 62228.61,
    178323.72 62225.14,
    178329.38 62219.28,
    178332.15 62217.39,
    178339.35 62217.49,
    178342.7 62218.66,
    178343.51 62221.14,
    178348.34 62226.92,
    178351.79 62228.99,
    178353.88 62228.77,
    178354.79 62226.72,
    178351.18 62221.84,
    178353.07 62216.87,
    178353.25 62214.12,
    178355.63 62211.13,
    178358.36 62209.3,
    178361.9 62208.86,
    178362.76 62206.43,
    178361.97 62203.62,
    178363.58 62201.57,
    178374.53 62193.67,
    178381.63 62189.79,
    178385.43 62189.76,
    178389.45 62192.04,
    178392.01 62192.3,
    178393.18 62189.44,
    178391.57 62187.72,
    178390.78 62185.63,
    178399.88 62175.2,
    178402.36 62174.4,
    178407.71 62177.98,
    178413.7 62175.14,
    178419.05 62176.68,
    178422.21 62174.44,
    178423.73 62172.07,
    178423.57 62169.19,
    178421.96 62166.64,
    178418.94 62165,
    178415.85 62165.96,
    178412.1 62170.44,
    178409.48 62169.88,
    178407.72 62163.55,
    178411.95 62162.4,
    178418.53 62156.4,
    178423.46 62150.54,
    178426.56 62148.62,
    178429.7 62149.94,
    178432.71 62149.19,
    178435.99 62144.98,
    178436.76 62142.14,
    178439.36 62139.27,
    178442.84 62138.83,
    178445.4 62135.85,
    178447.6 62128.51,
    178451.73 62120.49,
    178454.01 62118.47,
    178457.62 62116.53,
    178458.69 62112.83,
    178461.1 62111.48,
    178464.42 62110.72,
    178466.21 62108.01,
    178467.1 62104.31,
    178465.62 62097.07,
    178468.42 62087.79,
    178468.55 62082.53,
    178466.59 62081.04,
    178458.84 62079.15,
    178456.58 62076.29,
    178455.86 62072.53,
    178457.63 62070.82,
    178458.45 62068.91,
    178456.51 62066.55,
    178459.35 62062.85,
    178452.82 62060.08,
    178449.82 62056.67,
    178450.62 62053.45,
    178453.32 62051.97,
    178455.16 62049.21,
    178454.93 62047.57,
    178452.23 62046.52,
    178450.69 62043.67,
    178451.11 62040.83,
    178454.12 62039.86,
    178455.53 62036.39,
    178454.73 62032.33,
    178452.91 62029.35,
    178448.3 62026.56,
    178445.22 62025.7,
    178429.07 62026.53,
    178424.89 62023.48,
    178422.86 62005.51,
    178421.81 61980.76,
    178421.89 61962.48,
    178423.58 61949.11,
    178430.17 61919.22,
    178433.41 61907.8,
    178443.14 61886.28,
    178468.73 61806.63,
    178479.68 61780.1,
    178494.89 61734.32,
    178511.46 61692.33,
    178518.28 61666.62,
    178533.34 61622.92,
    178544.99 61595.95,
    178567.61 61537.18,
    178574.74 61521.82,
    178583.21 61495.5,
    178598.58 61458.21,
    178614.24 61428.39,
    178650.58 61354,
    178658.76 61340.98,
    178665.02 61327.95,
    178674.8 61313.2,
    178700.24 61274.86,
    178719.61 61242.68,
    178738.79 61214.38,
    178758.9 61190.94,
    178770.37 61180.47,
    178789.81 61169.58,
    178812.25 61159.56,
    178824.56 61155.6,
    178835.46 61148.73,
    178850.86 61141.32,
    178877.94 61132.47,
    178905.39 61124.35,
    178921.76 61117.34,
    178937.67 61111.55,
    178980.84 61104.68,
    179007.68 61098.47,
    179056.28 61084.32,
    179128.36 61065.61,
    179202.82 61047.78,
    179276.21 61027.13,
    179472.42 60961.08,
    179529.07 60936.85,
    179542.88 60927.94,
    179549.41 60922,
    179555.08 60911.73,
    179559.44 60900.77,
    179562.28 60889.12,
    179562.47 60877.05,
    179560.63 60866.89,
    179560.7 60863.09,
    179562.37 60857.61,
    179565.71 60846.64,
    179567.54 60832.84,
    179566.44 60823.14,
    179565.06 60818.43,
    179549.81 60764.67,
    179550.31 60758.45,
    179546.67 60734.77,
    179549.49 60731.03,
    179557.54 60733.31,
    179561.13 60738.93,
    179564.21 60739.89,
    179566.89 60745.6,
    179572.89 60748.67,
    179575.31 60751.42,
    179578.26 60756.38,
    179578.33 60762.32,
    179583.95 60763.05,
    179583.19 60771.19,
    179588.15 60772.63,
    179588.19 60782.91,
    179593.07 60784.13,
    179589.87 60805.68,
    179595.07 60815.48,
    179600.01 60822.77,
    179600.24 60826.95,
    179602.21 60832.23,
    179607.32 60835.03,
    179620.58 60838.4,
    179635.67 60841.41,
    179651.26 60843.16,
    179667.47 60843.16,
    179681.53 60838.67,
    179704.27 60828.05,
    179724.08 60814.96,
    179741.93 60801.19,
    179753.86 60790.42,
    179763.48 60779.45,
    179766.88 60773.18,
    179767.07 60771.12,
    179762.6 60765.99,
    179766.21 60747.38,
    179770.94 60741.75,
    179776.56 60738.66,
    179779.2 60737.22,
    179786.44 60742.03,
    179793.9 60741.33,
    179799.37 60742.37,
    179807.42 60735.01,
    179815.39 60724.84,
    179811.05 60721.94,
    179813.76 60715.68,
    179820.14 60717.55,
    179826.71 60710.34,
    179829.53 60708.82,
    179888.74 60612.93,
    179947.13 60522.16,
    179955.61 60507.32,
    179964.18 60496.92,
    179973.96 60490.42,
    179979.79 60485.25,
    179984.9 60477.61,
    180001.97 60445.85,
    180013.27 60430.79,
    180047.31 60395.4,
    180054.81 60389.16,
    180071.26 60381.38,
    180083.39 60373.8,
    180100.66 60358.77,
    180110.87 60348.94,
    180115.99 60340.86,
    180120.92 60330.67,
    180131.3 60290.31,
    180141.88 60252.91,
    180145.41 60243.95,
    180170.92 60161.14,
    180176.4 60146.3,
    180191.39 60114.53,
    180200.97 60096.39,
    180212.16 60078.29,
    180218.27 60071.66,
    180235.86 60057.92,
    180243.95 60050.52,
    180249.63 60043.36,
    180259.04 60025.98,
    180266.35 60007.91,
    180274.4 59993.5,
    180281.06 59983.38,
    180289.52 59973.93,
    180315.7 59949.8,
    180329.09 59939.62,
    180338.31 59934.05,
    180354.18 59926.34,
    180362.13 59924.76,
    180369.12 59926.79,
    180375.15 59931.75,
    180383 59935.53,
    180388.11 59938.77,
    180396.42 59949.49,
    180400.6 59946.77,
    180405.01 59956.2,
    180407.23 59954.8,
    180409.16 59952.08,
    180431.99 59882.17,
    180489.59 59719.98,
    180516.16 59668.73,
    180544.76 59619.86,
    180564.25 59578.8,
    180573.7 59551.7,
    180580.79 59525.35,
    180588.37 59505.63,
    180604.12 59473.13,
    180622.29 59445.18,
    180631.91 59429.05,
    180637.83 59412.74,
    180656.17 59339.6,
    180669.41 59299.14,
    180679.64 59275.76,
    180684.28 59266.53,
    180686.05 59263.02,
    180697.93 59246.56,
    180747.67 59189.18,
    180759.28 59178.74,
    180772.99 59167.85,
    180785.83 59162,
    180798.34 59158.18,
    180813.74 59154.37,
    180832.3 59151.97,
    180855.11 59147.46,
    180861.98 59142.9,
    180866.27 59138.42,
    180872.11 59130.67,
    180909.6 59075.52,
    180922.07 59061.58,
    180930.79 59055.13,
    180943.08 59050.38,
    180953.99 59047.52,
    180964.78 59041.87,
    180975.83 59032.72,
    180985.33 59022.92,
    181000.57 59002.51,
    181013.17 58990.67,
    181024.71 58983.21,
    181035.92 58978.57,
    181050.06 58975.38,
    181076.88 58972.92,
    181087.67 58970.91,
    181099.7 58966.76,
    181122.01 58955.77,
    181146.14 58947.76,
    181157.78 58942.19,
    181167.75 58934.2,
    181177.2 58925.53,
    181192.11 58906.31,
    181233.44 58862,
    181243.56 58849.94,
    181262.63 58824.07,
    181269.81 58813.01,
    181278.57 58797.49,
    181286.69 58781,
    181294.3 58748.54,
    181297.43 58721.7,
    181293.95 58693.46,
    181279.45 58644.96,
    181271.49 58621.9,
    181245.24 58566.88,
    181234.84 58548.6,
    181226.25 58524.73,
    181207.37 58438.02,
    181193.75 58388.29,
    181183.54 58357.62,
    181169.67 58302.15,
    181163.49 58274.38,
    181159.28 58246,
    181147.89 58107.32,
    181147.06 57991.43,
    181148.81 57965.73,
    181150.16 57909.44,
    181151.32 57888.4,
    181156.51 57844.11,
    181163.68 57796.12,
    181177.45 57719.23,
    181202.13 57619.71,
    181224.13 57544.69,
    181254.77 57474.29,
    181263.88 57451,
    181283.27 57406.83,
    181308.26 57364,
    181321.91 57342.42,
    181347.77 57297.32,
    181375.92 57255.37,
    181421.33 57195.25,
    181465.37 57132.96,
    181498.7 57089.91,
    181515.73 57069.3,
    181532.65 57051.11,
    181546.73 57031.97,
    181578.04 56994.2,
    181592.81 56974.79,
    181606.21 56955.33,
    181617.19 56937.88,
    181636.62 56901.76,
    181644.91 56883.67,
    181651.88 56866.37,
    181658.28 56848.86,
    181667.09 56820.5,
    181670.79 56812.22,
    181673.84 56805.41,
    181679.95 56789.22,
    181716.63 56710.19,
    181727.56 56693.78,
    181739.09 56674.37,
    181760.36 56634.75,
    181770.08 56621.43,
    181806.52 56563.56,
    181822.11 56541.55,
    181853.29 56501.39,
    181867.37 56484.47,
    181915.43 56418.28,
    181934.25 56389.84,
    181989.88 56324.58,
    182008.53 56304.44,
    182028.06 56281.36,
    182044.18 56260.03,
    182077.17 56220.41,
    182095.42 56200.24,
    182149.64 56149,
    182152.81 56145.38,
    182165.25 56131.22,
    182181.63 56109.2,
    182226.84 56059.65,
    182240.13 56042.18,
    182249.84 56026.52,
    182262.23 56004.41,
    182269.66 55988.27,
    182279.11 55970.17,
    182302.19 55934.92,
    182312.97 55920.44,
    182334.13 55894.79,
    182356.12 55865.14,
    182427.98 55779.79,
    182498.67 55702.44
)

>
> Michael Michaud wrote:
>> Hi Martin,
>>
>> Thanks for the precise answer.
>> I do not know a good buffer algorithm but I made some further tests
>> which show there is place for improvements with the excellent stuff
>> you recently added.
>>
>> I created a simple linestring : length = 25000 m, number of segments
>> = 1000
>>
>> Trying to create a buffer at a distance of 10000 m ended with a
>> heapspace exception (took more than 256 Mo !) after more than 4 mn of
>> intensive computation !
>>
>> The other way is :
>> - decompose into segments : less than 1 s
>> - create individual buffers : openjump says 8 s but I think it
>> includes redrawing
>> - cascaded union of resulting buffer : 6 s (less than 50 Mo)
>>
>> hope that helps
>>
>> Michael
>>
>>
>>
>> Martin Davis a écrit :
>>> The reason for this is that as the buffer size gets bigger, the "raw
>>> offset curve" that is initially created prior to extracting the
>>> buffer outline gets more and more complex.  Concave angles in the
>>> input geometry result in perpendicular "closing lines" being
>>> created, which usually intersect other offset lines.  The longer the
>>> perpendicular line, the more other lines it intersects, and hence
>>> the more noding and topology analysis has to be performed.  (I
>>> haven't found any good way of building the raw offset curve to avoid
>>> or reduce this problem - if anyone has any ideas I'd be interested
>>> to hear them).
>>>
>>> There's several ways that I've tried to reduce this problem:
>>>
>>> - compute the buffer in a series of steps, using an increasing
>>> series of buffer distances which add up to the desired distance.  
>>> Each successive buffer gets smoother, which makes the subsequent
>>> buffers run faster.  It may only be necessary to iterate say 3 times
>>> to get a good result.  The trick of course is to pick the right
>>> distances.
>>>
>>> - simplify the input geometry using DP, and a tolerance of say 2% of
>>> the buffer distance
>>>
>>> - A better way of simplifying I've been experimenting with only
>>> simplifies *outwards*.  This does 2 things - it reduces concavity
>>> (which is the source of the problem), and it avoid "losing" convex
>>> protrubances (which DP can often delete or alter).  Convex
>>> protrubances are the primary influence on the shape of the resulting
>>> buffer, so it is important to preserve them.  (Currently this code
>>> is in alpha only - but I can provide it if anyone's interested)
>>>
>>> Martin
>>>
>>> Michael Michaud wrote:
>>>> Hi,
>>>>
>>>> I noticed that OpenJUMP Buffer plugin performance decreases
>>>> dramatically if a large buffer size is used :
>>>> For a map with  rivers having vertices every few meters, I get :
>>>>
>>>> buffer =  25 m :     7 s
>>>> buffer =  50 m :    16 s
>>>> buffer = 100 m :    48 s
>>>> buffer = 200 m : 2m 59 s
>>>>
>>>> The plugin uses the BufferOp class. I have no idea why a large
>>>> buffer should take longer than a small one, and I don't know if
>>>> there is a better way to compute a buffer.
>>>>
>>>> Any idea ?
>>>>
>>>> Michaël
>>>>
>>>> _______________________________________________
>>>> jts-devel mailing list
>>>> [hidden email]
>>>> http://lists.refractions.net/mailman/listinfo/jts-devel
>>>>
>>>
>>
>> _______________________________________________
>> jts-devel mailing list
>> [hidden email]
>> http://lists.refractions.net/mailman/listinfo/jts-devel
>>
>

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Buffer operation performance

Martin Davis
Michael,

I'd be interested in seeing a comparison between iterated buffering and
the partioned-union approach.  Below is a simple method that performs
iterated buffering (Note: it's a prototype only - it works for the test
case & distances that you provided, but would need to be enhanced for
general purpose use.  But it's sufficient to do speed comparisons).

  Geometry iteratedBuffer(Geometry g, double dist)
  {
      // this initial value should be determined based on properties of the
      // input geometry and the required buffer distance
      double currInc = 0.1;
      double totalDist = 0.0;

      Geometry currBuf = g;
      while (true) {
          double bufDist = currInc;
          boolean isDone = false;
          if (totalDist + bufDist > dist) {
              bufDist = dist - totalDist;
              isDone = true;
          }
          currBuf = currBuf.buffer(bufDist);
          totalDist += bufDist;
          System.out.println("Incrementally buffering with dist = " +
bufDist
                  + " (total dist = " + totalDist);
          if (isDone)
              break;
         
          currInc *= 10.0;
      }
      return currBuf;
  }


Can you try it in your environment and see what the performance is?

I get:

Running case   buffer dist = 10.0
Incrementally buffering with dist = 0.1 (total dist = 0.1
Incrementally buffering with dist = 1.0 (total dist = 1.1
Incrementally buffering with dist = 8.9 (total dist = 10.0
Finished in 265 ms
Running case   buffer dist = 100.0
Incrementally buffering with dist = 0.1 (total dist = 0.1
Incrementally buffering with dist = 1.0 (total dist = 1.1
Incrementally buffering with dist = 10.0 (total dist = 11.1
Incrementally buffering with dist = 88.9 (total dist = 100.0
Finished in 500 ms
Running case   buffer dist = 10000.0
Incrementally buffering with dist = 0.1 (total dist = 0.1
Incrementally buffering with dist = 1.0 (total dist = 1.1
Incrementally buffering with dist = 10.0 (total dist = 11.1
Incrementally buffering with dist = 100.0 (total dist = 111.1
Incrementally buffering with dist = 1000.0 (total dist = 1111.1
Incrementally buffering with dist = 8888.9 (total dist = 10000.0
Finished in 2579 ms


Michael Michaud wrote:

> Hi,
>
>> Very interesting, Michael.  This "partitioned buffering" approach
>> seems pretty viable as well.  (It would also parallel nicely in a
>> multi-core environment!)
> Yes, but I'm not sure individual buffering takes much time compared to
> union operation (it would need more precise measurements)
>>
>> One limitation is that it's harder (or maybe impossible) to provide
>> different join styles using PB - but that is probably a minor price
>> to pay.
> Right, I did not think about it.
> Partitioned buffering could be made available for "round" buffering only.
>> Now, the challenge is to establish when to use the various
>> approaches.  Is it always better to use PB?  Or is there some cutover
>> point between the current buffer algorithm and PB?  This is one thing
>> which has held me back from offering these other options in JTS.  The
>> choice of which method to use really needs to be performed
>> automatically by the library.
> I agree that a single test is not enough to make decision. To complete
> the test I'll try to measure the difference for
> 1 / 10 / 100 / 1000  segments
> and for a buffer distance equals to
> 0.01x / 0.1x / 1x / 10x / 100x / 1000x the mean segment length
> It would also be interesting to measure improvements for polygon
> buffering
>> Can you send me your test dataset?
> Here is the 1031 points wkt of the linestring (I tried a 10000 buffer) :
>
> LINESTRING (
>    168000 75099.09,
>    168019.98 75079.81,
>    168058.38 75051.63,
>    168076.91 75045.01,
>    168096.34 75039.38,
>    168127.45 75021.15,
>    168167.12 74999.39,
>    168180.16 74991.79,
>    168192.45 74982.57,
>    168210.71 74972.38,
>    168227.46 74964.28,
>    168245.93 74951.24,
>    168256.76 74941.96,
>    168281.34 74925.48,
>    168317.49 74903.93,
>    168347.95 74893.42,
>    168359.81 74886.5,
>    168376.8 74873.61,
>    168396.02 74862.35,
>    168413.3 74857.15,
>    168427.85 74850.68,
>    168442.62 74840.26,
>    168472.25 74826.59,
>    168481.69 74819.74,
>    168509.94 74810.66,
>    168536.95 74796.66,
>    168568.02 74785.98,
>    168591.85 74776.06,
>    168620.28 74763.11,
>    168671.46 74735.14,
>    168702.77 74718.98,
>    168760.54 74684.78,
>    168790.68 74665.69,
>    168818.45 74651.59,
>    168839.39 74639.33,
>    168883.15 74612.66,
>    168904.37 74597.07,
>    168925.39 74585.69,
>    168947.76 74575.73,
>    168972.48 74562.28,
>    168996.29 74552.47,
>    169017.6 74547.3,
>    169028.94 74543.14,
>    169037.2 74537.14,
>    169052.36 74529.73,
>    169079 74518.34,
>    169124.49 74504.73,
>    169146.2 74496.7,
>    169160.17 74490.57,
>    169176.13 74483.44,
>    169186.06 74479.41,
>    169212.16 74474.08,
>    169227.63 74467.66,
>    169260.82 74439.9,
>    169276.59 74427.91,
>    169290.7 74415.52,
>    169305.05 74405.76,
>    169323.69 74389.86,
>    169339.44 74377.81,
>    169357.33 74366.16,
>    169414.53 74321.51,
>    169474.05 74282.78,
>    169489.52 74270.72,
>    169579.01 74223.09,
>    169604.78 74210.14,
>    169619.7 74199.66,
>    169629.14 74195.23,
>    169643.34 74192.88,
>    169659.96 74185.19,
>    169678.7 74177.96,
>    169693.96 74170.68,
>    169713.35 74162.96,
>    169739.08 74156.44,
>    169768.36 74152.97,
>    169799.54 74148.44,
>    169838.66 74144.65,
>    169885.9 74150.01,
>    169971.44 74167,
>    170024.34 74173.38,
>    170076.65 74178.2,
>    170094.55 74180.82,
>    170113.44 74185.45,
>    170132 74188.82,
>    170175.93 74192.59,
>    170205.21 74192.5,
>    170218.75 74191.32,
>    170233.84 74190.88,
>    170277.47 74190.61,
>    170316.34 74191.58,
>    170333.36 74190.76,
>    170348.04 74190.9,
>    170363.55 74188.79,
>    170393.8 74188.48,
>    170412.8 74190.33,
>    170431.6 74191.32,
>    170484.03 74196.25,
>    170516.54 74191.7,
>    170531.41 74190.82,
>    170558.77 74188.35,
>    170572.36 74182.24,
>    170583.63 74178.45,
>    170600.48 74171.3,
>    170638.11 74160.2,
>    170657.84 74153.73,
>    170670.51 74148.4,
>    170720.33 74125.39,
>    170749.99 74113.62,
>    170792.93 74100.61,
>    170835.33 74092.07,
>    170849.17 74088.43,
>    170863.59 74083.87,
>    170899.93 74068.73,
>    170939 74058.28,
>    170966.12 74049,
>    170989.65 74044.69,
>    171001.68 74041.17,
>    171028.85 74030.8,
>    171053.39 74019.23,
>    171081.07 74007.94,
>    171102.14 74002.15,
>    171117.33 73997.16,
>    171142.09 73992.68,
>    171151.89 73991.51,
>    171198.97 73979.07,
>    171232.93 73972.48,
>    171243.99 73969.27,
>    171268.54 73966.34,
>    171301.94 73958.88,
>    171310.31 73958.18,
>    171318.46 73959.11,
>    171334.75 73959.34,
>    171360.8 73955.36,
>    171390.53 73952.29,
>    171407.27 73951.84,
>    171454.52 73946.27,
>    171532.91 73942.72,
>    171559.19 73942.74,
>    171586.59 73941.28,
>    171606.07 73941.02,
>    171632.04 73942.05,
>    171648.7 73941.96,
>    171664.69 73940.23,
>    171703.79 73932.17,
>    171725.83 73923.91,
>    171786.57 73908.02,
>    171811.39 73902.01,
>    171862.01 73883.19,
>    171881.03 73877.34,
>    171904.53 73869.1,
>    171924.75 73861,
>    171942.63 73855.66,
>    171967.52 73846.29,
>    171989.09 73837.11,
>    172048.82 73819.06,
>    172065.95 73811.98,
>    172081.18 73803.66,
>    172112.57 73792.61,
>    172141.47 73781.54,
>    172199.07 73754.61,
>    172220.41 73746.36,
>    172258.74 73737.64,
>    172308.01 73719.25,
>    172327.08 73714.16,
>    172341.9 73711.22,
>    172357.39 73706.04,
>    172373.89 73699.51,
>    172387.83 73695.45,
>    172458.09 73667.62,
>    172487.31 73654.97,
>    172501.31 73647.79,
>    172537.91 73627.37,
>    172586.45 73599.14,
>    172602.33 73591.61,
>    172651.56 73576.46,
>    172666.88 73571.13,
>    172692.9 73558.6,
>    172709.76 73549.34,
>    172740.08 73534.5,
>    172760 73523.41,
>    172776.57 73511.27,
>    172785.72 73506.09,
>    172795.79 73501.6,
>    172806.59 73500.89,
>    172817.66 73498.13,
>    172826.77 73492.83,
>    172843.25 73480.68,
>    172861.8 73468.4,
>    172871.7 73463.21,
>    172918.85 73435.31,
>    172934.75 73420.57,
>    172999.52 73375.23,
>    173052.08 73332.33,
>    173061.72 73326.05,
>    173083.73 73320.93,
>    173102.39 73312.88,
>    173123.43 73301.81,
>    173152.75 73282.68,
>    173209.2 73242.11,
>    173228.86 73230.1,
>    173238.95 73224.75,
>    173249.15 73217.87,
>    173276.84 73196.72,
>    173338.16 73146.47,
>    173348.23 73139,
>    173384.35 73114.23,
>    173430.5 73084.55,
>    173440.47 73076.9,
>    173450.62 73072.16,
>    173469.56 73061.59,
>    173479.51 73055.68,
>    173497.59 73042.86,
>    173507.16 73038.03,
>    173528.29 73029.23,
>    173559.43 73019.59,
>    173569.08 73014.36,
>    173587.09 73001.77,
>    173674.43 72947.17,
>    173701.14 72928.72,
>    173709.48 72921.58,
>    173724.28 72906.98,
>    173739.66 72893.97,
>    173749.59 72890.25,
>    173775.23 72869.71,
>    173785.3 72863.62,
>    173818.13 72836.11,
>    173827.45 72829.13,
>    173856.34 72812.25,
>    173865.78 72805.46,
>    173875.48 72801,
>    173884.38 72795.17,
>    173917.08 72767.14,
>    173926.86 72762.21,
>    173937.93 72763.44,
>    173967.05 72749.76,
>    173974.73 72741.71,
>    173983.02 72734.67,
>    173992.68 72727.88,
>    174001.83 72722.59,
>    174030.88 72707.71,
>    174051.2 72698.45,
>    174071.1 72687.2,
>    174081.39 72683.5,
>    174089.48 72685.37,
>    174109.71 72677.64,
>    174119.75 72678.34,
>    174128.19 72671.13,
>    174137.3 72664.75,
>    174146.85 72659.03,
>    174157.34 72654.76,
>    174165.35 72648.08,
>    174184.53 72637.86,
>    174193.88 72633.25,
>    174204.59 72631.67,
>    174214.39 72625.59,
>    174224.21 72621.86,
>    174234.42 72616.88,
>    174243.59 72610.11,
>    174253.83 72605.56,
>    174274.88 72598.13,
>    174283.78 72592.38,
>    174300.78 72576.21,
>    174308.71 72569.51,
>    174359.48 72528.51,
>    174398.79 72492.94,
>    174405.5 72484.28,
>    174411.53 72474.83,
>    174419.13 72466.61,
>    174427.17 72459.43,
>    174458.79 72425.51,
>    174464.86 72417.51,
>    174477.4 72397.91,
>    174481.96 72388.65,
>    174486.63 72377.13,
>    174498.42 72343.67,
>    174502.95 72333.07,
>    174526.81 72283.89,
>    174536.17 72262.58,
>    174553.04 72234.6,
>    174561.1 72226.58,
>    174567.54 72216.87,
>    174571.16 72206.15,
>    174571.79 72195.91,
>    174574.97 72185.45,
>    174581.47 72175.77,
>    174590.94 72156.19,
>    174598.5 72148.42,
>    174604.26 72138.96,
>    174614.61 72119.31,
>    174617.86 72109.68,
>    174618.88 72098.83,
>    174620.62 72088.92,
>    174623.58 72079.08,
>    174652.24 72019.39,
>    174672.82 71980,
>    174679.52 71957.62,
>    174688.5 71937.78,
>    174699.09 71920.14,
>    174705.95 71911.18,
>    174713.49 71904.44,
>    174718.78 71894.98,
>    174725.86 71874.85,
>    174732.59 71864.99,
>    174738.83 71856.73,
>    174746.65 71848.06,
>    174756.08 71841.4,
>    174760.53 71831.95,
>    174772.07 71813.16,
>    174786.69 71793.3,
>    174801.7 71775.1,
>    174809.49 71766.29,
>    174826.27 71749.24,
>    174859.56 71717.58,
>    174866.89 71709.21,
>    174880.19 71691.3,
>    174887 71683.71,
>    174895.32 71676.12,
>    174904.3 71671.55,
>    174913.56 71664.66,
>    174920.92 71656.83,
>    174927.07 71648.48,
>    174935.22 71640.33,
>    174943.94 71634.84,
>    174954.01 71631.94,
>    174970.02 71616.71,
>    174986.09 71603.63,
>    174992.75 71595.93,
>    174997.89 71586.08,
>    175002.77 71574.24,
>    175007.92 71566.95,
>    175021.39 71554.85,
>    175026.4 71547.19,
>    175030.56 71538.06,
>    175044.96 71517.18,
>    175060.26 71493.05,
>    175077.44 71472.78,
>    175094.51 71455.41,
>    175111.47 71442.59,
>    175143.7 71420.42,
>    175156.81 71408.96,
>    175188.77 71371.82,
>    175267.54 71302.71,
>    175284.55 71286.73,
>    175299.75 71269.13,
>    175358.64 71206.84,
>    175396.74 71163.01,
>    175411.28 71150.26,
>    175442.64 71127.33,
>    175457.59 71115.13,
>    175500.48 71075.17,
>    175523.01 71052.94,
>    175566.34 71002.67,
>    175585.5 70982.26,
>    175601.18 70968.3,
>    175635.48 70940.41,
>    175645.97 70928.51,
>    175657.05 70917.56,
>    175669.35 70907.51,
>    175680.17 70899.55,
>    175708.08 70884.05,
>    175719.1 70875.15,
>    175728.9 70865.65,
>    175748.84 70840.67,
>    175760.26 70828.78,
>    175772.96 70816.86,
>    175797.59 70795.41,
>    175820.4 70771.58,
>    175830.81 70758.94,
>    175887.26 70702.46,
>    175939.77 70657.23,
>    175964.24 70638.02,
>    175991.59 70619.95,
>    176055.64 70575.16,
>    176079.86 70557.44,
>    176099.14 70540.66,
>    176111.84 70528.48,
>    176124.85 70521.62,
>    176138.75 70516.52,
>    176151.24 70509.62,
>    176162.55 70497.52,
>    176175.72 70481.45,
>    176206.32 70435.37,
>    176222.38 70407.62,
>    176237.17 70375.68,
>    176249.61 70346.63,
>    176265.36 70306.53,
>    176289.61 70252.4,
>    176304.59 70228.36,
>    176325.15 70199.27,
>    176346.33 70164.59,
>    176363.73 70134.77,
>    176376.6 70110.47,
>    176398.34 70074.51,
>    176425.63 70037.09,
>    176461.29 69993.33,
>    176538.04 69890.48,
>    176611.31 69795.95,
>    176642.89 69757.61,
>    176653.34 69740.97,
>    176667.53 69705.46,
>    176694.82 69587.45,
>    176710.85 69542.86,
>    176729.65 69499.4,
>    176750.13 69456.2,
>    176759.92 69440.95,
>    176765.47 69440.79,
>    176769.55 69437.84,
>    176775.95 69428.35,
>    176816.39 69344.34,
>    176838.52 69303.52,
>    176841.61 69288.41,
>    176847.4 69271.24,
>    176853.88 69257.39,
>    176866.38 69224.77,
>    176884.05 69191.75,
>    176908.14 69156.34,
>    176932.6 69124.48,
>    176941.5 69109.01,
>    176952.75 69087.58,
>    176962.34 69066.66,
>    177011.99 68975.48,
>    177047.55 68904.3,
>    177075.71 68857.75,
>    177086.06 68846.79,
>    177093.45 68840.28,
>    177113.15 68819.4,
>    177125.53 68803.37,
>    177145.01 68774.81,
>    177162.81 68744.93,
>    177175.04 68722.96,
>    177183.89 68711.15,
>    177195.55 68697.11,
>    177206.23 68681.8,
>    177232.19 68640.09,
>    177250.19 68607.22,
>    177286.85 68548.09,
>    177331.39 68483.17,
>    177380.45 68419.09,
>    177385.25 68410.57,
>    177415.26 68372.12,
>    177436.17 68348.33,
>    177461.11 68318.37,
>    177477.56 68301.44,
>    177486.38 68290.59,
>    177497.15 68278.98,
>    177504.31 68271.41,
>    177514.19 68263.47,
>    177531.39 68251.34,
>    177547.84 68236.75,
>    177556 68228.1,
>    177562.23 68220.36,
>    177604.15 68155.74,
>    177608.84 68145.94,
>    177623.1 68120.44,
>    177629.69 68105.2,
>    177650.02 68073.08,
>    177654.45 68065.11,
>    177658.56 68050.95,
>    177662.82 68042,
>    177667.36 68024.84,
>    177671 68015.54,
>    177681.4 67994.43,
>    177693.6 67949.74,
>    177703.26 67919.53,
>    177706.63 67911.94,
>    177714 67899.68,
>    177716.44 67893.18,
>    177718.91 67884.28,
>    177720.55 67871.14,
>    177724.45 67851.53,
>    177727.55 67839.84,
>    177728.77 67829,
>    177730.93 67818.94,
>    177739.33 67800.24,
>    177749.1 67785.58,
>    177752.04 67778.56,
>    177753.75 67770.32,
>    177746.91 67735.03,
>    177749.64 67718.67,
>    177751.88 67673.54,
>    177757.49 67617.74,
>    177766.81 67556.29,
>    177774.75 67524.5,
>    177789.56 67484.51,
>    177799.11 67451.34,
>    177808.39 67423.01,
>    177818.88 67380.1,
>    177824.98 67359.84,
>    177834.3 67337.45,
>    177842.13 67315.31,
>    177848.2 67276,
>    177855.87 67246.99,
>    177863.04 67223.1,
>    177875.61 67190.41,
>    177879.98 67179.07,
>    177883.21 67166.85,
>    177884.93 67160.33,
>    177887.27 67151.44,
>    177898.41 67109.32,
>    177909.04 67078.94,
>    177913.49 67064.05,
>    177918.13 67052.99,
>    177923.74 67042.42,
>    177929.09 67035.22,
>    177930.69 67029.22,
>    177930.66 67018.64,
>    177941.76 66972.23,
>    177945.36 66939.94,
>    177951.27 66907.91,
>    177952.98 66901.54,
>    177955.94 66887.96,
>    177959.41 66872.07,
>    177966.58 66851.6,
>    177971.62 66836.37,
>    177985.44 66786.6,
>    177989.64 66763.17,
>    177994.85 66733.27,
>    178001.66 66699.61,
>    178008.6 66667.66,
>    178013.75 66647.23,
>    178016.34 66636.11,
>    178017.08 66605.55,
>    178014.57 66554.14,
>    178010.24 66506.37,
>    178009.32 66465.24,
>    178009.96 66441.56,
>    178005.85 66419.82,
>    178002.49 66387.67,
>    177998.46 66338.04,
>    177993.35 66326.83,
>    177986.72 66324.9,
>    177985.23 66322.04,
>    177985.54 66319.15,
>    177989.56 66306.9,
>    177993.67 66298.82,
>    177995.86 66291.86,
>    177995.66 66289.33,
>    177992.99 66284.06,
>    177993.44 66281.23,
>    177992.3 66260.72,
>    177990.84 66248.64,
>    177981.56 66172.16,
>    177977.76 66141.43,
>    177974.54 66123.9,
>    177971.77 66108.86,
>    177967.86 66094.01,
>    177966.43 66092.26,
>    177967.2 66087.09,
>    177966.9 66082.9,
>    177966.02 66080.43,
>    177964.2 66078.21,
>    177963.59 66075.21,
>    177964.74 66064.46,
>    177964.35 66055.86,
>    177963.28 66052.01,
>    177959.34 66029.13,
>    177960.61 66022.97,
>    177959.04 66018.46,
>    177956.76 66015.2,
>    177956.89 66012.74,
>    177958.77 66009.48,
>    177959.85 66004.68,
>    177957.01 65995.03,
>    177957.25 65986.78,
>    177956.14 65982.15,
>    177953.29 65979.39,
>    177952.17 65976.64,
>    177957.95 65969.74,
>    177959.19 65962.62,
>    177957.37 65900.17,
>    177953.57 65856.26,
>    177953.93 65817.35,
>    177953.88 65813.27,
>    177955.48 65807.19,
>    177956.46 65799.14,
>    177955.03 65777.69,
>    177956.4 65734.55,
>    177956.23 65719.34,
>    177953.1 65713.03,
>    177954.45 65705.09,
>    177957.1 65697.01,
>    177956.84 65685.15,
>    177959 65679.49,
>    177959.49 65671.26,
>    177961.48 65638.16,
>    177968.9 65592.02,
>    177975.6 65560.06,
>    177979.15 65534.98,
>    177979.38 65495.95,
>    177982.31 65407.44,
>    177984.68 65358.91,
>    177987.11 65325.67,
>    177986.1 65293.15,
>    177989.96 65264.47,
>    177995.42 65209.31,
>    178001.47 65168.9,
>    178008.8 65113.21,
>    178013.31 65003.86,
>    178012.51 64952.06,
>    178009.63 64847.94,
>    178017.62 64682.43,
>    178021.64 64541.27,
>    178023.13 64396.67,
>    178027.75 64137.61,
>    178025.76 64028.45,
>    178020.43 63910.8,
>    178020.72 63849.5,
>    178029.19 63778.85,
>    178032.16 63763.6,
>    178032.6 63749.92,
>    178030.32 63733.73,
>    178026.47 63721.29,
>    178021.04 63709.32,
>    178016.35 63702.9,
>    178011.71 63699.25,
>    178006.61 63698.96,
>    178008.27 63678.14,
>    178009.61 63661.41,
>    178024.73 63657.03,
>    178035.53 63651.2,
>    178042.7 63644.43,
>    178048.96 63635.33,
>    178054.42 63625.44,
>    178066.74 63513.4,
>    178079.29 63350.15,
>    178113.91 63043.92,
>    178125.17 62967.61,
>    178139.81 62861.77,
>    178160.03 62739.24,
>    178166.8 62690.71,
>    178180.6 62598.21,
>    178196.38 62478.9,
>    178205.95 62429.83,
>    178215.68 62390.38,
>    178225.95 62355.56,
>    178234.91 62330.13,
>    178243.99 62312.58,
>    178252.42 62300.17,
>    178258.59 62293.76,
>    178271.74 62267.81,
>    178278.87 62259.41,
>    178281.2 62257.11,
>    178291.29 62241.06,
>    178296.59 62234.42,
>    178300.59 62233.22,
>    178306.14 62233.23,
>    178313.85 62230.84,
>    178318.53 62228.61,
>    178323.72 62225.14,
>    178329.38 62219.28,
>    178332.15 62217.39,
>    178339.35 62217.49,
>    178342.7 62218.66,
>    178343.51 62221.14,
>    178348.34 62226.92,
>    178351.79 62228.99,
>    178353.88 62228.77,
>    178354.79 62226.72,
>    178351.18 62221.84,
>    178353.07 62216.87,
>    178353.25 62214.12,
>    178355.63 62211.13,
>    178358.36 62209.3,
>    178361.9 62208.86,
>    178362.76 62206.43,
>    178361.97 62203.62,
>    178363.58 62201.57,
>    178374.53 62193.67,
>    178381.63 62189.79,
>    178385.43 62189.76,
>    178389.45 62192.04,
>    178392.01 62192.3,
>    178393.18 62189.44,
>    178391.57 62187.72,
>    178390.78 62185.63,
>    178399.88 62175.2,
>    178402.36 62174.4,
>    178407.71 62177.98,
>    178413.7 62175.14,
>    178419.05 62176.68,
>    178422.21 62174.44,
>    178423.73 62172.07,
>    178423.57 62169.19,
>    178421.96 62166.64,
>    178418.94 62165,
>    178415.85 62165.96,
>    178412.1 62170.44,
>    178409.48 62169.88,
>    178407.72 62163.55,
>    178411.95 62162.4,
>    178418.53 62156.4,
>    178423.46 62150.54,
>    178426.56 62148.62,
>    178429.7 62149.94,
>    178432.71 62149.19,
>    178435.99 62144.98,
>    178436.76 62142.14,
>    178439.36 62139.27,
>    178442.84 62138.83,
>    178445.4 62135.85,
>    178447.6 62128.51,
>    178451.73 62120.49,
>    178454.01 62118.47,
>    178457.62 62116.53,
>    178458.69 62112.83,
>    178461.1 62111.48,
>    178464.42 62110.72,
>    178466.21 62108.01,
>    178467.1 62104.31,
>    178465.62 62097.07,
>    178468.42 62087.79,
>    178468.55 62082.53,
>    178466.59 62081.04,
>    178458.84 62079.15,
>    178456.58 62076.29,
>    178455.86 62072.53,
>    178457.63 62070.82,
>    178458.45 62068.91,
>    178456.51 62066.55,
>    178459.35 62062.85,
>    178452.82 62060.08,
>    178449.82 62056.67,
>    178450.62 62053.45,
>    178453.32 62051.97,
>    178455.16 62049.21,
>    178454.93 62047.57,
>    178452.23 62046.52,
>    178450.69 62043.67,
>    178451.11 62040.83,
>    178454.12 62039.86,
>    178455.53 62036.39,
>    178454.73 62032.33,
>    178452.91 62029.35,
>    178448.3 62026.56,
>    178445.22 62025.7,
>    178429.07 62026.53,
>    178424.89 62023.48,
>    178422.86 62005.51,
>    178421.81 61980.76,
>    178421.89 61962.48,
>    178423.58 61949.11,
>    178430.17 61919.22,
>    178433.41 61907.8,
>    178443.14 61886.28,
>    178468.73 61806.63,
>    178479.68 61780.1,
>    178494.89 61734.32,
>    178511.46 61692.33,
>    178518.28 61666.62,
>    178533.34 61622.92,
>    178544.99 61595.95,
>    178567.61 61537.18,
>    178574.74 61521.82,
>    178583.21 61495.5,
>    178598.58 61458.21,
>    178614.24 61428.39,
>    178650.58 61354,
>    178658.76 61340.98,
>    178665.02 61327.95,
>    178674.8 61313.2,
>    178700.24 61274.86,
>    178719.61 61242.68,
>    178738.79 61214.38,
>    178758.9 61190.94,
>    178770.37 61180.47,
>    178789.81 61169.58,
>    178812.25 61159.56,
>    178824.56 61155.6,
>    178835.46 61148.73,
>    178850.86 61141.32,
>    178877.94 61132.47,
>    178905.39 61124.35,
>    178921.76 61117.34,
>    178937.67 61111.55,
>    178980.84 61104.68,
>    179007.68 61098.47,
>    179056.28 61084.32,
>    179128.36 61065.61,
>    179202.82 61047.78,
>    179276.21 61027.13,
>    179472.42 60961.08,
>    179529.07 60936.85,
>    179542.88 60927.94,
>    179549.41 60922,
>    179555.08 60911.73,
>    179559.44 60900.77,
>    179562.28 60889.12,
>    179562.47 60877.05,
>    179560.63 60866.89,
>    179560.7 60863.09,
>    179562.37 60857.61,
>    179565.71 60846.64,
>    179567.54 60832.84,
>    179566.44 60823.14,
>    179565.06 60818.43,
>    179549.81 60764.67,
>    179550.31 60758.45,
>    179546.67 60734.77,
>    179549.49 60731.03,
>    179557.54 60733.31,
>    179561.13 60738.93,
>    179564.21 60739.89,
>    179566.89 60745.6,
>    179572.89 60748.67,
>    179575.31 60751.42,
>    179578.26 60756.38,
>    179578.33 60762.32,
>    179583.95 60763.05,
>    179583.19 60771.19,
>    179588.15 60772.63,
>    179588.19 60782.91,
>    179593.07 60784.13,
>    179589.87 60805.68,
>    179595.07 60815.48,
>    179600.01 60822.77,
>    179600.24 60826.95,
>    179602.21 60832.23,
>    179607.32 60835.03,
>    179620.58 60838.4,
>    179635.67 60841.41,
>    179651.26 60843.16,
>    179667.47 60843.16,
>    179681.53 60838.67,
>    179704.27 60828.05,
>    179724.08 60814.96,
>    179741.93 60801.19,
>    179753.86 60790.42,
>    179763.48 60779.45,
>    179766.88 60773.18,
>    179767.07 60771.12,
>    179762.6 60765.99,
>    179766.21 60747.38,
>    179770.94 60741.75,
>    179776.56 60738.66,
>    179779.2 60737.22,
>    179786.44 60742.03,
>    179793.9 60741.33,
>    179799.37 60742.37,
>    179807.42 60735.01,
>    179815.39 60724.84,
>    179811.05 60721.94,
>    179813.76 60715.68,
>    179820.14 60717.55,
>    179826.71 60710.34,
>    179829.53 60708.82,
>    179888.74 60612.93,
>    179947.13 60522.16,
>    179955.61 60507.32,
>    179964.18 60496.92,
>    179973.96 60490.42,
>    179979.79 60485.25,
>    179984.9 60477.61,
>    180001.97 60445.85,
>    180013.27 60430.79,
>    180047.31 60395.4,
>    180054.81 60389.16,
>    180071.26 60381.38,
>    180083.39 60373.8,
>    180100.66 60358.77,
>    180110.87 60348.94,
>    180115.99 60340.86,
>    180120.92 60330.67,
>    180131.3 60290.31,
>    180141.88 60252.91,
>    180145.41 60243.95,
>    180170.92 60161.14,
>    180176.4 60146.3,
>    180191.39 60114.53,
>    180200.97 60096.39,
>    180212.16 60078.29,
>    180218.27 60071.66,
>    180235.86 60057.92,
>    180243.95 60050.52,
>    180249.63 60043.36,
>    180259.04 60025.98,
>    180266.35 60007.91,
>    180274.4 59993.5,
>    180281.06 59983.38,
>    180289.52 59973.93,
>    180315.7 59949.8,
>    180329.09 59939.62,
>    180338.31 59934.05,
>    180354.18 59926.34,
>    180362.13 59924.76,
>    180369.12 59926.79,
>    180375.15 59931.75,
>    180383 59935.53,
>    180388.11 59938.77,
>    180396.42 59949.49,
>    180400.6 59946.77,
>    180405.01 59956.2,
>    180407.23 59954.8,
>    180409.16 59952.08,
>    180431.99 59882.17,
>    180489.59 59719.98,
>    180516.16 59668.73,
>    180544.76 59619.86,
>    180564.25 59578.8,
>    180573.7 59551.7,
>    180580.79 59525.35,
>    180588.37 59505.63,
>    180604.12 59473.13,
>    180622.29 59445.18,
>    180631.91 59429.05,
>    180637.83 59412.74,
>    180656.17 59339.6,
>    180669.41 59299.14,
>    180679.64 59275.76,
>    180684.28 59266.53,
>    180686.05 59263.02,
>    180697.93 59246.56,
>    180747.67 59189.18,
>    180759.28 59178.74,
>    180772.99 59167.85,
>    180785.83 59162,
>    180798.34 59158.18,
>    180813.74 59154.37,
>    180832.3 59151.97,
>    180855.11 59147.46,
>    180861.98 59142.9,
>    180866.27 59138.42,
>    180872.11 59130.67,
>    180909.6 59075.52,
>    180922.07 59061.58,
>    180930.79 59055.13,
>    180943.08 59050.38,
>    180953.99 59047.52,
>    180964.78 59041.87,
>    180975.83 59032.72,
>    180985.33 59022.92,
>    181000.57 59002.51,
>    181013.17 58990.67,
>    181024.71 58983.21,
>    181035.92 58978.57,
>    181050.06 58975.38,
>    181076.88 58972.92,
>    181087.67 58970.91,
>    181099.7 58966.76,
>    181122.01 58955.77,
>    181146.14 58947.76,
>    181157.78 58942.19,
>    181167.75 58934.2,
>    181177.2 58925.53,
>    181192.11 58906.31,
>    181233.44 58862,
>    181243.56 58849.94,
>    181262.63 58824.07,
>    181269.81 58813.01,
>    181278.57 58797.49,
>    181286.69 58781,
>    181294.3 58748.54,
>    181297.43 58721.7,
>    181293.95 58693.46,
>    181279.45 58644.96,
>    181271.49 58621.9,
>    181245.24 58566.88,
>    181234.84 58548.6,
>    181226.25 58524.73,
>    181207.37 58438.02,
>    181193.75 58388.29,
>    181183.54 58357.62,
>    181169.67 58302.15,
>    181163.49 58274.38,
>    181159.28 58246,
>    181147.89 58107.32,
>    181147.06 57991.43,
>    181148.81 57965.73,
>    181150.16 57909.44,
>    181151.32 57888.4,
>    181156.51 57844.11,
>    181163.68 57796.12,
>    181177.45 57719.23,
>    181202.13 57619.71,
>    181224.13 57544.69,
>    181254.77 57474.29,
>    181263.88 57451,
>    181283.27 57406.83,
>    181308.26 57364,
>    181321.91 57342.42,
>    181347.77 57297.32,
>    181375.92 57255.37,
>    181421.33 57195.25,
>    181465.37 57132.96,
>    181498.7 57089.91,
>    181515.73 57069.3,
>    181532.65 57051.11,
>    181546.73 57031.97,
>    181578.04 56994.2,
>    181592.81 56974.79,
>    181606.21 56955.33,
>    181617.19 56937.88,
>    181636.62 56901.76,
>    181644.91 56883.67,
>    181651.88 56866.37,
>    181658.28 56848.86,
>    181667.09 56820.5,
>    181670.79 56812.22,
>    181673.84 56805.41,
>    181679.95 56789.22,
>    181716.63 56710.19,
>    181727.56 56693.78,
>    181739.09 56674.37,
>    181760.36 56634.75,
>    181770.08 56621.43,
>    181806.52 56563.56,
>    181822.11 56541.55,
>    181853.29 56501.39,
>    181867.37 56484.47,
>    181915.43 56418.28,
>    181934.25 56389.84,
>    181989.88 56324.58,
>    182008.53 56304.44,
>    182028.06 56281.36,
>    182044.18 56260.03,
>    182077.17 56220.41,
>    182095.42 56200.24,
>    182149.64 56149,
>    182152.81 56145.38,
>    182165.25 56131.22,
>    182181.63 56109.2,
>    182226.84 56059.65,
>    182240.13 56042.18,
>    182249.84 56026.52,
>    182262.23 56004.41,
>    182269.66 55988.27,
>    182279.11 55970.17,
>    182302.19 55934.92,
>    182312.97 55920.44,
>    182334.13 55894.79,
>    182356.12 55865.14,
>    182427.98 55779.79,
>    182498.67 55702.44
> )
>
>>
>> Michael Michaud wrote:
>>> Hi Martin,
>>>
>>> Thanks for the precise answer.
>>> I do not know a good buffer algorithm but I made some further tests
>>> which show there is place for improvements with the excellent stuff
>>> you recently added.
>>>
>>> I created a simple linestring : length = 25000 m, number of segments
>>> = 1000
>>>
>>> Trying to create a buffer at a distance of 10000 m ended with a
>>> heapspace exception (took more than 256 Mo !) after more than 4 mn
>>> of intensive computation !
>>>
>>> The other way is :
>>> - decompose into segments : less than 1 s
>>> - create individual buffers : openjump says 8 s but I think it
>>> includes redrawing
>>> - cascaded union of resulting buffer : 6 s (less than 50 Mo)
>>>
>>> hope that helps
>>>
>>> Michael
>>>
>>>
>>>
>>> Martin Davis a écrit :
>>>> The reason for this is that as the buffer size gets bigger, the
>>>> "raw offset curve" that is initially created prior to extracting
>>>> the buffer outline gets more and more complex.  Concave angles in
>>>> the input geometry result in perpendicular "closing lines" being
>>>> created, which usually intersect other offset lines.  The longer
>>>> the perpendicular line, the more other lines it intersects, and
>>>> hence the more noding and topology analysis has to be performed.  
>>>> (I haven't found any good way of building the raw offset curve to
>>>> avoid or reduce this problem - if anyone has any ideas I'd be
>>>> interested to hear them).
>>>>
>>>> There's several ways that I've tried to reduce this problem:
>>>>
>>>> - compute the buffer in a series of steps, using an increasing
>>>> series of buffer distances which add up to the desired distance.  
>>>> Each successive buffer gets smoother, which makes the subsequent
>>>> buffers run faster.  It may only be necessary to iterate say 3
>>>> times to get a good result.  The trick of course is to pick the
>>>> right distances.
>>>>
>>>> - simplify the input geometry using DP, and a tolerance of say 2%
>>>> of the buffer distance
>>>>
>>>> - A better way of simplifying I've been experimenting with only
>>>> simplifies *outwards*.  This does 2 things - it reduces concavity
>>>> (which is the source of the problem), and it avoid "losing" convex
>>>> protrubances (which DP can often delete or alter).  Convex
>>>> protrubances are the primary influence on the shape of the
>>>> resulting buffer, so it is important to preserve them.  (Currently
>>>> this code is in alpha only - but I can provide it if anyone's
>>>> interested)
>>>>
>>>> Martin
>>>>
>>>> Michael Michaud wrote:
>>>>> Hi,
>>>>>
>>>>> I noticed that OpenJUMP Buffer plugin performance decreases
>>>>> dramatically if a large buffer size is used :
>>>>> For a map with  rivers having vertices every few meters, I get :
>>>>>
>>>>> buffer =  25 m :     7 s
>>>>> buffer =  50 m :    16 s
>>>>> buffer = 100 m :    48 s
>>>>> buffer = 200 m : 2m 59 s
>>>>>
>>>>> The plugin uses the BufferOp class. I have no idea why a large
>>>>> buffer should take longer than a small one, and I don't know if
>>>>> there is a better way to compute a buffer.
>>>>>
>>>>> Any idea ?
>>>>>
>>>>> Michaël
>>>>>
>>>>> _______________________________________________
>>>>> jts-devel mailing list
>>>>> [hidden email]
>>>>> http://lists.refractions.net/mailman/listinfo/jts-devel
>>>>>
>>>>
>>>
>>> _______________________________________________
>>> jts-devel mailing list
>>> [hidden email]
>>> http://lists.refractions.net/mailman/listinfo/jts-devel
>>>
>>
>
> _______________________________________________
> jts-devel mailing list
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
>

--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Buffer operation performance

Martin Davis
In reply to this post by michaelm-2
Good stuff - look forward to seeing the results.

As I said, an important piece of this puzzle is being able to decide
automatically when to cut over from the standard "monolithic" buffer
approach to the "partitioned" approach.  The catch is that the
inefficiency is caused by the local details of how complex the shape of
the input linework is.  I haven't yet found a good way of measuring this
local complexity and relating it to the buffer size.

I still think the "outer simplification" ideas has some legs on it.  
Would you be interested in trying out this approach with my alpha code?

Michael Michaud wrote:

> Hi,
>
>> Very interesting, Michael.  This "partitioned buffering" approach
>> seems pretty viable as well.  (It would also parallel nicely in a
>> multi-core environment!)
> Yes, but I'm not sure individual buffering takes much time compared to
> union operation (it would need more precise measurements)
>>
>> One limitation is that it's harder (or maybe impossible) to provide
>> different join styles using PB - but that is probably a minor price
>> to pay.
> Right, I did not think about it.
> Partitioned buffering could be made available for "round" buffering only.
>> Now, the challenge is to establish when to use the various
>> approaches.  Is it always better to use PB?  Or is there some cutover
>> point between the current buffer algorithm and PB?  This is one thing
>> which has held me back from offering these other options in JTS.  The
>> choice of which method to use really needs to be performed
>> automatically by the library.
> I agree that a single test is not enough to make decision. To complete
> the test I'll try to measure the difference for
> 1 / 10 / 100 / 1000  segments
> and for a buffer distance equals to
> 0.01x / 0.1x / 1x / 10x / 100x / 1000x the mean segment length
> It would also be interesting to measure improvements for polygon
> buffering
>> Can you send me your test dataset?
> Here is the 1031 points wkt of the linestring (I tried a 10000 buffer) :
>
> LINESTRING (
>    168000 75099.09,
>    168019.98 75079.81,
>    168058.38 75051.63,
>    168076.91 75045.01,
>    168096.34 75039.38,
>    168127.45 75021.15,
>    168167.12 74999.39,
>    168180.16 74991.79,
>    168192.45 74982.57,
>    168210.71 74972.38,
>    168227.46 74964.28,
>    168245.93 74951.24,
>    168256.76 74941.96,
>    168281.34 74925.48,
>    168317.49 74903.93,
>    168347.95 74893.42,
>    168359.81 74886.5,
>    168376.8 74873.61,
>    168396.02 74862.35,
>    168413.3 74857.15,
>    168427.85 74850.68,
>    168442.62 74840.26,
>    168472.25 74826.59,
>    168481.69 74819.74,
>    168509.94 74810.66,
>    168536.95 74796.66,
>    168568.02 74785.98,
>    168591.85 74776.06,
>    168620.28 74763.11,
>    168671.46 74735.14,
>    168702.77 74718.98,
>    168760.54 74684.78,
>    168790.68 74665.69,
>    168818.45 74651.59,
>    168839.39 74639.33,
>    168883.15 74612.66,
>    168904.37 74597.07,
>    168925.39 74585.69,
>    168947.76 74575.73,
>    168972.48 74562.28,
>    168996.29 74552.47,
>    169017.6 74547.3,
>    169028.94 74543.14,
>    169037.2 74537.14,
>    169052.36 74529.73,
>    169079 74518.34,
>    169124.49 74504.73,
>    169146.2 74496.7,
>    169160.17 74490.57,
>    169176.13 74483.44,
>    169186.06 74479.41,
>    169212.16 74474.08,
>    169227.63 74467.66,
>    169260.82 74439.9,
>    169276.59 74427.91,
>    169290.7 74415.52,
>    169305.05 74405.76,
>    169323.69 74389.86,
>    169339.44 74377.81,
>    169357.33 74366.16,
>    169414.53 74321.51,
>    169474.05 74282.78,
>    169489.52 74270.72,
>    169579.01 74223.09,
>    169604.78 74210.14,
>    169619.7 74199.66,
>    169629.14 74195.23,
>    169643.34 74192.88,
>    169659.96 74185.19,
>    169678.7 74177.96,
>    169693.96 74170.68,
>    169713.35 74162.96,
>    169739.08 74156.44,
>    169768.36 74152.97,
>    169799.54 74148.44,
>    169838.66 74144.65,
>    169885.9 74150.01,
>    169971.44 74167,
>    170024.34 74173.38,
>    170076.65 74178.2,
>    170094.55 74180.82,
>    170113.44 74185.45,
>    170132 74188.82,
>    170175.93 74192.59,
>    170205.21 74192.5,
>    170218.75 74191.32,
>    170233.84 74190.88,
>    170277.47 74190.61,
>    170316.34 74191.58,
>    170333.36 74190.76,
>    170348.04 74190.9,
>    170363.55 74188.79,
>    170393.8 74188.48,
>    170412.8 74190.33,
>    170431.6 74191.32,
>    170484.03 74196.25,
>    170516.54 74191.7,
>    170531.41 74190.82,
>    170558.77 74188.35,
>    170572.36 74182.24,
>    170583.63 74178.45,
>    170600.48 74171.3,
>    170638.11 74160.2,
>    170657.84 74153.73,
>    170670.51 74148.4,
>    170720.33 74125.39,
>    170749.99 74113.62,
>    170792.93 74100.61,
>    170835.33 74092.07,
>    170849.17 74088.43,
>    170863.59 74083.87,
>    170899.93 74068.73,
>    170939 74058.28,
>    170966.12 74049,
>    170989.65 74044.69,
>    171001.68 74041.17,
>    171028.85 74030.8,
>    171053.39 74019.23,
>    171081.07 74007.94,
>    171102.14 74002.15,
>    171117.33 73997.16,
>    171142.09 73992.68,
>    171151.89 73991.51,
>    171198.97 73979.07,
>    171232.93 73972.48,
>    171243.99 73969.27,
>    171268.54 73966.34,
>    171301.94 73958.88,
>    171310.31 73958.18,
>    171318.46 73959.11,
>    171334.75 73959.34,
>    171360.8 73955.36,
>    171390.53 73952.29,
>    171407.27 73951.84,
>    171454.52 73946.27,
>    171532.91 73942.72,
>    171559.19 73942.74,
>    171586.59 73941.28,
>    171606.07 73941.02,
>    171632.04 73942.05,
>    171648.7 73941.96,
>    171664.69 73940.23,
>    171703.79 73932.17,
>    171725.83 73923.91,
>    171786.57 73908.02,
>    171811.39 73902.01,
>    171862.01 73883.19,
>    171881.03 73877.34,
>    171904.53 73869.1,
>    171924.75 73861,
>    171942.63 73855.66,
>    171967.52 73846.29,
>    171989.09 73837.11,
>    172048.82 73819.06,
>    172065.95 73811.98,
>    172081.18 73803.66,
>    172112.57 73792.61,
>    172141.47 73781.54,
>    172199.07 73754.61,
>    172220.41 73746.36,
>    172258.74 73737.64,
>    172308.01 73719.25,
>    172327.08 73714.16,
>    172341.9 73711.22,
>    172357.39 73706.04,
>    172373.89 73699.51,
>    172387.83 73695.45,
>    172458.09 73667.62,
>    172487.31 73654.97,
>    172501.31 73647.79,
>    172537.91 73627.37,
>    172586.45 73599.14,
>    172602.33 73591.61,
>    172651.56 73576.46,
>    172666.88 73571.13,
>    172692.9 73558.6,
>    172709.76 73549.34,
>    172740.08 73534.5,
>    172760 73523.41,
>    172776.57 73511.27,
>    172785.72 73506.09,
>    172795.79 73501.6,
>    172806.59 73500.89,
>    172817.66 73498.13,
>    172826.77 73492.83,
>    172843.25 73480.68,
>    172861.8 73468.4,
>    172871.7 73463.21,
>    172918.85 73435.31,
>    172934.75 73420.57,
>    172999.52 73375.23,
>    173052.08 73332.33,
>    173061.72 73326.05,
>    173083.73 73320.93,
>    173102.39 73312.88,
>    173123.43 73301.81,
>    173152.75 73282.68,
>    173209.2 73242.11,
>    173228.86 73230.1,
>    173238.95 73224.75,
>    173249.15 73217.87,
>    173276.84 73196.72,
>    173338.16 73146.47,
>    173348.23 73139,
>    173384.35 73114.23,
>    173430.5 73084.55,
>    173440.47 73076.9,
>    173450.62 73072.16,
>    173469.56 73061.59,
>    173479.51 73055.68,
>    173497.59 73042.86,
>    173507.16 73038.03,
>    173528.29 73029.23,
>    173559.43 73019.59,
>    173569.08 73014.36,
>    173587.09 73001.77,
>    173674.43 72947.17,
>    173701.14 72928.72,
>    173709.48 72921.58,
>    173724.28 72906.98,
>    173739.66 72893.97,
>    173749.59 72890.25,
>    173775.23 72869.71,
>    173785.3 72863.62,
>    173818.13 72836.11,
>    173827.45 72829.13,
>    173856.34 72812.25,
>    173865.78 72805.46,
>    173875.48 72801,
>    173884.38 72795.17,
>    173917.08 72767.14,
>    173926.86 72762.21,
>    173937.93 72763.44,
>    173967.05 72749.76,
>    173974.73 72741.71,
>    173983.02 72734.67,
>    173992.68 72727.88,
>    174001.83 72722.59,
>    174030.88 72707.71,
>    174051.2 72698.45,
>    174071.1 72687.2,
>    174081.39 72683.5,
>    174089.48 72685.37,
>    174109.71 72677.64,
>    174119.75 72678.34,
>    174128.19 72671.13,
>    174137.3 72664.75,
>    174146.85 72659.03,
>    174157.34 72654.76,
>    174165.35 72648.08,
>    174184.53 72637.86,
>    174193.88 72633.25,
>    174204.59 72631.67,
>    174214.39 72625.59,
>    174224.21 72621.86,
>    174234.42 72616.88,
>    174243.59 72610.11,
>    174253.83 72605.56,
>    174274.88 72598.13,
>    174283.78 72592.38,
>    174300.78 72576.21,
>    174308.71 72569.51,
>    174359.48 72528.51,
>    174398.79 72492.94,
>    174405.5 72484.28,
>    174411.53 72474.83,
>    174419.13 72466.61,
>    174427.17 72459.43,
>    174458.79 72425.51,
>    174464.86 72417.51,
>    174477.4 72397.91,
>    174481.96 72388.65,
>    174486.63 72377.13,
>    174498.42 72343.67,
>    174502.95 72333.07,
>    174526.81 72283.89,
>    174536.17 72262.58,
>    174553.04 72234.6,
>    174561.1 72226.58,
>    174567.54 72216.87,
>    174571.16 72206.15,
>    174571.79 72195.91,
>    174574.97 72185.45,
>    174581.47 72175.77,
>    174590.94 72156.19,
>    174598.5 72148.42,
>    174604.26 72138.96,
>    174614.61 72119.31,
>    174617.86 72109.68,
>    174618.88 72098.83,
>    174620.62 72088.92,
>    174623.58 72079.08,
>    174652.24 72019.39,
>    174672.82 71980,
>    174679.52 71957.62,
>    174688.5 71937.78,
>    174699.09 71920.14,
>    174705.95 71911.18,
>    174713.49 71904.44,
>    174718.78 71894.98,
>    174725.86 71874.85,
>    174732.59 71864.99,
>    174738.83 71856.73,
>    174746.65 71848.06,
>    174756.08 71841.4,
>    174760.53 71831.95,
>    174772.07 71813.16,
>    174786.69 71793.3,
>    174801.7 71775.1,
>    174809.49 71766.29,
>    174826.27 71749.24,
>    174859.56 71717.58,
>    174866.89 71709.21,
>    174880.19 71691.3,
>    174887 71683.71,
>    174895.32 71676.12,
>    174904.3 71671.55,
>    174913.56 71664.66,
>    174920.92 71656.83,
>    174927.07 71648.48,
>    174935.22 71640.33,
>    174943.94 71634.84,
>    174954.01 71631.94,
>    174970.02 71616.71,
>    174986.09 71603.63,
>    174992.75 71595.93,
>    174997.89 71586.08,
>    175002.77 71574.24,
>    175007.92 71566.95,
>    175021.39 71554.85,
>    175026.4 71547.19,
>    175030.56 71538.06,
>    175044.96 71517.18,
>    175060.26 71493.05,
>    175077.44 71472.78,
>    175094.51 71455.41,
>    175111.47 71442.59,
>    175143.7 71420.42,
>    175156.81 71408.96,
>    175188.77 71371.82,
>    175267.54 71302.71,
>    175284.55 71286.73,
>    175299.75 71269.13,
>    175358.64 71206.84,
>    175396.74 71163.01,
>    175411.28 71150.26,
>    175442.64 71127.33,
>    175457.59 71115.13,
>    175500.48 71075.17,
>    175523.01 71052.94,
>    175566.34 71002.67,
>    175585.5 70982.26,
>    175601.18 70968.3,
>    175635.48 70940.41,
>    175645.97 70928.51,
>    175657.05 70917.56,
>    175669.35 70907.51,
>    175680.17 70899.55,
>    175708.08 70884.05,
>    175719.1 70875.15,
>    175728.9 70865.65,
>    175748.84 70840.67,
>    175760.26 70828.78,
>    175772.96 70816.86,
>    175797.59 70795.41,
>    175820.4 70771.58,
>    175830.81 70758.94,
>    175887.26 70702.46,
>    175939.77 70657.23,
>    175964.24 70638.02,
>    175991.59 70619.95,
>    176055.64 70575.16,
>    176079.86 70557.44,
>    176099.14 70540.66,
>    176111.84 70528.48,
>    176124.85 70521.62,
>    176138.75 70516.52,
>    176151.24 70509.62,
>    176162.55 70497.52,
>    176175.72 70481.45,
>    176206.32 70435.37,
>    176222.38 70407.62,
>    176237.17 70375.68,
>    176249.61 70346.63,
>    176265.36 70306.53,
>    176289.61 70252.4,
>    176304.59 70228.36,
>    176325.15 70199.27,
>    176346.33 70164.59,
>    176363.73 70134.77,
>    176376.6 70110.47,
>    176398.34 70074.51,
>    176425.63 70037.09,
>    176461.29 69993.33,
>    176538.04 69890.48,
>    176611.31 69795.95,
>    176642.89 69757.61,
>    176653.34 69740.97,
>    176667.53 69705.46,
>    176694.82 69587.45,
>    176710.85 69542.86,
>    176729.65 69499.4,
>    176750.13 69456.2,
>    176759.92 69440.95,
>    176765.47 69440.79,
>    176769.55 69437.84,
>    176775.95 69428.35,
>    176816.39 69344.34,
>    176838.52 69303.52,
>    176841.61 69288.41,
>    176847.4 69271.24,
>    176853.88 69257.39,
>    176866.38 69224.77,
>    176884.05 69191.75,
>    176908.14 69156.34,
>    176932.6 69124.48,
>    176941.5 69109.01,
>    176952.75 69087.58,
>    176962.34 69066.66,
>    177011.99 68975.48,
>    177047.55 68904.3,
>    177075.71 68857.75,
>    177086.06 68846.79,
>    177093.45 68840.28,
>    177113.15 68819.4,
>    177125.53 68803.37,
>    177145.01 68774.81,
>    177162.81 68744.93,
>    177175.04 68722.96,
>    177183.89 68711.15,
>    177195.55 68697.11,
>    177206.23 68681.8,
>    177232.19 68640.09,
>    177250.19 68607.22,
>    177286.85 68548.09,
>    177331.39 68483.17,
>    177380.45 68419.09,
>    177385.25 68410.57,
>    177415.26 68372.12,
>    177436.17 68348.33,
>    177461.11 68318.37,
>    177477.56 68301.44,
>    177486.38 68290.59,
>    177497.15 68278.98,
>    177504.31 68271.41,
>    177514.19 68263.47,
>    177531.39 68251.34,
>    177547.84 68236.75,
>    177556 68228.1,
>    177562.23 68220.36,
>    177604.15 68155.74,
>    177608.84 68145.94,
>    177623.1 68120.44,
>    177629.69 68105.2,
>    177650.02 68073.08,
>    177654.45 68065.11,
>    177658.56 68050.95,
>    177662.82 68042,
>    177667.36 68024.84,
>    177671 68015.54,
>    177681.4 67994.43,
>    177693.6 67949.74,
>    177703.26 67919.53,
>    177706.63 67911.94,
>    177714 67899.68,
>    177716.44 67893.18,
>    177718.91 67884.28,
>    177720.55 67871.14,
>    177724.45 67851.53,
>    177727.55 67839.84,
>    177728.77 67829,
>    177730.93 67818.94,
>    177739.33 67800.24,
>    177749.1 67785.58,
>    177752.04 67778.56,
>    177753.75 67770.32,
>    177746.91 67735.03,
>    177749.64 67718.67,
>    177751.88 67673.54,
>    177757.49 67617.74,
>    177766.81 67556.29,
>    177774.75 67524.5,
>    177789.56 67484.51,
>    177799.11 67451.34,
>    177808.39 67423.01,
>    177818.88 67380.1,
>    177824.98 67359.84,
>    177834.3 67337.45,
>    177842.13 67315.31,
>    177848.2 67276,
>    177855.87 67246.99,
>    177863.04 67223.1,
>    177875.61 67190.41,
>    177879.98 67179.07,
>    177883.21 67166.85,
>    177884.93 67160.33,
>    177887.27 67151.44,
>    177898.41 67109.32,
>    177909.04 67078.94,
>    177913.49 67064.05,
>    177918.13 67052.99,
>    177923.74 67042.42,
>    177929.09 67035.22,
>    177930.69 67029.22,
>    177930.66 67018.64,
>    177941.76 66972.23,
>    177945.36 66939.94,
>    177951.27 66907.91,
>    177952.98 66901.54,
>    177955.94 66887.96,
>    177959.41 66872.07,
>    177966.58 66851.6,
>    177971.62 66836.37,
>    177985.44 66786.6,
>    177989.64 66763.17,
>    177994.85 66733.27,
>    178001.66 66699.61,
>    178008.6 66667.66,
>    178013.75 66647.23,
>    178016.34 66636.11,
>    178017.08 66605.55,
>    178014.57 66554.14,
>    178010.24 66506.37,
>    178009.32 66465.24,
>    178009.96 66441.56,
>    178005.85 66419.82,
>    178002.49 66387.67,
>    177998.46 66338.04,
>    177993.35 66326.83,
>    177986.72 66324.9,
>    177985.23 66322.04,
>    177985.54 66319.15,
>    177989.56 66306.9,
>    177993.67 66298.82,
>    177995.86 66291.86,
>    177995.66 66289.33,
>    177992.99 66284.06,
>    177993.44 66281.23,
>    177992.3 66260.72,
>    177990.84 66248.64,
>    177981.56 66172.16,
>    177977.76 66141.43,
>    177974.54 66123.9,
>    177971.77 66108.86,
>    177967.86 66094.01,
>    177966.43 66092.26,
>    177967.2 66087.09,
>    177966.9 66082.9,
>    177966.02 66080.43,
>    177964.2 66078.21,
>    177963.59 66075.21,
>    177964.74 66064.46,
>    177964.35 66055.86,
>    177963.28 66052.01,
>    177959.34 66029.13,
>    177960.61 66022.97,
>    177959.04 66018.46,
>    177956.76 66015.2,
>    177956.89 66012.74,
>    177958.77 66009.48,
>    177959.85 66004.68,
>    177957.01 65995.03,
>    177957.25 65986.78,
>    177956.14 65982.15,
>    177953.29 65979.39,
>    177952.17 65976.64,
>    177957.95 65969.74,
>    177959.19 65962.62,
>    177957.37 65900.17,
>    177953.57 65856.26,
>    177953.93 65817.35,
>    177953.88 65813.27,
>    177955.48 65807.19,
>    177956.46 65799.14,
>    177955.03 65777.69,
>    177956.4 65734.55,
>    177956.23 65719.34,
>    177953.1 65713.03,
>    177954.45 65705.09,
>    177957.1 65697.01,
>    177956.84 65685.15,
>    177959 65679.49,
>    177959.49 65671.26,
>    177961.48 65638.16,
>    177968.9 65592.02,
>    177975.6 65560.06,
>    177979.15 65534.98,
>    177979.38 65495.95,
>    177982.31 65407.44,
>    177984.68 65358.91,
>    177987.11 65325.67,
>    177986.1 65293.15,
>    177989.96 65264.47,
>    177995.42 65209.31,
>    178001.47 65168.9,
>    178008.8 65113.21,
>    178013.31 65003.86,
>    178012.51 64952.06,
>    178009.63 64847.94,
>    178017.62 64682.43,
>    178021.64 64541.27,
>    178023.13 64396.67,
>    178027.75 64137.61,
>    178025.76 64028.45,
>    178020.43 63910.8,
>    178020.72 63849.5,
>    178029.19 63778.85,
>    178032.16 63763.6,
>    178032.6 63749.92,
>    178030.32 63733.73,
>    178026.47 63721.29,
>    178021.04 63709.32,
>    178016.35 63702.9,
>    178011.71 63699.25,
>    178006.61 63698.96,
>    178008.27 63678.14,
>    178009.61 63661.41,
>    178024.73 63657.03,
>    178035.53 63651.2,
>    178042.7 63644.43,
>    178048.96 63635.33,
>    178054.42 63625.44,
>    178066.74 63513.4,
>    178079.29 63350.15,
>    178113.91 63043.92,
>    178125.17 62967.61,
>    178139.81 62861.77,
>    178160.03 62739.24,
>    178166.8 62690.71,
>    178180.6 62598.21,
>    178196.38 62478.9,
>    178205.95 62429.83,
>    178215.68 62390.38,
>    178225.95 62355.56,
>    178234.91 62330.13,
>    178243.99 62312.58,
>    178252.42 62300.17,
>    178258.59 62293.76,
>    178271.74 62267.81,
>    178278.87 62259.41,
>    178281.2 62257.11,
>    178291.29 62241.06,
>    178296.59 62234.42,
>    178300.59 62233.22,
>    178306.14 62233.23,
>    178313.85 62230.84,
>    178318.53 62228.61,
>    178323.72 62225.14,
>    178329.38 62219.28,
>    178332.15 62217.39,
>    178339.35 62217.49,
>    178342.7 62218.66,
>    178343.51 62221.14,
>    178348.34 62226.92,
>    178351.79 62228.99,
>    178353.88 62228.77,
>    178354.79 62226.72,
>    178351.18 62221.84,
>    178353.07 62216.87,
>    178353.25 62214.12,
>    178355.63 62211.13,
>    178358.36 62209.3,
>    178361.9 62208.86,
>    178362.76 62206.43,
>    178361.97 62203.62,
>    178363.58 62201.57,
>    178374.53 62193.67,
>    178381.63 62189.79,
>    178385.43 62189.76,
>    178389.45 62192.04,
>    178392.01 62192.3,
>    178393.18 62189.44,
>    178391.57 62187.72,
>    178390.78 62185.63,
>    178399.88 62175.2,
>    178402.36 62174.4,
>    178407.71 62177.98,
>    178413.7 62175.14,
>    178419.05 62176.68,
>    178422.21 62174.44,
>    178423.73 62172.07,
>    178423.57 62169.19,
>    178421.96 62166.64,
>    178418.94 62165,
>    178415.85 62165.96,
>    178412.1 62170.44,
>    178409.48 62169.88,
>    178407.72 62163.55,
>    178411.95 62162.4,
>    178418.53 62156.4,
>    178423.46 62150.54,
>    178426.56 62148.62,
>    178429.7 62149.94,
>    178432.71 62149.19,
>    178435.99 62144.98,
>    178436.76 62142.14,
>    178439.36 62139.27,
>    178442.84 62138.83,
>    178445.4 62135.85,
>    178447.6 62128.51,
>    178451.73 62120.49,
>    178454.01 62118.47,
>    178457.62 62116.53,
>    178458.69 62112.83,
>    178461.1 62111.48,
>    178464.42 62110.72,
>    178466.21 62108.01,
>    178467.1 62104.31,
>    178465.62 62097.07,
>    178468.42 62087.79,
>    178468.55 62082.53,
>    178466.59 62081.04,
>    178458.84 62079.15,
>    178456.58 62076.29,
>    178455.86 62072.53,
>    178457.63 62070.82,
>    178458.45 62068.91,
>    178456.51 62066.55,
>    178459.35 62062.85,
>    178452.82 62060.08,
>    178449.82 62056.67,
>    178450.62 62053.45,
>    178453.32 62051.97,
>    178455.16 62049.21,
>    178454.93 62047.57,
>    178452.23 62046.52,
>    178450.69 62043.67,
>    178451.11 62040.83,
>    178454.12 62039.86,
>    178455.53 62036.39,
>    178454.73 62032.33,
>    178452.91 62029.35,
>    178448.3 62026.56,
>    178445.22 62025.7,
>    178429.07 62026.53,
>    178424.89 62023.48,
>    178422.86 62005.51,
>    178421.81 61980.76,
>    178421.89 61962.48,
>    178423.58 61949.11,
>    178430.17 61919.22,
>    178433.41 61907.8,
>    178443.14 61886.28,
>    178468.73 61806.63,
>    178479.68 61780.1,
>    178494.89 61734.32,
>    178511.46 61692.33,
>    178518.28 61666.62,
>    178533.34 61622.92,
>    178544.99 61595.95,
>    178567.61 61537.18,
>    178574.74 61521.82,
>    178583.21 61495.5,
>    178598.58 61458.21,
>    178614.24 61428.39,
>    178650.58 61354,
>    178658.76 61340.98,
>    178665.02 61327.95,
>    178674.8 61313.2,
>    178700.24 61274.86,
>    178719.61 61242.68,
>    178738.79 61214.38,
>    178758.9 61190.94,
>    178770.37 61180.47,
>    178789.81 61169.58,
>    178812.25 61159.56,
>    178824.56 61155.6,
>    178835.46 61148.73,
>    178850.86 61141.32,
>    178877.94 61132.47,
>    178905.39 61124.35,
>    178921.76 61117.34,
>    178937.67 61111.55,
>    178980.84 61104.68,
>    179007.68 61098.47,
>    179056.28 61084.32,
>    179128.36 61065.61,
>    179202.82 61047.78,
>    179276.21 61027.13,
>    179472.42 60961.08,
>    179529.07 60936.85,
>    179542.88 60927.94,
>    179549.41 60922,
>    179555.08 60911.73,
>    179559.44 60900.77,
>    179562.28 60889.12,
>    179562.47 60877.05,
>    179560.63 60866.89,
>    179560.7 60863.09,
>    179562.37 60857.61,
>    179565.71 60846.64,
>    179567.54 60832.84,
>    179566.44 60823.14,
>    179565.06 60818.43,
>    179549.81 60764.67,
>    179550.31 60758.45,
>    179546.67 60734.77,
>    179549.49 60731.03,
>    179557.54 60733.31,
>    179561.13 60738.93,
>    179564.21 60739.89,
>    179566.89 60745.6,
>    179572.89 60748.67,
>    179575.31 60751.42,
>    179578.26 60756.38,
>    179578.33 60762.32,
>    179583.95 60763.05,
>    179583.19 60771.19,
>    179588.15 60772.63,
>    179588.19 60782.91,
>    179593.07 60784.13,
>    179589.87 60805.68,
>    179595.07 60815.48,
>    179600.01 60822.77,
>    179600.24 60826.95,
>    179602.21 60832.23,
>    179607.32 60835.03,
>    179620.58 60838.4,
>    179635.67 60841.41,
>    179651.26 60843.16,
>    179667.47 60843.16,
>    179681.53 60838.67,
>    179704.27 60828.05,
>    179724.08 60814.96,
>    179741.93 60801.19,
>    179753.86 60790.42,
>    179763.48 60779.45,
>    179766.88 60773.18,
>    179767.07 60771.12,
>    179762.6 60765.99,
>    179766.21 60747.38,
>    179770.94 60741.75,
>    179776.56 60738.66,
>    179779.2 60737.22,
>    179786.44 60742.03,
>    179793.9 60741.33,
>    179799.37 60742.37,
>    179807.42 60735.01,
>    179815.39 60724.84,
>    179811.05 60721.94,
>    179813.76 60715.68,
>    179820.14 60717.55,
>    179826.71 60710.34,
>    179829.53 60708.82,
>    179888.74 60612.93,
>    179947.13 60522.16,
>    179955.61 60507.32,
>    179964.18 60496.92,
>    179973.96 60490.42,
>    179979.79 60485.25,
>    179984.9 60477.61,
>    180001.97 60445.85,
>    180013.27 60430.79,
>    180047.31 60395.4,
>    180054.81 60389.16,
>    180071.26 60381.38,
>    180083.39 60373.8,
>    180100.66 60358.77,
>    180110.87 60348.94,
>    180115.99 60340.86,
>    180120.92 60330.67,
>    180131.3 60290.31,
>    180141.88 60252.91,
>    180145.41 60243.95,
>    180170.92 60161.14,
>    180176.4 60146.3,
>    180191.39 60114.53,
>    180200.97 60096.39,
>    180212.16 60078.29,
>    180218.27 60071.66,
>    180235.86 60057.92,
>    180243.95 60050.52,
>    180249.63 60043.36,
>    180259.04 60025.98,
>    180266.35 60007.91,
>    180274.4 59993.5,
>    180281.06 59983.38,
>    180289.52 59973.93,
>    180315.7 59949.8,
>    180329.09 59939.62,
>    180338.31 59934.05,
>    180354.18 59926.34,
>    180362.13 59924.76,
>    180369.12 59926.79,
>    180375.15 59931.75,
>    180383 59935.53,
>    180388.11 59938.77,
>    180396.42 59949.49,
>    180400.6 59946.77,
>    180405.01 59956.2,
>    180407.23 59954.8,
>    180409.16 59952.08,
>    180431.99 59882.17,
>    180489.59 59719.98,
>    180516.16 59668.73,
>    180544.76 59619.86,
>    180564.25 59578.8,
>    180573.7 59551.7,
>    180580.79 59525.35,
>    180588.37 59505.63,
>    180604.12 59473.13,
>    180622.29 59445.18,
>    180631.91 59429.05,
>    180637.83 59412.74,
>    180656.17 59339.6,
>    180669.41 59299.14,
>    180679.64 59275.76,
>    180684.28 59266.53,
>    180686.05 59263.02,
>    180697.93 59246.56,
>    180747.67 59189.18,
>    180759.28 59178.74,
>    180772.99 59167.85,
>    180785.83 59162,
>    180798.34 59158.18,
>    180813.74 59154.37,
>    180832.3 59151.97,
>    180855.11 59147.46,
>    180861.98 59142.9,
>    180866.27 59138.42,
>    180872.11 59130.67,
>    180909.6 59075.52,
>    180922.07 59061.58,
>    180930.79 59055.13,
>    180943.08 59050.38,
>    180953.99 59047.52,
>    180964.78 59041.87,
>    180975.83 59032.72,
>    180985.33 59022.92,
>    181000.57 59002.51,
>    181013.17 58990.67,
>    181024.71 58983.21,
>    181035.92 58978.57,
>    181050.06 58975.38,
>    181076.88 58972.92,
>    181087.67 58970.91,
>    181099.7 58966.76,
>    181122.01 58955.77,
>    181146.14 58947.76,
>    181157.78 58942.19,
>    181167.75 58934.2,
>    181177.2 58925.53,
>    181192.11 58906.31,
>    181233.44 58862,
>    181243.56 58849.94,
>    181262.63 58824.07,
>    181269.81 58813.01,
>    181278.57 58797.49,
>    181286.69 58781,
>    181294.3 58748.54,
>    181297.43 58721.7,
>    181293.95 58693.46,
>    181279.45 58644.96,
>    181271.49 58621.9,
>    181245.24 58566.88,
>    181234.84 58548.6,
>    181226.25 58524.73,
>    181207.37 58438.02,
>    181193.75 58388.29,
>    181183.54 58357.62,
>    181169.67 58302.15,
>    181163.49 58274.38,
>    181159.28 58246,
>    181147.89 58107.32,
>    181147.06 57991.43,
>    181148.81 57965.73,
>    181150.16 57909.44,
>    181151.32 57888.4,
>    181156.51 57844.11,
>    181163.68 57796.12,
>    181177.45 57719.23,
>    181202.13 57619.71,
>    181224.13 57544.69,
>    181254.77 57474.29,
>    181263.88 57451,
>    181283.27 57406.83,
>    181308.26 57364,
>    181321.91 57342.42,
>    181347.77 57297.32,
>    181375.92 57255.37,
>    181421.33 57195.25,
>    181465.37 57132.96,
>    181498.7 57089.91,
>    181515.73 57069.3,
>    181532.65 57051.11,
>    181546.73 57031.97,
>    181578.04 56994.2,
>    181592.81 56974.79,
>    181606.21 56955.33,
>    181617.19 56937.88,
>    181636.62 56901.76,
>    181644.91 56883.67,
>    181651.88 56866.37,
>    181658.28 56848.86,
>    181667.09 56820.5,
>    181670.79 56812.22,
>    181673.84 56805.41,
>    181679.95 56789.22,
>    181716.63 56710.19,
>    181727.56 56693.78,
>    181739.09 56674.37,
>    181760.36 56634.75,
>    181770.08 56621.43,
>    181806.52 56563.56,
>    181822.11 56541.55,
>    181853.29 56501.39,
>    181867.37 56484.47,
>    181915.43 56418.28,
>    181934.25 56389.84,
>    181989.88 56324.58,
>    182008.53 56304.44,
>    182028.06 56281.36,
>    182044.18 56260.03,
>    182077.17 56220.41,
>    182095.42 56200.24,
>    182149.64 56149,
>    182152.81 56145.38,
>    182165.25 56131.22,
>    182181.63 56109.2,
>    182226.84 56059.65,
>    182240.13 56042.18,
>    182249.84 56026.52,
>    182262.23 56004.41,
>    182269.66 55988.27,
>    182279.11 55970.17,
>    182302.19 55934.92,
>    182312.97 55920.44,
>    182334.13 55894.79,
>    182356.12 55865.14,
>    182427.98 55779.79,
>    182498.67 55702.44
> )
>
>>
>> Michael Michaud wrote:
>>> Hi Martin,
>>>
>>> Thanks for the precise answer.
>>> I do not know a good buffer algorithm but I made some further tests
>>> which show there is place for improvements with the excellent stuff
>>> you recently added.
>>>
>>> I created a simple linestring : length = 25000 m, number of segments
>>> = 1000
>>>
>>> Trying to create a buffer at a distance of 10000 m ended with a
>>> heapspace exception (took more than 256 Mo !) after more than 4 mn
>>> of intensive computation !
>>>
>>> The other way is :
>>> - decompose into segments : less than 1 s
>>> - create individual buffers : openjump says 8 s but I think it
>>> includes redrawing
>>> - cascaded union of resulting buffer : 6 s (less than 50 Mo)
>>>
>>> hope that helps
>>>
>>> Michael
>>>
>>>
>>>
>>> Martin Davis a écrit :
>>>> The reason for this is that as the buffer size gets bigger, the
>>>> "raw offset curve" that is initially created prior to extracting
>>>> the buffer outline gets more and more complex.  Concave angles in
>>>> the input geometry result in perpendicular "closing lines" being
>>>> created, which usually intersect other offset lines.  The longer
>>>> the perpendicular line, the more other lines it intersects, and
>>>> hence the more noding and topology analysis has to be performed.  
>>>> (I haven't found any good way of building the raw offset curve to
>>>> avoid or reduce this problem - if anyone has any ideas I'd be
>>>> interested to hear them).
>>>>
>>>> There's several ways that I've tried to reduce this problem:
>>>>
>>>> - compute the buffer in a series of steps, using an increasing
>>>> series of buffer distances which add up to the desired distance.  
>>>> Each successive buffer gets smoother, which makes the subsequent
>>>> buffers run faster.  It may only be necessary to iterate say 3
>>>> times to get a good result.  The trick of course is to pick the
>>>> right distances.
>>>>
>>>> - simplify the input geometry using DP, and a tolerance of say 2%
>>>> of the buffer distance
>>>>
>>>> - A better way of simplifying I've been experimenting with only
>>>> simplifies *outwards*.  This does 2 things - it reduces concavity
>>>> (which is the source of the problem), and it avoid "losing" convex
>>>> protrubances (which DP can often delete or alter).  Convex
>>>> protrubances are the primary influence on the shape of the
>>>> resulting buffer, so it is important to preserve them.  (Currently
>>>> this code is in alpha only - but I can provide it if anyone's
>>>> interested)
>>>>
>>>> Martin
>>>>
>>>> Michael Michaud wrote:
>>>>> Hi,
>>>>>
>>>>> I noticed that OpenJUMP Buffer plugin performance decreases
>>>>> dramatically if a large buffer size is used :
>>>>> For a map with  rivers having vertices every few meters, I get :
>>>>>
>>>>> buffer =  25 m :     7 s
>>>>> buffer =  50 m :    16 s
>>>>> buffer = 100 m :    48 s
>>>>> buffer = 200 m : 2m 59 s
>>>>>
>>>>> The plugin uses the BufferOp class. I have no idea why a large
>>>>> buffer should take longer than a small one, and I don't know if
>>>>> there is a better way to compute a buffer.
>>>>>
>>>>> Any idea ?
>>>>>
>>>>> Michaël
>>>>>
>>>>> _______________________________________________
>>>>> jts-devel mailing list
>>>>> [hidden email]
>>>>> http://lists.refractions.net/mailman/listinfo/jts-devel
>>>>>
>>>>
>>>
>>> _______________________________________________
>>> jts-devel mailing list
>>> [hidden email]
>>> http://lists.refractions.net/mailman/listinfo/jts-devel
>>>
>>
>
> _______________________________________________
> jts-devel mailing list
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
>

--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Buffer operation performance

Martin Davis
More on this topic...

I've been doing some testing of my prototype implementation of "Buffer
Input Simplification".  This uses a special-purpose linestring
simplification algorithm which weeds out *concave* sections of the
linework, but leaves *convex* sections untouched (up to a given
tolerance).  This is based on the observation that as buffers get
larger, the concave sections contribute less and the convex areas more
to the shape of the final buffer.  In the limit, very large buffers are
simply "blobs", which are dominated by a only a few of the larger
"protrubances" in the input curve.

Using this simplification technique with a conservative tolerance
produces high-quality buffers which are very close to the "pure" buffer
compute by the current JTS code (which is itself an approximation).  The
best part is that by linking the tolerance factor to the buffer
distance, as the distance goes up the performance of generating the
overall buffer increases dramatically!   Some results (using Michael's
test geometry) are given here:

Running case   buffer dist = 10.0
Num coords - input: 1031  simplified: 2045
Finished in 234 ms

Running case   buffer dist = 100.0
Num coords - input: 1031  simplified: 2039
Finished in 641 ms

Running case   buffer dist = 200.0
Num coords - input: 1031  simplified: 2036
Finished in 719 ms

Running case   buffer dist = 300.0
Num coords - input: 1031  simplified: 2022
Finished in 953 ms

Running case   buffer dist = 400.0
Num coords - input: 1031  simplified: 2005
Finished in 968 ms

Running case   buffer dist = 1000.0
Num coords - input: 1031  simplified: 1651
Finished in 985 ms

Running case   buffer dist = 1100.0
Num coords - input: 1031  simplified: 1617
Finished in 953 ms

Running case   buffer dist = 1200.0
Num coords - input: 1031  simplified: 1563
Finished in 1219 ms

Running case   buffer dist = 1300.0
Num coords - input: 1031  simplified: 1502
Finished in 843 ms

Running case   buffer dist = 2000.0
Num coords - input: 1031  simplified: 1264
Finished in 844 ms

Running case   buffer dist = 10000.0
Num coords - input: 1031  simplified: 470
Finished in 281 ms

Running case   buffer dist = 20000.0
Num coords - input: 1031  simplified: 309
Finished in 63 ms

Running case   buffer dist = 30000.0
Num coords - input: 1031  simplified: 233
Finished in 31 ms

This seems to me to be the most promising direction to take for
optimizing the computation of large buffers.

That said, the partitioned technique would parallelize nicely.  It can
also be used in combination with the simplification technique.  So
perhaps in a future "parallelJTS" they could both be used.



Martin Davis wrote:

> Good stuff - look forward to seeing the results.
>
> As I said, an important piece of this puzzle is being able to decide
> automatically when to cut over from the standard "monolithic" buffer
> approach to the "partitioned" approach.  The catch is that the
> inefficiency is caused by the local details of how complex the shape
> of the input linework is.  I haven't yet found a good way of measuring
> this local complexity and relating it to the buffer size.
>
> I still think the "outer simplification" ideas has some legs on it.  
> Would you be interested in trying out this approach with my alpha code?
>
> Michael Michaud wrote:
>> Hi,
>>
>>> Very interesting, Michael.  This "partitioned buffering" approach
>>> seems pretty viable as well.  (It would also parallel nicely in a
>>> multi-core environment!)
>> Yes, but I'm not sure individual buffering takes much time compared
>> to union operation (it would need more precise measurements)
>>>
>>> One limitation is that it's harder (or maybe impossible) to provide
>>> different join styles using PB - but that is probably a minor price
>>> to pay.
>> Right, I did not think about it.
>> Partitioned buffering could be made available for "round" buffering
>> only.
>>> Now, the challenge is to establish when to use the various
>>> approaches.  Is it always better to use PB?  Or is there some
>>> cutover point between the current buffer algorithm and PB?  This is
>>> one thing which has held me back from offering these other options
>>> in JTS.  The choice of which method to use really needs to be
>>> performed automatically by the library.
>> I agree that a single test is not enough to make decision. To
>> complete the test I'll try to measure the difference for
>> 1 / 10 / 100 / 1000  segments
>> and for a buffer distance equals to
>> 0.01x / 0.1x / 1x / 10x / 100x / 1000x the mean segment length
>> It would also be interesting to measure improvements for polygon
>> buffering
>>> Can you send me your test dataset?
>> Here is the 1031 points wkt of the linestring (I tried a 10000 buffer) :
>>
>> LINESTRING (
>>    168000 75099.09,
>>    168019.98 75079.81,
>>    168058.38 75051.63,
>>    168076.91 75045.01,
>>    168096.34 75039.38,
>>    168127.45 75021.15,
>>    168167.12 74999.39,
>>    168180.16 74991.79,
>>    168192.45 74982.57,
>>    168210.71 74972.38,
>>    168227.46 74964.28,
>>    168245.93 74951.24,
>>    168256.76 74941.96,
>>    168281.34 74925.48,
>>    168317.49 74903.93,
>>    168347.95 74893.42,
>>    168359.81 74886.5,
>>    168376.8 74873.61,
>>    168396.02 74862.35,
>>    168413.3 74857.15,
>>    168427.85 74850.68,
>>    168442.62 74840.26,
>>    168472.25 74826.59,
>>    168481.69 74819.74,
>>    168509.94 74810.66,
>>    168536.95 74796.66,
>>    168568.02 74785.98,
>>    168591.85 74776.06,
>>    168620.28 74763.11,
>>    168671.46 74735.14,
>>    168702.77 74718.98,
>>    168760.54 74684.78,
>>    168790.68 74665.69,
>>    168818.45 74651.59,
>>    168839.39 74639.33,
>>    168883.15 74612.66,
>>    168904.37 74597.07,
>>    168925.39 74585.69,
>>    168947.76 74575.73,
>>    168972.48 74562.28,
>>    168996.29 74552.47,
>>    169017.6 74547.3,
>>    169028.94 74543.14,
>>    169037.2 74537.14,
>>    169052.36 74529.73,
>>    169079 74518.34,
>>    169124.49 74504.73,
>>    169146.2 74496.7,
>>    169160.17 74490.57,
>>    169176.13 74483.44,
>>    169186.06 74479.41,
>>    169212.16 74474.08,
>>    169227.63 74467.66,
>>    169260.82 74439.9,
>>    169276.59 74427.91,
>>    169290.7 74415.52,
>>    169305.05 74405.76,
>>    169323.69 74389.86,
>>    169339.44 74377.81,
>>    169357.33 74366.16,
>>    169414.53 74321.51,
>>    169474.05 74282.78,
>>    169489.52 74270.72,
>>    169579.01 74223.09,
>>    169604.78 74210.14,
>>    169619.7 74199.66,
>>    169629.14 74195.23,
>>    169643.34 74192.88,
>>    169659.96 74185.19,
>>    169678.7 74177.96,
>>    169693.96 74170.68,
>>    169713.35 74162.96,
>>    169739.08 74156.44,
>>    169768.36 74152.97,
>>    169799.54 74148.44,
>>    169838.66 74144.65,
>>    169885.9 74150.01,
>>    169971.44 74167,
>>    170024.34 74173.38,
>>    170076.65 74178.2,
>>    170094.55 74180.82,
>>    170113.44 74185.45,
>>    170132 74188.82,
>>    170175.93 74192.59,
>>    170205.21 74192.5,
>>    170218.75 74191.32,
>>    170233.84 74190.88,
>>    170277.47 74190.61,
>>    170316.34 74191.58,
>>    170333.36 74190.76,
>>    170348.04 74190.9,
>>    170363.55 74188.79,
>>    170393.8 74188.48,
>>    170412.8 74190.33,
>>    170431.6 74191.32,
>>    170484.03 74196.25,
>>    170516.54 74191.7,
>>    170531.41 74190.82,
>>    170558.77 74188.35,
>>    170572.36 74182.24,
>>    170583.63 74178.45,
>>    170600.48 74171.3,
>>    170638.11 74160.2,
>>    170657.84 74153.73,
>>    170670.51 74148.4,
>>    170720.33 74125.39,
>>    170749.99 74113.62,
>>    170792.93 74100.61,
>>    170835.33 74092.07,
>>    170849.17 74088.43,
>>    170863.59 74083.87,
>>    170899.93 74068.73,
>>    170939 74058.28,
>>    170966.12 74049,
>>    170989.65 74044.69,
>>    171001.68 74041.17,
>>    171028.85 74030.8,
>>    171053.39 74019.23,
>>    171081.07 74007.94,
>>    171102.14 74002.15,
>>    171117.33 73997.16,
>>    171142.09 73992.68,
>>    171151.89 73991.51,
>>    171198.97 73979.07,
>>    171232.93 73972.48,
>>    171243.99 73969.27,
>>    171268.54 73966.34,
>>    171301.94 73958.88,
>>    171310.31 73958.18,
>>    171318.46 73959.11,
>>    171334.75 73959.34,
>>    171360.8 73955.36,
>>    171390.53 73952.29,
>>    171407.27 73951.84,
>>    171454.52 73946.27,
>>    171532.91 73942.72,
>>    171559.19 73942.74,
>>    171586.59 73941.28,
>>    171606.07 73941.02,
>>    171632.04 73942.05,
>>    171648.7 73941.96,
>>    171664.69 73940.23,
>>    171703.79 73932.17,
>>    171725.83 73923.91,
>>    171786.57 73908.02,
>>    171811.39 73902.01,
>>    171862.01 73883.19,
>>    171881.03 73877.34,
>>    171904.53 73869.1,
>>    171924.75 73861,
>>    171942.63 73855.66,
>>    171967.52 73846.29,
>>    171989.09 73837.11,
>>    172048.82 73819.06,
>>    172065.95 73811.98,
>>    172081.18 73803.66,
>>    172112.57 73792.61,
>>    172141.47 73781.54,
>>    172199.07 73754.61,
>>    172220.41 73746.36,
>>    172258.74 73737.64,
>>    172308.01 73719.25,
>>    172327.08 73714.16,
>>    172341.9 73711.22,
>>    172357.39 73706.04,
>>    172373.89 73699.51,
>>    172387.83 73695.45,
>>    172458.09 73667.62,
>>    172487.31 73654.97,
>>    172501.31 73647.79,
>>    172537.91 73627.37,
>>    172586.45 73599.14,
>>    172602.33 73591.61,
>>    172651.56 73576.46,
>>    172666.88 73571.13,
>>    172692.9 73558.6,
>>    172709.76 73549.34,
>>    172740.08 73534.5,
>>    172760 73523.41,
>>    172776.57 73511.27,
>>    172785.72 73506.09,
>>    172795.79 73501.6,
>>    172806.59 73500.89,
>>    172817.66 73498.13,
>>    172826.77 73492.83,
>>    172843.25 73480.68,
>>    172861.8 73468.4,
>>    172871.7 73463.21,
>>    172918.85 73435.31,
>>    172934.75 73420.57,
>>    172999.52 73375.23,
>>    173052.08 73332.33,
>>    173061.72 73326.05,
>>    173083.73 73320.93,
>>    173102.39 73312.88,
>>    173123.43 73301.81,
>>    173152.75 73282.68,
>>    173209.2 73242.11,
>>    173228.86 73230.1,
>>    173238.95 73224.75,
>>    173249.15 73217.87,
>>    173276.84 73196.72,
>>    173338.16 73146.47,
>>    173348.23 73139,
>>    173384.35 73114.23,
>>    173430.5 73084.55,
>>    173440.47 73076.9,
>>    173450.62 73072.16,
>>    173469.56 73061.59,
>>    173479.51 73055.68,
>>    173497.59 73042.86,
>>    173507.16 73038.03,
>>    173528.29 73029.23,
>>    173559.43 73019.59,
>>    173569.08 73014.36,
>>    173587.09 73001.77,
>>    173674.43 72947.17,
>>    173701.14 72928.72,
>>    173709.48 72921.58,
>>    173724.28 72906.98,
>>    173739.66 72893.97,
>>    173749.59 72890.25,
>>    173775.23 72869.71,
>>    173785.3 72863.62,
>>    173818.13 72836.11,
>>    173827.45 72829.13,
>>    173856.34 72812.25,
>>    173865.78 72805.46,
>>    173875.48 72801,
>>    173884.38 72795.17,
>>    173917.08 72767.14,
>>    173926.86 72762.21,
>>    173937.93 72763.44,
>>    173967.05 72749.76,
>>    173974.73 72741.71,
>>    173983.02 72734.67,
>>    173992.68 72727.88,
>>    174001.83 72722.59,
>>    174030.88 72707.71,
>>    174051.2 72698.45,
>>    174071.1 72687.2,
>>    174081.39 72683.5,
>>    174089.48 72685.37,
>>    174109.71 72677.64,
>>    174119.75 72678.34,
>>    174128.19 72671.13,
>>    174137.3 72664.75,
>>    174146.85 72659.03,
>>    174157.34 72654.76,
>>    174165.35 72648.08,
>>    174184.53 72637.86,
>>    174193.88 72633.25,
>>    174204.59 72631.67,
>>    174214.39 72625.59,
>>    174224.21 72621.86,
>>    174234.42 72616.88,
>>    174243.59 72610.11,
>>    174253.83 72605.56,
>>    174274.88 72598.13,
>>    174283.78 72592.38,
>>    174300.78 72576.21,
>>    174308.71 72569.51,
>>    174359.48 72528.51,
>>    174398.79 72492.94,
>>    174405.5 72484.28,
>>    174411.53 72474.83,
>>    174419.13 72466.61,
>>    174427.17 72459.43,
>>    174458.79 72425.51,
>>    174464.86 72417.51,
>>    174477.4 72397.91,
>>    174481.96 72388.65,
>>    174486.63 72377.13,
>>    174498.42 72343.67,
>>    174502.95 72333.07,
>>    174526.81 72283.89,
>>    174536.17 72262.58,
>>    174553.04 72234.6,
>>    174561.1 72226.58,
>>    174567.54 72216.87,
>>    174571.16 72206.15,
>>    174571.79 72195.91,
>>    174574.97 72185.45,
>>    174581.47 72175.77,
>>    174590.94 72156.19,
>>    174598.5 72148.42,
>>    174604.26 72138.96,
>>    174614.61 72119.31,
>>    174617.86 72109.68,
>>    174618.88 72098.83,
>>    174620.62 72088.92,
>>    174623.58 72079.08,
>>    174652.24 72019.39,
>>    174672.82 71980,
>>    174679.52 71957.62,
>>    174688.5 71937.78,
>>    174699.09 71920.14,
>>    174705.95 71911.18,
>>    174713.49 71904.44,
>>    174718.78 71894.98,
>>    174725.86 71874.85,
>>    174732.59 71864.99,
>>    174738.83 71856.73,
>>    174746.65 71848.06,
>>    174756.08 71841.4,
>>    174760.53 71831.95,
>>    174772.07 71813.16,
>>    174786.69 71793.3,
>>    174801.7 71775.1,
>>    174809.49 71766.29,
>>    174826.27 71749.24,
>>    174859.56 71717.58,
>>    174866.89 71709.21,
>>    174880.19 71691.3,
>>    174887 71683.71,
>>    174895.32 71676.12,
>>    174904.3 71671.55,
>>    174913.56 71664.66,
>>    174920.92 71656.83,
>>    174927.07 71648.48,
>>    174935.22 71640.33,
>>    174943.94 71634.84,
>>    174954.01 71631.94,
>>    174970.02 71616.71,
>>    174986.09 71603.63,
>>    174992.75 71595.93,
>>    174997.89 71586.08,
>>    175002.77 71574.24,
>>    175007.92 71566.95,
>>    175021.39 71554.85,
>>    175026.4 71547.19,
>>    175030.56 71538.06,
>>    175044.96 71517.18,
>>    175060.26 71493.05,
>>    175077.44 71472.78,
>>    175094.51 71455.41,
>>    175111.47 71442.59,
>>    175143.7 71420.42,
>>    175156.81 71408.96,
>>    175188.77 71371.82,
>>    175267.54 71302.71,
>>    175284.55 71286.73,
>>    175299.75 71269.13,
>>    175358.64 71206.84,
>>    175396.74 71163.01,
>>    175411.28 71150.26,
>>    175442.64 71127.33,
>>    175457.59 71115.13,
>>    175500.48 71075.17,
>>    175523.01 71052.94,
>>    175566.34 71002.67,
>>    175585.5 70982.26,
>>    175601.18 70968.3,
>>    175635.48 70940.41,
>>    175645.97 70928.51,
>>    175657.05 70917.56,
>>    175669.35 70907.51,
>>    175680.17 70899.55,
>>    175708.08 70884.05,
>>    175719.1 70875.15,
>>    175728.9 70865.65,
>>    175748.84 70840.67,
>>    175760.26 70828.78,
>>    175772.96 70816.86,
>>    175797.59 70795.41,
>>    175820.4 70771.58,
>>    175830.81 70758.94,
>>    175887.26 70702.46,
>>    175939.77 70657.23,
>>    175964.24 70638.02,
>>    175991.59 70619.95,
>>    176055.64 70575.16,
>>    176079.86 70557.44,
>>    176099.14 70540.66,
>>    176111.84 70528.48,
>>    176124.85 70521.62,
>>    176138.75 70516.52,
>>    176151.24 70509.62,
>>    176162.55 70497.52,
>>    176175.72 70481.45,
>>    176206.32 70435.37,
>>    176222.38 70407.62,
>>    176237.17 70375.68,
>>    176249.61 70346.63,
>>    176265.36 70306.53,
>>    176289.61 70252.4,
>>    176304.59 70228.36,
>>    176325.15 70199.27,
>>    176346.33 70164.59,
>>    176363.73 70134.77,
>>    176376.6 70110.47,
>>    176398.34 70074.51,
>>    176425.63 70037.09,
>>    176461.29 69993.33,
>>    176538.04 69890.48,
>>    176611.31 69795.95,
>>    176642.89 69757.61,
>>    176653.34 69740.97,
>>    176667.53 69705.46,
>>    176694.82 69587.45,
>>    176710.85 69542.86,
>>    176729.65 69499.4,
>>    176750.13 69456.2,
>>    176759.92 69440.95,
>>    176765.47 69440.79,
>>    176769.55 69437.84,
>>    176775.95 69428.35,
>>    176816.39 69344.34,
>>    176838.52 69303.52,
>>    176841.61 69288.41,
>>    176847.4 69271.24,
>>    176853.88 69257.39,
>>    176866.38 69224.77,
>>    176884.05 69191.75,
>>    176908.14 69156.34,
>>    176932.6 69124.48,
>>    176941.5 69109.01,
>>    176952.75 69087.58,
>>    176962.34 69066.66,
>>    177011.99 68975.48,
>>    177047.55 68904.3,
>>    177075.71 68857.75,
>>    177086.06 68846.79,
>>    177093.45 68840.28,
>>    177113.15 68819.4,
>>    177125.53 68803.37,
>>    177145.01 68774.81,
>>    177162.81 68744.93,
>>    177175.04 68722.96,
>>    177183.89 68711.15,
>>    177195.55 68697.11,
>>    177206.23 68681.8,
>>    177232.19 68640.09,
>>    177250.19 68607.22,
>>    177286.85 68548.09,
>>    177331.39 68483.17,
>>    177380.45 68419.09,
>>    177385.25 68410.57,
>>    177415.26 68372.12,
>>    177436.17 68348.33,
>>    177461.11 68318.37,
>>    177477.56 68301.44,
>>    177486.38 68290.59,
>>    177497.15 68278.98,
>>    177504.31 68271.41,
>>    177514.19 68263.47,
>>    177531.39 68251.34,
>>    177547.84 68236.75,
>>    177556 68228.1,
>>    177562.23 68220.36,
>>    177604.15 68155.74,
>>    177608.84 68145.94,
>>    177623.1 68120.44,
>>    177629.69 68105.2,
>>    177650.02 68073.08,
>>    177654.45 68065.11,
>>    177658.56 68050.95,
>>    177662.82 68042,
>>    177667.36 68024.84,
>>    177671 68015.54,
>>    177681.4 67994.43,
>>    177693.6 67949.74,
>>    177703.26 67919.53,
>>    177706.63 67911.94,
>>    177714 67899.68,
>>    177716.44 67893.18,
>>    177718.91 67884.28,
>>    177720.55 67871.14,
>>    177724.45 67851.53,
>>    177727.55 67839.84,
>>    177728.77 67829,
>>    177730.93 67818.94,
>>    177739.33 67800.24,
>>    177749.1 67785.58,
>>    177752.04 67778.56,
>>    177753.75 67770.32,
>>    177746.91 67735.03,
>>    177749.64 67718.67,
>>    177751.88 67673.54,
>>    177757.49 67617.74,
>>    177766.81 67556.29,
>>    177774.75 67524.5,
>>    177789.56 67484.51,
>>    177799.11 67451.34,
>>    177808.39 67423.01,
>>    177818.88 67380.1,
>>    177824.98 67359.84,
>>    177834.3 67337.45,
>>    177842.13 67315.31,
>>    177848.2 67276,
>>    177855.87 67246.99,
>>    177863.04 67223.1,
>>    177875.61 67190.41,
>>    177879.98 67179.07,
>>    177883.21 67166.85,
>>    177884.93 67160.33,
>>    177887.27 67151.44,
>>    177898.41 67109.32,
>>    177909.04 67078.94,
>>    177913.49 67064.05,
>>    177918.13 67052.99,
>>    177923.74 67042.42,
>>    177929.09 67035.22,
>>    177930.69 67029.22,
>>    177930.66 67018.64,
>>    177941.76 66972.23,
>>    177945.36 66939.94,
>>    177951.27 66907.91,
>>    177952.98 66901.54,
>>    177955.94 66887.96,
>>    177959.41 66872.07,
>>    177966.58 66851.6,
>>    177971.62 66836.37,
>>    177985.44 66786.6,
>>    177989.64 66763.17,
>>    177994.85 66733.27,
>>    178001.66 66699.61,
>>    178008.6 66667.66,
>>    178013.75 66647.23,
>>    178016.34 66636.11,
>>    178017.08 66605.55,
>>    178014.57 66554.14,
>>    178010.24 66506.37,
>>    178009.32 66465.24,
>>    178009.96 66441.56,
>>    178005.85 66419.82,
>>    178002.49 66387.67,
>>    177998.46 66338.04,
>>    177993.35 66326.83,
>>    177986.72 66324.9,
>>    177985.23 66322.04,
>>    177985.54 66319.15,
>>    177989.56 66306.9,
>>    177993.67 66298.82,
>>    177995.86 66291.86,
>>    177995.66 66289.33,
>>    177992.99 66284.06,
>>    177993.44 66281.23,
>>    177992.3 66260.72,
>>    177990.84 66248.64,
>>    177981.56 66172.16,
>>    177977.76 66141.43,
>>    177974.54 66123.9,
>>    177971.77 66108.86,
>>    177967.86 66094.01,
>>    177966.43 66092.26,
>>    177967.2 66087.09,
>>    177966.9 66082.9,
>>    177966.02 66080.43,
>>    177964.2 66078.21,
>>    177963.59 66075.21,
>>    177964.74 66064.46,
>>    177964.35 66055.86,
>>    177963.28 66052.01,
>>    177959.34 66029.13,
>>    177960.61 66022.97,
>>    177959.04 66018.46,
>>    177956.76 66015.2,
>>    177956.89 66012.74,
>>    177958.77 66009.48,
>>    177959.85 66004.68,
>>    177957.01 65995.03,
>>    177957.25 65986.78,
>>    177956.14 65982.15,
>>    177953.29 65979.39,
>>    177952.17 65976.64,
>>    177957.95 65969.74,
>>    177959.19 65962.62,
>>    177957.37 65900.17,
>>    177953.57 65856.26,
>>    177953.93 65817.35,
>>    177953.88 65813.27,
>>    177955.48 65807.19,
>>    177956.46 65799.14,
>>    177955.03 65777.69,
>>    177956.4 65734.55,
>>    177956.23 65719.34,
>>    177953.1 65713.03,
>>    177954.45 65705.09,
>>    177957.1 65697.01,
>>    177956.84 65685.15,
>>    177959 65679.49,
>>    177959.49 65671.26,
>>    177961.48 65638.16,
>>    177968.9 65592.02,
>>    177975.6 65560.06,
>>    177979.15 65534.98,
>>    177979.38 65495.95,
>>    177982.31 65407.44,
>>    177984.68 65358.91,
>>    177987.11 65325.67,
>>    177986.1 65293.15,
>>    177989.96 65264.47,
>>    177995.42 65209.31,
>>    178001.47 65168.9,
>>    178008.8 65113.21,
>>    178013.31 65003.86,
>>    178012.51 64952.06,
>>    178009.63 64847.94,
>>    178017.62 64682.43,
>>    178021.64 64541.27,
>>    178023.13 64396.67,
>>    178027.75 64137.61,
>>    178025.76 64028.45,
>>    178020.43 63910.8,
>>    178020.72 63849.5,
>>    178029.19 63778.85,
>>    178032.16 63763.6,
>>    178032.6 63749.92,
>>    178030.32 63733.73,
>>    178026.47 63721.29,
>>    178021.04 63709.32,
>>    178016.35 63702.9,
>>    178011.71 63699.25,
>>    178006.61 63698.96,
>>    178008.27 63678.14,
>>    178009.61 63661.41,
>>    178024.73 63657.03,
>>    178035.53 63651.2,
>>    178042.7 63644.43,
>>    178048.96 63635.33,
>>    178054.42 63625.44,
>>    178066.74 63513.4,
>>    178079.29 63350.15,
>>    178113.91 63043.92,
>>    178125.17 62967.61,
>>    178139.81 62861.77,
>>    178160.03 62739.24,
>>    178166.8 62690.71,
>>    178180.6 62598.21,
>>    178196.38 62478.9,
>>    178205.95 62429.83,
>>    178215.68 62390.38,
>>    178225.95 62355.56,
>>    178234.91 62330.13,
>>    178243.99 62312.58,
>>    178252.42 62300.17,
>>    178258.59 62293.76,
>>    178271.74 62267.81,
>>    178278.87 62259.41,
>>    178281.2 62257.11,
>>    178291.29 62241.06,
>>    178296.59 62234.42,
>>    178300.59 62233.22,
>>    178306.14 62233.23,
>>    178313.85 62230.84,
>>    178318.53 62228.61,
>>    178323.72 62225.14,
>>    178329.38 62219.28,
>>    178332.15 62217.39,
>>    178339.35 62217.49,
>>    178342.7 62218.66,
>>    178343.51 62221.14,
>>    178348.34 62226.92,
>>    178351.79 62228.99,
>>    178353.88 62228.77,
>>    178354.79 62226.72,
>>    178351.18 62221.84,
>>    178353.07 62216.87,
>>    178353.25 62214.12,
>>    178355.63 62211.13,
>>    178358.36 62209.3,
>>    178361.9 62208.86,
>>    178362.76 62206.43,
>>    178361.97 62203.62,
>>    178363.58 62201.57,
>>    178374.53 62193.67,
>>    178381.63 62189.79,
>>    178385.43 62189.76,
>>    178389.45 62192.04,
>>    178392.01 62192.3,
>>    178393.18 62189.44,
>>    178391.57 62187.72,
>>    178390.78 62185.63,
>>    178399.88 62175.2,
>>    178402.36 62174.4,
>>    178407.71 62177.98,
>>    178413.7 62175.14,
>>    178419.05 62176.68,
>>    178422.21 62174.44,
>>    178423.73 62172.07,
>>    178423.57 62169.19,
>>    178421.96 62166.64,
>>    178418.94 62165,
>>    178415.85 62165.96,
>>    178412.1 62170.44,
>>    178409.48 62169.88,
>>    178407.72 62163.55,
>>    178411.95 62162.4,
>>    178418.53 62156.4,
>>    178423.46 62150.54,
>>    178426.56 62148.62,
>>    178429.7 62149.94,
>>    178432.71 62149.19,
>>    178435.99 62144.98,
>>    178436.76 62142.14,
>>    178439.36 62139.27,
>>    178442.84 62138.83,
>>    178445.4 62135.85,
>>    178447.6 62128.51,
>>    178451.73 62120.49,
>>    178454.01 62118.47,
>>    178457.62 62116.53,
>>    178458.69 62112.83,
>>    178461.1 62111.48,
>>    178464.42 62110.72,
>>    178466.21 62108.01,
>>    178467.1 62104.31,
>>    178465.62 62097.07,
>>    178468.42 62087.79,
>>    178468.55 62082.53,
>>    178466.59 62081.04,
>>    178458.84 62079.15,
>>    178456.58 62076.29,
>>    178455.86 62072.53,
>>    178457.63 62070.82,
>>    178458.45 62068.91,
>>    178456.51 62066.55,
>>    178459.35 62062.85,
>>    178452.82 62060.08,
>>    178449.82 62056.67,
>>    178450.62 62053.45,
>>    178453.32 62051.97,
>>    178455.16 62049.21,
>>    178454.93 62047.57,
>>    178452.23 62046.52,
>>    178450.69 62043.67,
>>    178451.11 62040.83,
>>    178454.12 62039.86,
>>    178455.53 62036.39,
>>    178454.73 62032.33,
>>    178452.91 62029.35,
>>    178448.3 62026.56,
>>    178445.22 62025.7,
>>    178429.07 62026.53,
>>    178424.89 62023.48,
>>    178422.86 62005.51,
>>    178421.81 61980.76,
>>    178421.89 61962.48,
>>    178423.58 61949.11,
>>    178430.17 61919.22,
>>    178433.41 61907.8,
>>    178443.14 61886.28,
>>    178468.73 61806.63,
>>    178479.68 61780.1,
>>    178494.89 61734.32,
>>    178511.46 61692.33,
>>    178518.28 61666.62,
>>    178533.34 61622.92,
>>    178544.99 61595.95,
>>    178567.61 61537.18,
>>    178574.74 61521.82,
>>    178583.21 61495.5,
>>    178598.58 61458.21,
>>    178614.24 61428.39,
>>    178650.58 61354,
>>    178658.76 61340.98,
>>    178665.02 61327.95,
>>    178674.8 61313.2,
>>    178700.24 61274.86,
>>    178719.61 61242.68,
>>    178738.79 61214.38,
>>    178758.9 61190.94,
>>    178770.37 61180.47,
>>    178789.81 61169.58,
>>    178812.25 61159.56,
>>    178824.56 61155.6,
>>    178835.46 61148.73,
>>    178850.86 61141.32,
>>    178877.94 61132.47,
>>    178905.39 61124.35,
>>    178921.76 61117.34,
>>    178937.67 61111.55,
>>    178980.84 61104.68,
>>    179007.68 61098.47,
>>    179056.28 61084.32,
>>    179128.36 61065.61,
>>    179202.82 61047.78,
>>    179276.21 61027.13,
>>    179472.42 60961.08,
>>    179529.07 60936.85,
>>    179542.88 60927.94,
>>    179549.41 60922,
>>    179555.08 60911.73,
>>    179559.44 60900.77,
>>    179562.28 60889.12,
>>    179562.47 60877.05,
>>    179560.63 60866.89,
>>    179560.7 60863.09,
>>    179562.37 60857.61,
>>    179565.71 60846.64,
>>    179567.54 60832.84,
>>    179566.44 60823.14,
>>    179565.06 60818.43,
>>    179549.81 60764.67,
>>    179550.31 60758.45,
>>    179546.67 60734.77,
>>    179549.49 60731.03,
>>    179557.54 60733.31,
>>    179561.13 60738.93,
>>    179564.21 60739.89,
>>    179566.89 60745.6,
>>    179572.89 60748.67,
>>    179575.31 60751.42,
>>    179578.26 60756.38,
>>    179578.33 60762.32,
>>    179583.95 60763.05,
>>    179583.19 60771.19,
>>    179588.15 60772.63,
>>    179588.19 60782.91,
>>    179593.07 60784.13,
>>    179589.87 60805.68,
>>    179595.07 60815.48,
>>    179600.01 60822.77,
>>    179600.24 60826.95,
>>    179602.21 60832.23,
>>    179607.32 60835.03,
>>    179620.58 60838.4,
>>    179635.67 60841.41,
>>    179651.26 60843.16,
>>    179667.47 60843.16,
>>    179681.53 60838.67,
>>    179704.27 60828.05,
>>    179724.08 60814.96,
>>    179741.93 60801.19,
>>    179753.86 60790.42,
>>    179763.48 60779.45,
>>    179766.88 60773.18,
>>    179767.07 60771.12,
>>    179762.6 60765.99,
>>    179766.21 60747.38,
>>    179770.94 60741.75,
>>    179776.56 60738.66,
>>    179779.2 60737.22,
>>    179786.44 60742.03,
>>    179793.9 60741.33,
>>    179799.37 60742.37,
>>    179807.42 60735.01,
>>    179815.39 60724.84,
>>    179811.05 60721.94,
>>    179813.76 60715.68,
>>    179820.14 60717.55,
>>    179826.71 60710.34,
>>    179829.53 60708.82,
>>    179888.74 60612.93,
>>    179947.13 60522.16,
>>    179955.61 60507.32,
>>    179964.18 60496.92,
>>    179973.96 60490.42,
>>    179979.79 60485.25,
>>    179984.9 60477.61,
>>    180001.97 60445.85,
>>    180013.27 60430.79,
>>    180047.31 60395.4,
>>    180054.81 60389.16,
>>    180071.26 60381.38,
>>    180083.39 60373.8,
>>    180100.66 60358.77,
>>    180110.87 60348.94,
>>    180115.99 60340.86,
>>    180120.92 60330.67,
>>    180131.3 60290.31,
>>    180141.88 60252.91,
>>    180145.41 60243.95,
>>    180170.92 60161.14,
>>    180176.4 60146.3,
>>    180191.39 60114.53,
>>    180200.97 60096.39,
>>    180212.16 60078.29,
>>    180218.27 60071.66,
>>    180235.86 60057.92,
>>    180243.95 60050.52,
>>    180249.63 60043.36,
>>    180259.04 60025.98,
>>    180266.35 60007.91,
>>    180274.4 59993.5,
>>    180281.06 59983.38,
>>    180289.52 59973.93,
>>    180315.7 59949.8,
>>    180329.09 59939.62,
>>    180338.31 59934.05,
>>    180354.18 59926.34,
>>    180362.13 59924.76,
>>    180369.12 59926.79,
>>    180375.15 59931.75,
>>    180383 59935.53,
>>    180388.11 59938.77,
>>    180396.42 59949.49,
>>    180400.6 59946.77,
>>    180405.01 59956.2,
>>    180407.23 59954.8,
>>    180409.16 59952.08,
>>    180431.99 59882.17,
>>    180489.59 59719.98,
>>    180516.16 59668.73,
>>    180544.76 59619.86,
>>    180564.25 59578.8,
>>    180573.7 59551.7,
>>    180580.79 59525.35,
>>    180588.37 59505.63,
>>    180604.12 59473.13,
>>    180622.29 59445.18,
>>    180631.91 59429.05,
>>    180637.83 59412.74,
>>    180656.17 59339.6,
>>    180669.41 59299.14,
>>    180679.64 59275.76,
>>    180684.28 59266.53,
>>    180686.05 59263.02,
>>    180697.93 59246.56,
>>    180747.67 59189.18,
>>    180759.28 59178.74,
>>    180772.99 59167.85,
>>    180785.83 59162,
>>    180798.34 59158.18,
>>    180813.74 59154.37,
>>    180832.3 59151.97,
>>    180855.11 59147.46,
>>    180861.98 59142.9,
>>    180866.27 59138.42,
>>    180872.11 59130.67,
>>    180909.6 59075.52,
>>    180922.07 59061.58,
>>    180930.79 59055.13,
>>    180943.08 59050.38,
>>    180953.99 59047.52,
>>    180964.78 59041.87,
>>    180975.83 59032.72,
>>    180985.33 59022.92,
>>    181000.57 59002.51,
>>    181013.17 58990.67,
>>    181024.71 58983.21,
>>    181035.92 58978.57,
>>    181050.06 58975.38,
>>    181076.88 58972.92,
>>    181087.67 58970.91,
>>    181099.7 58966.76,
>>    181122.01 58955.77,
>>    181146.14 58947.76,
>>    181157.78 58942.19,
>>    181167.75 58934.2,
>>    181177.2 58925.53,
>>    181192.11 58906.31,
>>    181233.44 58862,
>>    181243.56 58849.94,
>>    181262.63 58824.07,
>>    181269.81 58813.01,
>>    181278.57 58797.49,
>>    181286.69 58781,
>>    181294.3 58748.54,
>>    181297.43 58721.7,
>>    181293.95 58693.46,
>>    181279.45 58644.96,
>>    181271.49 58621.9,
>>    181245.24 58566.88,
>>    181234.84 58548.6,
>>    181226.25 58524.73,
>>    181207.37 58438.02,
>>    181193.75 58388.29,
>>    181183.54 58357.62,
>>    181169.67 58302.15,
>>    181163.49 58274.38,
>>    181159.28 58246,
>>    181147.89 58107.32,
>>    181147.06 57991.43,
>>    181148.81 57965.73,
>>    181150.16 57909.44,
>>    181151.32 57888.4,
>>    181156.51 57844.11,
>>    181163.68 57796.12,
>>    181177.45 57719.23,
>>    181202.13 57619.71,
>>    181224.13 57544.69,
>>    181254.77 57474.29,
>>    181263.88 57451,
>>    181283.27 57406.83,
>>    181308.26 57364,
>>    181321.91 57342.42,
>>    181347.77 57297.32,
>>    181375.92 57255.37,
>>    181421.33 57195.25,
>>    181465.37 57132.96,
>>    181498.7 57089.91,
>>    181515.73 57069.3,
>>    181532.65 57051.11,
>>    181546.73 57031.97,
>>    181578.04 56994.2,
>>    181592.81 56974.79,
>>    181606.21 56955.33,
>>    181617.19 56937.88,
>>    181636.62 56901.76,
>>    181644.91 56883.67,
>>    181651.88 56866.37,
>>    181658.28 56848.86,
>>    181667.09 56820.5,
>>    181670.79 56812.22,
>>    181673.84 56805.41,
>>    181679.95 56789.22,
>>    181716.63 56710.19,
>>    181727.56 56693.78,
>>    181739.09 56674.37,
>>    181760.36 56634.75,
>>    181770.08 56621.43,
>>    181806.52 56563.56,
>>    181822.11 56541.55,
>>    181853.29 56501.39,
>>    181867.37 56484.47,
>>    181915.43 56418.28,
>>    181934.25 56389.84,
>>    181989.88 56324.58,
>>    182008.53 56304.44,
>>    182028.06 56281.36,
>>    182044.18 56260.03,
>>    182077.17 56220.41,
>>    182095.42 56200.24,
>>    182149.64 56149,
>>    182152.81 56145.38,
>>    182165.25 56131.22,
>>    182181.63 56109.2,
>>    182226.84 56059.65,
>>    182240.13 56042.18,
>>    182249.84 56026.52,
>>    182262.23 56004.41,
>>    182269.66 55988.27,
>>    182279.11 55970.17,
>>    182302.19 55934.92,
>>    182312.97 55920.44,
>>    182334.13 55894.79,
>>    182356.12 55865.14,
>>    182427.98 55779.79,
>>    182498.67 55702.44
>> )
>>
>>>
>>> Michael Michaud wrote:
>>>> Hi Martin,
>>>>
>>>> Thanks for the precise answer.
>>>> I do not know a good buffer algorithm but I made some further tests
>>>> which show there is place for improvements with the excellent stuff
>>>> you recently added.
>>>>
>>>> I created a simple linestring : length = 25000 m, number of
>>>> segments = 1000
>>>>
>>>> Trying to create a buffer at a distance of 10000 m ended with a
>>>> heapspace exception (took more than 256 Mo !) after more than 4 mn
>>>> of intensive computation !
>>>>
>>>> The other way is :
>>>> - decompose into segments : less than 1 s
>>>> - create individual buffers : openjump says 8 s but I think it
>>>> includes redrawing
>>>> - cascaded union of resulting buffer : 6 s (less than 50 Mo)
>>>>
>>>> hope that helps
>>>>
>>>> Michael
>>>>
>>>>
>>>>
>>>> Martin Davis a écrit :
>>>>> The reason for this is that as the buffer size gets bigger, the
>>>>> "raw offset curve" that is initially created prior to extracting
>>>>> the buffer outline gets more and more complex.  Concave angles in
>>>>> the input geometry result in perpendicular "closing lines" being
>>>>> created, which usually intersect other offset lines.  The longer
>>>>> the perpendicular line, the more other lines it intersects, and
>>>>> hence the more noding and topology analysis has to be performed.  
>>>>> (I haven't found any good way of building the raw offset curve to
>>>>> avoid or reduce this problem - if anyone has any ideas I'd be
>>>>> interested to hear them).
>>>>>
>>>>> There's several ways that I've tried to reduce this problem:
>>>>>
>>>>> - compute the buffer in a series of steps, using an increasing
>>>>> series of buffer distances which add up to the desired distance.  
>>>>> Each successive buffer gets smoother, which makes the subsequent
>>>>> buffers run faster.  It may only be necessary to iterate say 3
>>>>> times to get a good result.  The trick of course is to pick the
>>>>> right distances.
>>>>>
>>>>> - simplify the input geometry using DP, and a tolerance of say 2%
>>>>> of the buffer distance
>>>>>
>>>>> - A better way of simplifying I've been experimenting with only
>>>>> simplifies *outwards*.  This does 2 things - it reduces concavity
>>>>> (which is the source of the problem), and it avoid "losing" convex
>>>>> protrubances (which DP can often delete or alter).  Convex
>>>>> protrubances are the primary influence on the shape of the
>>>>> resulting buffer, so it is important to preserve them.  (Currently
>>>>> this code is in alpha only - but I can provide it if anyone's
>>>>> interested)
>>>>>
>>>>> Martin
>>>>>
>>>>> Michael Michaud wrote:
>>>>>> Hi,
>>>>>>
>>>>>> I noticed that OpenJUMP Buffer plugin performance decreases
>>>>>> dramatically if a large buffer size is used :
>>>>>> For a map with  rivers having vertices every few meters, I get :
>>>>>>
>>>>>> buffer =  25 m :     7 s
>>>>>> buffer =  50 m :    16 s
>>>>>> buffer = 100 m :    48 s
>>>>>> buffer = 200 m : 2m 59 s
>>>>>>
>>>>>> The plugin uses the BufferOp class. I have no idea why a large
>>>>>> buffer should take longer than a small one, and I don't know if
>>>>>> there is a better way to compute a buffer.
>>>>>>
>>>>>> Any idea ?
>>>>>>
>>>>>> Michaël
>>>>>>
>>>>>> _______________________________________________
>>>>>> jts-devel mailing list
>>>>>> [hidden email]
>>>>>> http://lists.refractions.net/mailman/listinfo/jts-devel
>>>>>>
>>>>>
>>>>
>>>> _______________________________________________
>>>> jts-devel mailing list
>>>> [hidden email]
>>>> http://lists.refractions.net/mailman/listinfo/jts-devel
>>>>
>>>
>>
>> _______________________________________________
>> jts-devel mailing list
>> [hidden email]
>> http://lists.refractions.net/mailman/listinfo/jts-devel
>>
>

--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Buffer operation performance

Sunburned Surveyor
This is an interesting discussion, although I don't pretend to
understand all of it. I did want to offer a suggestion on one thing
Martin said:

Martin wrote: "The catch is that the inefficiency is caused by the
local details of how complex the shape of the input linework is.  I
haven't yet found a good way of measuring this local complexity and
relating it to the buffer size."

It seems to me like we would want to determine how much one line
segment differed in direction from the previous line segments. If you
have a multi-segment LineString that is fairly straight, your buffer
computation will be fairly simple, when you have a multi-segment
LineString that wiggles all over the place you need the optimized
buffer routine.

One way to determine how "wiggled" your LineString would be is to test
for the variation in direction for each segment in the LineString
compared to the previous segment.

As an example, you could give each segment a point score. For each 10
degrees in variation of direction the segment would get one point. So
if the angle between two connected line segments was 60 degrees, the
second line segment would get 6 points. You could then sum the total
points and divide by the number of line segments to get an average
"wiggle" rating. You could use this rating to determine if the
optimized buffer routine would be needed.

I hope I am making sense. Perhaps I am thinking too much like a
surveyor and not enough like a mathematician. I always look for the
angles...

At any rate, if this would be worth pursuing it would be a good test
of my JTSWarped Anlge code. I could write a simple class that rates
the "wiggleness" of a provided LineString.

Of course, this scoring of "wiggleness" might take longer than the
non-optimized buffer opreation. :]

Let me know if I can help.

Landon

On Wed, Jul 30, 2008 at 2:09 PM, Martin Davis <[hidden email]> wrote:

> More on this topic...
>
> I've been doing some testing of my prototype implementation of "Buffer Input
> Simplification".  This uses a special-purpose linestring simplification
> algorithm which weeds out *concave* sections of the linework, but leaves
> *convex* sections untouched (up to a given tolerance).  This is based on the
> observation that as buffers get larger, the concave sections contribute less
> and the convex areas more to the shape of the final buffer.  In the limit,
> very large buffers are simply "blobs", which are dominated by a only a few
> of the larger "protrubances" in the input curve.
>
> Using this simplification technique with a conservative tolerance produces
> high-quality buffers which are very close to the "pure" buffer compute by
> the current JTS code (which is itself an approximation).  The best part is
> that by linking the tolerance factor to the buffer distance, as the distance
> goes up the performance of generating the overall buffer increases
> dramatically!   Some results (using Michael's test geometry) are given here:
>
> Running case   buffer dist = 10.0
> Num coords - input: 1031  simplified: 2045
> Finished in 234 ms
>
> Running case   buffer dist = 100.0
> Num coords - input: 1031  simplified: 2039
> Finished in 641 ms
>
> Running case   buffer dist = 200.0
> Num coords - input: 1031  simplified: 2036
> Finished in 719 ms
>
> Running case   buffer dist = 300.0
> Num coords - input: 1031  simplified: 2022
> Finished in 953 ms
>
> Running case   buffer dist = 400.0
> Num coords - input: 1031  simplified: 2005
> Finished in 968 ms
>
> Running case   buffer dist = 1000.0
> Num coords - input: 1031  simplified: 1651
> Finished in 985 ms
>
> Running case   buffer dist = 1100.0
> Num coords - input: 1031  simplified: 1617
> Finished in 953 ms
>
> Running case   buffer dist = 1200.0
> Num coords - input: 1031  simplified: 1563
> Finished in 1219 ms
>
> Running case   buffer dist = 1300.0
> Num coords - input: 1031  simplified: 1502
> Finished in 843 ms
>
> Running case   buffer dist = 2000.0
> Num coords - input: 1031  simplified: 1264
> Finished in 844 ms
>
> Running case   buffer dist = 10000.0
> Num coords - input: 1031  simplified: 470
> Finished in 281 ms
>
> Running case   buffer dist = 20000.0
> Num coords - input: 1031  simplified: 309
> Finished in 63 ms
>
> Running case   buffer dist = 30000.0
> Num coords - input: 1031  simplified: 233
> Finished in 31 ms
>
> This seems to me to be the most promising direction to take for optimizing
> the computation of large buffers.
>
> That said, the partitioned technique would parallelize nicely.  It can also
> be used in combination with the simplification technique.  So perhaps in a
> future "parallelJTS" they could both be used.
>
>
>
> Martin Davis wrote:
>>
>> Good stuff - look forward to seeing the results.
>>
>> As I said, an important piece of this puzzle is being able to decide
>> automatically when to cut over from the standard "monolithic" buffer
>> approach to the "partitioned" approach.  The catch is that the inefficiency
>> is caused by the local details of how complex the shape of the input
>> linework is.  I haven't yet found a good way of measuring this local
>> complexity and relating it to the buffer size.
>>
>> I still think the "outer simplification" ideas has some legs on it.  Would
>> you be interested in trying out this approach with my alpha code?
>>
>> Michael Michaud wrote:
>>>
>>> Hi,
>>>
>>>> Very interesting, Michael.  This "partitioned buffering" approach seems
>>>> pretty viable as well.  (It would also parallel nicely in a multi-core
>>>> environment!)
>>>
>>> Yes, but I'm not sure individual buffering takes much time compared to
>>> union operation (it would need more precise measurements)
>>>>
>>>> One limitation is that it's harder (or maybe impossible) to provide
>>>> different join styles using PB - but that is probably a minor price to pay.
>>>
>>> Right, I did not think about it.
>>> Partitioned buffering could be made available for "round" buffering only.
>>>>
>>>> Now, the challenge is to establish when to use the various approaches.
>>>>  Is it always better to use PB?  Or is there some cutover point between the
>>>> current buffer algorithm and PB?  This is one thing which has held me back
>>>> from offering these other options in JTS.  The choice of which method to use
>>>> really needs to be performed automatically by the library.
>>>
>>> I agree that a single test is not enough to make decision. To complete
>>> the test I'll try to measure the difference for
>>> 1 / 10 / 100 / 1000  segments
>>> and for a buffer distance equals to
>>> 0.01x / 0.1x / 1x / 10x / 100x / 1000x the mean segment length
>>> It would also be interesting to measure improvements for polygon
>>> buffering
>>>>
>>>> Can you send me your test dataset?
>>>
>>> Here is the 1031 points wkt of the linestring (I tried a 10000 buffer) :
>>>
>>> LINESTRING (
>>>   168000 75099.09,
>>>   168019.98 75079.81,
>>>   168058.38 75051.63,
>>>   168076.91 75045.01,
>>>   168096.34 75039.38,
>>>   168127.45 75021.15,
>>>   168167.12 74999.39,
>>>   168180.16 74991.79,
>>>   168192.45 74982.57,
>>>   168210.71 74972.38,
>>>   168227.46 74964.28,
>>>   168245.93 74951.24,
>>>   168256.76 74941.96,
>>>   168281.34 74925.48,
>>>   168317.49 74903.93,
>>>   168347.95 74893.42,
>>>   168359.81 74886.5,
>>>   168376.8 74873.61,
>>>   168396.02 74862.35,
>>>   168413.3 74857.15,
>>>   168427.85 74850.68,
>>>   168442.62 74840.26,
>>>   168472.25 74826.59,
>>>   168481.69 74819.74,
>>>   168509.94 74810.66,
>>>   168536.95 74796.66,
>>>   168568.02 74785.98,
>>>   168591.85 74776.06,
>>>   168620.28 74763.11,
>>>   168671.46 74735.14,
>>>   168702.77 74718.98,
>>>   168760.54 74684.78,
>>>   168790.68 74665.69,
>>>   168818.45 74651.59,
>>>   168839.39 74639.33,
>>>   168883.15 74612.66,
>>>   168904.37 74597.07,
>>>   168925.39 74585.69,
>>>   168947.76 74575.73,
>>>   168972.48 74562.28,
>>>   168996.29 74552.47,
>>>   169017.6 74547.3,
>>>   169028.94 74543.14,
>>>   169037.2 74537.14,
>>>   169052.36 74529.73,
>>>   169079 74518.34,
>>>   169124.49 74504.73,
>>>   169146.2 74496.7,
>>>   169160.17 74490.57,
>>>   169176.13 74483.44,
>>>   169186.06 74479.41,
>>>   169212.16 74474.08,
>>>   169227.63 74467.66,
>>>   169260.82 74439.9,
>>>   169276.59 74427.91,
>>>   169290.7 74415.52,
>>>   169305.05 74405.76,
>>>   169323.69 74389.86,
>>>   169339.44 74377.81,
>>>   169357.33 74366.16,
>>>   169414.53 74321.51,
>>>   169474.05 74282.78,
>>>   169489.52 74270.72,
>>>   169579.01 74223.09,
>>>   169604.78 74210.14,
>>>   169619.7 74199.66,
>>>   169629.14 74195.23,
>>>   169643.34 74192.88,
>>>   169659.96 74185.19,
>>>   169678.7 74177.96,
>>>   169693.96 74170.68,
>>>   169713.35 74162.96,
>>>   169739.08 74156.44,
>>>   169768.36 74152.97,
>>>   169799.54 74148.44,
>>>   169838.66 74144.65,
>>>   169885.9 74150.01,
>>>   169971.44 74167,
>>>   170024.34 74173.38,
>>>   170076.65 74178.2,
>>>   170094.55 74180.82,
>>>   170113.44 74185.45,
>>>   170132 74188.82,
>>>   170175.93 74192.59,
>>>   170205.21 74192.5,
>>>   170218.75 74191.32,
>>>   170233.84 74190.88,
>>>   170277.47 74190.61,
>>>   170316.34 74191.58,
>>>   170333.36 74190.76,
>>>   170348.04 74190.9,
>>>   170363.55 74188.79,
>>>   170393.8 74188.48,
>>>   170412.8 74190.33,
>>>   170431.6 74191.32,
>>>   170484.03 74196.25,
>>>   170516.54 74191.7,
>>>   170531.41 74190.82,
>>>   170558.77 74188.35,
>>>   170572.36 74182.24,
>>>   170583.63 74178.45,
>>>   170600.48 74171.3,
>>>   170638.11 74160.2,
>>>   170657.84 74153.73,
>>>   170670.51 74148.4,
>>>   170720.33 74125.39,
>>>   170749.99 74113.62,
>>>   170792.93 74100.61,
>>>   170835.33 74092.07,
>>>   170849.17 74088.43,
>>>   170863.59 74083.87,
>>>   170899.93 74068.73,
>>>   170939 74058.28,
>>>   170966.12 74049,
>>>   170989.65 74044.69,
>>>   171001.68 74041.17,
>>>   171028.85 74030.8,
>>>   171053.39 74019.23,
>>>   171081.07 74007.94,
>>>   171102.14 74002.15,
>>>   171117.33 73997.16,
>>>   171142.09 73992.68,
>>>   171151.89 73991.51,
>>>   171198.97 73979.07,
>>>   171232.93 73972.48,
>>>   171243.99 73969.27,
>>>   171268.54 73966.34,
>>>   171301.94 73958.88,
>>>   171310.31 73958.18,
>>>   171318.46 73959.11,
>>>   171334.75 73959.34,
>>>   171360.8 73955.36,
>>>   171390.53 73952.29,
>>>   171407.27 73951.84,
>>>   171454.52 73946.27,
>>>   171532.91 73942.72,
>>>   171559.19 73942.74,
>>>   171586.59 73941.28,
>>>   171606.07 73941.02,
>>>   171632.04 73942.05,
>>>   171648.7 73941.96,
>>>   171664.69 73940.23,
>>>   171703.79 73932.17,
>>>   171725.83 73923.91,
>>>   171786.57 73908.02,
>>>   171811.39 73902.01,
>>>   171862.01 73883.19,
>>>   171881.03 73877.34,
>>>   171904.53 73869.1,
>>>   171924.75 73861,
>>>   171942.63 73855.66,
>>>   171967.52 73846.29,
>>>   171989.09 73837.11,
>>>   172048.82 73819.06,
>>>   172065.95 73811.98,
>>>   172081.18 73803.66,
>>>   172112.57 73792.61,
>>>   172141.47 73781.54,
>>>   172199.07 73754.61,
>>>   172220.41 73746.36,
>>>   172258.74 73737.64,
>>>   172308.01 73719.25,
>>>   172327.08 73714.16,
>>>   172341.9 73711.22,
>>>   172357.39 73706.04,
>>>   172373.89 73699.51,
>>>   172387.83 73695.45,
>>>   172458.09 73667.62,
>>>   172487.31 73654.97,
>>>   172501.31 73647.79,
>>>   172537.91 73627.37,
>>>   172586.45 73599.14,
>>>   172602.33 73591.61,
>>>   172651.56 73576.46,
>>>   172666.88 73571.13,
>>>   172692.9 73558.6,
>>>   172709.76 73549.34,
>>>   172740.08 73534.5,
>>>   172760 73523.41,
>>>   172776.57 73511.27,
>>>   172785.72 73506.09,
>>>   172795.79 73501.6,
>>>   172806.59 73500.89,
>>>   172817.66 73498.13,
>>>   172826.77 73492.83,
>>>   172843.25 73480.68,
>>>   172861.8 73468.4,
>>>   172871.7 73463.21,
>>>   172918.85 73435.31,
>>>   172934.75 73420.57,
>>>   172999.52 73375.23,
>>>   173052.08 73332.33,
>>>   173061.72 73326.05,
>>>   173083.73 73320.93,
>>>   173102.39 73312.88,
>>>   173123.43 73301.81,
>>>   173152.75 73282.68,
>>>   173209.2 73242.11,
>>>   173228.86 73230.1,
>>>   173238.95 73224.75,
>>>   173249.15 73217.87,
>>>   173276.84 73196.72,
>>>   173338.16 73146.47,
>>>   173348.23 73139,
>>>   173384.35 73114.23,
>>>   173430.5 73084.55,
>>>   173440.47 73076.9,
>>>   173450.62 73072.16,
>>>   173469.56 73061.59,
>>>   173479.51 73055.68,
>>>   173497.59 73042.86,
>>>   173507.16 73038.03,
>>>   173528.29 73029.23,
>>>   173559.43 73019.59,
>>>   173569.08 73014.36,
>>>   173587.09 73001.77,
>>>   173674.43 72947.17,
>>>   173701.14 72928.72,
>>>   173709.48 72921.58,
>>>   173724.28 72906.98,
>>>   173739.66 72893.97,
>>>   173749.59 72890.25,
>>>   173775.23 72869.71,
>>>   173785.3 72863.62,
>>>   173818.13 72836.11,
>>>   173827.45 72829.13,
>>>   173856.34 72812.25,
>>>   173865.78 72805.46,
>>>   173875.48 72801,
>>>   173884.38 72795.17,
>>>   173917.08 72767.14,
>>>   173926.86 72762.21,
>>>   173937.93 72763.44,
>>>   173967.05 72749.76,
>>>   173974.73 72741.71,
>>>   173983.02 72734.67,
>>>   173992.68 72727.88,
>>>   174001.83 72722.59,
>>>   174030.88 72707.71,
>>>   174051.2 72698.45,
>>>   174071.1 72687.2,
>>>   174081.39 72683.5,
>>>   174089.48 72685.37,
>>>   174109.71 72677.64,
>>>   174119.75 72678.34,
>>>   174128.19 72671.13,
>>>   174137.3 72664.75,
>>>   174146.85 72659.03,
>>>   174157.34 72654.76,
>>>   174165.35 72648.08,
>>>   174184.53 72637.86,
>>>   174193.88 72633.25,
>>>   174204.59 72631.67,
>>>   174214.39 72625.59,
>>>   174224.21 72621.86,
>>>   174234.42 72616.88,
>>>   174243.59 72610.11,
>>>   174253.83 72605.56,
>>>   174274.88 72598.13,
>>>   174283.78 72592.38,
>>>   174300.78 72576.21,
>>>   174308.71 72569.51,
>>>   174359.48 72528.51,
>>>   174398.79 72492.94,
>>>   174405.5 72484.28,
>>>   174411.53 72474.83,
>>>   174419.13 72466.61,
>>>   174427.17 72459.43,
>>>   174458.79 72425.51,
>>>   174464.86 72417.51,
>>>   174477.4 72397.91,
>>>   174481.96 72388.65,
>>>   174486.63 72377.13,
>>>   174498.42 72343.67,
>>>   174502.95 72333.07,
>>>   174526.81 72283.89,
>>>   174536.17 72262.58,
>>>   174553.04 72234.6,
>>>   174561.1 72226.58,
>>>   174567.54 72216.87,
>>>   174571.16 72206.15,
>>>   174571.79 72195.91,
>>>   174574.97 72185.45,
>>>   174581.47 72175.77,
>>>   174590.94 72156.19,
>>>   174598.5 72148.42,
>>>   174604.26 72138.96,
>>>   174614.61 72119.31,
>>>   174617.86 72109.68,
>>>   174618.88 72098.83,
>>>   174620.62 72088.92,
>>>   174623.58 72079.08,
>>>   174652.24 72019.39,
>>>   174672.82 71980,
>>>   174679.52 71957.62,
>>>   174688.5 71937.78,
>>>   174699.09 71920.14,
>>>   174705.95 71911.18,
>>>   174713.49 71904.44,
>>>   174718.78 71894.98,
>>>   174725.86 71874.85,
>>>   174732.59 71864.99,
>>>   174738.83 71856.73,
>>>   174746.65 71848.06,
>>>   174756.08 71841.4,
>>>   174760.53 71831.95,
>>>   174772.07 71813.16,
>>>   174786.69 71793.3,
>>>   174801.7 71775.1,
>>>   174809.49 71766.29,
>>>   174826.27 71749.24,
>>>   174859.56 71717.58,
>>>   174866.89 71709.21,
>>>   174880.19 71691.3,
>>>   174887 71683.71,
>>>   174895.32 71676.12,
>>>   174904.3 71671.55,
>>>   174913.56 71664.66,
>>>   174920.92 71656.83,
>>>   174927.07 71648.48,
>>>   174935.22 71640.33,
>>>   174943.94 71634.84,
>>>   174954.01 71631.94,
>>>   174970.02 71616.71,
>>>   174986.09 71603.63,
>>>   174992.75 71595.93,
>>>   174997.89 71586.08,
>>>   175002.77 71574.24,
>>>   175007.92 71566.95,
>>>   175021.39 71554.85,
>>>   175026.4 71547.19,
>>>   175030.56 71538.06,
>>>   175044.96 71517.18,
>>>   175060.26 71493.05,
>>>   175077.44 71472.78,
>>>   175094.51 71455.41,
>>>   175111.47 71442.59,
>>>   175143.7 71420.42,
>>>   175156.81 71408.96,
>>>   175188.77 71371.82,
>>>   175267.54 71302.71,
>>>   175284.55 71286.73,
>>>   175299.75 71269.13,
>>>   175358.64 71206.84,
>>>   175396.74 71163.01,
>>>   175411.28 71150.26,
>>>   175442.64 71127.33,
>>>   175457.59 71115.13,
>>>   175500.48 71075.17,
>>>   175523.01 71052.94,
>>>   175566.34 71002.67,
>>>   175585.5 70982.26,
>>>   175601.18 70968.3,
>>>   175635.48 70940.41,
>>>   175645.97 70928.51,
>>>   175657.05 70917.56,
>>>   175669.35 70907.51,
>>>   175680.17 70899.55,
>>>   175708.08 70884.05,
>>>   175719.1 70875.15,
>>>   175728.9 70865.65,
>>>   175748.84 70840.67,
>>>   175760.26 70828.78,
>>>   175772.96 70816.86,
>>>   175797.59 70795.41,
>>>   175820.4 70771.58,
>>>   175830.81 70758.94,
>>>   175887.26 70702.46,
>>>   175939.77 70657.23,
>>>   175964.24 70638.02,
>>>   175991.59 70619.95,
>>>   176055.64 70575.16,
>>>   176079.86 70557.44,
>>>   176099.14 70540.66,
>>>   176111.84 70528.48,
>>>   176124.85 70521.62,
>>>   176138.75 70516.52,
>>>   176151.24 70509.62,
>>>   176162.55 70497.52,
>>>   176175.72 70481.45,
>>>   176206.32 70435.37,
>>>   176222.38 70407.62,
>>>   176237.17 70375.68,
>>>   176249.61 70346.63,
>>>   176265.36 70306.53,
>>>   176289.61 70252.4,
>>>   176304.59 70228.36,
>>>   176325.15 70199.27,
>>>   176346.33 70164.59,
>>>   176363.73 70134.77,
>>>   176376.6 70110.47,
>>>   176398.34 70074.51,
>>>   176425.63 70037.09,
>>>   176461.29 69993.33,
>>>   176538.04 69890.48,
>>>   176611.31 69795.95,
>>>   176642.89 69757.61,
>>>   176653.34 69740.97,
>>>   176667.53 69705.46,
>>>   176694.82 69587.45,
>>>   176710.85 69542.86,
>>>   176729.65 69499.4,
>>>   176750.13 69456.2,
>>>   176759.92 69440.95,
>>>   176765.47 69440.79,
>>>   176769.55 69437.84,
>>>   176775.95 69428.35,
>>>   176816.39 69344.34,
>>>   176838.52 69303.52,
>>>   176841.61 69288.41,
>>>   176847.4 69271.24,
>>>   176853.88 69257.39,
>>>   176866.38 69224.77,
>>>   176884.05 69191.75,
>>>   176908.14 69156.34,
>>>   176932.6 69124.48,
>>>   176941.5 69109.01,
>>>   176952.75 69087.58,
>>>   176962.34 69066.66,
>>>   177011.99 68975.48,
>>>   177047.55 68904.3,
>>>   177075.71 68857.75,
>>>   177086.06 68846.79,
>>>   177093.45 68840.28,
>>>   177113.15 68819.4,
>>>   177125.53 68803.37,
>>>   177145.01 68774.81,
>>>   177162.81 68744.93,
>>>   177175.04 68722.96,
>>>   177183.89 68711.15,
>>>   177195.55 68697.11,
>>>   177206.23 68681.8,
>>>   177232.19 68640.09,
>>>   177250.19 68607.22,
>>>   177286.85 68548.09,
>>>   177331.39 68483.17,
>>>   177380.45 68419.09,
>>>   177385.25 68410.57,
>>>   177415.26 68372.12,
>>>   177436.17 68348.33,
>>>   177461.11 68318.37,
>>>   177477.56 68301.44,
>>>   177486.38 68290.59,
>>>   177497.15 68278.98,
>>>   177504.31 68271.41,
>>>   177514.19 68263.47,
>>>   177531.39 68251.34,
>>>   177547.84 68236.75,
>>>   177556 68228.1,
>>>   177562.23 68220.36,
>>>   177604.15 68155.74,
>>>   177608.84 68145.94,
>>>   177623.1 68120.44,
>>>   177629.69 68105.2,
>>>   177650.02 68073.08,
>>>   177654.45 68065.11,
>>>   177658.56 68050.95,
>>>   177662.82 68042,
>>>   177667.36 68024.84,
>>>   177671 68015.54,
>>>   177681.4 67994.43,
>>>   177693.6 67949.74,
>>>   177703.26 67919.53,
>>>   177706.63 67911.94,
>>>   177714 67899.68,
>>>   177716.44 67893.18,
>>>   177718.91 67884.28,
>>>   177720.55 67871.14,
>>>   177724.45 67851.53,
>>>   177727.55 67839.84,
>>>   177728.77 67829,
>>>   177730.93 67818.94,
>>>   177739.33 67800.24,
>>>   177749.1 67785.58,
>>>   177752.04 67778.56,
>>>   177753.75 67770.32,
>>>   177746.91 67735.03,
>>>   177749.64 67718.67,
>>>   177751.88 67673.54,
>>>   177757.49 67617.74,
>>>   177766.81 67556.29,
>>>   177774.75 67524.5,
>>>   177789.56 67484.51,
>>>   177799.11 67451.34,
>>>   177808.39 67423.01,
>>>   177818.88 67380.1,
>>>   177824.98 67359.84,
>>>   177834.3 67337.45,
>>>   177842.13 67315.31,
>>>   177848.2 67276,
>>>   177855.87 67246.99,
>>>   177863.04 67223.1,
>>>   177875.61 67190.41,
>>>   177879.98 67179.07,
>>>   177883.21 67166.85,
>>>   177884.93 67160.33,
>>>   177887.27 67151.44,
>>>   177898.41 67109.32,
>>>   177909.04 67078.94,
>>>   177913.49 67064.05,
>>>   177918.13 67052.99,
>>>   177923.74 67042.42,
>>>   177929.09 67035.22,
>>>   177930.69 67029.22,
>>>   177930.66 67018.64,
>>>   177941.76 66972.23,
>>>   177945.36 66939.94,
>>>   177951.27 66907.91,
>>>   177952.98 66901.54,
>>>   177955.94 66887.96,
>>>   177959.41 66872.07,
>>>   177966.58 66851.6,
>>>   177971.62 66836.37,
>>>   177985.44 66786.6,
>>>   177989.64 66763.17,
>>>   177994.85 66733.27,
>>>   178001.66 66699.61,
>>>   178008.6 66667.66,
>>>   178013.75 66647.23,
>>>   178016.34 66636.11,
>>>   178017.08 66605.55,
>>>   178014.57 66554.14,
>>>   178010.24 66506.37,
>>>   178009.32 66465.24,
>>>   178009.96 66441.56,
>>>   178005.85 66419.82,
>>>   178002.49 66387.67,
>>>   177998.46 66338.04,
>>>   177993.35 66326.83,
>>>   177986.72 66324.9,
>>>   177985.23 66322.04,
>>>   177985.54 66319.15,
>>>   177989.56 66306.9,
>>>   177993.67 66298.82,
>>>   177995.86 66291.86,
>>>   177995.66 66289.33,
>>>   177992.99 66284.06,
>>>   177993.44 66281.23,
>>>   177992.3 66260.72,
>>>   177990.84 66248.64,
>>>   177981.56 66172.16,
>>>   177977.76 66141.43,
>>>   177974.54 66123.9,
>>>   177971.77 66108.86,
>>>   177967.86 66094.01,
>>>   177966.43 66092.26,
>>>   177967.2 66087.09,
>>>   177966.9 66082.9,
>>>   177966.02 66080.43,
>>>   177964.2 66078.21,
>>>   177963.59 66075.21,
>>>   177964.74 66064.46,
>>>   177964.35 66055.86,
>>>   177963.28 66052.01,
>>>   177959.34 66029.13,
>>>   177960.61 66022.97,
>>>   177959.04 66018.46,
>>>   177956.76 66015.2,
>>>   177956.89 66012.74,
>>>   177958.77 66009.48,
>>>   177959.85 66004.68,
>>>   177957.01 65995.03,
>>>   177957.25 65986.78,
>>>   177956.14 65982.15,
>>>   177953.29 65979.39,
>>>   177952.17 65976.64,
>>>   177957.95 65969.74,
>>>   177959.19 65962.62,
>>>   177957.37 65900.17,
>>>   177953.57 65856.26,
>>>   177953.93 65817.35,
>>>   177953.88 65813.27,
>>>   177955.48 65807.19,
>>>   177956.46 65799.14,
>>>   177955.03 65777.69,
>>>   177956.4 65734.55,
>>>   177956.23 65719.34,
>>>   177953.1 65713.03,
>>>   177954.45 65705.09,
>>>   177957.1 65697.01,
>>>   177956.84 65685.15,
>>>   177959 65679.49,
>>>   177959.49 65671.26,
>>>   177961.48 65638.16,
>>>   177968.9 65592.02,
>>>   177975.6 65560.06,
>>>   177979.15 65534.98,
>>>   177979.38 65495.95,
>>>   177982.31 65407.44,
>>>   177984.68 65358.91,
>>>   177987.11 65325.67,
>>>   177986.1 65293.15,
>>>   177989.96 65264.47,
>>>   177995.42 65209.31,
>>>   178001.47 65168.9,
>>>   178008.8 65113.21,
>>>   178013.31 65003.86,
>>>   178012.51 64952.06,
>>>   178009.63 64847.94,
>>>   178017.62 64682.43,
>>>   178021.64 64541.27,
>>>   178023.13 64396.67,
>>>   178027.75 64137.61,
>>>   178025.76 64028.45,
>>>   178020.43 63910.8,
>>>   178020.72 63849.5,
>>>   178029.19 63778.85,
>>>   178032.16 63763.6,
>>>   178032.6 63749.92,
>>>   178030.32 63733.73,
>>>   178026.47 63721.29,
>>>   178021.04 63709.32,
>>>   178016.35 63702.9,
>>>   178011.71 63699.25,
>>>   178006.61 63698.96,
>>>   178008.27 63678.14,
>>>   178009.61 63661.41,
>>>   178024.73 63657.03,
>>>   178035.53 63651.2,
>>>   178042.7 63644.43,
>>>   178048.96 63635.33,
>>>   178054.42 63625.44,
>>>   178066.74 63513.4,
>>>   178079.29 63350.15,
>>>   178113.91 63043.92,
>>>   178125.17 62967.61,
>>>   178139.81 62861.77,
>>>   178160.03 62739.24,
>>>   178166.8 62690.71,
>>>   178180.6 62598.21,
>>>   178196.38 62478.9,
>>>   178205.95 62429.83,
>>>   178215.68 62390.38,
>>>   178225.95 62355.56,
>>>   178234.91 62330.13,
>>>   178243.99 62312.58,
>>>   178252.42 62300.17,
>>>   178258.59 62293.76,
>>>   178271.74 62267.81,
>>>   178278.87 62259.41,
>>>   178281.2 62257.11,
>>>   178291.29 62241.06,
>>>   178296.59 62234.42,
>>>   178300.59 62233.22,
>>>   178306.14 62233.23,
>>>   178313.85 62230.84,
>>>   178318.53 62228.61,
>>>   178323.72 62225.14,
>>>   178329.38 62219.28,
>>>   178332.15 62217.39,
>>>   178339.35 62217.49,
>>>   178342.7 62218.66,
>>>   178343.51 62221.14,
>>>   178348.34 62226.92,
>>>   178351.79 62228.99,
>>>   178353.88 62228.77,
>>>   178354.79 62226.72,
>>>   178351.18 62221.84,
>>>   178353.07 62216.87,
>>>   178353.25 62214.12,
>>>   178355.63 62211.13,
>>>   178358.36 62209.3,
>>>   178361.9 62208.86,
>>>   178362.76 62206.43,
>>>   178361.97 62203.62,
>>>   178363.58 62201.57,
>>>   178374.53 62193.67,
>>>   178381.63 62189.79,
>>>   178385.43 62189.76,
>>>   178389.45 62192.04,
>>>   178392.01 62192.3,
>>>   178393.18 62189.44,
>>>   178391.57 62187.72,
>>>   178390.78 62185.63,
>>>   178399.88 62175.2,
>>>   178402.36 62174.4,
>>>   178407.71 62177.98,
>>>   178413.7 62175.14,
>>>   178419.05 62176.68,
>>>   178422.21 62174.44,
>>>   178423.73 62172.07,
>>>   178423.57 62169.19,
>>>   178421.96 62166.64,
>>>   178418.94 62165,
>>>   178415.85 62165.96,
>>>   178412.1 62170.44,
>>>   178409.48 62169.88,
>>>   178407.72 62163.55,
>>>   178411.95 62162.4,
>>>   178418.53 62156.4,
>>>   178423.46 62150.54,
>>>   178426.56 62148.62,
>>>   178429.7 62149.94,
>>>   178432.71 62149.19,
>>>   178435.99 62144.98,
>>>   178436.76 62142.14,
>>>   178439.36 62139.27,
>>>   178442.84 62138.83,
>>>   178445.4 62135.85,
>>>   178447.6 62128.51,
>>>   178451.73 62120.49,
>>>   178454.01 62118.47,
>>>   178457.62 62116.53,
>>>   178458.69 62112.83,
>>>   178461.1 62111.48,
>>>   178464.42 62110.72,
>>>   178466.21 62108.01,
>>>   178467.1 62104.31,
>>>   178465.62 62097.07,
>>>   178468.42 62087.79,
>>>   178468.55 62082.53,
>>>   178466.59 62081.04,
>>>   178458.84 62079.15,
>>>   178456.58 62076.29,
>>>   178455.86 62072.53,
>>>   178457.63 62070.82,
>>>   178458.45 62068.91,
>>>   178456.51 62066.55,
>>>   178459.35 62062.85,
>>>   178452.82 62060.08,
>>>   178449.82 62056.67,
>>>   178450.62 62053.45,
>>>   178453.32 62051.97,
>>>   178455.16 62049.21,
>>>   178454.93 62047.57,
>>>   178452.23 62046.52,
>>>   178450.69 62043.67,
>>>   178451.11 62040.83,
>>>   178454.12 62039.86,
>>>   178455.53 62036.39,
>>>   178454.73 62032.33,
>>>   178452.91 62029.35,
>>>   178448.3 62026.56,
>>>   178445.22 62025.7,
>>>   178429.07 62026.53,
>>>   178424.89 62023.48,
>>>   178422.86 62005.51,
>>>   178421.81 61980.76,
>>>   178421.89 61962.48,
>>>   178423.58 61949.11,
>>>   178430.17 61919.22,
>>>   178433.41 61907.8,
>>>   178443.14 61886.28,
>>>   178468.73 61806.63,
>>>   178479.68 61780.1,
>>>   178494.89 61734.32,
>>>   178511.46 61692.33,
>>>   178518.28 61666.62,
>>>   178533.34 61622.92,
>>>   178544.99 61595.95,
>>>   178567.61 61537.18,
>>>   178574.74 61521.82,
>>>   178583.21 61495.5,
>>>   178598.58 61458.21,
>>>   178614.24 61428.39,
>>>   178650.58 61354,
>>>   178658.76 61340.98,
>>>   178665.02 61327.95,
>>>   178674.8 61313.2,
>>>   178700.24 61274.86,
>>>   178719.61 61242.68,
>>>   178738.79 61214.38,
>>>   178758.9 61190.94,
>>>   178770.37 61180.47,
>>>   178789.81 61169.58,
>>>   178812.25 61159.56,
>>>   178824.56 61155.6,
>>>   178835.46 61148.73,
>>>   178850.86 61141.32,
>>>   178877.94 61132.47,
>>>   178905.39 61124.35,
>>>   178921.76 61117.34,
>>>   178937.67 61111.55,
>>>   178980.84 61104.68,
>>>   179007.68 61098.47,
>>>   179056.28 61084.32,
>>>   179128.36 61065.61,
>>>   179202.82 61047.78,
>>>   179276.21 61027.13,
>>>   179472.42 60961.08,
>>>   179529.07 60936.85,
>>>   179542.88 60927.94,
>>>   179549.41 60922,
>>>   179555.08 60911.73,
>>>   179559.44 60900.77,
>>>   179562.28 60889.12,
>>>   179562.47 60877.05,
>>>   179560.63 60866.89,
>>>   179560.7 60863.09,
>>>   179562.37 60857.61,
>>>   179565.71 60846.64,
>>>   179567.54 60832.84,
>>>   179566.44 60823.14,
>>>   179565.06 60818.43,
>>>   179549.81 60764.67,
>>>   179550.31 60758.45,
>>>   179546.67 60734.77,
>>>   179549.49 60731.03,
>>>   179557.54 60733.31,
>>>   179561.13 60738.93,
>>>   179564.21 60739.89,
>>>   179566.89 60745.6,
>>>   179572.89 60748.67,
>>>   179575.31 60751.42,
>>>   179578.26 60756.38,
>>>   179578.33 60762.32,
>>>   179583.95 60763.05,
>>>   179583.19 60771.19,
>>>   179588.15 60772.63,
>>>   179588.19 60782.91,
>>>   179593.07 60784.13,
>>>   179589.87 60805.68,
>>>   179595.07 60815.48,
>>>   179600.01 60822.77,
>>>   179600.24 60826.95,
>>>   179602.21 60832.23,
>>>   179607.32 60835.03,
>>>   179620.58 60838.4,
>>>   179635.67 60841.41,
>>>   179651.26 60843.16,
>>>   179667.47 60843.16,
>>>   179681.53 60838.67,
>>>   179704.27 60828.05,
>>>   179724.08 60814.96,
>>>   179741.93 60801.19,
>>>   179753.86 60790.42,
>>>   179763.48 60779.45,
>>>   179766.88 60773.18,
>>>   179767.07 60771.12,
>>>   179762.6 60765.99,
>>>   179766.21 60747.38,
>>>   179770.94 60741.75,
>>>   179776.56 60738.66,
>>>   179779.2 60737.22,
>>>   179786.44 60742.03,
>>>   179793.9 60741.33,
>>>   179799.37 60742.37,
>>>   179807.42 60735.01,
>>>   179815.39 60724.84,
>>>   179811.05 60721.94,
>>>   179813.76 60715.68,
>>>   179820.14 60717.55,
>>>   179826.71 60710.34,
>>>   179829.53 60708.82,
>>>   179888.74 60612.93,
>>>   179947.13 60522.16,
>>>   179955.61 60507.32,
>>>   179964.18 60496.92,
>>>   179973.96 60490.42,
>>>   179979.79 60485.25,
>>>   179984.9 60477.61,
>>>   180001.97 60445.85,
>>>   180013.27 60430.79,
>>>   180047.31 60395.4,
>>>   180054.81 60389.16,
>>>   180071.26 60381.38,
>>>   180083.39 60373.8,
>>>   180100.66 60358.77,
>>>   180110.87 60348.94,
>>>   180115.99 60340.86,
>>>   180120.92 60330.67,
>>>   180131.3 60290.31,
>>>   180141.88 60252.91,
>>>   180145.41 60243.95,
>>>   180170.92 60161.14,
>>>   180176.4 60146.3,
>>>   180191.39 60114.53,
>>>   180200.97 60096.39,
>>>   180212.16 60078.29,
>>>   180218.27 60071.66,
>>>   180235.86 60057.92,
>>>   180243.95 60050.52,
>>>   180249.63 60043.36,
>>>   180259.04 60025.98,
>>>   180266.35 60007.91,
>>>   180274.4 59993.5,
>>>   180281.06 59983.38,
>>>   180289.52 59973.93,
>>>   180315.7 59949.8,
>>>   180329.09 59939.62,
>>>   180338.31 59934.05,
>>>   180354.18 59926.34,
>>>   180362.13 59924.76,
>>>   180369.12 59926.79,
>>>   180375.15 59931.75,
>>>   180383 59935.53,
>>>   180388.11 59938.77,
>>>   180396.42 59949.49,
>>>   180400.6 59946.77,
>>>   180405.01 59956.2,
>>>   180407.23 59954.8,
>>>   180409.16 59952.08,
>>>   180431.99 59882.17,
>>>   180489.59 59719.98,
>>>   180516.16 59668.73,
>>>   180544.76 59619.86,
>>>   180564.25 59578.8,
>>>   180573.7 59551.7,
>>>   180580.79 59525.35,
>>>   180588.37 59505.63,
>>>   180604.12 59473.13,
>>>   180622.29 59445.18,
>>>   180631.91 59429.05,
>>>   180637.83 59412.74,
>>>   180656.17 59339.6,
>>>   180669.41 59299.14,
>>>   180679.64 59275.76,
>>>   180684.28 59266.53,
>>>   180686.05 59263.02,
>>>   180697.93 59246.56,
>>>   180747.67 59189.18,
>>>   180759.28 59178.74,
>>>   180772.99 59167.85,
>>>   180785.83 59162,
>>>   180798.34 59158.18,
>>>   180813.74 59154.37,
>>>   180832.3 59151.97,
>>>   180855.11 59147.46,
>>>   180861.98 59142.9,
>>>   180866.27 59138.42,
>>>   180872.11 59130.67,
>>>   180909.6 59075.52,
>>>   180922.07 59061.58,
>>>   180930.79 59055.13,
>>>   180943.08 59050.38,
>>>   180953.99 59047.52,
>>>   180964.78 59041.87,
>>>   180975.83 59032.72,
>>>   180985.33 59022.92,
>>>   181000.57 59002.51,
>>>   181013.17 58990.67,
>>>   181024.71 58983.21,
>>>   181035.92 58978.57,
>>>   181050.06 58975.38,
>>>   181076.88 58972.92,
>>>   181087.67 58970.91,
>>>   181099.7 58966.76,
>>>   181122.01 58955.77,
>>>   181146.14 58947.76,
>>>   181157.78 58942.19,
>>>   181167.75 58934.2,
>>>   181177.2 58925.53,
>>>   181192.11 58906.31,
>>>   181233.44 58862,
>>>   181243.56 58849.94,
>>>   181262.63 58824.07,
>>>   181269.81 58813.01,
>>>   181278.57 58797.49,
>>>   181286.69 58781,
>>>   181294.3 58748.54,
>>>   181297.43 58721.7,
>>>   181293.95 58693.46,
>>>   181279.45 58644.96,
>>>   181271.49 58621.9,
>>>   181245.24 58566.88,
>>>   181234.84 58548.6,
>>>   181226.25 58524.73,
>>>   181207.37 58438.02,
>>>   181193.75 58388.29,
>>>   181183.54 58357.62,
>>>   181169.67 58302.15,
>>>   181163.49 58274.38,
>>>   181159.28 58246,
>>>   181147.89 58107.32,
>>>   181147.06 57991.43,
>>>   181148.81 57965.73,
>>>   181150.16 57909.44,
>>>   181151.32 57888.4,
>>>   181156.51 57844.11,
>>>   181163.68 57796.12,
>>>   181177.45 57719.23,
>>>   181202.13 57619.71,
>>>   181224.13 57544.69,
>>>   181254.77 57474.29,
>>>   181263.88 57451,
>>>   181283.27 57406.83,
>>>   181308.26 57364,
>>>   181321.91 57342.42,
>>>   181347.77 57297.32,
>>>   181375.92 57255.37,
>>>   181421.33 57195.25,
>>>   181465.37 57132.96,
>>>   181498.7 57089.91,
>>>   181515.73 57069.3,
>>>   181532.65 57051.11,
>>>   181546.73 57031.97,
>>>   181578.04 56994.2,
>>>   181592.81 56974.79,
>>>   181606.21 56955.33,
>>>   181617.19 56937.88,
>>>   181636.62 56901.76,
>>>   181644.91 56883.67,
>>>   181651.88 56866.37,
>>>   181658.28 56848.86,
>>>   181667.09 56820.5,
>>>   181670.79 56812.22,
>>>   181673.84 56805.41,
>>>   181679.95 56789.22,
>>>   181716.63 56710.19,
>>>   181727.56 56693.78,
>>>   181739.09 56674.37,
>>>   181760.36 56634.75,
>>>   181770.08 56621.43,
>>>   181806.52 56563.56,
>>>   181822.11 56541.55,
>>>   181853.29 56501.39,
>>>   181867.37 56484.47,
>>>   181915.43 56418.28,
>>>   181934.25 56389.84,
>>>   181989.88 56324.58,
>>>   182008.53 56304.44,
>>>   182028.06 56281.36,
>>>   182044.18 56260.03,
>>>   182077.17 56220.41,
>>>   182095.42 56200.24,
>>>   182149.64 56149,
>>>   182152.81 56145.38,
>>>   182165.25 56131.22,
>>>   182181.63 56109.2,
>>>   182226.84 56059.65,
>>>   182240.13 56042.18,
>>>   182249.84 56026.52,
>>>   182262.23 56004.41,
>>>   182269.66 55988.27,
>>>   182279.11 55970.17,
>>>   182302.19 55934.92,
>>>   182312.97 55920.44,
>>>   182334.13 55894.79,
>>>   182356.12 55865.14,
>>>   182427.98 55779.79,
>>>   182498.67 55702.44
>>> )
>>>
>>>>
>>>> Michael Michaud wrote:
>>>>>
>>>>> Hi Martin,
>>>>>
>>>>> Thanks for the precise answer.
>>>>> I do not know a good buffer algorithm but I made some further tests
>>>>> which show there is place for improvements with the excellent stuff you
>>>>> recently added.
>>>>>
>>>>> I created a simple linestring : length = 25000 m, number of segments =
>>>>> 1000
>>>>>
>>>>> Trying to create a buffer at a distance of 10000 m ended with a
>>>>> heapspace exception (took more than 256 Mo !) after more than 4 mn of
>>>>> intensive computation !
>>>>>
>>>>> The other way is :
>>>>> - decompose into segments : less than 1 s
>>>>> - create individual buffers : openjump says 8 s but I think it includes
>>>>> redrawing
>>>>> - cascaded union of resulting buffer : 6 s (less than 50 Mo)
>>>>>
>>>>> hope that helps
>>>>>
>>>>> Michael
>>>>>
>>>>>
>>>>>
>>>>> Martin Davis a écrit :
>>>>>>
>>>>>> The reason for this is that as the buffer size gets bigger, the "raw
>>>>>> offset curve" that is initially created prior to extracting the buffer
>>>>>> outline gets more and more complex.  Concave angles in the input geometry
>>>>>> result in perpendicular "closing lines" being created, which usually
>>>>>> intersect other offset lines.  The longer the perpendicular line, the more
>>>>>> other lines it intersects, and hence the more noding and topology analysis
>>>>>> has to be performed.  (I haven't found any good way of building the raw
>>>>>> offset curve to avoid or reduce this problem - if anyone has any ideas I'd
>>>>>> be interested to hear them).
>>>>>>
>>>>>> There's several ways that I've tried to reduce this problem:
>>>>>>
>>>>>> - compute the buffer in a series of steps, using an increasing series
>>>>>> of buffer distances which add up to the desired distance.  Each successive
>>>>>> buffer gets smoother, which makes the subsequent buffers run faster.  It may
>>>>>> only be necessary to iterate say 3 times to get a good result.  The trick of
>>>>>> course is to pick the right distances.
>>>>>>
>>>>>> - simplify the input geometry using DP, and a tolerance of say 2% of
>>>>>> the buffer distance
>>>>>>
>>>>>> - A better way of simplifying I've been experimenting with only
>>>>>> simplifies *outwards*.  This does 2 things - it reduces concavity (which is
>>>>>> the source of the problem), and it avoid "losing" convex protrubances (which
>>>>>> DP can often delete or alter).  Convex protrubances are the primary
>>>>>> influence on the shape of the resulting buffer, so it is important to
>>>>>> preserve them.  (Currently this code is in alpha only - but I can provide it
>>>>>> if anyone's interested)
>>>>>>
>>>>>> Martin
>>>>>>
>>>>>> Michael Michaud wrote:
>>>>>>>
>>>>>>> Hi,
>>>>>>>
>>>>>>> I noticed that OpenJUMP Buffer plugin performance decreases
>>>>>>> dramatically if a large buffer size is used :
>>>>>>> For a map with  rivers having vertices every few meters, I get :
>>>>>>>
>>>>>>> buffer =  25 m :     7 s
>>>>>>> buffer =  50 m :    16 s
>>>>>>> buffer = 100 m :    48 s
>>>>>>> buffer = 200 m : 2m 59 s
>>>>>>>
>>>>>>> The plugin uses the BufferOp class. I have no idea why a large buffer
>>>>>>> should take longer than a small one, and I don't know if there is a better
>>>>>>> way to compute a buffer.
>>>>>>>
>>>>>>> Any idea ?
>>>>>>>
>>>>>>> Michaël
>>>>>>>
>>>>>>> _______________________________________________
>>>>>>> jts-devel mailing list
>>>>>>> [hidden email]
>>>>>>> http://lists.refractions.net/mailman/listinfo/jts-devel
>>>>>>>
>>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> jts-devel mailing list
>>>>> [hidden email]
>>>>> http://lists.refractions.net/mailman/listinfo/jts-devel
>>>>>
>>>>
>>>
>>> _______________________________________________
>>> jts-devel mailing list
>>> [hidden email]
>>> http://lists.refractions.net/mailman/listinfo/jts-devel
>>>
>>
>
> --
> Martin Davis
> Senior Technical Architect
> Refractions Research, Inc.
> (250) 383-3022
>
> _______________________________________________
> jts-devel mailing list
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
>
_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Buffer operation performance

michaelm-2
In reply to this post by Martin Davis
Hi,

> More on this topic...
>
> I've been doing some testing of my prototype implementation of "Buffer
> Input Simplification".  This uses a special-purpose linestring
> simplification algorithm which weeds out *concave* sections of the
> linework, but leaves *convex* sections untouched (up to a given
> tolerance).  This is based on the observation that as buffers get
> larger, the concave sections contribute less and the convex areas more
> to the shape of the final buffer.  In the limit, very large buffers
> are simply "blobs", which are dominated by a only a few of the larger
> "protrubances" in the input curve.
Interesting !
Can we extrapolate and consider that in the limit the buffer of the line
equals the buffer of its convex hull ?
> Using this simplification technique with a conservative tolerance
> produces high-quality buffers which are very close to the "pure"
> buffer compute by the current JTS code (which is itself an
> approximation).  The best part is that by linking the tolerance factor
> to the buffer distance, as the distance goes up the performance of
> generating the overall buffer increases dramatically!   Some results
> (using Michael's test geometry) are given here:
How do you make sure that your conservative tolerance is, in fact,
conservative. Anyway, results are impressive, and having job done faster
for larger buffers is an excellent and unexpected result.
About your outputs compared to "pure buffer", I realize that buffer
outputs are never "pure" (because of curved parts) and it could make
sense to simplify the input line in a way which is both consistent with
the buffer size and the "segments per quadrant" parameter (but it may be
difficult to "measure" how the input line simplification will impact the
precision buffer output).

If I can help with tests, I'll try to do my best on my spare time.

Michaël

>
> Running case   buffer dist = 10.0
> Num coords - input: 1031  simplified: 2045
> Finished in 234 ms
>
> Running case   buffer dist = 100.0
> Num coords - input: 1031  simplified: 2039
> Finished in 641 ms
>
> Running case   buffer dist = 200.0
> Num coords - input: 1031  simplified: 2036
> Finished in 719 ms
>
> Running case   buffer dist = 300.0
> Num coords - input: 1031  simplified: 2022
> Finished in 953 ms
>
> Running case   buffer dist = 400.0
> Num coords - input: 1031  simplified: 2005
> Finished in 968 ms
>
> Running case   buffer dist = 1000.0
> Num coords - input: 1031  simplified: 1651
> Finished in 985 ms
>
> Running case   buffer dist = 1100.0
> Num coords - input: 1031  simplified: 1617
> Finished in 953 ms
>
> Running case   buffer dist = 1200.0
> Num coords - input: 1031  simplified: 1563
> Finished in 1219 ms
>
> Running case   buffer dist = 1300.0
> Num coords - input: 1031  simplified: 1502
> Finished in 843 ms
>
> Running case   buffer dist = 2000.0
> Num coords - input: 1031  simplified: 1264
> Finished in 844 ms
>
> Running case   buffer dist = 10000.0
> Num coords - input: 1031  simplified: 470
> Finished in 281 ms
>
> Running case   buffer dist = 20000.0
> Num coords - input: 1031  simplified: 309
> Finished in 63 ms
>
> Running case   buffer dist = 30000.0
> Num coords - input: 1031  simplified: 233
> Finished in 31 ms
>
> This seems to me to be the most promising direction to take for
> optimizing the computation of large buffers.
>
> That said, the partitioned technique would parallelize nicely.  It can
> also be used in combination with the simplification technique.  So
> perhaps in a future "parallelJTS" they could both be used.
>
>
>
> Martin Davis wrote:
>> Good stuff - look forward to seeing the results.
>>
>> As I said, an important piece of this puzzle is being able to decide
>> automatically when to cut over from the standard "monolithic" buffer
>> approach to the "partitioned" approach.  The catch is that the
>> inefficiency is caused by the local details of how complex the shape
>> of the input linework is.  I haven't yet found a good way of
>> measuring this local complexity and relating it to the buffer size.
>>
>> I still think the "outer simplification" ideas has some legs on it.  
>> Would you be interested in trying out this approach with my alpha code?
>>
>> Michael Michaud wrote:
>>> Hi,
>>>
>>>> Very interesting, Michael.  This "partitioned buffering" approach
>>>> seems pretty viable as well.  (It would also parallel nicely in a
>>>> multi-core environment!)
>>> Yes, but I'm not sure individual buffering takes much time compared
>>> to union operation (it would need more precise measurements)
>>>>
>>>> One limitation is that it's harder (or maybe impossible) to provide
>>>> different join styles using PB - but that is probably a minor price
>>>> to pay.
>>> Right, I did not think about it.
>>> Partitioned buffering could be made available for "round" buffering
>>> only.
>>>> Now, the challenge is to establish when to use the various
>>>> approaches.  Is it always better to use PB?  Or is there some
>>>> cutover point between the current buffer algorithm and PB?  This is
>>>> one thing which has held me back from offering these other options
>>>> in JTS.  The choice of which method to use really needs to be
>>>> performed automatically by the library.
>>> I agree that a single test is not enough to make decision. To
>>> complete the test I'll try to measure the difference for
>>> 1 / 10 / 100 / 1000  segments
>>> and for a buffer distance equals to
>>> 0.01x / 0.1x / 1x / 10x / 100x / 1000x the mean segment length
>>> It would also be interesting to measure improvements for polygon
>>> buffering
>>>> Can you send me your test dataset?
>>> Here is the 1031 points wkt of the linestring (I tried a 10000
>>> buffer) :
>>>
>>> LINESTRING (
>>>    168000 75099.09,
>>>    168019.98 75079.81,
>>>    168058.38 75051.63,
>>>    168076.91 75045.01,
>>>    168096.34 75039.38,
>>>    168127.45 75021.15,
>>>    168167.12 74999.39,
>>>    168180.16 74991.79,
>>>    168192.45 74982.57,
>>>    168210.71 74972.38,
>>>    168227.46 74964.28,
>>>    168245.93 74951.24,
>>>    168256.76 74941.96,
>>>    168281.34 74925.48,
>>>    168317.49 74903.93,
>>>    168347.95 74893.42,
>>>    168359.81 74886.5,
>>>    168376.8 74873.61,
>>>    168396.02 74862.35,
>>>    168413.3 74857.15,
>>>    168427.85 74850.68,
>>>    168442.62 74840.26,
>>>    168472.25 74826.59,
>>>    168481.69 74819.74,
>>>    168509.94 74810.66,
>>>    168536.95 74796.66,
>>>    168568.02 74785.98,
>>>    168591.85 74776.06,
>>>    168620.28 74763.11,
>>>    168671.46 74735.14,
>>>    168702.77 74718.98,
>>>    168760.54 74684.78,
>>>    168790.68 74665.69,
>>>    168818.45 74651.59,
>>>    168839.39 74639.33,
>>>    168883.15 74612.66,
>>>    168904.37 74597.07,
>>>    168925.39 74585.69,
>>>    168947.76 74575.73,
>>>    168972.48 74562.28,
>>>    168996.29 74552.47,
>>>    169017.6 74547.3,
>>>    169028.94 74543.14,
>>>    169037.2 74537.14,
>>>    169052.36 74529.73,
>>>    169079 74518.34,
>>>    169124.49 74504.73,
>>>    169146.2 74496.7,
>>>    169160.17 74490.57,
>>>    169176.13 74483.44,
>>>    169186.06 74479.41,
>>>    169212.16 74474.08,
>>>    169227.63 74467.66,
>>>    169260.82 74439.9,
>>>    169276.59 74427.91,
>>>    169290.7 74415.52,
>>>    169305.05 74405.76,
>>>    169323.69 74389.86,
>>>    169339.44 74377.81,
>>>    169357.33 74366.16,
>>>    169414.53 74321.51,
>>>    169474.05 74282.78,
>>>    169489.52 74270.72,
>>>    169579.01 74223.09,
>>>    169604.78 74210.14,
>>>    169619.7 74199.66,
>>>    169629.14 74195.23,
>>>    169643.34 74192.88,
>>>    169659.96 74185.19,
>>>    169678.7 74177.96,
>>>    169693.96 74170.68,
>>>    169713.35 74162.96,
>>>    169739.08 74156.44,
>>>    169768.36 74152.97,
>>>    169799.54 74148.44,
>>>    169838.66 74144.65,
>>>    169885.9 74150.01,
>>>    169971.44 74167,
>>>    170024.34 74173.38,
>>>    170076.65 74178.2,
>>>    170094.55 74180.82,
>>>    170113.44 74185.45,
>>>    170132 74188.82,
>>>    170175.93 74192.59,
>>>    170205.21 74192.5,
>>>    170218.75 74191.32,
>>>    170233.84 74190.88,
>>>    170277.47 74190.61,
>>>    170316.34 74191.58,
>>>    170333.36 74190.76,
>>>    170348.04 74190.9,
>>>    170363.55 74188.79,
>>>    170393.8 74188.48,
>>>    170412.8 74190.33,
>>>    170431.6 74191.32,
>>>    170484.03 74196.25,
>>>    170516.54 74191.7,
>>>    170531.41 74190.82,
>>>    170558.77 74188.35,
>>>    170572.36 74182.24,
>>>    170583.63 74178.45,
>>>    170600.48 74171.3,
>>>    170638.11 74160.2,
>>>    170657.84 74153.73,
>>>    170670.51 74148.4,
>>>    170720.33 74125.39,
>>>    170749.99 74113.62,
>>>    170792.93 74100.61,
>>>    170835.33 74092.07,
>>>    170849.17 74088.43,
>>>    170863.59 74083.87,
>>>    170899.93 74068.73,
>>>    170939 74058.28,
>>>    170966.12 74049,
>>>    170989.65 74044.69,
>>>    171001.68 74041.17,
>>>    171028.85 74030.8,
>>>    171053.39 74019.23,
>>>    171081.07 74007.94,
>>>    171102.14 74002.15,
>>>    171117.33 73997.16,
>>>    171142.09 73992.68,
>>>    171151.89 73991.51,
>>>    171198.97 73979.07,
>>>    171232.93 73972.48,
>>>    171243.99 73969.27,
>>>    171268.54 73966.34,
>>>    171301.94 73958.88,
>>>    171310.31 73958.18,
>>>    171318.46 73959.11,
>>>    171334.75 73959.34,
>>>    171360.8 73955.36,
>>>    171390.53 73952.29,
>>>    171407.27 73951.84,
>>>    171454.52 73946.27,
>>>    171532.91 73942.72,
>>>    171559.19 73942.74,
>>>    171586.59 73941.28,
>>>    171606.07 73941.02,
>>>    171632.04 73942.05,
>>>    171648.7 73941.96,
>>>    171664.69 73940.23,
>>>    171703.79 73932.17,
>>>    171725.83 73923.91,
>>>    171786.57 73908.02,
>>>    171811.39 73902.01,
>>>    171862.01 73883.19,
>>>    171881.03 73877.34,
>>>    171904.53 73869.1,
>>>    171924.75 73861,
>>>    171942.63 73855.66,
>>>    171967.52 73846.29,
>>>    171989.09 73837.11,
>>>    172048.82 73819.06,
>>>    172065.95 73811.98,
>>>    172081.18 73803.66,
>>>    172112.57 73792.61,
>>>    172141.47 73781.54,
>>>    172199.07 73754.61,
>>>    172220.41 73746.36,
>>>    172258.74 73737.64,
>>>    172308.01 73719.25,
>>>    172327.08 73714.16,
>>>    172341.9 73711.22,
>>>    172357.39 73706.04,
>>>    172373.89 73699.51,
>>>    172387.83 73695.45,
>>>    172458.09 73667.62,
>>>    172487.31 73654.97,
>>>    172501.31 73647.79,
>>>    172537.91 73627.37,
>>>    172586.45 73599.14,
>>>    172602.33 73591.61,
>>>    172651.56 73576.46,
>>>    172666.88 73571.13,
>>>    172692.9 73558.6,
>>>    172709.76 73549.34,
>>>    172740.08 73534.5,
>>>    172760 73523.41,
>>>    172776.57 73511.27,
>>>    172785.72 73506.09,
>>>    172795.79 73501.6,
>>>    172806.59 73500.89,
>>>    172817.66 73498.13,
>>>    172826.77 73492.83,
>>>    172843.25 73480.68,
>>>    172861.8 73468.4,
>>>    172871.7 73463.21,
>>>    172918.85 73435.31,
>>>    172934.75 73420.57,
>>>    172999.52 73375.23,
>>>    173052.08 73332.33,
>>>    173061.72 73326.05,
>>>    173083.73 73320.93,
>>>    173102.39 73312.88,
>>>    173123.43 73301.81,
>>>    173152.75 73282.68,
>>>    173209.2 73242.11,
>>>    173228.86 73230.1,
>>>    173238.95 73224.75,
>>>    173249.15 73217.87,
>>>    173276.84 73196.72,
>>>    173338.16 73146.47,
>>>    173348.23 73139,
>>>    173384.35 73114.23,
>>>    173430.5 73084.55,
>>>    173440.47 73076.9,
>>>    173450.62 73072.16,
>>>    173469.56 73061.59,
>>>    173479.51 73055.68,
>>>    173497.59 73042.86,
>>>    173507.16 73038.03,
>>>    173528.29 73029.23,
>>>    173559.43 73019.59,
>>>    173569.08 73014.36,
>>>    173587.09 73001.77,
>>>    173674.43 72947.17,
>>>    173701.14 72928.72,
>>>    173709.48 72921.58,
>>>    173724.28 72906.98,
>>>    173739.66 72893.97,
>>>    173749.59 72890.25,
>>>    173775.23 72869.71,
>>>    173785.3 72863.62,
>>>    173818.13 72836.11,
>>>    173827.45 72829.13,
>>>    173856.34 72812.25,
>>>    173865.78 72805.46,
>>>    173875.48 72801,
>>>    173884.38 72795.17,
>>>    173917.08 72767.14,
>>>    173926.86 72762.21,
>>>    173937.93 72763.44,
>>>    173967.05 72749.76,
>>>    173974.73 72741.71,
>>>    173983.02 72734.67,
>>>    173992.68 72727.88,
>>>    174001.83 72722.59,
>>>    174030.88 72707.71,
>>>    174051.2 72698.45,
>>>    174071.1 72687.2,
>>>    174081.39 72683.5,
>>>    174089.48 72685.37,
>>>    174109.71 72677.64,
>>>    174119.75 72678.34,
>>>    174128.19 72671.13,
>>>    174137.3 72664.75,
>>>    174146.85 72659.03,
>>>    174157.34 72654.76,
>>>    174165.35 72648.08,
>>>    174184.53 72637.86,
>>>    174193.88 72633.25,
>>>    174204.59 72631.67,
>>>    174214.39 72625.59,
>>>    174224.21 72621.86,
>>>    174234.42 72616.88,
>>>    174243.59 72610.11,
>>>    174253.83 72605.56,
>>>    174274.88 72598.13,
>>>    174283.78 72592.38,
>>>    174300.78 72576.21,
>>>    174308.71 72569.51,
>>>    174359.48 72528.51,
>>>    174398.79 72492.94,
>>>    174405.5 72484.28,
>>>    174411.53 72474.83,
>>>    174419.13 72466.61,
>>>    174427.17 72459.43,
>>>    174458.79 72425.51,
>>>    174464.86 72417.51,
>>>    174477.4 72397.91,
>>>    174481.96 72388.65,
>>>    174486.63 72377.13,
>>>    174498.42 72343.67,
>>>    174502.95 72333.07,
>>>    174526.81 72283.89,
>>>    174536.17 72262.58,
>>>    174553.04 72234.6,
>>>    174561.1 72226.58,
>>>    174567.54 72216.87,
>>>    174571.16 72206.15,
>>>    174571.79 72195.91,
>>>    174574.97 72185.45,
>>>    174581.47 72175.77,
>>>    174590.94 72156.19,
>>>    174598.5 72148.42,
>>>    174604.26 72138.96,
>>>    174614.61 72119.31,
>>>    174617.86 72109.68,
>>>    174618.88 72098.83,
>>>    174620.62 72088.92,
>>>    174623.58 72079.08,
>>>    174652.24 72019.39,
>>>    174672.82 71980,
>>>    174679.52 71957.62,
>>>    174688.5 71937.78,
>>>    174699.09 71920.14,
>>>    174705.95 71911.18,
>>>    174713.49 71904.44,
>>>    174718.78 71894.98,
>>>    174725.86 71874.85,
>>>    174732.59 71864.99,
>>>    174738.83 71856.73,
>>>    174746.65 71848.06,
>>>    174756.08 71841.4,
>>>    174760.53 71831.95,
>>>    174772.07 71813.16,
>>>    174786.69 71793.3,
>>>    174801.7 71775.1,
>>>    174809.49 71766.29,
>>>    174826.27 71749.24,
>>>    174859.56 71717.58,
>>>    174866.89 71709.21,
>>>    174880.19 71691.3,
>>>    174887 71683.71,
>>>    174895.32 71676.12,
>>>    174904.3 71671.55,
>>>    174913.56 71664.66,
>>>    174920.92 71656.83,
>>>    174927.07 71648.48,
>>>    174935.22 71640.33,
>>>    174943.94 71634.84,
>>>    174954.01 71631.94,
>>>    174970.02 71616.71,
>>>    174986.09 71603.63,
>>>    174992.75 71595.93,
>>>    174997.89 71586.08,
>>>    175002.77 71574.24,
>>>    175007.92 71566.95,
>>>    175021.39 71554.85,
>>>    175026.4 71547.19,
>>>    175030.56 71538.06,
>>>    175044.96 71517.18,
>>>    175060.26 71493.05,
>>>    175077.44 71472.78,
>>>    175094.51 71455.41,
>>>    175111.47 71442.59,
>>>    175143.7 71420.42,
>>>    175156.81 71408.96,
>>>    175188.77 71371.82,
>>>    175267.54 71302.71,
>>>    175284.55 71286.73,
>>>    175299.75 71269.13,
>>>    175358.64 71206.84,
>>>    175396.74 71163.01,
>>>    175411.28 71150.26,
>>>    175442.64 71127.33,
>>>    175457.59 71115.13,
>>>    175500.48 71075.17,
>>>    175523.01 71052.94,
>>>    175566.34 71002.67,
>>>    175585.5 70982.26,
>>>    175601.18 70968.3,
>>>    175635.48 70940.41,
>>>    175645.97 70928.51,
>>>    175657.05 70917.56,
>>>    175669.35 70907.51,
>>>    175680.17 70899.55,
>>>    175708.08 70884.05,
>>>    175719.1 70875.15,
>>>    175728.9 70865.65,
>>>    175748.84 70840.67,
>>>    175760.26 70828.78,
>>>    175772.96 70816.86,
>>>    175797.59 70795.41,
>>>    175820.4 70771.58,
>>>    175830.81 70758.94,
>>>    175887.26 70702.46,
>>>    175939.77 70657.23,
>>>    175964.24 70638.02,
>>>    175991.59 70619.95,
>>>    176055.64 70575.16,
>>>    176079.86 70557.44,
>>>    176099.14 70540.66,
>>>    176111.84 70528.48,
>>>    176124.85 70521.62,
>>>    176138.75 70516.52,
>>>    176151.24 70509.62,
>>>    176162.55 70497.52,
>>>    176175.72 70481.45,
>>>    176206.32 70435.37,
>>>    176222.38 70407.62,
>>>    176237.17 70375.68,
>>>    176249.61 70346.63,
>>>    176265.36 70306.53,
>>>    176289.61 70252.4,
>>>    176304.59 70228.36,
>>>    176325.15 70199.27,
>>>    176346.33 70164.59,
>>>    176363.73 70134.77,
>>>    176376.6 70110.47,
>>>    176398.34 70074.51,
>>>    176425.63 70037.09,
>>>    176461.29 69993.33,
>>>    176538.04 69890.48,
>>>    176611.31 69795.95,
>>>    176642.89 69757.61,
>>>    176653.34 69740.97,
>>>    176667.53 69705.46,
>>>    176694.82 69587.45,
>>>    176710.85 69542.86,
>>>    176729.65 69499.4,
>>>    176750.13 69456.2,
>>>    176759.92 69440.95,
>>>    176765.47 69440.79,
>>>    176769.55 69437.84,
>>>    176775.95 69428.35,
>>>    176816.39 69344.34,
>>>    176838.52 69303.52,
>>>    176841.61 69288.41,
>>>    176847.4 69271.24,
>>>    176853.88 69257.39,
>>>    176866.38 69224.77,
>>>    176884.05 69191.75,
>>>    176908.14 69156.34,
>>>    176932.6 69124.48,
>>>    176941.5 69109.01,
>>>    176952.75 69087.58,
>>>    176962.34 69066.66,
>>>    177011.99 68975.48,
>>>    177047.55 68904.3,
>>>    177075.71 68857.75,
>>>    177086.06 68846.79,
>>>    177093.45 68840.28,
>>>    177113.15 68819.4,
>>>    177125.53 68803.37,
>>>    177145.01 68774.81,
>>>    177162.81 68744.93,
>>>    177175.04 68722.96,
>>>    177183.89 68711.15,
>>>    177195.55 68697.11,
>>>    177206.23 68681.8,
>>>    177232.19 68640.09,
>>>    177250.19 68607.22,
>>>    177286.85 68548.09,
>>>    177331.39 68483.17,
>>>    177380.45 68419.09,
>>>    177385.25 68410.57,
>>>    177415.26 68372.12,
>>>    177436.17 68348.33,
>>>    177461.11 68318.37,
>>>    177477.56 68301.44,
>>>    177486.38 68290.59,
>>>    177497.15 68278.98,
>>>    177504.31 68271.41,
>>>    177514.19 68263.47,
>>>    177531.39 68251.34,
>>>    177547.84 68236.75,
>>>    177556 68228.1,
>>>    177562.23 68220.36,
>>>    177604.15 68155.74,
>>>    177608.84 68145.94,
>>>    177623.1 68120.44,
>>>    177629.69 68105.2,
>>>    177650.02 68073.08,
>>>    177654.45 68065.11,
>>>    177658.56 68050.95,
>>>    177662.82 68042,
>>>    177667.36 68024.84,
>>>    177671 68015.54,
>>>    177681.4 67994.43,
>>>    177693.6 67949.74,
>>>    177703.26 67919.53,
>>>    177706.63 67911.94,
>>>    177714 67899.68,
>>>    177716.44 67893.18,
>>>    177718.91 67884.28,
>>>    177720.55 67871.14,
>>>    177724.45 67851.53,
>>>    177727.55 67839.84,
>>>    177728.77 67829,
>>>    177730.93 67818.94,
>>>    177739.33 67800.24,
>>>    177749.1 67785.58,
>>>    177752.04 67778.56,
>>>    177753.75 67770.32,
>>>    177746.91 67735.03,
>>>    177749.64 67718.67,
>>>    177751.88 67673.54,
>>>    177757.49 67617.74,
>>>    177766.81 67556.29,
>>>    177774.75 67524.5,
>>>    177789.56 67484.51,
>>>    177799.11 67451.34,
>>>    177808.39 67423.01,
>>>    177818.88 67380.1,
>>>    177824.98 67359.84,
>>>    177834.3 67337.45,
>>>    177842.13 67315.31,
>>>    177848.2 67276,
>>>    177855.87 67246.99,
>>>    177863.04 67223.1,
>>>    177875.61 67190.41,
>>>    177879.98 67179.07,
>>>    177883.21 67166.85,
>>>    177884.93 67160.33,
>>>    177887.27 67151.44,
>>>    177898.41 67109.32,
>>>    177909.04 67078.94,
>>>    177913.49 67064.05,
>>>    177918.13 67052.99,
>>>    177923.74 67042.42,
>>>    177929.09 67035.22,
>>>    177930.69 67029.22,
>>>    177930.66 67018.64,
>>>    177941.76 66972.23,
>>>    177945.36 66939.94,
>>>    177951.27 66907.91,
>>>    177952.98 66901.54,
>>>    177955.94 66887.96,
>>>    177959.41 66872.07,
>>>    177966.58 66851.6,
>>>    177971.62 66836.37,
>>>    177985.44 66786.6,
>>>    177989.64 66763.17,
>>>    177994.85 66733.27,
>>>    178001.66 66699.61,
>>>    178008.6 66667.66,
>>>    178013.75 66647.23,
>>>    178016.34 66636.11,
>>>    178017.08 66605.55,
>>>    178014.57 66554.14,
>>>    178010.24 66506.37,
>>>    178009.32 66465.24,
>>>    178009.96 66441.56,
>>>    178005.85 66419.82,
>>>    178002.49 66387.67,
>>>    177998.46 66338.04,
>>>    177993.35 66326.83,
>>>    177986.72 66324.9,
>>>    177985.23 66322.04,
>>>    177985.54 66319.15,
>>>    177989.56 66306.9,
>>>    177993.67 66298.82,
>>>    177995.86 66291.86,
>>>    177995.66 66289.33,
>>>    177992.99 66284.06,
>>>    177993.44 66281.23,
>>>    177992.3 66260.72,
>>>    177990.84 66248.64,
>>>    177981.56 66172.16,
>>>    177977.76 66141.43,
>>>    177974.54 66123.9,
>>>    177971.77 66108.86,
>>>    177967.86 66094.01,
>>>    177966.43 66092.26,
>>>    177967.2 66087.09,
>>>    177966.9 66082.9,
>>>    177966.02 66080.43,
>>>    177964.2 66078.21,
>>>    177963.59 66075.21,
>>>    177964.74 66064.46,
>>>    177964.35 66055.86,
>>>    177963.28 66052.01,
>>>    177959.34 66029.13,
>>>    177960.61 66022.97,
>>>    177959.04 66018.46,
>>>    177956.76 66015.2,
>>>    177956.89 66012.74,
>>>    177958.77 66009.48,
>>>    177959.85 66004.68,
>>>    177957.01 65995.03,
>>>    177957.25 65986.78,
>>>    177956.14 65982.15,
>>>    177953.29 65979.39,
>>>    177952.17 65976.64,
>>>    177957.95 65969.74,
>>>    177959.19 65962.62,
>>>    177957.37 65900.17,
>>>    177953.57 65856.26,
>>>    177953.93 65817.35,
>>>    177953.88 65813.27,
>>>    177955.48 65807.19,
>>>    177956.46 65799.14,
>>>    177955.03 65777.69,
>>>    177956.4 65734.55,
>>>    177956.23 65719.34,
>>>    177953.1 65713.03,
>>>    177954.45 65705.09,
>>>    177957.1 65697.01,
>>>    177956.84 65685.15,
>>>    177959 65679.49,
>>>    177959.49 65671.26,
>>>    177961.48 65638.16,
>>>    177968.9 65592.02,
>>>    177975.6 65560.06,
>>>    177979.15 65534.98,
>>>    177979.38 65495.95,
>>>    177982.31 65407.44,
>>>    177984.68 65358.91,
>>>    177987.11 65325.67,
>>>    177986.1 65293.15,
>>>    177989.96 65264.47,
>>>    177995.42 65209.31,
>>>    178001.47 65168.9,
>>>    178008.8 65113.21,
>>>    178013.31 65003.86,
>>>    178012.51 64952.06,
>>>    178009.63 64847.94,
>>>    178017.62 64682.43,
>>>    178021.64 64541.27,
>>>    178023.13 64396.67,
>>>    178027.75 64137.61,
>>>    178025.76 64028.45,
>>>    178020.43 63910.8,
>>>    178020.72 63849.5,
>>>    178029.19 63778.85,
>>>    178032.16 63763.6,
>>>    178032.6 63749.92,
>>>    178030.32 63733.73,
>>>    178026.47 63721.29,
>>>    178021.04 63709.32,
>>>    178016.35 63702.9,
>>>    178011.71 63699.25,
>>>    178006.61 63698.96,
>>>    178008.27 63678.14,
>>>    178009.61 63661.41,
>>>    178024.73 63657.03,
>>>    178035.53 63651.2,
>>>    178042.7 63644.43,
>>>    178048.96 63635.33,
>>>    178054.42 63625.44,
>>>    178066.74 63513.4,
>>>    178079.29 63350.15,
>>>    178113.91 63043.92,
>>>    178125.17 62967.61,
>>>    178139.81 62861.77,
>>>    178160.03 62739.24,
>>>    178166.8 62690.71,
>>>    178180.6 62598.21,
>>>    178196.38 62478.9,
>>>    178205.95 62429.83,
>>>    178215.68 62390.38,
>>>    178225.95 62355.56,
>>>    178234.91 62330.13,
>>>    178243.99 62312.58,
>>>    178252.42 62300.17,
>>>    178258.59 62293.76,
>>>    178271.74 62267.81,
>>>    178278.87 62259.41,
>>>    178281.2 62257.11,
>>>    178291.29 62241.06,
>>>    178296.59 62234.42,
>>>    178300.59 62233.22,
>>>    178306.14 62233.23,
>>>    178313.85 62230.84,
>>>    178318.53 62228.61,
>>>    178323.72 62225.14,
>>>    178329.38 62219.28,
>>>    178332.15 62217.39,
>>>    178339.35 62217.49,
>>>    178342.7 62218.66,
>>>    178343.51 62221.14,
>>>    178348.34 62226.92,
>>>    178351.79 62228.99,
>>>    178353.88 62228.77,
>>>    178354.79 62226.72,
>>>    178351.18 62221.84,
>>>    178353.07 62216.87,
>>>    178353.25 62214.12,
>>>    178355.63 62211.13,
>>>    178358.36 62209.3,
>>>    178361.9 62208.86,
>>>    178362.76 62206.43,
>>>    178361.97 62203.62,
>>>    178363.58 62201.57,
>>>    178374.53 62193.67,
>>>    178381.63 62189.79,
>>>    178385.43 62189.76,
>>>    178389.45 62192.04,
>>>    178392.01 62192.3,
>>>    178393.18 62189.44,
>>>    178391.57 62187.72,
>>>    178390.78 62185.63,
>>>    178399.88 62175.2,
>>>    178402.36 62174.4,
>>>    178407.71 62177.98,
>>>    178413.7 62175.14,
>>>    178419.05 62176.68,
>>>    178422.21 62174.44,
>>>    178423.73 62172.07,
>>>    178423.57 62169.19,
>>>    178421.96 62166.64,
>>>    178418.94 62165,
>>>    178415.85 62165.96,
>>>    178412.1 62170.44,
>>>    178409.48 62169.88,
>>>    178407.72 62163.55,
>>>    178411.95 62162.4,
>>>    178418.53 62156.4,
>>>    178423.46 62150.54,
>>>    178426.56 62148.62,
>>>    178429.7 62149.94,
>>>    178432.71 62149.19,
>>>    178435.99 62144.98,
>>>    178436.76 62142.14,
>>>    178439.36 62139.27,
>>>    178442.84 62138.83,
>>>    178445.4 62135.85,
>>>    178447.6 62128.51,
>>>    178451.73 62120.49,
>>>    178454.01 62118.47,
>>>    178457.62 62116.53,
>>>    178458.69 62112.83,
>>>    178461.1 62111.48,
>>>    178464.42 62110.72,
>>>    178466.21 62108.01,
>>>    178467.1 62104.31,
>>>    178465.62 62097.07,
>>>    178468.42 62087.79,
>>>    178468.55 62082.53,
>>>    178466.59 62081.04,
>>>    178458.84 62079.15,
>>>    178456.58 62076.29,
>>>    178455.86 62072.53,
>>>    178457.63 62070.82,
>>>    178458.45 62068.91,
>>>    178456.51 62066.55,
>>>    178459.35 62062.85,
>>>    178452.82 62060.08,
>>>    178449.82 62056.67,
>>>    178450.62 62053.45,
>>>    178453.32 62051.97,
>>>    178455.16 62049.21,
>>>    178454.93 62047.57,
>>>    178452.23 62046.52,
>>>    178450.69 62043.67,
>>>    178451.11 62040.83,
>>>    178454.12 62039.86,
>>>    178455.53 62036.39,
>>>    178454.73 62032.33,
>>>    178452.91 62029.35,
>>>    178448.3 62026.56,
>>>    178445.22 62025.7,
>>>    178429.07 62026.53,
>>>    178424.89 62023.48,
>>>    178422.86 62005.51,
>>>    178421.81 61980.76,
>>>    178421.89 61962.48,
>>>    178423.58 61949.11,
>>>    178430.17 61919.22,
>>>    178433.41 61907.8,
>>>    178443.14 61886.28,
>>>    178468.73 61806.63,
>>>    178479.68 61780.1,
>>>    178494.89 61734.32,
>>>    178511.46 61692.33,
>>>    178518.28 61666.62,
>>>    178533.34 61622.92,
>>>    178544.99 61595.95,
>>>    178567.61 61537.18,
>>>    178574.74 61521.82,
>>>    178583.21 61495.5,
>>>    178598.58 61458.21,
>>>    178614.24 61428.39,
>>>    178650.58 61354,
>>>    178658.76 61340.98,
>>>    178665.02 61327.95,
>>>    178674.8 61313.2,
>>>    178700.24 61274.86,
>>>    178719.61 61242.68,
>>>    178738.79 61214.38,
>>>    178758.9 61190.94,
>>>    178770.37 61180.47,
>>>    178789.81 61169.58,
>>>    178812.25 61159.56,
>>>    178824.56 61155.6,
>>>    178835.46 61148.73,
>>>    178850.86 61141.32,
>>>    178877.94 61132.47,
>>>    178905.39 61124.35,
>>>    178921.76 61117.34,
>>>    178937.67 61111.55,
>>>    178980.84 61104.68,
>>>    179007.68 61098.47,
>>>    179056.28 61084.32,
>>>    179128.36 61065.61,
>>>    179202.82 61047.78,
>>>    179276.21 61027.13,
>>>    179472.42 60961.08,
>>>    179529.07 60936.85,
>>>    179542.88 60927.94,
>>>    179549.41 60922,
>>>    179555.08 60911.73,
>>>    179559.44 60900.77,
>>>    179562.28 60889.12,
>>>    179562.47 60877.05,
>>>    179560.63 60866.89,
>>>    179560.7 60863.09,
>>>    179562.37 60857.61,
>>>    179565.71 60846.64,
>>>    179567.54 60832.84,
>>>    179566.44 60823.14,
>>>    179565.06 60818.43,
>>>    179549.81 60764.67,
>>>    179550.31 60758.45,
>>>    179546.67 60734.77,
>>>    179549.49 60731.03,
>>>    179557.54 60733.31,
>>>    179561.13 60738.93,
>>>    179564.21 60739.89,
>>>    179566.89 60745.6,
>>>    179572.89 60748.67,
>>>    179575.31 60751.42,
>>>    179578.26 60756.38,
>>>    179578.33 60762.32,
>>>    179583.95 60763.05,
>>>    179583.19 60771.19,
>>>    179588.15 60772.63,
>>>    179588.19 60782.91,
>>>    179593.07 60784.13,
>>>    179589.87 60805.68,
>>>    179595.07 60815.48,
>>>    179600.01 60822.77,
>>>    179600.24 60826.95,
>>>    179602.21 60832.23,
>>>    179607.32 60835.03,
>>>    179620.58 60838.4,
>>>    179635.67 60841.41,
>>>    179651.26 60843.16,
>>>    179667.47 60843.16,
>>>    179681.53 60838.67,
>>>    179704.27 60828.05,
>>>    179724.08 60814.96,
>>>    179741.93 60801.19,
>>>    179753.86 60790.42,
>>>    179763.48 60779.45,
>>>    179766.88 60773.18,
>>>    179767.07 60771.12,
>>>    179762.6 60765.99,
>>>    179766.21 60747.38,
>>>    179770.94 60741.75,
>>>    179776.56 60738.66,
>>>    179779.2 60737.22,
>>>    179786.44 60742.03,
>>>    179793.9 60741.33,
>>>    179799.37 60742.37,
>>>    179807.42 60735.01,
>>>    179815.39 60724.84,
>>>    179811.05 60721.94,
>>>    179813.76 60715.68,
>>>    179820.14 60717.55,
>>>    179826.71 60710.34,
>>>    179829.53 60708.82,
>>>    179888.74 60612.93,
>>>    179947.13 60522.16,
>>>    179955.61 60507.32,
>>>    179964.18 60496.92,
>>>    179973.96 60490.42,
>>>    179979.79 60485.25,
>>>    179984.9 60477.61,
>>>    180001.97 60445.85,
>>>    180013.27 60430.79,
>>>    180047.31 60395.4,
>>>    180054.81 60389.16,
>>>    180071.26 60381.38,
>>>    180083.39 60373.8,
>>>    180100.66 60358.77,
>>>    180110.87 60348.94,
>>>    180115.99 60340.86,
>>>    180120.92 60330.67,
>>>    180131.3 60290.31,
>>>    180141.88 60252.91,
>>>    180145.41 60243.95,
>>>    180170.92 60161.14,
>>>    180176.4 60146.3,
>>>    180191.39 60114.53,
>>>    180200.97 60096.39,
>>>    180212.16 60078.29,
>>>    180218.27 60071.66,
>>>    180235.86 60057.92,
>>>    180243.95 60050.52,
>>>    180249.63 60043.36,
>>>    180259.04 60025.98,
>>>    180266.35 60007.91,
>>>    180274.4 59993.5,
>>>    180281.06 59983.38,
>>>    180289.52 59973.93,
>>>    180315.7 59949.8,
>>>    180329.09 59939.62,
>>>    180338.31 59934.05,
>>>    180354.18 59926.34,
>>>    180362.13 59924.76,
>>>    180369.12 59926.79,
>>>    180375.15 59931.75,
>>>    180383 59935.53,
>>>    180388.11 59938.77,
>>>    180396.42 59949.49,
>>>    180400.6 59946.77,
>>>    180405.01 59956.2,
>>>    180407.23 59954.8,
>>>    180409.16 59952.08,
>>>    180431.99 59882.17,
>>>    180489.59 59719.98,
>>>    180516.16 59668.73,
>>>    180544.76 59619.86,
>>>    180564.25 59578.8,
>>>    180573.7 59551.7,
>>>    180580.79 59525.35,
>>>    180588.37 59505.63,
>>>    180604.12 59473.13,
>>>    180622.29 59445.18,
>>>    180631.91 59429.05,
>>>    180637.83 59412.74,
>>>    180656.17 59339.6,
>>>    180669.41 59299.14,
>>>    180679.64 59275.76,
>>>    180684.28 59266.53,
>>>    180686.05 59263.02,
>>>    180697.93 59246.56,
>>>    180747.67 59189.18,
>>>    180759.28 59178.74,
>>>    180772.99 59167.85,
>>>    180785.83 59162,
>>>    180798.34 59158.18,
>>>    180813.74 59154.37,
>>>    180832.3 59151.97,
>>>    180855.11 59147.46,
>>>    180861.98 59142.9,
>>>    180866.27 59138.42,
>>>    180872.11 59130.67,
>>>    180909.6 59075.52,
>>>    180922.07 59061.58,
>>>    180930.79 59055.13,
>>>    180943.08 59050.38,
>>>    180953.99 59047.52,
>>>    180964.78 59041.87,
>>>    180975.83 59032.72,
>>>    180985.33 59022.92,
>>>    181000.57 59002.51,
>>>    181013.17 58990.67,
>>>    181024.71 58983.21,
>>>    181035.92 58978.57,
>>>    181050.06 58975.38,
>>>    181076.88 58972.92,
>>>    181087.67 58970.91,
>>>    181099.7 58966.76,
>>>    181122.01 58955.77,
>>>    181146.14 58947.76,
>>>    181157.78 58942.19,
>>>    181167.75 58934.2,
>>>    181177.2 58925.53,
>>>    181192.11 58906.31,
>>>    181233.44 58862,
>>>    181243.56 58849.94,
>>>    181262.63 58824.07,
>>>    181269.81 58813.01,
>>>    181278.57 58797.49,
>>>    181286.69 58781,
>>>    181294.3 58748.54,
>>>    181297.43 58721.7,
>>>    181293.95 58693.46,
>>>    181279.45 58644.96,
>>>    181271.49 58621.9,
>>>    181245.24 58566.88,
>>>    181234.84 58548.6,
>>>    181226.25 58524.73,
>>>    181207.37 58438.02,
>>>    181193.75 58388.29,
>>>    181183.54 58357.62,
>>>    181169.67 58302.15,
>>>    181163.49 58274.38,
>>>    181159.28 58246,
>>>    181147.89 58107.32,
>>>    181147.06 57991.43,
>>>    181148.81 57965.73,
>>>    181150.16 57909.44,
>>>    181151.32 57888.4,
>>>    181156.51 57844.11,
>>>    181163.68 57796.12,
>>>    181177.45 57719.23,
>>>    181202.13 57619.71,
>>>    181224.13 57544.69,
>>>    181254.77 57474.29,
>>>    181263.88 57451,
>>>    181283.27 57406.83,
>>>    181308.26 57364,
>>>    181321.91 57342.42,
>>>    181347.77 57297.32,
>>>    181375.92 57255.37,
>>>    181421.33 57195.25,
>>>    181465.37 57132.96,
>>>    181498.7 57089.91,
>>>    181515.73 57069.3,
>>>    181532.65 57051.11,
>>>    181546.73 57031.97,
>>>    181578.04 56994.2,
>>>    181592.81 56974.79,
>>>    181606.21 56955.33,
>>>    181617.19 56937.88,
>>>    181636.62 56901.76,
>>>    181644.91 56883.67,
>>>    181651.88 56866.37,
>>>    181658.28 56848.86,
>>>    181667.09 56820.5,
>>>    181670.79 56812.22,
>>>    181673.84 56805.41,
>>>    181679.95 56789.22,
>>>    181716.63 56710.19,
>>>    181727.56 56693.78,
>>>    181739.09 56674.37,
>>>    181760.36 56634.75,
>>>    181770.08 56621.43,
>>>    181806.52 56563.56,
>>>    181822.11 56541.55,
>>>    181853.29 56501.39,
>>>    181867.37 56484.47,
>>>    181915.43 56418.28,
>>>    181934.25 56389.84,
>>>    181989.88 56324.58,
>>>    182008.53 56304.44,
>>>    182028.06 56281.36,
>>>    182044.18 56260.03,
>>>    182077.17 56220.41,
>>>    182095.42 56200.24,
>>>    182149.64 56149,
>>>    182152.81 56145.38,
>>>    182165.25 56131.22,
>>>    182181.63 56109.2,
>>>    182226.84 56059.65,
>>>    182240.13 56042.18,
>>>    182249.84 56026.52,
>>>    182262.23 56004.41,
>>>    182269.66 55988.27,
>>>    182279.11 55970.17,
>>>    182302.19 55934.92,
>>>    182312.97 55920.44,
>>>    182334.13 55894.79,
>>>    182356.12 55865.14,
>>>    182427.98 55779.79,
>>>    182498.67 55702.44
>>> )
>>>
>>>>
>>>> Michael Michaud wrote:
>>>>> Hi Martin,
>>>>>
>>>>> Thanks for the precise answer.
>>>>> I do not know a good buffer algorithm but I made some further
>>>>> tests which show there is place for improvements with the
>>>>> excellent stuff you recently added.
>>>>>
>>>>> I created a simple linestring : length = 25000 m, number of
>>>>> segments = 1000
>>>>>
>>>>> Trying to create a buffer at a distance of 10000 m ended with a
>>>>> heapspace exception (took more than 256 Mo !) after more than 4 mn
>>>>> of intensive computation !
>>>>>
>>>>> The other way is :
>>>>> - decompose into segments : less than 1 s
>>>>> - create individual buffers : openjump says 8 s but I think it
>>>>> includes redrawing
>>>>> - cascaded union of resulting buffer : 6 s (less than 50 Mo)
>>>>>
>>>>> hope that helps
>>>>>
>>>>> Michael
>>>>>
>>>>>
>>>>>
>>>>> Martin Davis a écrit :
>>>>>> The reason for this is that as the buffer size gets bigger, the
>>>>>> "raw offset curve" that is initially created prior to extracting
>>>>>> the buffer outline gets more and more complex.  Concave angles in
>>>>>> the input geometry result in perpendicular "closing lines" being
>>>>>> created, which usually intersect other offset lines.  The longer
>>>>>> the perpendicular line, the more other lines it intersects, and
>>>>>> hence the more noding and topology analysis has to be performed.  
>>>>>> (I haven't found any good way of building the raw offset curve to
>>>>>> avoid or reduce this problem - if anyone has any ideas I'd be
>>>>>> interested to hear them).
>>>>>>
>>>>>> There's several ways that I've tried to reduce this problem:
>>>>>>
>>>>>> - compute the buffer in a series of steps, using an increasing
>>>>>> series of buffer distances which add up to the desired distance.  
>>>>>> Each successive buffer gets smoother, which makes the subsequent
>>>>>> buffers run faster.  It may only be necessary to iterate say 3
>>>>>> times to get a good result.  The trick of course is to pick the
>>>>>> right distances.
>>>>>>
>>>>>> - simplify the input geometry using DP, and a tolerance of say 2%
>>>>>> of the buffer distance
>>>>>>
>>>>>> - A better way of simplifying I've been experimenting with only
>>>>>> simplifies *outwards*.  This does 2 things - it reduces concavity
>>>>>> (which is the source of the problem), and it avoid "losing"
>>>>>> convex protrubances (which DP can often delete or alter).  Convex
>>>>>> protrubances are the primary influence on the shape of the
>>>>>> resulting buffer, so it is important to preserve them.  
>>>>>> (Currently this code is in alpha only - but I can provide it if
>>>>>> anyone's interested)
>>>>>>
>>>>>> Martin
>>>>>>
>>>>>> Michael Michaud wrote:
>>>>>>> Hi,
>>>>>>>
>>>>>>> I noticed that OpenJUMP Buffer plugin performance decreases
>>>>>>> dramatically if a large buffer size is used :
>>>>>>> For a map with  rivers having vertices every few meters, I get :
>>>>>>>
>>>>>>> buffer =  25 m :     7 s
>>>>>>> buffer =  50 m :    16 s
>>>>>>> buffer = 100 m :    48 s
>>>>>>> buffer = 200 m : 2m 59 s
>>>>>>>
>>>>>>> The plugin uses the BufferOp class. I have no idea why a large
>>>>>>> buffer should take longer than a small one, and I don't know if
>>>>>>> there is a better way to compute a buffer.
>>>>>>>
>>>>>>> Any idea ?
>>>>>>>
>>>>>>> Michaël
>>>>>>>
>>>>>>> _______________________________________________
>>>>>>> jts-devel mailing list
>>>>>>> [hidden email]
>>>>>>> http://lists.refractions.net/mailman/listinfo/jts-devel
>>>>>>>
>>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> jts-devel mailing list
>>>>> [hidden email]
>>>>> http://lists.refractions.net/mailman/listinfo/jts-devel
>>>>>
>>>>
>>>
>>> _______________________________________________
>>> jts-devel mailing list
>>> [hidden email]
>>> http://lists.refractions.net/mailman/listinfo/jts-devel
>>>
>>
>

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Buffer operation performance

Martin Davis


Michael Michaud wrote:

> Hi,
>
>> More on this topic...
>>
>> I've been doing some testing of my prototype implementation of
>> "Buffer Input Simplification".  This uses a special-purpose
>> linestring simplification algorithm which weeds out *concave*
>> sections of the linework, but leaves *convex* sections untouched (up
>> to a given tolerance).  This is based on the observation that as
>> buffers get larger, the concave sections contribute less and the
>> convex areas more to the shape of the final buffer.  In the limit,
>> very large buffers are simply "blobs", which are dominated by a only
>> a few of the larger "protrubances" in the input curve.
> Interesting !
> Can we extrapolate and consider that in the limit the buffer of the
> line equals the buffer of its convex hull ?
Yes, I think that's correct.  Determining what that limit is is the
tricky part!  In any case, the limit case for the "Buffer Input
Simplifier" is the convex hull of the input.

>> Using this simplification technique with a conservative tolerance
>> produces high-quality buffers which are very close to the "pure"
>> buffer compute by the current JTS code (which is itself an
>> approximation).  The best part is that by linking the tolerance
>> factor to the buffer distance, as the distance goes up the
>> performance of generating the overall buffer increases
>> dramatically!   Some results (using Michael's test geometry) are
>> given here:
> How do you make sure that your conservative tolerance is, in fact,
> conservative. Anyway, results are impressive, and having job done
> faster for larger buffers is an excellent and unexpected result.
> About your outputs compared to "pure buffer", I realize that buffer
> outputs are never "pure" (because of curved parts) and it could make
> sense to simplify the input line in a way which is both consistent
> with the buffer size and the "segments per quadrant" parameter (but it
> may be difficult to "measure" how the input line simplification will
> impact the precision buffer output).
Re the choice of "conservative tolerance":  As you point out, the
accuracy of the generated buffer is primarily determined by the choice
of resolution of the approximations to the circular arcs around convex
vertices.  This is controlled by the "quadrant segments" parameter in
JTS.  The default setting is 8 lines per quadrant, which gives a
difference from the true arc of < 1%.  By using a tolerance distance for
the simplification which is well below this, there should be essentially
no impact from the simplification.   I actually used a tolerance of 10
times less than this (0.001).  (I used a fixed tolerance, but it would
be easy to make it depend on the users choice of quadrantSegments value).
>
> If I can help with tests, I'll try to do my best on my spare time.
Great!

I actually have run into a bit of a snag with the simplification
algorithm, so I'm going to have to think my way thru that before
carrying on.  I'll post when I make some progress.
>
> Michaël
>

--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Loading...