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