Re: [Jts-topo-suite-user] i want to add an algrithem in jts

[xschen <xs...@cl...>]

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 <xs...@cl... 
> <mailto:xs...@cl...>> 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
>     Jts...@li...
>     <mailto:Jts...@li...>
>     https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>
>