Tore,
Good news for you! I'm working right now on optimized predicates for
batch situations (which I assume yours is). If you like I can provide
you with an alpha version to test out. I wouldn't mind getting your
feedback on performance.
And are you able to share the datasets you are using for your testing?
Martin
Tore Halset wrote:
Hello.
I am desperate for faster intersection calculations. For my case,
spatial indexes does not seem to help that much. However doing special
tricks based on the geometry type seem to help a lot. For a single
dataset I reduced the time spent on intersection calculations from
110s to 9s by switching from the standard
Geometry#intersects(Geometry) to the attached variant.
Anyone got any better tricks?
Regards,
- Tore.
public class IntersectsCalculator {
private Geometry g1;
private Coordinate[] g1Coords;
private PointLocator pointLocator;
public IntersectsCalculator(Geometry g1) {
this.g1 = g1;
}
private PointLocator getPointLocator() {
if (pointLocator == null) {
pointLocator = new PointLocator();
}
return pointLocator;
}
public boolean intersect(Geometry g2) {
// TODO: remove redundant calculations done on g1 in JTS
// for P-A case: If P is in env(A), test for point-in-poly
if (g1 instanceof Point) {
return _intersectsPointGeometry((Point) g1, g2);
}
if (g2 instanceof Point) {
return _intersectsPointGeometry((Point) g2, g1);
}
// two polygons
if ((g1 instanceof Polygon) && (g2 instanceof Polygon)) {
return _intersectsPolyPoly(g2);
}
// line and polygon
if ((g1 instanceof LineString) && (g2 instanceof Polygon)) {
return _intersects((LineString) g1, (Polygon) g2);
}
if ((g1 instanceof Polygon) && (g2 instanceof LineString)) {
return _intersects((LineString) g2, (Polygon) g1);
}
return g1.intersects(g2);
}
private boolean _intersectsPointGeometry(Point point, Geometry g) {
Coordinate pointc = point.getCoordinate();
// test for special case with two points
if (g instanceof Point) {
return pointc.equals(g.getCoordinate());
}
// short-circuit envelope test
if (!g.getEnvelopeInternal().contains(pointc)) {
return false;
}
// special case for point in polygon with holes
/*
* if ((g instanceof Polygon)) { Polygon p = (Polygon) g; if
* (p.getNumInteriorRing() > 0) { // TODO: 1 this reduces the
number of
* matches :( // TODO: 2 it does not reduce time very much if
* (!getPointLocator().intersects(pointc,
p.getExteriorRing())) { return
* false; } } }
*/
return getPointLocator().intersects(pointc, g);
}
private Coordinate[] getG1Coordinates() {
if (g1Coords == null) {
g1Coords = g1.getCoordinates();
}
return g1Coords;
}
private boolean _intersectsPolyPoly(Geometry g2) {
Polygon p1 = (Polygon) g1;
Polygon p2 = (Polygon) g2;
// short-circuit envelope test
if
(!p1.getEnvelopeInternal().intersects(p2.getEnvelopeInternal())) {
return false;
}
// it might be faster to first check if any of the coordinates
belong in
// the other polygon.
if (_intersects(getG1Coordinates(), p2)) {
return true;
}
if (_intersects(p2.getCoordinates(), p1)) {
return true;
}
// check if exteriour rings intersect first..
if ((p1.getNumInteriorRing() > 0) || (p2.getNumInteriorRing()
> 0)) {
LineString e1 = p1.getExteriorRing();
LineString e2 = p2.getExteriorRing();
if (!e1.intersects(e2)) {
return false;
}
}
// so we are very slow for non-intersecting polygons
return p1.intersects(p2);
}
private boolean _intersects(LineString ls, Polygon p) {
if
(!ls.getEnvelopeInternal().intersects(p.getEnvelopeInternal())) {
return false;
}
if (_intersects(ls.getCoordinates(), p)) {
return true;
}
// special case for polygon with holes
// TODO: does not reduce time that much as it is poly-poly
that are
// eating all cycles
if (p.getNumInteriorRing() > 0) {
if (!ls.intersects(p.getExteriorRing())) {
return false;
}
}
// so we are very slow for non-intersecting geometries
return ls.intersects(p);
}
private boolean _intersects(Coordinate[] coords, Polygon polygon) {
for (int i = 0; i < coords.length; i++) {
Coordinate c = coords[i];
if (getPointLocator().intersects(c, polygon)) {
return true;
}
}
return false;
}
_______________________________________________
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022
_______________________________________________
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
