Re: [Jts-topo-suite-user] how to find repeated points

[Martin D. <mtn...@te...>]

Good to have it confirmed that HashSet/Map is the fastest way of testing 
for point equality.

It's worth noting that KdTree is still useful, since it supports range 
queries, as well as an "equality tolerance".

Jose C. Martinez-Llario wrote:
>   Martin, as you sugested me I did some bechmark about finding repeated 
> poitns.
> Here is the result.
>
> Some conclusions about the results in my computer:
>
> < 25 points brute force shows little bit better result than hashset
>  > 50 points hashset is the best one
>
> Dont use brute force for more then 100 points.
> kdtree shows good performance but around 4 times slower than hashset in 
> most cases.
>
>
> Didnt check the java memory..in that sense brute force should be the 
> best one.
>
> cheers,
> Jose
>
>
>
> Method 0 is HashSet
> Method 1 is KdTree
> Method 2 is Brute force
> Base Points: 9
> Repeated Points: 1
> Iterations: 5000000
>      Method: 0 start...
>      Method: 0 end... Average time one iteration: 8.474E-4ms
>      Method: 1 start...
>      Method: 1 end... Average time one iteration: 0.001378ms
>      Method: 2 start...
>      Method: 2 end... Average time one iteration: 4.396E-4ms
> Base Points: 22
> Repeated Points: 3
> Iterations: 1000000
>      Method: 0 start...
>      Method: 0 end... Average time one iteration: 0.002135ms
>      Method: 1 start...
>      Method: 1 end... Average time one iteration: 0.005063ms
>      Method: 2 start...
>      Method: 2 end... Average time one iteration: 0.002506ms
> Base Points: 45
> Repeated Points: 5
> Iterations: 500000
>      Method: 0 start...
>      Method: 0 end... Average time one iteration: 0.004596ms
>      Method: 1 start...
>      Method: 1 end... Average time one iteration: 0.012818ms
>      Method: 2 start...
>      Method: 2 end... Average time one iteration: 0.009758ms
> Base Points: 90
> Repeated Points: 10
> Iterations: 50000
>      Method: 0 start...
>      Method: 0 end... Average time one iteration: 0.00974ms
>      Method: 1 start...
>      Method: 1 end... Average time one iteration: 0.02988ms
>      Method: 2 start...
>      Method: 2 end... Average time one iteration: 0.03828ms
> Base Points: 450
> Repeated Points: 50
> Iterations: 5000
>      Method: 0 start...
>      Method: 0 end... Average time one iteration: 0.0582ms
>      Method: 1 start...
>      Method: 1 end... Average time one iteration: 0.22ms
>      Method: 2 start...
>      Method: 2 end... Average time one iteration: 0.942ms
> Base Points: 900
> Repeated Points: 100
> Iterations: 500
>      Method: 0 start...
>      Method: 0 end... Average time one iteration: 0.114ms
>      Method: 1 start...
>      Method: 1 end... Average time one iteration: 0.476ms
>      Method: 2 start...
>      Method: 2 end... Average time one iteration: 3.74ms
> Base Points: 4500
> Repeated Points: 500
> Iterations: 20
>      Method: 0 start...
>      Method: 0 end... Average time one iteration: 0.55ms
>      Method: 1 start...
>      Method: 1 end... Average time one iteration: 3.95ms
>      Method: 2 start...
>      Method: 2 end... Average time one iteration: 94.25ms
>
>
> main function:
> public static void repeatedPoints (Coordinate[] coors, int type) {
>          int n = 0;
>
>          if (type == 0) {
>              HashSet <Coordinate> hashCoor = new HashSet <Coordinate>();
>
>              int prevSize = 0;
>              int newSize = 0;
>
>              for (Coordinate c: coors) {
>                  hashCoor.add(c);
>                  newSize = hashCoor.size();
>                  if (newSize == prevSize) {
>                      //This one is repeated
>                      n++;
>                  }
>                  prevSize = newSize;
>              }
>              //it will work but i want to know witch points are repeated
>              //n = coors.length - hashCoor.size();
>          } else if (type == 1) {
>
>              n = 0;
>              KdTree kdtree = new KdTree();
>              KdNode node;
>              for (Coordinate c: coors) {
>                  node = kdtree.insert(c);
>                  if (node.getCount() > 1) {
>                      //This one is repeated
>                      n++;
>                  }
>              }
>          } else if (type == 2) {
>              //Brute force
>              n = 0;
>              int np = coors.length;
>              for (int i = 0; i < np - 1; i++)
>                  for (int j = i+1; j < np; j++) {
>                      if (coors[i].equals(coors[j])) {
>                          n++;
>                      }
>                  }
>          } else Assert.shouldNeverReachHere();
>
>          //System.out.println ("\t\tTotal points: " + coors.length + " 
> Repeated points: " + n);
>      }
>
>
>
> ------------------------------------------------------------------------------
> Download new Adobe(R) Flash(R) Builder(TM) 4
> The new Adobe(R) Flex(R) 4 and Flash(R) Builder(TM) 4 (formerly 
> Flex(R) Builder(TM)) enable the development of rich applications that run
> across multiple browsers and platforms. Download your free trials today!
> http://p.sf.net/sfu/adobe-dev2dev
> _______________________________________________
> Jts-topo-suite-user mailing list
> Jts...@li...
> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>
>