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