HotPixelIndex.java
/*
* Copyright (c) 2019 Martin Davis.
*
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License 2.0
* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
* and the Eclipse Distribution License is available at
*
* http://www.eclipse.org/org/documents/edl-v10.php.
*/
package org.locationtech.jts.noding.snapround;
import java.util.Iterator;
import java.util.List;
import java.util.Random;
import org.locationtech.jts.geom.Coordinate;
import org.locationtech.jts.geom.Envelope;
import org.locationtech.jts.geom.PrecisionModel;
import org.locationtech.jts.index.kdtree.KdNode;
import org.locationtech.jts.index.kdtree.KdNodeVisitor;
import org.locationtech.jts.index.kdtree.KdTree;
/**
* An index which creates unique {@link HotPixel}s for provided points,
* and performs range queries on them.
* The points passed to the index do not needed to be
* rounded to the specified scale factor; this is done internally
* when creating the HotPixels for them.
*
* @author mdavis
*
*/
class HotPixelIndex {
private PrecisionModel precModel;
private double scaleFactor;
/**
* Use a kd-tree to index the pixel centers for optimum performance.
* Since HotPixels have an extent, range queries to the
* index must enlarge the query range by a suitable value
* (using the pixel width is safest).
*/
private KdTree index = new KdTree();
public HotPixelIndex(PrecisionModel pm) {
this.precModel = pm;
scaleFactor = pm.getScale();
}
/**
* Utility class to shuffle an array of {@link Coordinate}s using
* the Fisher-Yates shuffle algorithm
*
* @see <a href="https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle">Fihser-Yates shuffle</a>
*/
private static final class CoordinateShuffler implements Iterator<Coordinate> {
private final Random rnd = new Random(13);
private final Coordinate[] coordinates;
private final int[] indices;
private int index;
/**
* Creates an instance of this class
* @param pts An array of {@link Coordinate}s.
*/
public CoordinateShuffler(Coordinate[] pts) {
coordinates = pts;
indices = new int[pts.length];
for (int i = 0; i < pts.length; i++)
indices[i] = i;
index = pts.length - 1;
}
@Override
public boolean hasNext() {
return index >= 0;
}
@Override
public Coordinate next() {
int j = rnd.nextInt(index + 1);
Coordinate res = coordinates[indices[j]];
indices[j] = indices[index--];
return res;
}
}
/**
* Adds a list of points as non-node pixels.
*
* @param pts the points to add
*/
public void add(Coordinate[] pts) {
/**
* Shuffle the points before adding.
* This avoids having long monontic runs of points
* causing an unbalanced KD-tree, which would create
* performance and robustness issues.
*/
Iterator<Coordinate> it = new CoordinateShuffler(pts);
while (it.hasNext()) {
add(it.next());
}
}
/**
* Adds a list of points as node pixels.
*
* @param pts the points to add
*/
public void addNodes(List<Coordinate> pts) {
/**
* Node points are not shuffled, since they are
* added after the vertex points, and hence the KD-tree should
* be reasonably balanced already.
*/
for (Coordinate pt : pts) {
HotPixel hp = add(pt);
hp.setToNode();
}
}
/**
* Adds a point as a Hot Pixel.
* If the point has been added already, it is marked as a node.
*
* @param p the point to add
* @return the HotPixel for the point
*/
public HotPixel add(Coordinate p) {
// TODO: is there a faster way of doing this?
Coordinate pRound = round(p);
HotPixel hp = find(pRound);
/**
* Hot Pixels which are added more than once
* must have more than one vertex in them
* and thus must be nodes.
*/
if (hp != null) {
hp.setToNode();
return hp;
}
/**
* A pixel containing the point was not found, so create a new one.
* It is initially set to NOT be a node
* (but may become one later on).
*/
hp = new HotPixel(pRound, scaleFactor);
index.insert(hp.getCoordinate(), hp);
return hp;
}
private HotPixel find(Coordinate pixelPt) {
KdNode kdNode = index.query(pixelPt);
if (kdNode == null)
return null;
return (HotPixel) kdNode.getData();
}
private Coordinate round(Coordinate pt) {
Coordinate p2 = pt.copy();
precModel.makePrecise(p2);
return p2;
}
/**
* Visits all the hot pixels which may intersect a segment (p0-p1).
* The visitor must determine whether each hot pixel actually intersects
* the segment.
*
* @param p0 the segment start point
* @param p1 the segment end point
* @param visitor the visitor to apply
*/
public void query(Coordinate p0, Coordinate p1, KdNodeVisitor visitor) {
Envelope queryEnv = new Envelope(p0, p1);
// expand query range to account for HotPixel extent
// expand by full width of one pixel to be safe
queryEnv.expandBy( 1.0 / scaleFactor );
index.query(queryEnv, visitor);
}
}