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 <[EMAIL PROTECTED]>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 <[EMAIL PROTECTED]<mailto: >> [EMAIL PROTECTED]>> 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 >> [email protected] >> <mailto:[email protected]> >> >> http://lists.refractions.net/mailman/listinfo/jts-devel >> >> >> -- Martin Davis >> Senior Technical Architect >> Refractions Research, Inc. >> (250) 383-3022 >> >> _______________________________________________ >> jts-devel mailing list >> [email protected] >> <mailto:[email protected]> >> >> http://lists.refractions.net/mailman/listinfo/jts-devel >> >> >> >> >> -- >> http://amusingprogrammer.blogspot.com/ >> ------------------------------------------------------------------------ >> >> _______________________________________________ >> jts-devel mailing list >> [email protected] >> http://lists.refractions.net/mailman/listinfo/jts-devel >> >> > > -- > Martin Davis > Senior Technical Architect > Refractions Research, Inc. > (250) 383-3022 > > _______________________________________________ > jts-devel mailing list > [email protected] > http://lists.refractions.net/mailman/listinfo/jts-devel > -- http://amusingprogrammer.blogspot.com/
_______________________________________________ jts-devel mailing list [email protected] http://lists.refractions.net/mailman/listinfo/jts-devel
