How to query a JTS QuadTree using a query envelope with holes

Question

I have a Java Topology Suite QuadTree containing Points, now I'm trying to query the QuadTree with a polygon that contains a hole. Here's how I create the polygon.

//Method will create a searchable Polygon in the shape of a donut.
public Polygon searchAreaPoly(double outterBoundry, double innerBoundry) {

    Coordinate center = MyIndex.getWGSCoord(longitude, latitude);
    GeometricShapeFactory gsf = new GeometricShapeFactory();

    gsf.setCentre(center);
    gsf.setNumPoints(20);
    LinearRing[] holes = null;
    GeometryFactory fact = new GeometryFactory();

    //create the hole in the shape if innerBoundry is > 0
    if (innerBoundry > 0) {
        gsf.setSize(innerBoundry);
        Polygon innerPoly = gsf.createCircle();
        Coordinate[] innerCoords = innerPoly.getCoordinates();
        LinearRing hole = fact.createLinearRing(innerCoords);
        holes = new LinearRing[]{hole};
    }

    //create the outter boundry
    gsf.setSize(outterBoundry);
    Polygon outterPoly = gsf.createCircle();
    Coordinate[] outterCoords = outterPoly.getCoordinates();
    LinearRing shell = fact.createLinearRing(outterCoords);

    Polygon searchPoly = fact.createPolygon(shell, holes);

    return searchPoly;
}

Here's how I am querying the QuadTree;

//create polygon to search for points the intersect with it
Polygon polygon = data_bounds.searchAreaPoly(shell, hole);

List<MyQuadNode> items = quadTree.query(polygon.getEnvelopeInternal());

However the QuadTree returns a list that doesn't remove the Points the fall within the hole, no matter how big the hole. Does anyone know how to do this, or even if it is possible?

Answer 1

What you're trying to do doesn't really make sense. Quadtree.query works by intersecting the extents of the elements with a rectangular extent. It's up to you to further filter them.

However, you can use the overloaded version of query with a subclass of ItemVisitor to achieve what you want.

public class QtreeTest {

    public static class HoleVisitor implements ItemVisitor {

        private List<Object> result;
        private Polygon filter;

        public HoleVisitor(Polygon filter, List<Object> result) {
            this.result = result;
            this.filter = filter;
        }

        @Override
        public void visitItem(Object obj) {
            if(filter.contains((Geometry) obj))
                result.add(obj);
        }

    }

    public static void main(String[] args) throws ParseException {
        Quadtree t = new Quadtree();
        Polygon p = (Polygon) new WKTReader().read("POLYGON((0 0, 10 0, 10 10, 0 10, 0 0), (2 2, 2 8, 8 8, 8 2, 2 2))");

        Point pt;
        GeometryFactory gf = new GeometryFactory();
        for(int i=0;i<10;++i) {
            pt = gf.createPoint(new Coordinate(Math.random() * 10.0, Math.random() * 10.0));
            t.insert(pt.getEnvelopeInternal(), pt);
        }

        System.out.println("Filter on envelope");
        List<Object> result = t.query(p.getEnvelopeInternal());
        for(Object r:result)
            System.out.println(r);

        System.out.println("Filter with a hole");
        result = new ArrayList<Object>();
        t.query(p.getEnvelopeInternal(), new HoleVisitor(p, result));
        for(Object r:result)
            System.out.println(r);
    }
}

With this code, my output is:

Filter on envelope
POINT (8.080553167044306 0.769379948630533)
POINT (4.569154948368714 4.153733384631248)
POINT (5.92938526520641 3.1663861099889603)
POINT (2.3904730266232455 7.900178460639396)
POINT (5.3909389056227885 5.740854801361649)
POINT (5.493532978665588 4.639022578600436)
POINT (4.736884600312752 5.631310976535514)
POINT (7.076479161641357 5.435151697017327)
POINT (9.409961828398178 2.126750667639794)
POINT (8.753077632261641 6.4171226291983245)

Filter with a hole
POINT (8.080553167044306 0.769379948630533)
POINT (9.409961828398178 2.126750667639794)
POINT (8.753077632261641 6.4171226291983245)