Re:Buffer operation performance

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

Re:Buffer operation performance

Larry Becker
Hello Martin and Michael ,

I have a buffer algorithm that seems to provide significant performance improvements.  I developed it in the early 90's and implemented it in Delphi Pascal. 

  I randomly surfed into this post and decided to join the JTS Devel list so that I could participate.   I have recently been noticing the same thing that Michael is talking about - the issue of larger distances causing slower performance.   I made up my own tests and found cases where it took several minutes to finish.  I tried these cases on my own buffer algorithm and it seems quite a bit faster, although I need benchmark times to verify this result.

I have been looking over my buffer code for the first time in over ten years, and a few things stood out initially. 

The offset curves are generated pre-intersected with adjacent offset curves using a poly-arc data structure that stores either the intersection point or a point-angle-point arc, depending on if it is an inside or outside turn respectively.  The result of each pass is always a complete polygon/arc structure.  The next step is to node and remove interior self-intersections.  All of the node intersections are done with exact calculations using circular arcs.  This can cause some issues with robustness, but produces a much more accurate buffer than simulating arcs with line segments, and reduces the number of total intersection tests.

regards,
Larry Becker

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
>> jts-devel at lists.jump-project.org
>> 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: Re:Buffer operation performance

Martin Davis
Welcome, Larry - nice to have you aboard!

Your buffer approach is very interesting - I've speculated about similar
techniques, but never had the time to try them out - and was not sure if
they would really lead to an improvement.   (Your comment about "can
cause robustness issues" makes me a bit nervous...)

I've always thought that trying to "pre-intersect" offset curves would
be quite inefficent in bad cases (e.g. ones with large buffer distances,
where any given offset segment/arc might intersect many other parts of
the offset curve).  Did you do something special to avoid this?

I can see that maintaining explicit arcs would produce smoother curves.  
The math and tolerances involved in computing arc intersections always
scared me off this approach.  But it sounds like you cracked this problem.

The reason why the current JTS algorithm slows down with large buffer
distances is because in inside corners two "closing segments" are added
to ensure that the offset curve is always closed (a picture would show
this better).  When closing segments get very long, they end up
intersecting many other segments. This causes the noding to get very
slow.  So far I haven't figured out a way to remove or reduce the impact
of these segments.  Your "pre-intersection" algorithm might do this -
but I'm curious to know how it works (short of scanning all previously
generated offser curve components - which sounds very slow)

Martin


Larry Becker wrote:

> Hello Martin and Michael ,
>
> I have a buffer algorithm that seems to provide significant
> performance improvements.  I developed it in the early 90's and
> implemented it in Delphi Pascal.
>
>   I randomly surfed into this post and decided to join the JTS Devel
> list so that I could participate.   I have recently been noticing the
> same thing that Michael is talking about - the issue of larger
> distances causing slower performance.   I made up my own tests and
> found cases where it took several minutes to finish.  I tried these
> cases on my own buffer algorithm and it seems quite a bit faster,
> although I need benchmark times to verify this result.
>
> I have been looking over my buffer code for the first time in over ten
> years, and a few things stood out initially.
>
> The offset curves are generated pre-intersected with adjacent offset
> curves using a poly-arc data structure that stores either the
> intersection point or a point-angle-point arc, depending on if it is
> an inside or outside turn respectively.  The result of each pass is
> always a complete polygon/arc structure.  The next step is to node and
> remove interior self-intersections.  All of the node intersections are
> done with exact calculations using circular arcs.  This can cause some
> issues with robustness, but produces a much more accurate buffer than
> simulating arcs with line segments, and reduces the number of total
> intersection tests.
>
> regards,
> Larry Becker
>
>     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
> />>/ jts-devel at lists.jump-project.org <http://lists.refractions.net/mailman/listinfo/jts-devel>
> />>/ http://lists.refractions.net/mailman/listinfo/jts-devel
>
> />>/
> />/
> /
>
>
> --
> http://amusingprogrammer.blogspot.com/
> ------------------------------------------------------------------------
>
> _______________________________________________
> 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: Re:Buffer operation performance

Larry Becker
Hi Martin,

I've completed some preliminary benchmarks:

JTS
distance      time
         10       1 s
         40      30 s
        100     64 s

My Algorithm (need a name here)
 distance      time
         10       1 s
         40       1 s
        100      1 s

My test data is a LineString of an aircraft. (Not that common in GIS, but it works for me.)

My comments about robustness refer to the arc-arc intersection problem of coincident circles (where do they intersect).  It causes problems, but special processing could potentially prevent this (fairly rare) issue.

I developed the special algorithm because accurate buffers are very important in our (ISA) area of business.

I'll try to describe the algorithm in more detail when I get a chance.  I'll need to review it more.

regards,
Larry

LINESTRING (
    7787.609776069839 5723.961632293637,
    7787.6109453082145 5724.028278881019,
    7788.250945308214 5724.268278881019,
    7787.920945308213 5731.67827888102,
    7789.050945308214 5732.578278881019,
    7791.960945308214 5732.578278881019,
    7796.330945308214 5726.63827888102,
    7800.970945308213 5726.6282788810195,
    7800.970945308213 5733.058278881019,
    7799.490945308215 5733.068278881019,
    7798.680945308214 5732.42827888102,
    7797.480945308213 5732.42827888102,
    7797.480945308213 5733.028278881019,
    7797.480945308213 5734.518278881019,
    7798.700945308214 5734.518278881019,
    7799.480945308214 5733.908278881019,
    7800.970945308213 5733.908278881019,
    7800.970945308213 5735.648278881019,
    7799.490945308215 5735.658278881019,
    7798.680945308214 5735.018278881019,
    7797.480945308213 5735.018278881019,
    7797.480945308213 5735.618278881019,
    7797.480945308213 5737.108278881019,
    7798.700945308214 5737.108278881019,
    7799.480945308214 5736.498278881019,
    7800.970945308213 5736.498278881019,
    7800.970945308213 5738.028278881019,
    7800.150945308213 5737.418278881019,
    7798.950945308214 5737.418278881019,
    7798.950945308214 5738.028278881019,
    7798.950945308214 5738.618278881019,
    7798.950945308214 5739.21827888102,
    7800.150945308213 5739.21827888102,
    7800.950945308214 5738.618278881019,
    7806.420945308214 5738.618278881019,
    7806.760945308215 5738.608278881019,
    7806.910945308214 5738.598278881019,
    7806.450945308215 5739.148278881019,
    7806.790945308214 5739.148278881019,
    7807.580945308214 5738.578278881019,
    7807.870945308214 5738.558278881019,
    7808.130945308214 5738.538278881019,
    7808.380945308214 5738.498278881019,
    7808.590945308214 5738.458278881019,
    7808.710945308214 5738.418278881019,
    7808.9409453082135 5738.318278881019,
    7808.720945308213 5738.228278881019,
    7808.600945308213 5738.188278881019,
    7808.390945308214 5738.13827888102,
    7808.140945308214 5738.108278881019,
    7807.880945308214 5738.0882788810195,
    7807.620945308215 5738.068278881019,
    7807.560945308213 5738.058278881019,
    7806.790945308214 5737.498278881019,
    7806.450945308215 5737.498278881019,
    7806.890945308215 5738.028278881019,
    7806.770945308213 5738.028278881019,
    7806.420945308214 5738.028278881019,
    7804.500945308214 5738.028278881019,
    7805.670945308214 5736.488278881019,
    7808.580945308214 5736.488278881019,
    7809.760945308214 5736.368278881019,
    7810.120945308214 5736.278278881019,
    7810.690945308214 5736.078278881019,
    7810.080945308215 5735.858278881019,
    7809.390945308214 5735.71827888102,
    7808.060945308215 5735.658278881019,
    7806.300945308214 5735.658278881019,
    7807.640945308214 5733.88827888102,
    7808.580945308214 5733.898278881019,
    7809.340945308213 5733.858278881019,
    7810.180945308214 5733.698278881019,
    7810.690945308214 5733.488278881019,
    7810.160945308214 5733.278278881019,
    7809.410945308214 5733.168278881019,
    7808.240945308214 5733.078278881019,
    7811.540945308213 5728.75827888102,
    7813.230945308213 5728.75827888102,
    7813.420945308214 5728.75827888102,
    7813.620945308214 5728.748278881019,
    7813.770945308213 5728.738278881019,
    7813.910945308214 5728.71827888102,
    7814.050945308214 5728.698278881019,
    7814.200945308215 5728.67827888102,
    7814.340945308214 5728.63827888102,
    7814.460945308214 5728.5882788810195,
    7814.530945308214 5728.5482788810195,
    7814.590945308214 5728.488278881019,
    7814.620945308213 5728.42827888102,
    7814.600945308214 5728.38827888102,
    7814.540945308214 5728.328278881019,
    7814.470945308214 5728.278278881019,
    7814.350945308214 5728.228278881019,
    7814.210945308215 5728.188278881019,
    7814.060945308214 5728.168278881019,
    7813.920945308214 5728.13827888102,
    7813.780945308214 5728.118278881019,
    7813.630945308214 5728.108278881019,
    7813.440945308213 5728.098278881019,
    7813.240945308214 5728.0882788810195,
    7812.070945308214 5728.0882788810195,
    7812.240945308214 5727.8382788810195,
    7813.320945308213 5727.498278881019,
    7814.180945308214 5727.21827888102,
    7815.670945308213 5726.768278881019,
    7816.700945308214 5726.46827888102,
    7817.530945308214 5726.25827888102,
    7818.350945308214 5726.068278881019,
    7819.310945308213 5725.868278881019,
    7820.140945308214 5725.698278881019,
    7820.880945308214 5725.568278881019,
    7821.860945308214 5725.3782788810195,
    7822.7309453082125 5725.25827888102,
    7823.580945308214 5725.198278881019,
    7824.4409453082135 5725.108278881019,
    7825.420945308214 5725.028278881019,
    7826.290945308214 5724.938278881019,
    7827.3609453082145 5724.868278881019,
    7828.160945308213 5724.828278881019,
    7828.640945308214 5724.788278881019,
    7829.410945308214 5724.708278881019,
    7830.210945308215 5724.578278881019,
    7830.860945308213 5724.438278881019,
    7831.420945308213 5724.278278881019,
    7832.070945308214 5724.068278881019,
    7832.6909453082135 5723.808278881019,
    7833.130945308214 5723.5882788810195,
    7833.530945308214 5723.368278881019,
    7833.870945308214 5723.13827888102,
    7836.650945308213 5722.898278881019,
    7833.870945308214 5722.63827888102,
    7833.530945308214 5722.408278881019,
    7833.130945308214 5722.188278881019,
    7832.6909453082135 5721.96827888102,
    7832.070945308214 5721.708278881019,
    7831.420945308213 5721.498278881019,
    7830.860945308213 5721.3382788810195,
    7830.210945308215 5721.198278881019,
    7829.410945308214 5721.068278881019,
    7828.640945308214 5720.988278881019,
    7828.160945308213 5720.948278881019,
    7827.3609453082145 5720.908278881019,
    7826.290945308214 5720.8382788810195,
    7825.420945308214 5720.748278881019,
    7824.4409453082135 5720.668278881019,
    7823.580945308214 5720.578278881019,
    7822.7309453082125 5720.518278881019,
    7821.860945308214 5720.398278881019,
    7820.880945308214 5720.208278881019,
    7820.140945308214 5720.078278881019,
    7819.310945308213 5719.908278881019,
    7818.350945308214 5719.708278881019,
    7817.530945308214 5719.518278881019,
    7816.700945308214 5719.308278881019,
    7815.670945308213 5719.00827888102,
    7814.180945308214 5718.558278881019,
    7813.320945308213 5718.278278881019,
    7812.240945308214 5717.938278881019,
    7812.040945308213 5717.67827888102,
    7813.240945308214 5717.688278881019,
    7813.440945308213 5717.67827888102,
    7813.630945308214 5717.668278881019,
    7813.780945308214 5717.658278881019,
    7813.920945308214 5717.63827888102,
    7814.060945308214 5717.608278881019,
    7814.210945308215 5717.5882788810195,
    7814.350945308214 5717.5482788810195,
    7814.470945308214 5717.498278881019,
    7814.540945308214 5717.448278881019,
    7814.600945308214 5717.38827888102,
    7814.620945308213 5717.348278881019,
    7814.590945308214 5717.288278881019,
    7814.530945308214 5717.228278881019,
    7814.460945308214 5717.188278881019,
    7814.340945308214 5717.13827888102,
    7814.200945308215 5717.098278881019,
    7814.050945308214 5717.078278881019,
    7813.910945308214 5717.058278881019,
    7813.770945308213 5717.038278881019,
    7813.620945308214 5717.028278881019,
    7813.420945308214 5717.018278881019,
    7813.230945308213 5717.018278881019,
    7811.570945308214 5717.018278881019,
    7808.260945308214 5712.698278881019,
    7809.410945308214 5712.608278881019,
    7810.160945308214 5712.498278881019,
    7810.690945308214 5712.288278881019,
    7810.180945308214 5712.078278881019,
    7809.340945308213 5711.918278881019,
    7808.580945308214 5711.8782788810195,
    7807.600945308214 5711.8782788810195,
    7806.300945308214 5710.1282788810195,
    7808.060945308215 5710.118278881019,
    7809.390945308214 5710.058278881019,
    7810.080945308215 5709.918278881019,
    7810.690945308214 5709.698278881019,
    7810.120945308214 5709.498278881019,
    7809.760945308214 5709.408278881019,
    7808.580945308214 5709.288278881019,
    7805.660945308214 5709.288278881019,
    7804.500945308214 5707.748278881019,
    7806.420945308214 5707.748278881019,
    7806.770945308213 5707.748278881019,
    7806.890945308215 5707.738278881019,
    7806.450945308215 5708.278278881019,
    7806.790945308214 5708.278278881019,
    7807.570945308214 5707.708278881019,
    7807.880945308214 5707.688278881019,
    7808.140945308214 5707.668278881019,
    7808.390945308214 5707.63827888102,
    7808.600945308213 5707.5882788810195,
    7808.720945308213 5707.5482788810195,
    7808.9409453082135 5707.458278881019,
    7808.710945308214 5707.358278881019,
    7808.590945308214 5707.318278881019,
    7808.380945308214 5707.278278881019,
    7808.130945308214 5707.238278881019,
    7807.870945308214 5707.21827888102,
    7807.6109453082145 5707.198278881019,
    7806.790945308214 5706.6282788810195,
    7806.450945308215 5706.6282788810195,
    7806.920945308214 5707.168278881019,
    7806.760945308215 5707.168278881019,
    7806.420945308214 5707.158278881019,
    7800.920945308215 5707.158278881019,
    7800.150945308213 5706.558278881019,
    7798.950945308214 5706.558278881019,
    7798.950945308214 5707.158278881019,
    7798.950945308214 5707.768278881019,
    7798.950945308214 5708.368278881019,
    7800.150945308213 5708.368278881019,
    7800.970945308213 5707.748278881019,
    7800.970945308213 5709.278278881019,
    7799.480945308214 5709.278278881019,
    7798.700945308214 5708.668278881019,
    7797.500945308214 5708.668278881019,
    7797.500945308214 5709.2982788810195,
    7797.500945308214 5710.75827888102,
    7798.680945308214 5710.75827888102,
    7799.480945308214 5710.118278881019,
    7800.970945308213 5710.1282788810195,
    7800.970945308213 5711.858278881019,
    7799.490945308215 5711.868278881019,
    7798.700945308214 5711.25827888102,
    7797.480945308213 5711.25827888102,
    7797.480945308213 5711.868278881019,
    7797.480945308213 5713.348278881019,
    7798.680945308214 5713.348278881019,
    7799.470945308214 5712.698278881019,
    7800.970945308213 5712.708278881019,
    7800.970945308213 5719.148278881019,
    7796.330945308214 5719.13827888102,
    7791.960945308214 5713.198278881019,
    7789.050945308214 5713.198278881019,
    7787.920945308213 5714.098278881019,
    7788.2709453082125 5721.498278881019,
    7787.6109453082145 5721.748278881019,
    7787.609801510807 5721.813475333222
)
On Mon, Sep 22, 2008 at 3:37 PM, Martin Davis <[hidden email]> wrote:
Welcome, Larry - nice to have you aboard!

Your buffer approach is very interesting - I've speculated about similar techniques, but never had the time to try them out - and was not sure if they would really lead to an improvement.   (Your comment about "can cause robustness issues" makes me a bit nervous...)

I've always thought that trying to "pre-intersect" offset curves would be quite inefficent in bad cases (e.g. ones with large buffer distances, where any given offset segment/arc might intersect many other parts of the offset curve).  Did you do something special to avoid this?

I can see that maintaining explicit arcs would produce smoother curves.  The math and tolerances involved in computing arc intersections always scared me off this approach.  But it sounds like you cracked this problem.

The reason why the current JTS algorithm slows down with large buffer distances is because in inside corners two "closing segments" are added to ensure that the offset curve is always closed (a picture would show this better).  When closing segments get very long, they end up intersecting many other segments. This causes the noding to get very slow.  So far I haven't figured out a way to remove or reduce the impact of these segments.  Your "pre-intersection" algorithm might do this - but I'm curious to know how it works (short of scanning all previously generated offser curve components - which sounds very slow)

Martin


Larry Becker wrote:
Hello Martin and Michael ,

I have a buffer algorithm that seems to provide significant performance improvements.  I developed it in the early 90's and implemented it in Delphi Pascal.
 I randomly surfed into this post and decided to join the JTS Devel list so that I could participate.   I have recently been noticing the same thing that Michael is talking about - the issue of larger distances causing slower performance.   I made up my own tests and found cases where it took several minutes to finish.  I tried these cases on my own buffer algorithm and it seems quite a bit faster, although I need benchmark times to verify this result.

I have been looking over my buffer code for the first time in over ten years, and a few things stood out initially.
The offset curves are generated pre-intersected with adjacent offset curves using a poly-arc data structure that stores either the intersection point or a point-angle-point arc, depending on if it is an inside or outside turn respectively.  The result of each pass is always a complete polygon/arc structure.  The next step is to node and remove interior self-intersections.  All of the node intersections are done with exact calculations using circular arcs.  This can cause some issues with robustness, but produces a much more accurate buffer than simulating arcs with line segments, and reduces the number of total intersection tests.

regards,
Larry Becker

   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
/>>/ jts-devel at lists.jump-project.org <http://lists.refractions.net/mailman/listinfo/jts-devel>
/>>/ http://lists.refractions.net/mailman/listinfo/jts-devel

/>>/
/>/
/


--
http://amusingprogrammer.blogspot.com/
------------------------------------------------------------------------

_______________________________________________
jts-devel mailing list
[hidden email]

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

_______________________________________________
jts-devel mailing list
[hidden email]



--
http://amusingprogrammer.blogspot.com/

_______________________________________________
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: Re:Buffer operation performance

Martin Davis
Yes, that's a good test case alright - it definitely stresses the JTS
algorithm.

So it would be great to get some more details on your secret sauce...  
TIA for sharing anything you find.

Martin

Larry Becker wrote:

> Hi Martin,
>
> I've completed some preliminary benchmarks:
>
> JTS
> distance      time
>          10       1 s
>          40      30 s
>         100     64 s
>
> My Algorithm (need a name here)
>  distance      time
>          10       1 s
>          40       1 s
>         100      1 s
>
> My test data is a LineString of an aircraft. (Not that common in GIS,
> but it works for me.)
>
> My comments about robustness refer to the arc-arc intersection problem
> of coincident circles (where do they intersect).  It causes problems,
> but special processing could potentially prevent this (fairly rare) issue.
>
> I developed the special algorithm because accurate buffers are very
> important in our (ISA) area of business.
>
> I'll try to describe the algorithm in more detail when I get a
> chance.  I'll need to review it more.
>
> regards,
> Larry
>
> LINESTRING (
>     7787.609776069839 5723.961632293637,
>     7787.6109453082145 5724.028278881019,
>     7788.250945308214 5724.268278881019,
>     7787.920945308213 5731.67827888102,
>     7789.050945308214 5732.578278881019,
>     7791.960945308214 5732.578278881019,
>     7796.330945308214 5726.63827888102,
>     7800.970945308213 5726.6282788810195,
>     7800.970945308213 5733.058278881019,
>     7799.490945308215 5733.068278881019,
>     7798.680945308214 5732.42827888102,
>     7797.480945308213 5732.42827888102,
>     7797.480945308213 5733.028278881019,
>     7797.480945308213 5734.518278881019,
>     7798.700945308214 5734.518278881019,
>     7799.480945308214 5733.908278881019,
>     7800.970945308213 5733.908278881019,
>     7800.970945308213 5735.648278881019,
>     7799.490945308215 5735.658278881019,
>     7798.680945308214 5735.018278881019,
>     7797.480945308213 5735.018278881019,
>     7797.480945308213 5735.618278881019,
>     7797.480945308213 5737.108278881019,
>     7798.700945308214 5737.108278881019,
>     7799.480945308214 5736.498278881019,
>     7800.970945308213 5736.498278881019,
>     7800.970945308213 5738.028278881019,
>     7800.150945308213 5737.418278881019,
>     7798.950945308214 5737.418278881019,
>     7798.950945308214 5738.028278881019,
>     7798.950945308214 5738.618278881019,
>     7798.950945308214 5739.21827888102,
>     7800.150945308213 5739.21827888102,
>     7800.950945308214 5738.618278881019,
>     7806.420945308214 5738.618278881019,
>     7806.760945308215 5738.608278881019,
>     7806.910945308214 5738.598278881019,
>     7806.450945308215 5739.148278881019,
>     7806.790945308214 5739.148278881019,
>     7807.580945308214 5738.578278881019,
>     7807.870945308214 5738.558278881019,
>     7808.130945308214 5738.538278881019,
>     7808.380945308214 5738.498278881019,
>     7808.590945308214 5738.458278881019,
>     7808.710945308214 5738.418278881019,
>     7808.9409453082135 5738.318278881019,
>     7808.720945308213 5738.228278881019,
>     7808.600945308213 5738.188278881019,
>     7808.390945308214 5738.13827888102,
>     7808.140945308214 5738.108278881019,
>     7807.880945308214 5738.0882788810195,
>     7807.620945308215 5738.068278881019,
>     7807.560945308213 5738.058278881019,
>     7806.790945308214 5737.498278881019,
>     7806.450945308215 5737.498278881019,
>     7806.890945308215 5738.028278881019,
>     7806.770945308213 5738.028278881019,
>     7806.420945308214 5738.028278881019,
>     7804.500945308214 5738.028278881019,
>     7805.670945308214 5736.488278881019,
>     7808.580945308214 5736.488278881019,
>     7809.760945308214 5736.368278881019,
>     7810.120945308214 5736.278278881019,
>     7810.690945308214 5736.078278881019,
>     7810.080945308215 5735.858278881019,
>     7809.390945308214 5735.71827888102,
>     7808.060945308215 5735.658278881019,
>     7806.300945308214 5735.658278881019,
>     7807.640945308214 5733.88827888102,
>     7808.580945308214 5733.898278881019,
>     7809.340945308213 5733.858278881019,
>     7810.180945308214 5733.698278881019,
>     7810.690945308214 5733.488278881019,
>     7810.160945308214 5733.278278881019,
>     7809.410945308214 5733.168278881019,
>     7808.240945308214 5733.078278881019,
>     7811.540945308213 5728.75827888102,
>     7813.230945308213 5728.75827888102,
>     7813.420945308214 5728.75827888102,
>     7813.620945308214 5728.748278881019,
>     7813.770945308213 5728.738278881019,
>     7813.910945308214 5728.71827888102,
>     7814.050945308214 5728.698278881019,
>     7814.200945308215 5728.67827888102,
>     7814.340945308214 5728.63827888102,
>     7814.460945308214 5728.5882788810195,
>     7814.530945308214 5728.5482788810195,
>     7814.590945308214 5728.488278881019,
>     7814.620945308213 5728.42827888102,
>     7814.600945308214 5728.38827888102,
>     7814.540945308214 5728.328278881019,
>     7814.470945308214 5728.278278881019,
>     7814.350945308214 5728.228278881019,
>     7814.210945308215 5728.188278881019,
>     7814.060945308214 5728.168278881019,
>     7813.920945308214 5728.13827888102,
>     7813.780945308214 5728.118278881019,
>     7813.630945308214 5728.108278881019,
>     7813.440945308213 5728.098278881019,
>     7813.240945308214 5728.0882788810195,
>     7812.070945308214 5728.0882788810195,
>     7812.240945308214 5727.8382788810195,
>     7813.320945308213 5727.498278881019,
>     7814.180945308214 5727.21827888102,
>     7815.670945308213 5726.768278881019,
>     7816.700945308214 5726.46827888102,
>     7817.530945308214 5726.25827888102,
>     7818.350945308214 5726.068278881019,
>     7819.310945308213 5725.868278881019,
>     7820.140945308214 5725.698278881019,
>     7820.880945308214 5725.568278881019,
>     7821.860945308214 5725.3782788810195,
>     7822.7309453082125 5725.25827888102,
>     7823.580945308214 5725.198278881019,
>     7824.4409453082135 5725.108278881019,
>     7825.420945308214 5725.028278881019,
>     7826.290945308214 5724.938278881019,
>     7827.3609453082145 5724.868278881019,
>     7828.160945308213 5724.828278881019,
>     7828.640945308214 5724.788278881019,
>     7829.410945308214 5724.708278881019,
>     7830.210945308215 5724.578278881019,
>     7830.860945308213 5724.438278881019,
>     7831.420945308213 5724.278278881019,
>     7832.070945308214 5724.068278881019,
>     7832.6909453082135 5723.808278881019,
>     7833.130945308214 5723.5882788810195,
>     7833.530945308214 5723.368278881019,
>     7833.870945308214 5723.13827888102,
>     7836.650945308213 5722.898278881019,
>     7833.870945308214 5722.63827888102,
>     7833.530945308214 5722.408278881019,
>     7833.130945308214 5722.188278881019,
>     7832.6909453082135 5721.96827888102,
>     7832.070945308214 5721.708278881019,
>     7831.420945308213 5721.498278881019,
>     7830.860945308213 5721.3382788810195,
>     7830.210945308215 5721.198278881019,
>     7829.410945308214 5721.068278881019,
>     7828.640945308214 5720.988278881019,
>     7828.160945308213 5720.948278881019,
>     7827.3609453082145 5720.908278881019,
>     7826.290945308214 5720.8382788810195,
>     7825.420945308214 5720.748278881019,
>     7824.4409453082135 5720.668278881019,
>     7823.580945308214 5720.578278881019,
>     7822.7309453082125 5720.518278881019,
>     7821.860945308214 5720.398278881019,
>     7820.880945308214 5720.208278881019,
>     7820.140945308214 5720.078278881019,
>     7819.310945308213 5719.908278881019,
>     7818.350945308214 5719.708278881019,
>     7817.530945308214 5719.518278881019,
>     7816.700945308214 5719.308278881019,
>     7815.670945308213 5719.00827888102,
>     7814.180945308214 5718.558278881019,
>     7813.320945308213 5718.278278881019,
>     7812.240945308214 5717.938278881019,
>     7812.040945308213 5717.67827888102,
>     7813.240945308214 5717.688278881019,
>     7813.440945308213 5717.67827888102,
>     7813.630945308214 5717.668278881019,
>     7813.780945308214 5717.658278881019,
>     7813.920945308214 5717.63827888102,
>     7814.060945308214 5717.608278881019,
>     7814.210945308215 5717.5882788810195,
>     7814.350945308214 5717.5482788810195,
>     7814.470945308214 5717.498278881019,
>     7814.540945308214 5717.448278881019,
>     7814.600945308214 5717.38827888102,
>     7814.620945308213 5717.348278881019,
>     7814.590945308214 5717.288278881019,
>     7814.530945308214 5717.228278881019,
>     7814.460945308214 5717.188278881019,
>     7814.340945308214 5717.13827888102,
>     7814.200945308215 5717.098278881019,
>     7814.050945308214 5717.078278881019,
>     7813.910945308214 5717.058278881019,
>     7813.770945308213 5717.038278881019,
>     7813.620945308214 5717.028278881019,
>     7813.420945308214 5717.018278881019,
>     7813.230945308213 5717.018278881019,
>     7811.570945308214 5717.018278881019,
>     7808.260945308214 5712.698278881019,
>     7809.410945308214 5712.608278881019,
>     7810.160945308214 5712.498278881019,
>     7810.690945308214 5712.288278881019,
>     7810.180945308214 5712.078278881019,
>     7809.340945308213 5711.918278881019,
>     7808.580945308214 5711.8782788810195,
>     7807.600945308214 5711.8782788810195,
>     7806.300945308214 5710.1282788810195,
>     7808.060945308215 5710.118278881019,
>     7809.390945308214 5710.058278881019,
>     7810.080945308215 5709.918278881019,
>     7810.690945308214 5709.698278881019,
>     7810.120945308214 5709.498278881019,
>     7809.760945308214 5709.408278881019,
>     7808.580945308214 5709.288278881019,
>     7805.660945308214 5709.288278881019,
>     7804.500945308214 5707.748278881019,
>     7806.420945308214 5707.748278881019,
>     7806.770945308213 5707.748278881019,
>     7806.890945308215 5707.738278881019,
>     7806.450945308215 5708.278278881019,
>     7806.790945308214 5708.278278881019,
>     7807.570945308214 5707.708278881019,
>     7807.880945308214 5707.688278881019,
>     7808.140945308214 5707.668278881019,
>     7808.390945308214 5707.63827888102,
>     7808.600945308213 5707.5882788810195,
>     7808.720945308213 5707.5482788810195,
>     7808.9409453082135 5707.458278881019,
>     7808.710945308214 5707.358278881019,
>     7808.590945308214 5707.318278881019,
>     7808.380945308214 5707.278278881019,
>     7808.130945308214 5707.238278881019,
>     7807.870945308214 5707.21827888102,
>     7807.6109453082145 5707.198278881019,
>     7806.790945308214 5706.6282788810195,
>     7806.450945308215 5706.6282788810195,
>     7806.920945308214 5707.168278881019,
>     7806.760945308215 5707.168278881019,
>     7806.420945308214 5707.158278881019,
>     7800.920945308215 5707.158278881019,
>     7800.150945308213 5706.558278881019,
>     7798.950945308214 5706.558278881019,
>     7798.950945308214 5707.158278881019,
>     7798.950945308214 5707.768278881019,
>     7798.950945308214 5708.368278881019,
>     7800.150945308213 5708.368278881019,
>     7800.970945308213 5707.748278881019,
>     7800.970945308213 5709.278278881019,
>     7799.480945308214 5709.278278881019,
>     7798.700945308214 5708.668278881019,
>     7797.500945308214 5708.668278881019,
>     7797.500945308214 5709.2982788810195,
>     7797.500945308214 5710.75827888102,
>     7798.680945308214 5710.75827888102,
>     7799.480945308214 5710.118278881019,
>     7800.970945308213 5710.1282788810195,
>     7800.970945308213 5711.858278881019,
>     7799.490945308215 5711.868278881019,
>     7798.700945308214 5711.25827888102,
>     7797.480945308213 5711.25827888102,
>     7797.480945308213 5711.868278881019,
>     7797.480945308213 5713.348278881019,
>     7798.680945308214 5713.348278881019,
>     7799.470945308214 5712.698278881019,
>     7800.970945308213 5712.708278881019,
>     7800.970945308213 5719.148278881019,
>     7796.330945308214 5719.13827888102,
>     7791.960945308214 5713.198278881019,
>     7789.050945308214 5713.198278881019,
>     7787.920945308213 5714.098278881019,
>     7788.2709453082125 5721.498278881019,
>     7787.6109453082145 5721.748278881019,
>     7787.609801510807 5721.813475333222
> )
> On Mon, Sep 22, 2008 at 3:37 PM, Martin Davis <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     Welcome, Larry - nice to have you aboard!
>
>     Your buffer approach is very interesting - I've speculated about
>     similar techniques, but never had the time to try them out - and
>     was not sure if they would really lead to an improvement.   (Your
>     comment about "can cause robustness issues" makes me a bit nervous...)
>
>     I've always thought that trying to "pre-intersect" offset curves
>     would be quite inefficent in bad cases (e.g. ones with large
>     buffer distances, where any given offset segment/arc might
>     intersect many other parts of the offset curve).  Did you do
>     something special to avoid this?
>
>     I can see that maintaining explicit arcs would produce smoother
>     curves.  The math and tolerances involved in computing arc
>     intersections always scared me off this approach.  But it sounds
>     like you cracked this problem.
>
>     The reason why the current JTS algorithm slows down with large
>     buffer distances is because in inside corners two "closing
>     segments" are added to ensure that the offset curve is always
>     closed (a picture would show this better).  When closing segments
>     get very long, they end up intersecting many other segments. This
>     causes the noding to get very slow.  So far I haven't figured out
>     a way to remove or reduce the impact of these segments.  Your
>     "pre-intersection" algorithm might do this - but I'm curious to
>     know how it works (short of scanning all previously generated
>     offser curve components - which sounds very slow)
>
>     Martin
>
>
>     Larry Becker wrote:
>
>         Hello Martin and Michael ,
>
>         I have a buffer algorithm that seems to provide significant
>         performance improvements.  I developed it in the early 90's
>         and implemented it in Delphi Pascal.
>          I randomly surfed into this post and decided to join the JTS
>         Devel list so that I could participate.   I have recently been
>         noticing the same thing that Michael is talking about - the
>         issue of larger distances causing slower performance.   I made
>         up my own tests and found cases where it took several minutes
>         to finish.  I tried these cases on my own buffer algorithm and
>         it seems quite a bit faster, although I need benchmark times
>         to verify this result.
>
>         I have been looking over my buffer code for the first time in
>         over ten years, and a few things stood out initially.
>         The offset curves are generated pre-intersected with adjacent
>         offset curves using a poly-arc data structure that stores
>         either the intersection point or a point-angle-point arc,
>         depending on if it is an inside or outside turn respectively.
>          The result of each pass is always a complete polygon/arc
>         structure.  The next step is to node and remove interior
>         self-intersections.  All of the node intersections are done
>         with exact calculations using circular arcs.  This can cause
>         some issues with robustness, but produces a much more accurate
>         buffer than simulating arcs with line segments, and reduces
>         the number of total intersection tests.
>
>         regards,
>         Larry Becker
>
>            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
>         />>/ jts-devel at lists.jump-project.org
>         <http://lists.jump-project.org>
>         <http://lists.refractions.net/mailman/listinfo/jts-devel>
>         />>/ http://lists.refractions.net/mailman/listinfo/jts-devel
>
>         />>/
>         />/
>         /
>
>
>         --
>         http://amusingprogrammer.blogspot.com/
>         ------------------------------------------------------------------------
>
>         _______________________________________________
>         jts-devel mailing list
>         [hidden email]
>         <mailto:[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]
>     <mailto:[hidden email]>
>
>     http://lists.refractions.net/mailman/listinfo/jts-devel
>
>
>
>
> --
> http://amusingprogrammer.blogspot.com/
> ------------------------------------------------------------------------
>
> _______________________________________________
> 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: Re:Buffer operation performance

Larry Becker
One more thing...  If you close the aircraft LineString and make a polygon out of it, the JTS 100 distance case completes in 281 ms!

On Mon, Sep 22, 2008 at 4:00 PM, Martin Davis <[hidden email]> wrote:
Yes, that's a good test case alright - it definitely stresses the JTS algorithm.

So it would be great to get some more details on your secret sauce...  TIA for sharing anything you find.

Martin

Larry Becker wrote:
Hi Martin,

I've completed some preliminary benchmarks:

JTS
distance      time
        10       1 s
        40      30 s
       100     64 s

My Algorithm (need a name here)
 distance      time
        10       1 s
        40       1 s
       100      1 s

My test data is a LineString of an aircraft. (Not that common in GIS, but it works for me.)

My comments about robustness refer to the arc-arc intersection problem of coincident circles (where do they intersect).  It causes problems, but special processing could potentially prevent this (fairly rare) issue.

I developed the special algorithm because accurate buffers are very important in our (ISA) area of business.

I'll try to describe the algorithm in more detail when I get a chance.  I'll need to review it more.

regards,
Larry

LINESTRING (
   7787.609776069839 5723.961632293637,
   7787.6109453082145 5724.028278881019,
   7788.250945308214 5724.268278881019,
   7787.920945308213 5731.67827888102,
   7789.050945308214 5732.578278881019,
   7791.960945308214 5732.578278881019,
   7796.330945308214 5726.63827888102,
   7800.970945308213 5726.6282788810195,
   7800.970945308213 5733.058278881019,
   7799.490945308215 5733.068278881019,
   7798.680945308214 5732.42827888102,
   7797.480945308213 5732.42827888102,
   7797.480945308213 5733.028278881019,
   7797.480945308213 5734.518278881019,
   7798.700945308214 5734.518278881019,
   7799.480945308214 5733.908278881019,
   7800.970945308213 5733.908278881019,
   7800.970945308213 5735.648278881019,
   7799.490945308215 5735.658278881019,
   7798.680945308214 5735.018278881019,
   7797.480945308213 5735.018278881019,
   7797.480945308213 5735.618278881019,
   7797.480945308213 5737.108278881019,
   7798.700945308214 5737.108278881019,
   7799.480945308214 5736.498278881019,
   7800.970945308213 5736.498278881019,
   7800.970945308213 5738.028278881019,
   7800.150945308213 5737.418278881019,
   7798.950945308214 5737.418278881019,
   7798.950945308214 5738.028278881019,
   7798.950945308214 5738.618278881019,
   7798.950945308214 5739.21827888102,
   7800.150945308213 5739.21827888102,
   7800.950945308214 5738.618278881019,
   7806.420945308214 5738.618278881019,
   7806.760945308215 5738.608278881019,
   7806.910945308214 5738.598278881019,
   7806.450945308215 5739.148278881019,
   7806.790945308214 5739.148278881019,
   7807.580945308214 5738.578278881019,
   7807.870945308214 5738.558278881019,
   7808.130945308214 5738.538278881019,
   7808.380945308214 5738.498278881019,
   7808.590945308214 5738.458278881019,
   7808.710945308214 5738.418278881019,
   7808.9409453082135 5738.318278881019,
   7808.720945308213 5738.228278881019,
   7808.600945308213 5738.188278881019,
   7808.390945308214 5738.13827888102,
   7808.140945308214 5738.108278881019,
   7807.880945308214 5738.0882788810195,
   7807.620945308215 5738.068278881019,
   7807.560945308213 5738.058278881019,
   7806.790945308214 5737.498278881019,
   7806.450945308215 5737.498278881019,
   7806.890945308215 5738.028278881019,
   7806.770945308213 5738.028278881019,
   7806.420945308214 5738.028278881019,
   7804.500945308214 5738.028278881019,
   7805.670945308214 5736.488278881019,
   7808.580945308214 5736.488278881019,
   7809.760945308214 5736.368278881019,
   7810.120945308214 5736.278278881019,
   7810.690945308214 5736.078278881019,
   7810.080945308215 5735.858278881019,
   7809.390945308214 5735.71827888102,
   7808.060945308215 5735.658278881019,
   7806.300945308214 5735.658278881019,
   7807.640945308214 5733.88827888102,
   7808.580945308214 5733.898278881019,
   7809.340945308213 5733.858278881019,
   7810.180945308214 5733.698278881019,
   7810.690945308214 5733.488278881019,
   7810.160945308214 5733.278278881019,
   7809.410945308214 5733.168278881019,
   7808.240945308214 5733.078278881019,
   7811.540945308213 5728.75827888102,
   7813.230945308213 5728.75827888102,
   7813.420945308214 5728.75827888102,
   7813.620945308214 5728.748278881019,
   7813.770945308213 5728.738278881019,
   7813.910945308214 5728.71827888102,
   7814.050945308214 5728.698278881019,
   7814.200945308215 5728.67827888102,
   7814.340945308214 5728.63827888102,
   7814.460945308214 5728.5882788810195,
   7814.530945308214 5728.5482788810195,
   7814.590945308214 5728.488278881019,
   7814.620945308213 5728.42827888102,
   7814.600945308214 5728.38827888102,
   7814.540945308214 5728.328278881019,
   7814.470945308214 5728.278278881019,
   7814.350945308214 5728.228278881019,
   7814.210945308215 5728.188278881019,
   7814.060945308214 5728.168278881019,
   7813.920945308214 5728.13827888102,
   7813.780945308214 5728.118278881019,
   7813.630945308214 5728.108278881019,
   7813.440945308213 5728.098278881019,
   7813.240945308214 5728.0882788810195,
   7812.070945308214 5728.0882788810195,
   7812.240945308214 5727.8382788810195,
   7813.320945308213 5727.498278881019,
   7814.180945308214 5727.21827888102,
   7815.670945308213 5726.768278881019,
   7816.700945308214 5726.46827888102,
   7817.530945308214 5726.25827888102,
   7818.350945308214 5726.068278881019,
   7819.310945308213 5725.868278881019,
   7820.140945308214 5725.698278881019,
   7820.880945308214 5725.568278881019,
   7821.860945308214 5725.3782788810195,
   7822.7309453082125 5725.25827888102,
   7823.580945308214 5725.198278881019,
   7824.4409453082135 5725.108278881019,
   7825.420945308214 5725.028278881019,
   7826.290945308214 5724.938278881019,
   7827.3609453082145 5724.868278881019,
   7828.160945308213 5724.828278881019,
   7828.640945308214 5724.788278881019,
   7829.410945308214 5724.708278881019,
   7830.210945308215 5724.578278881019,
   7830.860945308213 5724.438278881019,
   7831.420945308213 5724.278278881019,
   7832.070945308214 5724.068278881019,
   7832.6909453082135 5723.808278881019,
   7833.130945308214 5723.5882788810195,
   7833.530945308214 5723.368278881019,
   7833.870945308214 5723.13827888102,
   7836.650945308213 5722.898278881019,
   7833.870945308214 5722.63827888102,
   7833.530945308214 5722.408278881019,
   7833.130945308214 5722.188278881019,
   7832.6909453082135 5721.96827888102,
   7832.070945308214 5721.708278881019,
   7831.420945308213 5721.498278881019,
   7830.860945308213 5721.3382788810195,
   7830.210945308215 5721.198278881019,
   7829.410945308214 5721.068278881019,
   7828.640945308214 5720.988278881019,
   7828.160945308213 5720.948278881019,
   7827.3609453082145 5720.908278881019,
   7826.290945308214 5720.8382788810195,
   7825.420945308214 5720.748278881019,
   7824.4409453082135 5720.668278881019,
   7823.580945308214 5720.578278881019,
   7822.7309453082125 5720.518278881019,
   7821.860945308214 5720.398278881019,
   7820.880945308214 5720.208278881019,
   7820.140945308214 5720.078278881019,
   7819.310945308213 5719.908278881019,
   7818.350945308214 5719.708278881019,
   7817.530945308214 5719.518278881019,
   7816.700945308214 5719.308278881019,
   7815.670945308213 5719.00827888102,
   7814.180945308214 5718.558278881019,
   7813.320945308213 5718.278278881019,
   7812.240945308214 5717.938278881019,
   7812.040945308213 5717.67827888102,
   7813.240945308214 5717.688278881019,
   7813.440945308213 5717.67827888102,
   7813.630945308214 5717.668278881019,
   7813.780945308214 5717.658278881019,
   7813.920945308214 5717.63827888102,
   7814.060945308214 5717.608278881019,
   7814.210945308215 5717.5882788810195,
   7814.350945308214 5717.5482788810195,
   7814.470945308214 5717.498278881019,
   7814.540945308214 5717.448278881019,
   7814.600945308214 5717.38827888102,
   7814.620945308213 5717.348278881019,
   7814.590945308214 5717.288278881019,
   7814.530945308214 5717.228278881019,
   7814.460945308214 5717.188278881019,
   7814.340945308214 5717.13827888102,
   7814.200945308215 5717.098278881019,
   7814.050945308214 5717.078278881019,
   7813.910945308214 5717.058278881019,
   7813.770945308213 5717.038278881019,
   7813.620945308214 5717.028278881019,
   7813.420945308214 5717.018278881019,
   7813.230945308213 5717.018278881019,
   7811.570945308214 5717.018278881019,
   7808.260945308214 5712.698278881019,
   7809.410945308214 5712.608278881019,
   7810.160945308214 5712.498278881019,
   7810.690945308214 5712.288278881019,
   7810.180945308214 5712.078278881019,
   7809.340945308213 5711.918278881019,
   7808.580945308214 5711.8782788810195,
   7807.600945308214 5711.8782788810195,
   7806.300945308214 5710.1282788810195,
   7808.060945308215 5710.118278881019,
   7809.390945308214 5710.058278881019,
   7810.080945308215 5709.918278881019,
   7810.690945308214 5709.698278881019,
   7810.120945308214 5709.498278881019,
   7809.760945308214 5709.408278881019,
   7808.580945308214 5709.288278881019,
   7805.660945308214 5709.288278881019,
   7804.500945308214 5707.748278881019,
   7806.420945308214 5707.748278881019,
   7806.770945308213 5707.748278881019,
   7806.890945308215 5707.738278881019,
   7806.450945308215 5708.278278881019,
   7806.790945308214 5708.278278881019,
   7807.570945308214 5707.708278881019,
   7807.880945308214 5707.688278881019,
   7808.140945308214 5707.668278881019,
   7808.390945308214 5707.63827888102,
   7808.600945308213 5707.5882788810195,
   7808.720945308213 5707.5482788810195,
   7808.9409453082135 5707.458278881019,
   7808.710945308214 5707.358278881019,
   7808.590945308214 5707.318278881019,
   7808.380945308214 5707.278278881019,
   7808.130945308214 5707.238278881019,
   7807.870945308214 5707.21827888102,
   7807.6109453082145 5707.198278881019,
   7806.790945308214 5706.6282788810195,
   7806.450945308215 5706.6282788810195,
   7806.920945308214 5707.168278881019,
   7806.760945308215 5707.168278881019,
   7806.420945308214 5707.158278881019,
   7800.920945308215 5707.158278881019,
   7800.150945308213 5706.558278881019,
   7798.950945308214 5706.558278881019,
   7798.950945308214 5707.158278881019,
   7798.950945308214 5707.768278881019,
   7798.950945308214 5708.368278881019,
   7800.150945308213 5708.368278881019,
   7800.970945308213 5707.748278881019,
   7800.970945308213 5709.278278881019,
   7799.480945308214 5709.278278881019,
   7798.700945308214 5708.668278881019,
   7797.500945308214 5708.668278881019,
   7797.500945308214 5709.2982788810195,
   7797.500945308214 5710.75827888102,
   7798.680945308214 5710.75827888102,
   7799.480945308214 5710.118278881019,
   7800.970945308213 5710.1282788810195,
   7800.970945308213 5711.858278881019,
   7799.490945308215 5711.868278881019,
   7798.700945308214 5711.25827888102,
   7797.480945308213 5711.25827888102,
   7797.480945308213 5711.868278881019,
   7797.480945308213 5713.348278881019,
   7798.680945308214 5713.348278881019,
   7799.470945308214 5712.698278881019,
   7800.970945308213 5712.708278881019,
   7800.970945308213 5719.148278881019,
   7796.330945308214 5719.13827888102,
   7791.960945308214 5713.198278881019,
   7789.050945308214 5713.198278881019,
   7787.920945308213 5714.098278881019,
   7788.2709453082125 5721.498278881019,
   7787.6109453082145 5721.748278881019,
   7787.609801510807 5721.813475333222
)
On Mon, Sep 22, 2008 at 3:37 PM, Martin Davis <[hidden email] <mailto:[hidden email]>> wrote:

   Welcome, Larry - nice to have you aboard!

   Your buffer approach is very interesting - I've speculated about
   similar techniques, but never had the time to try them out - and
   was not sure if they would really lead to an improvement.   (Your
   comment about "can cause robustness issues" makes me a bit nervous...)

   I've always thought that trying to "pre-intersect" offset curves
   would be quite inefficent in bad cases (e.g. ones with large
   buffer distances, where any given offset segment/arc might
   intersect many other parts of the offset curve).  Did you do
   something special to avoid this?

   I can see that maintaining explicit arcs would produce smoother
   curves.  The math and tolerances involved in computing arc
   intersections always scared me off this approach.  But it sounds
   like you cracked this problem.

   The reason why the current JTS algorithm slows down with large
   buffer distances is because in inside corners two "closing
   segments" are added to ensure that the offset curve is always
   closed (a picture would show this better).  When closing segments
   get very long, they end up intersecting many other segments. This
   causes the noding to get very slow.  So far I haven't figured out
   a way to remove or reduce the impact of these segments.  Your
   "pre-intersection" algorithm might do this - but I'm curious to
   know how it works (short of scanning all previously generated
   offser curve components - which sounds very slow)

   Martin


   Larry Becker wrote:

       Hello Martin and Michael ,

       I have a buffer algorithm that seems to provide significant
       performance improvements.  I developed it in the early 90's
       and implemented it in Delphi Pascal.
        I randomly surfed into this post and decided to join the JTS
       Devel list so that I could participate.   I have recently been
       noticing the same thing that Michael is talking about - the
       issue of larger distances causing slower performance.   I made
       up my own tests and found cases where it took several minutes
       to finish.  I tried these cases on my own buffer algorithm and
       it seems quite a bit faster, although I need benchmark times
       to verify this result.

       I have been looking over my buffer code for the first time in
       over ten years, and a few things stood out initially.
       The offset curves are generated pre-intersected with adjacent
       offset curves using a poly-arc data structure that stores
       either the intersection point or a point-angle-point arc,
       depending on if it is an inside or outside turn respectively.
        The result of each pass is always a complete polygon/arc
       structure.  The next step is to node and remove interior
       self-intersections.  All of the node intersections are done
       with exact calculations using circular arcs.  This can cause
       some issues with robustness, but produces a much more accurate
       buffer than simulating arcs with line segments, and reduces
       the number of total intersection tests.

       regards,
       Larry Becker

          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
       />>/ jts-devel at lists.jump-project.org
       <http://lists.jump-project.org>

       <http://lists.refractions.net/mailman/listinfo/jts-devel>
       />>/ http://lists.refractions.net/mailman/listinfo/jts-devel

       />>/
       />/
       /


       --        http://amusingprogrammer.blogspot.com/
       ------------------------------------------------------------------------

       _______________________________________________
       jts-devel mailing list
       [hidden email]
       <mailto:[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]
   <mailto:[hidden email]>


   http://lists.refractions.net/mailman/listinfo/jts-devel




--
http://amusingprogrammer.blogspot.com/
------------------------------------------------------------------------

_______________________________________________
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



--
http://amusingprogrammer.blogspot.com/

_______________________________________________
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: Re:Buffer operation performance

Martin Davis
That's because now JTS only computes an offset curve for one side of the
shape (and the side which has fewer inside corners).  This makes for a
much less complex offset curve, which can be noded a lot faster.

How does your code perform in this situation?   Still 1 sec?  8^)

Larry Becker wrote:

> One more thing...  If you close the aircraft LineString and make a
> polygon out of it, the JTS 100 distance case completes in 281 ms!
>
> On Mon, Sep 22, 2008 at 4:00 PM, Martin Davis <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     Yes, that's a good test case alright - it definitely stresses the
>     JTS algorithm.
>
>     So it would be great to get some more details on your secret
>     sauce...  TIA for sharing anything you find.
>
>     Martin
>
>     Larry Becker wrote:
>
>         Hi Martin,
>
>         I've completed some preliminary benchmarks:
>
>         JTS
>         distance      time
>                 10       1 s
>                 40      30 s
>                100     64 s
>
>         My Algorithm (need a name here)
>          distance      time
>                 10       1 s
>                 40       1 s
>                100      1 s
>
>         My test data is a LineString of an aircraft. (Not that common
>         in GIS, but it works for me.)
>
>         My comments about robustness refer to the arc-arc intersection
>         problem of coincident circles (where do they intersect).  It
>         causes problems, but special processing could potentially
>         prevent this (fairly rare) issue.
>
>         I developed the special algorithm because accurate buffers are
>         very important in our (ISA) area of business.
>
>         I'll try to describe the algorithm in more detail when I get a
>         chance.  I'll need to review it more.
>
>         regards,
>         Larry
>
>         LINESTRING (
>            7787.609776069839 5723.961632293637,
>            7787.6109453082145 5724.028278881019,
>            7788.250945308214 5724.268278881019,
>            7787.920945308213 5731.67827888102,
>            7789.050945308214 5732.578278881019,
>            7791.960945308214 5732.578278881019,
>            7796.330945308214 5726.63827888102,
>            7800.970945308213 5726.6282788810195,
>            7800.970945308213 5733.058278881019,
>            7799.490945308215 5733.068278881019,
>            7798.680945308214 5732.42827888102,
>            7797.480945308213 5732.42827888102,
>            7797.480945308213 5733.028278881019,
>            7797.480945308213 5734.518278881019,
>            7798.700945308214 5734.518278881019,
>            7799.480945308214 5733.908278881019,
>            7800.970945308213 5733.908278881019,
>            7800.970945308213 5735.648278881019,
>            7799.490945308215 5735.658278881019,
>            7798.680945308214 5735.018278881019,
>            7797.480945308213 5735.018278881019,
>            7797.480945308213 5735.618278881019,
>            7797.480945308213 5737.108278881019,
>            7798.700945308214 5737.108278881019,
>            7799.480945308214 5736.498278881019,
>            7800.970945308213 5736.498278881019,
>            7800.970945308213 5738.028278881019,
>            7800.150945308213 5737.418278881019,
>            7798.950945308214 5737.418278881019,
>            7798.950945308214 5738.028278881019,
>            7798.950945308214 5738.618278881019,
>            7798.950945308214 5739.21827888102,
>            7800.150945308213 5739.21827888102,
>            7800.950945308214 5738.618278881019,
>            7806.420945308214 5738.618278881019,
>            7806.760945308215 5738.608278881019,
>            7806.910945308214 5738.598278881019,
>            7806.450945308215 5739.148278881019,
>            7806.790945308214 5739.148278881019,
>            7807.580945308214 5738.578278881019,
>            7807.870945308214 5738.558278881019,
>            7808.130945308214 5738.538278881019,
>            7808.380945308214 5738.498278881019,
>            7808.590945308214 5738.458278881019,
>            7808.710945308214 5738.418278881019,
>            7808.9409453082135 5738.318278881019,
>            7808.720945308213 5738.228278881019,
>            7808.600945308213 5738.188278881019,
>            7808.390945308214 5738.13827888102,
>            7808.140945308214 5738.108278881019,
>            7807.880945308214 5738.0882788810195,
>            7807.620945308215 5738.068278881019,
>            7807.560945308213 5738.058278881019,
>            7806.790945308214 5737.498278881019,
>            7806.450945308215 5737.498278881019,
>            7806.890945308215 5738.028278881019,
>            7806.770945308213 5738.028278881019,
>            7806.420945308214 5738.028278881019,
>            7804.500945308214 5738.028278881019,
>            7805.670945308214 5736.488278881019,
>            7808.580945308214 5736.488278881019,
>            7809.760945308214 5736.368278881019,
>            7810.120945308214 5736.278278881019,
>            7810.690945308214 5736.078278881019,
>            7810.080945308215 5735.858278881019,
>            7809.390945308214 5735.71827888102,
>            7808.060945308215 5735.658278881019,
>            7806.300945308214 5735.658278881019,
>            7807.640945308214 5733.88827888102,
>            7808.580945308214 5733.898278881019,
>            7809.340945308213 5733.858278881019,
>            7810.180945308214 5733.698278881019,
>            7810.690945308214 5733.488278881019,
>            7810.160945308214 5733.278278881019,
>            7809.410945308214 5733.168278881019,
>            7808.240945308214 5733.078278881019,
>            7811.540945308213 5728.75827888102,
>            7813.230945308213 5728.75827888102,
>            7813.420945308214 5728.75827888102,
>            7813.620945308214 5728.748278881019,
>            7813.770945308213 5728.738278881019,
>            7813.910945308214 5728.71827888102,
>            7814.050945308214 5728.698278881019,
>            7814.200945308215 5728.67827888102,
>            7814.340945308214 5728.63827888102,
>            7814.460945308214 5728.5882788810195,
>            7814.530945308214 5728.5482788810195,
>            7814.590945308214 5728.488278881019,
>            7814.620945308213 5728.42827888102,
>            7814.600945308214 5728.38827888102,
>            7814.540945308214 5728.328278881019,
>            7814.470945308214 5728.278278881019,
>            7814.350945308214 5728.228278881019,
>            7814.210945308215 5728.188278881019,
>            7814.060945308214 5728.168278881019,
>            7813.920945308214 5728.13827888102,
>            7813.780945308214 5728.118278881019,
>            7813.630945308214 5728.108278881019,
>            7813.440945308213 5728.098278881019,
>            7813.240945308214 5728.0882788810195,
>            7812.070945308214 5728.0882788810195,
>            7812.240945308214 5727.8382788810195,
>            7813.320945308213 5727.498278881019,
>            7814.180945308214 5727.21827888102,
>            7815.670945308213 5726.768278881019,
>            7816.700945308214 5726.46827888102,
>            7817.530945308214 5726.25827888102,
>            7818.350945308214 5726.068278881019,
>            7819.310945308213 5725.868278881019,
>            7820.140945308214 5725.698278881019,
>            7820.880945308214 5725.568278881019,
>            7821.860945308214 5725.3782788810195,
>            7822.7309453082125 5725.25827888102,
>            7823.580945308214 5725.198278881019,
>            7824.4409453082135 5725.108278881019,
>            7825.420945308214 5725.028278881019,
>            7826.290945308214 5724.938278881019,
>            7827.3609453082145 5724.868278881019,
>            7828.160945308213 5724.828278881019,
>            7828.640945308214 5724.788278881019,
>            7829.410945308214 5724.708278881019,
>            7830.210945308215 5724.578278881019,
>            7830.860945308213 5724.438278881019,
>            7831.420945308213 5724.278278881019,
>            7832.070945308214 5724.068278881019,
>            7832.6909453082135 5723.808278881019,
>            7833.130945308214 5723.5882788810195,
>            7833.530945308214 5723.368278881019,
>            7833.870945308214 5723.13827888102,
>            7836.650945308213 5722.898278881019,
>            7833.870945308214 5722.63827888102,
>            7833.530945308214 5722.408278881019,
>            7833.130945308214 5722.188278881019,
>            7832.6909453082135 5721.96827888102,
>            7832.070945308214 5721.708278881019,
>            7831.420945308213 5721.498278881019,
>            7830.860945308213 5721.3382788810195,
>            7830.210945308215 5721.198278881019,
>            7829.410945308214 5721.068278881019,
>            7828.640945308214 5720.988278881019,
>            7828.160945308213 5720.948278881019,
>            7827.3609453082145 5720.908278881019,
>            7826.290945308214 5720.8382788810195,
>            7825.420945308214 5720.748278881019,
>            7824.4409453082135 5720.668278881019,
>            7823.580945308214 5720.578278881019,
>            7822.7309453082125 5720.518278881019,
>            7821.860945308214 5720.398278881019,
>            7820.880945308214 5720.208278881019,
>            7820.140945308214 5720.078278881019,
>            7819.310945308213 5719.908278881019,
>            7818.350945308214 5719.708278881019,
>            7817.530945308214 5719.518278881019,
>            7816.700945308214 5719.308278881019,
>            7815.670945308213 5719.00827888102,
>            7814.180945308214 5718.558278881019,
>            7813.320945308213 5718.278278881019,
>            7812.240945308214 5717.938278881019,
>            7812.040945308213 5717.67827888102,
>            7813.240945308214 5717.688278881019,
>            7813.440945308213 5717.67827888102,
>            7813.630945308214 5717.668278881019,
>            7813.780945308214 5717.658278881019,
>            7813.920945308214 5717.63827888102,
>            7814.060945308214 5717.608278881019,
>            7814.210945308215 5717.5882788810195,
>            7814.350945308214 5717.5482788810195,
>            7814.470945308214 5717.498278881019,
>            7814.540945308214 5717.448278881019,
>            7814.600945308214 5717.38827888102,
>            7814.620945308213 5717.348278881019,
>            7814.590945308214 5717.288278881019,
>            7814.530945308214 5717.228278881019,
>            7814.460945308214 5717.188278881019,
>            7814.340945308214 5717.13827888102,
>            7814.200945308215 5717.098278881019,
>            7814.050945308214 5717.078278881019,
>            7813.910945308214 5717.058278881019,
>            7813.770945308213 5717.038278881019,
>            7813.620945308214 5717.028278881019,
>            7813.420945308214 5717.018278881019,
>            7813.230945308213 5717.018278881019,
>            7811.570945308214 5717.018278881019,
>            7808.260945308214 5712.698278881019,
>            7809.410945308214 5712.608278881019,
>            7810.160945308214 5712.498278881019,
>            7810.690945308214 5712.288278881019,
>            7810.180945308214 5712.078278881019,
>            7809.340945308213 5711.918278881019,
>            7808.580945308214 5711.8782788810195,
>            7807.600945308214 5711.8782788810195,
>            7806.300945308214 5710.1282788810195,
>            7808.060945308215 5710.118278881019,
>            7809.390945308214 5710.058278881019,
>            7810.080945308215 5709.918278881019,
>            7810.690945308214 5709.698278881019,
>            7810.120945308214 5709.498278881019,
>            7809.760945308214 5709.408278881019,
>            7808.580945308214 5709.288278881019,
>            7805.660945308214 5709.288278881019,
>            7804.500945308214 5707.748278881019,
>            7806.420945308214 5707.748278881019,
>            7806.770945308213 5707.748278881019,
>            7806.890945308215 5707.738278881019,
>            7806.450945308215 5708.278278881019,
>            7806.790945308214 5708.278278881019,
>            7807.570945308214 5707.708278881019,
>            7807.880945308214 5707.688278881019,
>            7808.140945308214 5707.668278881019,
>            7808.390945308214 5707.63827888102,
>            7808.600945308213 5707.5882788810195,
>            7808.720945308213 5707.5482788810195,
>            7808.9409453082135 5707.458278881019,
>            7808.710945308214 5707.358278881019,
>            7808.590945308214 5707.318278881019,
>            7808.380945308214 5707.278278881019,
>            7808.130945308214 5707.238278881019,
>            7807.870945308214 5707.21827888102,
>            7807.6109453082145 5707.198278881019,
>            7806.790945308214 5706.6282788810195,
>            7806.450945308215 5706.6282788810195,
>            7806.920945308214 5707.168278881019,
>            7806.760945308215 5707.168278881019,
>            7806.420945308214 5707.158278881019,
>            7800.920945308215 5707.158278881019,
>            7800.150945308213 5706.558278881019,
>            7798.950945308214 5706.558278881019,
>            7798.950945308214 5707.158278881019,
>            7798.950945308214 5707.768278881019,
>            7798.950945308214 5708.368278881019,
>            7800.150945308213 5708.368278881019,
>            7800.970945308213 5707.748278881019,
>            7800.970945308213 5709.278278881019,
>            7799.480945308214 5709.278278881019,
>            7798.700945308214 5708.668278881019,
>            7797.500945308214 5708.668278881019,
>            7797.500945308214 5709.2982788810195,
>            7797.500945308214 5710.75827888102,
>            7798.680945308214 5710.75827888102,
>            7799.480945308214 5710.118278881019,
>            7800.970945308213 5710.1282788810195,
>            7800.970945308213 5711.858278881019,
>            7799.490945308215 5711.868278881019,
>            7798.700945308214 5711.25827888102,
>            7797.480945308213 5711.25827888102,
>            7797.480945308213 5711.868278881019,
>            7797.480945308213 5713.348278881019,
>            7798.680945308214 5713.348278881019,
>            7799.470945308214 5712.698278881019,
>            7800.970945308213 5712.708278881019,
>            7800.970945308213 5719.148278881019,
>            7796.330945308214 5719.13827888102,
>            7791.960945308214 5713.198278881019,
>            7789.050945308214 5713.198278881019,
>            7787.920945308213 5714.098278881019,
>            7788.2709453082125 5721.498278881019,
>            7787.6109453082145 5721.748278881019,
>            7787.609801510807 5721.813475333222
>         )
>         On Mon, Sep 22, 2008 at 3:37 PM, Martin Davis
>         <[hidden email] <mailto:[hidden email]>
>         <mailto:[hidden email]
>         <mailto:[hidden email]>>> wrote:
>
>            Welcome, Larry - nice to have you aboard!
>
>            Your buffer approach is very interesting - I've speculated
>         about
>            similar techniques, but never had the time to try them out
>         - and
>            was not sure if they would really lead to an improvement.  
>         (Your
>            comment about "can cause robustness issues" makes me a bit
>         nervous...)
>
>            I've always thought that trying to "pre-intersect" offset
>         curves
>            would be quite inefficent in bad cases (e.g. ones with large
>            buffer distances, where any given offset segment/arc might
>            intersect many other parts of the offset curve).  Did you do
>            something special to avoid this?
>
>            I can see that maintaining explicit arcs would produce smoother
>            curves.  The math and tolerances involved in computing arc
>            intersections always scared me off this approach.  But it
>         sounds
>            like you cracked this problem.
>
>            The reason why the current JTS algorithm slows down with large
>            buffer distances is because in inside corners two "closing
>            segments" are added to ensure that the offset curve is always
>            closed (a picture would show this better).  When closing
>         segments
>            get very long, they end up intersecting many other
>         segments. This
>            causes the noding to get very slow.  So far I haven't
>         figured out
>            a way to remove or reduce the impact of these segments.  Your
>            "pre-intersection" algorithm might do this - but I'm curious to
>            know how it works (short of scanning all previously generated
>            offser curve components - which sounds very slow)
>
>            Martin
>
>
>            Larry Becker wrote:
>
>                Hello Martin and Michael ,
>
>                I have a buffer algorithm that seems to provide significant
>                performance improvements.  I developed it in the early 90's
>                and implemented it in Delphi Pascal.
>                 I randomly surfed into this post and decided to join
>         the JTS
>                Devel list so that I could participate.   I have
>         recently been
>                noticing the same thing that Michael is talking about - the
>                issue of larger distances causing slower performance.  
>         I made
>                up my own tests and found cases where it took several
>         minutes
>                to finish.  I tried these cases on my own buffer
>         algorithm and
>                it seems quite a bit faster, although I need benchmark
>         times
>                to verify this result.
>
>                I have been looking over my buffer code for the first
>         time in
>                over ten years, and a few things stood out initially.
>                The offset curves are generated pre-intersected with
>         adjacent
>                offset curves using a poly-arc data structure that stores
>                either the intersection point or a point-angle-point arc,
>                depending on if it is an inside or outside turn
>         respectively.
>                 The result of each pass is always a complete polygon/arc
>                structure.  The next step is to node and remove interior
>                self-intersections.  All of the node intersections are done
>                with exact calculations using circular arcs.  This can
>         cause
>                some issues with robustness, but produces a much more
>         accurate
>                buffer than simulating arcs with line segments, and reduces
>                the number of total intersection tests.
>
>                regards,
>                Larry Becker
>
>                   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
>                />>/ jts-devel at lists.jump-project.org
>         <http://lists.jump-project.org>
>                <http://lists.jump-project.org>
>
>                <http://lists.refractions.net/mailman/listinfo/jts-devel>
>                />>/
>         http://lists.refractions.net/mailman/listinfo/jts-devel
>
>                />>/
>                />/
>                /
>
>
>                --        http://amusingprogrammer.blogspot.com/
>              
>          ------------------------------------------------------------------------
>
>                _______________________________________________
>                jts-devel mailing list
>                [hidden email]
>         <mailto:[hidden email]>
>                <mailto:[hidden email]
>         <mailto:[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]
>         <mailto:[hidden email]>
>            <mailto:[hidden email]
>         <mailto:[hidden email]>>
>
>
>            http://lists.refractions.net/mailman/listinfo/jts-devel
>
>
>
>
>         --
>         http://amusingprogrammer.blogspot.com/
>         ------------------------------------------------------------------------
>
>         _______________________________________________
>         jts-devel mailing list
>         [hidden email]
>         <mailto:[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]
>     <mailto:[hidden email]>
>     http://lists.refractions.net/mailman/listinfo/jts-devel
>
>
>
>
> --
> http://amusingprogrammer.blogspot.com/
> ------------------------------------------------------------------------
>
> _______________________________________________
> 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: Re:Buffer operation performance

Larry Becker
I'm sure it is faster on that case too, but I don't have fine enough metrics to tell.  :-}

BTW, my algorithm removes the special case of linestrings by doubling them back on themselves, effectively producing an infinitely thin polygon.

On Mon, Sep 22, 2008 at 4:17 PM, Martin Davis <[hidden email]> wrote:
That's because now JTS only computes an offset curve for one side of the shape (and the side which has fewer inside corners).  This makes for a much less complex offset curve, which can be noded a lot faster.

How does your code perform in this situation?   Still 1 sec?  8^)

Larry Becker wrote:
One more thing...  If you close the aircraft LineString and make a polygon out of it, the JTS 100 distance case completes in 281 ms!

On Mon, Sep 22, 2008 at 4:00 PM, Martin Davis <[hidden email] <mailto:[hidden email]>> wrote:

   Yes, that's a good test case alright - it definitely stresses the
   JTS algorithm.

   So it would be great to get some more details on your secret
   sauce...  TIA for sharing anything you find.

   Martin

   Larry Becker wrote:

       Hi Martin,

       I've completed some preliminary benchmarks:

       JTS
       distance      time
               10       1 s
               40      30 s
              100     64 s

       My Algorithm (need a name here)
        distance      time
               10       1 s
               40       1 s
              100      1 s

       My test data is a LineString of an aircraft. (Not that common
       in GIS, but it works for me.)

       My comments about robustness refer to the arc-arc intersection
       problem of coincident circles (where do they intersect).  It
       causes problems, but special processing could potentially
       prevent this (fairly rare) issue.

       I developed the special algorithm because accurate buffers are
       very important in our (ISA) area of business.

       I'll try to describe the algorithm in more detail when I get a
       chance.  I'll need to review it more.

       regards,
       Larry

       LINESTRING (
          7787.609776069839 5723.961632293637,
          7787.6109453082145 5724.028278881019,
          7788.250945308214 5724.268278881019,
          7787.920945308213 5731.67827888102,
          7789.050945308214 5732.578278881019,
          7791.960945308214 5732.578278881019,
          7796.330945308214 5726.63827888102,
          7800.970945308213 5726.6282788810195,
          7800.970945308213 5733.058278881019,
          7799.490945308215 5733.068278881019,
          7798.680945308214 5732.42827888102,
          7797.480945308213 5732.42827888102,
          7797.480945308213 5733.028278881019,
          7797.480945308213 5734.518278881019,
          7798.700945308214 5734.518278881019,
          7799.480945308214 5733.908278881019,
          7800.970945308213 5733.908278881019,
          7800.970945308213 5735.648278881019,
          7799.490945308215 5735.658278881019,
          7798.680945308214 5735.018278881019,
          7797.480945308213 5735.018278881019,
          7797.480945308213 5735.618278881019,
          7797.480945308213 5737.108278881019,
          7798.700945308214 5737.108278881019,
          7799.480945308214 5736.498278881019,
          7800.970945308213 5736.498278881019,
          7800.970945308213 5738.028278881019,
          7800.150945308213 5737.418278881019,
          7798.950945308214 5737.418278881019,
          7798.950945308214 5738.028278881019,
          7798.950945308214 5738.618278881019,
          7798.950945308214 5739.21827888102,
          7800.150945308213 5739.21827888102,
          7800.950945308214 5738.618278881019,
          7806.420945308214 5738.618278881019,
          7806.760945308215 5738.608278881019,
          7806.910945308214 5738.598278881019,
          7806.450945308215 5739.148278881019,
          7806.790945308214 5739.148278881019,
          7807.580945308214 5738.578278881019,
          7807.870945308214 5738.558278881019,
          7808.130945308214 5738.538278881019,
          7808.380945308214 5738.498278881019,
          7808.590945308214 5738.458278881019,
          7808.710945308214 5738.418278881019,
          7808.9409453082135 5738.318278881019,
          7808.720945308213 5738.228278881019,
          7808.600945308213 5738.188278881019,
          7808.390945308214 5738.13827888102,
          7808.140945308214 5738.108278881019,
          7807.880945308214 5738.0882788810195,
          7807.620945308215 5738.068278881019,
          7807.560945308213 5738.058278881019,
          7806.790945308214 5737.498278881019,
          7806.450945308215 5737.498278881019,
          7806.890945308215 5738.028278881019,
          7806.770945308213 5738.028278881019,
          7806.420945308214 5738.028278881019,
          7804.500945308214 5738.028278881019,
          7805.670945308214 5736.488278881019,
          7808.580945308214 5736.488278881019,
          7809.760945308214 5736.368278881019,
          7810.120945308214 5736.278278881019,
          7810.690945308214 5736.078278881019,
          7810.080945308215 5735.858278881019,
          7809.390945308214 5735.71827888102,
          7808.060945308215 5735.658278881019,
          7806.300945308214 5735.658278881019,
          7807.640945308214 5733.88827888102,
          7808.580945308214 5733.898278881019,
          7809.340945308213 5733.858278881019,
          7810.180945308214 5733.698278881019,
          7810.690945308214 5733.488278881019,
          7810.160945308214 5733.278278881019,
          7809.410945308214 5733.168278881019,
          7808.240945308214 5733.078278881019,
          7811.540945308213 5728.75827888102,
          7813.230945308213 5728.75827888102,
          7813.420945308214 5728.75827888102,
          7813.620945308214 5728.748278881019,
          7813.770945308213 5728.738278881019,
          7813.910945308214 5728.71827888102,
          7814.050945308214 5728.698278881019,
          7814.200945308215 5728.67827888102,
          7814.340945308214 5728.63827888102,
          7814.460945308214 5728.5882788810195,
          7814.530945308214 5728.5482788810195,
          7814.590945308214 5728.488278881019,
          7814.620945308213 5728.42827888102,
          7814.600945308214 5728.38827888102,
          7814.540945308214 5728.328278881019,
          7814.470945308214 5728.278278881019,
          7814.350945308214 5728.228278881019,
          7814.210945308215 5728.188278881019,
          7814.060945308214 5728.168278881019,
          7813.920945308214 5728.13827888102,
          7813.780945308214 5728.118278881019,
          7813.630945308214 5728.108278881019,
          7813.440945308213 5728.098278881019,
          7813.240945308214 5728.0882788810195,
          7812.070945308214 5728.0882788810195,
          7812.240945308214 5727.8382788810195,
          7813.320945308213 5727.498278881019,
          7814.180945308214 5727.21827888102,
          7815.670945308213 5726.768278881019,
          7816.700945308214 5726.46827888102,
          7817.530945308214 5726.25827888102,
          7818.350945308214 5726.068278881019,
          7819.310945308213 5725.868278881019,
          7820.140945308214 5725.698278881019,
          7820.880945308214 5725.568278881019,
          7821.860945308214 5725.3782788810195,
          7822.7309453082125 5725.25827888102,
          7823.580945308214 5725.198278881019,
          7824.4409453082135 5725.108278881019,
          7825.420945308214 5725.028278881019,
          7826.290945308214 5724.938278881019,
          7827.3609453082145 5724.868278881019,
          7828.160945308213 5724.828278881019,
          7828.640945308214 5724.788278881019,
          7829.410945308214 5724.708278881019,
          7830.210945308215 5724.578278881019,
          7830.860945308213 5724.438278881019,
          7831.420945308213 5724.278278881019,
          7832.070945308214 5724.068278881019,
          7832.6909453082135 5723.808278881019,
          7833.130945308214 5723.5882788810195,
          7833.530945308214 5723.368278881019,
          7833.870945308214 5723.13827888102,
          7836.650945308213 5722.898278881019,
          7833.870945308214 5722.63827888102,
          7833.530945308214 5722.408278881019,
          7833.130945308214 5722.188278881019,
          7832.6909453082135 5721.96827888102,
          7832.070945308214 5721.708278881019,
          7831.420945308213 5721.498278881019,
          7830.860945308213 5721.3382788810195,
          7830.210945308215 5721.198278881019,
          7829.410945308214 5721.068278881019,
          7828.640945308214 5720.988278881019,
          7828.160945308213 5720.948278881019,
          7827.3609453082145 5720.908278881019,
          7826.290945308214 5720.8382788810195,
          7825.420945308214 5720.748278881019,
          7824.4409453082135 5720.668278881019,
          7823.580945308214 5720.578278881019,
          7822.7309453082125 5720.518278881019,
          7821.860945308214 5720.398278881019,
          7820.880945308214 5720.208278881019,
          7820.140945308214 5720.078278881019,
          7819.310945308213 5719.908278881019,
          7818.350945308214 5719.708278881019,
          7817.530945308214 5719.518278881019,
          7816.700945308214 5719.308278881019,
          7815.670945308213 5719.00827888102,
          7814.180945308214 5718.558278881019,
          7813.320945308213 5718.278278881019,
          7812.240945308214 5717.938278881019,
          7812.040945308213 5717.67827888102,
          7813.240945308214 5717.688278881019,
          7813.440945308213 5717.67827888102,
          7813.630945308214 5717.668278881019,
          7813.780945308214 5717.658278881019,
          7813.920945308214 5717.63827888102,
          7814.060945308214 5717.608278881019,
          7814.210945308215 5717.5882788810195,
          7814.350945308214 5717.5482788810195,
          7814.470945308214 5717.498278881019,
          7814.540945308214 5717.448278881019,
          7814.600945308214 5717.38827888102,
          7814.620945308213 5717.348278881019,
          7814.590945308214 5717.288278881019,
          7814.530945308214 5717.228278881019,
          7814.460945308214 5717.188278881019,
          7814.340945308214 5717.13827888102,
          7814.200945308215 5717.098278881019,
          7814.050945308214 5717.078278881019,
          7813.910945308214 5717.058278881019,
          7813.770945308213 5717.038278881019,
          7813.620945308214 5717.028278881019,
          7813.420945308214 5717.018278881019,
          7813.230945308213 5717.018278881019,
          7811.570945308214 5717.018278881019,
          7808.260945308214 5712.698278881019,
          7809.410945308214 5712.608278881019,
          7810.160945308214 5712.498278881019,
          7810.690945308214 5712.288278881019,
          7810.180945308214 5712.078278881019,
          7809.340945308213 5711.918278881019,
          7808.580945308214 5711.8782788810195,
          7807.600945308214 5711.8782788810195,
          7806.300945308214 5710.1282788810195,
          7808.060945308215 5710.118278881019,
          7809.390945308214 5710.058278881019,
          7810.080945308215 5709.918278881019,
          7810.690945308214 5709.698278881019,
          7810.120945308214 5709.498278881019,
          7809.760945308214 5709.408278881019,
          7808.580945308214 5709.288278881019,
          7805.660945308214 5709.288278881019,
          7804.500945308214 5707.748278881019,
          7806.420945308214 5707.748278881019,
          7806.770945308213 5707.748278881019,
          7806.890945308215 5707.738278881019,
          7806.450945308215 5708.278278881019,
          7806.790945308214 5708.278278881019,
          7807.570945308214 5707.708278881019,
          7807.880945308214 5707.688278881019,
          7808.140945308214 5707.668278881019,
          7808.390945308214 5707.63827888102,
          7808.600945308213 5707.5882788810195,
          7808.720945308213 5707.5482788810195,
          7808.9409453082135 5707.458278881019,
          7808.710945308214 5707.358278881019,
          7808.590945308214 5707.318278881019,
          7808.380945308214 5707.278278881019,
          7808.130945308214 5707.238278881019,
          7807.870945308214 5707.21827888102,
          7807.6109453082145 5707.198278881019,
          7806.790945308214 5706.6282788810195,
          7806.450945308215 5706.6282788810195,
          7806.920945308214 5707.168278881019,
          7806.760945308215 5707.168278881019,
          7806.420945308214 5707.158278881019,
          7800.920945308215 5707.158278881019,
          7800.150945308213 5706.558278881019,
          7798.950945308214 5706.558278881019,
          7798.950945308214 5707.158278881019,
          7798.950945308214 5707.768278881019,
          7798.950945308214 5708.368278881019,
          7800.150945308213 5708.368278881019,
          7800.970945308213 5707.748278881019,
          7800.970945308213 5709.278278881019,
          7799.480945308214 5709.278278881019,
          7798.700945308214 5708.668278881019,
          7797.500945308214 5708.668278881019,
          7797.500945308214 5709.2982788810195,
          7797.500945308214 5710.75827888102,
          7798.680945308214 5710.75827888102,
          7799.480945308214 5710.118278881019,
          7800.970945308213 5710.1282788810195,
          7800.970945308213 5711.858278881019,
          7799.490945308215 5711.868278881019,
          7798.700945308214 5711.25827888102,
          7797.480945308213 5711.25827888102,
          7797.480945308213 5711.868278881019,
          7797.480945308213 5713.348278881019,
          7798.680945308214 5713.348278881019,
          7799.470945308214 5712.698278881019,
          7800.970945308213 5712.708278881019,
          7800.970945308213 5719.148278881019,
          7796.330945308214 5719.13827888102,
          7791.960945308214 5713.198278881019,
          7789.050945308214 5713.198278881019,
          7787.920945308213 5714.098278881019,
          7788.2709453082125 5721.498278881019,
          7787.6109453082145 5721.748278881019,
          7787.609801510807 5721.813475333222
       )
       On Mon, Sep 22, 2008 at 3:37 PM, Martin Davis
       <[hidden email] <mailto:[hidden email]>
       <mailto:[hidden email]

       <mailto:[hidden email]>>> wrote:

          Welcome, Larry - nice to have you aboard!

          Your buffer approach is very interesting - I've speculated
       about
          similar techniques, but never had the time to try them out
       - and
          was not sure if they would really lead to an improvement.          (Your
          comment about "can cause robustness issues" makes me a bit
       nervous...)

          I've always thought that trying to "pre-intersect" offset
       curves
          would be quite inefficent in bad cases (e.g. ones with large
          buffer distances, where any given offset segment/arc might
          intersect many other parts of the offset curve).  Did you do
          something special to avoid this?

          I can see that maintaining explicit arcs would produce smoother
          curves.  The math and tolerances involved in computing arc
          intersections always scared me off this approach.  But it
       sounds
          like you cracked this problem.

          The reason why the current JTS algorithm slows down with large
          buffer distances is because in inside corners two "closing
          segments" are added to ensure that the offset curve is always
          closed (a picture would show this better).  When closing
       segments
          get very long, they end up intersecting many other
       segments. This
          causes the noding to get very slow.  So far I haven't
       figured out
          a way to remove or reduce the impact of these segments.  Your
          "pre-intersection" algorithm might do this - but I'm curious to
          know how it works (short of scanning all previously generated
          offser curve components - which sounds very slow)

          Martin


          Larry Becker wrote:

              Hello Martin and Michael ,

              I have a buffer algorithm that seems to provide significant
              performance improvements.  I developed it in the early 90's
              and implemented it in Delphi Pascal.
               I randomly surfed into this post and decided to join
       the JTS
              Devel list so that I could participate.   I have
       recently been
              noticing the same thing that Michael is talking about - the
              issue of larger distances causing slower performance.          I made
              up my own tests and found cases where it took several
       minutes
              to finish.  I tried these cases on my own buffer
       algorithm and
              it seems quite a bit faster, although I need benchmark
       times
              to verify this result.

              I have been looking over my buffer code for the first
       time in
              over ten years, and a few things stood out initially.
              The offset curves are generated pre-intersected with
       adjacent
              offset curves using a poly-arc data structure that stores
              either the intersection point or a point-angle-point arc,
              depending on if it is an inside or outside turn
       respectively.
               The result of each pass is always a complete polygon/arc
              structure.  The next step is to node and remove interior
              self-intersections.  All of the node intersections are done
              with exact calculations using circular arcs.  This can
       cause
              some issues with robustness, but produces a much more
       accurate
              buffer than simulating arcs with line segments, and reduces
              the number of total intersection tests.

              regards,
              Larry Becker

                 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
              />>/ jts-devel at lists.jump-project.org
       <http://lists.jump-project.org>
              <http://lists.jump-project.org>

              <http://lists.refractions.net/mailman/listinfo/jts-devel>
              />>/
       http://lists.refractions.net/mailman/listinfo/jts-devel

              />>/
              />/
              /


              --        http://amusingprogrammer.blogspot.com/
                    ------------------------------------------------------------------------

              _______________________________________________
              jts-devel mailing list
              [hidden email]
       <mailto:[hidden email]>
              <mailto:[hidden email]
       <mailto:[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]
       <mailto:[hidden email]>
          <mailto:[hidden email]
       <mailto:[hidden email]>>


          http://lists.refractions.net/mailman/listinfo/jts-devel




       --        http://amusingprogrammer.blogspot.com/
       ------------------------------------------------------------------------

       _______________________________________________
       jts-devel mailing list
       [hidden email]
       <mailto:[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]
   <mailto:[hidden email]>
   http://lists.refractions.net/mailman/listinfo/jts-devel




--
http://amusingprogrammer.blogspot.com/
------------------------------------------------------------------------

_______________________________________________
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



--
http://amusingprogrammer.blogspot.com/

_______________________________________________
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: Re:Buffer operation performance

Martin Davis


Larry Becker wrote:
>
> BTW, my algorithm removes the special case of linestrings by doubling
> them back on themselves, effectively producing an infinitely thin polygon.
I do this as well, by traversing the linestring once in each direction
(linked by an "end cap arc").  My comment below still stands, though -
for linework which is a polygon, the coordinate sequence is traversed in
only one direction.
>
> On Mon, Sep 22, 2008 at 4:17 PM, Martin Davis <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     That's because now JTS only computes an offset curve for one side
>     of the shape (and the side which has fewer inside corners).  This
>     makes for a much less complex offset curve, which can be noded a
>     lot faster.
>

--
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...