Hmm... I'm not quite sure how you approach of gathering all edges and
then sorting them to remove duplicates actually works, since the code
that calls findEqualEdge depends on know whether an edge is duplicated
right at that time, not just after all edges have been processed. In
other words, the EdgeList needs to be dynamic, not static. But perhaps
I'm missing something.
Anyway, the OCA approach is pretty much equivalent, and I'm guessing not
perceptibly slower. If you can try it and compare that would be great.
Can you post your test dataset? It's always useful to have test data.
The situation where the buffer dist >> segment length is the toughest
case for buffering. I was going to suggest some heuristics that you
could use to speed things up - you've already found one of them:
- simplify the input polygon using a tolerance of say bufDist/100
- buffer the input polygon twice, once with a small bufDist (say
origBufDist / 10), and then with the difference
I have some other ideas about a "FastBufferSimplifier" which would
simplfy concave areas but leave convex areas alone (since they are more
visible in the resulting buffer)
Janda Martin wrote:
Thank you very much for information. I'm looking forward to test your solution
with OrientedCoordinateArray.
I tested my approach 'EdgeItemVisitor' on my home AMD 64 3000, Java 1.6b4 and it took about 30s (to create and merge Edges).
I tried another way how to eliminate equal Edges. I create array of all Edges that has same size as Collection of 'nodedSegStrings' in BufferBuilder.computeNodedEdges. Than I sort them with mergeSort (to index). Now equal edges should be behind each other in row. And I can remove equal Edges.
a) create Edge array - O(n)
b) create Edge array index (don't want to change order - I don't know if the
buffer algorithm depends on order of Edges) - O(n log n)
c) iterate through 'sorted' Edge array to merge duplicates O(n)
d) fill edgeList with result Edges O(n)
It's a little bit tricky but I it works. There are only 2 allocation of array
and small overhead for created Edges (that are not immediately merged).
With my last version it took about 3 seconds to create and merge Edges. 10
times faster.
Some statistics:
Polygon : border of administration part in Czech Republic
Coordinates : 3288
--
Buffer offset: offset (~km) >> average length of polygon edge ( ~100m )
--
Created edges: 221569
Merged edges : 0
I think this is very special case.
Some profiler information for my data: TOTAL ALLOCATED OBJECTS (live + garbage
collected)
Type Instance count - Size (kB)
geom.Coordinate 1,348,648 - 42,145kB
geomgraph.TopologyLocation 1,550,988 - 24,234kB
geomgraph.DirectedEdge 443,138 - 34,620kB
HCoordinate 777,658 - 24,301kB
Envelope 448,725 - 17,528kB
int[] in PlanarGraph.addEdges 1,661,769 - 37,216kB
int[] in computeNodedEdges - Label 443,138 - 10,386kB
int[] in computeNodedEdges - Edge 443,138 - 10,386kB
---
I decided to simplify polygon (due to buffering offset >> edge length) and
afterwards to compute buffering. And the total time of simplifying and buffering is
less than 1s. :-)
I still want to help improve JTS.
Martin
--
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
