001: /*
002: * The JTS Topology Suite is a collection of Java classes that
003: * implement the fundamental operations required to validate a given
004: * geo-spatial data set to a known topological specification.
005: *
006: * Copyright (C) 2001 Vivid Solutions
007: *
008: * This library is free software; you can redistribute it and/or
009: * modify it under the terms of the GNU Lesser General Public
010: * License as published by the Free Software Foundation; either
011: * version 2.1 of the License, or (at your option) any later version.
012: *
013: * This library is distributed in the hope that it will be useful,
014: * but WITHOUT ANY WARRANTY; without even the implied warranty of
015: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
016: * Lesser General Public License for more details.
017: *
018: * You should have received a copy of the GNU Lesser General Public
019: * License along with this library; if not, write to the Free Software
020: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
021: *
022: * For more information, contact:
023: *
024: * Vivid Solutions
025: * Suite #1A
026: * 2328 Government Street
027: * Victoria BC V8T 5G5
028: * Canada
029: *
030: * (250)385-6040
031: * www.vividsolutions.com
032: */
033: package com.vividsolutions.jts.operation.valid;
034:
035: import java.util.*;
036: import com.vividsolutions.jts.algorithm.*;
037: import com.vividsolutions.jts.geom.*;
038: import com.vividsolutions.jts.geomgraph.*;
039: import com.vividsolutions.jts.index.quadtree.Quadtree;
040: import com.vividsolutions.jts.util.*;
041:
042: /**
043: * Tests whether any of a set of {@link LinearRing}s are
044: * nested inside another ring in the set, using a {@link Quadtree}
045: * index to speed up the comparisons.
046: *
047: * @version 1.7
048: */
049: public class QuadtreeNestedRingTester {
050:
051: private GeometryGraph graph; // used to find non-node vertices
052: private List rings = new ArrayList();
053: private Envelope totalEnv = new Envelope();
054: private Quadtree quadtree;
055: private Coordinate nestedPt;
056:
057: public QuadtreeNestedRingTester(GeometryGraph graph) {
058: this .graph = graph;
059: }
060:
061: public Coordinate getNestedPoint() {
062: return nestedPt;
063: }
064:
065: public void add(LinearRing ring) {
066: rings.add(ring);
067: totalEnv.expandToInclude(ring.getEnvelopeInternal());
068: }
069:
070: public boolean isNonNested() {
071: buildQuadtree();
072:
073: for (int i = 0; i < rings.size(); i++) {
074: LinearRing innerRing = (LinearRing) rings.get(i);
075: Coordinate[] innerRingPts = innerRing.getCoordinates();
076:
077: List results = quadtree.query(innerRing
078: .getEnvelopeInternal());
079: //System.out.println(results.size());
080: for (int j = 0; j < results.size(); j++) {
081: LinearRing searchRing = (LinearRing) results.get(j);
082: Coordinate[] searchRingPts = searchRing
083: .getCoordinates();
084:
085: if (innerRing == searchRing)
086: continue;
087:
088: if (!innerRing.getEnvelopeInternal().intersects(
089: searchRing.getEnvelopeInternal()))
090: continue;
091:
092: Coordinate innerRingPt = IsValidOp.findPtNotNode(
093: innerRingPts, searchRing, graph);
094: Assert
095: .isTrue(innerRingPt != null,
096: "Unable to find a ring point not a node of the search ring");
097: //Coordinate innerRingPt = innerRingPts[0];
098:
099: boolean isInside = CGAlgorithms.isPointInRing(
100: innerRingPt, searchRingPts);
101: if (isInside) {
102: nestedPt = innerRingPt;
103: return false;
104: }
105: }
106: }
107: return true;
108: }
109:
110: private void buildQuadtree() {
111: quadtree = new Quadtree();
112:
113: for (int i = 0; i < rings.size(); i++) {
114: LinearRing ring = (LinearRing) rings.get(i);
115: Envelope env = ring.getEnvelopeInternal();
116: quadtree.insert(env, ring);
117: }
118: }
119: }
|