// TreeSearch.java
// Murat Öksüzer, April 2021
// https://www.smartycoder.com/2021/04/geometry-model-jts-tutorial-1.html
// Modified by Andrew Davison, ad@coe.psu.ac.th, March 2023

/* Use Quadtree and Kdtree to determine which of NUM_PTS random 
   points intersect a rectangle.

   Note: the quadtree search sometimes identify points which are outside
   the search rectangle. This is most easily seen since the selected
   points are drawn in green in GeomsViewer.

   Other tree data structures in JTS:
     * 2D: STRtree 
     * 1D: Bintree, SortedPackedIntervalRTree

   Usage:
    > compile TreeSearch.java
    > run TreeSearch [k]
        -- add the 'k' to switch from Quadtree to kdtree

*/

import java.awt.Color;
import java.util.*;

import org.locationtech.jts.geom.*;
import org.locationtech.jts.index.quadtree.Quadtree;
import org.locationtech.jts.index.kdtree.*;


public class TreeSearch
{
  private static final int NUM_PTS = 20;


  public static void main(String[] args)
  {
    boolean isKd = false;
    if (args.length != 0) {
      System.out.println("Using a Kdtree");
      isKd = true;
    }
    else
      System.out.println("Using a Quadtree");

    GeomsViewer gv =  Utils.view("Tree Search");
    GeometryFactory gf = new GeometryFactory();
    Random rand = new Random();

    // create both trees, but we will only use one of them
    Quadtree quadTree = new Quadtree();
    KdTree kdTree = new KdTree();

    // random points
    System.out.println("Generating " + NUM_PTS + " points");
    for(int i = 0; i < NUM_PTS; i++) {
      int x = rand.nextInt(250) + 65;
      int y = rand.nextInt(250) + 50;
      Coordinate coord = new Coordinate(x, y);
      Point pt = gf.createPoint(coord);
      gv.add(pt);

      quadTree.insert(pt.getEnvelopeInternal(), pt);
      kdTree.insert(coord, pt);
    }

    // rectangle used for point selection
    double[] coords = new double[] {
                  150,60, 250,60, 250,250, 150,250, 150,60 };
    Geometry rect = Utils.makeGeometry(coords, Utils.POLY);
    System.out.println("Rectangle: " + rect);
    gv.add(rect, Color.RED);

    // use the kdtree or the quadtree for the search
    if (isKd) {
      gv.setTitle("Kdtree");
      System.out.println("kdTree Intersecting points:");
      List items = kdTree.query(rect.getEnvelopeInternal());
      for (int i =0; i < items.size(); i++) {
        KdNode node = (KdNode)items.get(i);  // first get a KdNode
        Point pt = (Point)node.getData();

        System.out.println((i+1) + ". " + pt);
        gv.remove(pt);
        gv.add("Selected " + (i+1), pt, Color.GREEN);
      }
    }
    else {  // use the Quadtree
      gv.setTitle("Quadtree");
      System.out.println("QuadTree Intersecting points:");
      List items = quadTree.query(rect.getEnvelopeInternal());
      for (int i =0; i < items.size(); i++) {
        Point pt = (Point)items.get(i);

        System.out.println((i+1) + ". " + pt);
        gv.remove(pt);
        gv.add("Selected " + (i+1), pt, Color.GREEN);
      }
    }
  } /* main */


}  // end of TreeSearch class