but my testing result is as follow:
when calculate two long linestring,
if insert them into postgis, 2 rows, intersects function will cost 10second,
if cut each linestring into 10 pieces, insert them into postgis ,20
rows, intersects function will cost 1 second. (with GIST index)
if intersects function of postGIS is O(n log n), those two method
should spend almost same time.
On 08/08/2015 11:16 AM, Martin Davis wrote:
No, in JTS the overlay algorithm uses SimpleMCSweepLineIntersector
(see method createEdgeSetIntersector in GeometryGraph.java). This is
approximatey O(n log n).
If the PostGIS overlay is backed by GEOS code, this should be using
the same logic.
On Sat, Aug 8, 2015 at 3:39 AM, xschen <[email protected]
<mailto:[email protected]>> wrote:
I found the "intersects, intersection" calculation of postgis is very
slow, so that I read the JTS, and found the intersects algrithem
is this
one:
package com.vividsolutions.jts.geomgraph.index;
public class SimpleEdgeSetIntersector extends EdgeSetIntersector
private void computeIntersects(Edge e0, Edge e1,
SegmentIntersector
si)
{
com.vividsolutions.jts.geom.Coordinate pts0[] =
e0.getCoordinates();
com.vividsolutions.jts.geom.Coordinate pts1[] =
e1.getCoordinates();
for(int i0 = 0; i0 < pts0.length - 1; i0++)
{
for(int i1 = 0; i1 < pts1.length - 1; i1++)
si.addIntersections(e0, i0, e1, i1);
}
}
if an n points line intersects an n points line ,the complexity
will be
O(n*n).
this algrithem wiil show very low performance, if n>10000
i suggest to cut each line into sevel small pieces, group them into 4
branch trees boxes and join, then calculate the intersects of small
pieces in the same boxes
so that the complexity will be O(nlog(n)).
------------------------------------------------------------------------------
_______________________________________________
Jts-topo-suite-user mailing list
[email protected]
<mailto:[email protected]>
https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
------------------------------------------------------------------------------
_______________________________________________
Jts-topo-suite-user mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
