001:
002: /*
003: * The JTS Topology Suite is a collection of Java classes that
004: * implement the fundamental operations required to validate a given
005: * geo-spatial data set to a known topological specification.
006: *
007: * Copyright (C) 2001 Vivid Solutions
008: *
009: * This library is free software; you can redistribute it and/or
010: * modify it under the terms of the GNU Lesser General Public
011: * License as published by the Free Software Foundation; either
012: * version 2.1 of the License, or (at your option) any later version.
013: *
014: * This library is distributed in the hope that it will be useful,
015: * but WITHOUT ANY WARRANTY; without even the implied warranty of
016: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
017: * Lesser General Public License for more details.
018: *
019: * You should have received a copy of the GNU Lesser General Public
020: * License along with this library; if not, write to the Free Software
021: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
022: *
023: * For more information, contact:
024: *
025: * Vivid Solutions
026: * Suite #1A
027: * 2328 Government Street
028: * Victoria BC V8T 5G5
029: * Canada
030: *
031: * (250)385-6040
032: * www.vividsolutions.com
033: */
034: package com.vividsolutions.jts.geomgraph.index;
035:
036: import java.util.*;
037: import com.vividsolutions.jts.geom.*;
038: import com.vividsolutions.jts.geomgraph.*;
039: import com.vividsolutions.jts.algorithm.LineIntersector;
040: import com.vividsolutions.jts.util.Debug;
041:
042: /**
043: * @version 1.7
044: */
045: public class SegmentIntersector {
046:
047: public static boolean isAdjacentSegments(int i1, int i2) {
048: return Math.abs(i1 - i2) == 1;
049: }
050:
051: /**
052: * These variables keep track of what types of intersections were
053: * found during ALL edges that have been intersected.
054: */
055: private boolean hasIntersection = false;
056: private boolean hasProper = false;
057: private boolean hasProperInterior = false;
058: // the proper intersection point found
059: private Coordinate properIntersectionPoint = null;
060:
061: private LineIntersector li;
062: private boolean includeProper;
063: private boolean recordIsolated;
064: private boolean isSelfIntersection;
065: //private boolean intersectionFound;
066: private int numIntersections = 0;
067:
068: // testing only
069: public int numTests = 0;
070:
071: private Collection[] bdyNodes;
072:
073: /*
074: public SegmentIntersector()
075: {
076: }
077: */
078: public SegmentIntersector(LineIntersector li,
079: boolean includeProper, boolean recordIsolated) {
080: this .li = li;
081: this .includeProper = includeProper;
082: this .recordIsolated = recordIsolated;
083: }
084:
085: public void setBoundaryNodes(Collection bdyNodes0,
086: Collection bdyNodes1) {
087: bdyNodes = new Collection[2];
088: bdyNodes[0] = bdyNodes0;
089: bdyNodes[1] = bdyNodes1;
090: }
091:
092: /**
093: * @return the proper intersection point, or <code>null</code> if none was found
094: */
095: public Coordinate getProperIntersectionPoint() {
096: return properIntersectionPoint;
097: }
098:
099: public boolean hasIntersection() {
100: return hasIntersection;
101: }
102:
103: /**
104: * A proper intersection is an intersection which is interior to at least two
105: * line segments. Note that a proper intersection is not necessarily
106: * in the interior of the entire Geometry, since another edge may have
107: * an endpoint equal to the intersection, which according to SFS semantics
108: * can result in the point being on the Boundary of the Geometry.
109: */
110: public boolean hasProperIntersection() {
111: return hasProper;
112: }
113:
114: /**
115: * A proper interior intersection is a proper intersection which is <b>not</b>
116: * contained in the set of boundary nodes set for this SegmentIntersector.
117: */
118: public boolean hasProperInteriorIntersection() {
119: return hasProperInterior;
120: }
121:
122: /**
123: * A trivial intersection is an apparent self-intersection which in fact
124: * is simply the point shared by adjacent line segments.
125: * Note that closed edges require a special check for the point shared by the beginning
126: * and end segments.
127: */
128: private boolean isTrivialIntersection(Edge e0, int segIndex0,
129: Edge e1, int segIndex1) {
130: if (e0 == e1) {
131: if (li.getIntersectionNum() == 1) {
132: if (isAdjacentSegments(segIndex0, segIndex1))
133: return true;
134: if (e0.isClosed()) {
135: int maxSegIndex = e0.getNumPoints() - 1;
136: if ((segIndex0 == 0 && segIndex1 == maxSegIndex)
137: || (segIndex1 == 0 && segIndex0 == maxSegIndex)) {
138: return true;
139: }
140: }
141: }
142: }
143: return false;
144: }
145:
146: /**
147: * This method is called by clients of the EdgeIntersector class to test for and add
148: * intersections for two segments of the edges being intersected.
149: * Note that clients (such as MonotoneChainEdges) may choose not to intersect
150: * certain pairs of segments for efficiency reasons.
151: */
152: public void addIntersections(Edge e0, int segIndex0, Edge e1,
153: int segIndex1) {
154: if (e0 == e1 && segIndex0 == segIndex1)
155: return;
156: numTests++;
157: Coordinate p00 = e0.getCoordinates()[segIndex0];
158: Coordinate p01 = e0.getCoordinates()[segIndex0 + 1];
159: Coordinate p10 = e1.getCoordinates()[segIndex1];
160: Coordinate p11 = e1.getCoordinates()[segIndex1 + 1];
161:
162: li.computeIntersection(p00, p01, p10, p11);
163: //if (li.hasIntersection() && li.isProper()) Debug.println(li);
164: /**
165: * Always record any non-proper intersections.
166: * If includeProper is true, record any proper intersections as well.
167: */
168: if (li.hasIntersection()) {
169: if (recordIsolated) {
170: e0.setIsolated(false);
171: e1.setIsolated(false);
172: }
173: //intersectionFound = true;
174: numIntersections++;
175: // if the segments are adjacent they have at least one trivial intersection,
176: // the shared endpoint. Don't bother adding it if it is the
177: // only intersection.
178: if (!isTrivialIntersection(e0, segIndex0, e1, segIndex1)) {
179: hasIntersection = true;
180: if (includeProper || !li.isProper()) {
181: //Debug.println(li);
182: e0.addIntersections(li, segIndex0, 0);
183: e1.addIntersections(li, segIndex1, 1);
184: }
185: if (li.isProper()) {
186: properIntersectionPoint = (Coordinate) li
187: .getIntersection(0).clone();
188: hasProper = true;
189: if (!isBoundaryPoint(li, bdyNodes))
190: hasProperInterior = true;
191: }
192: //if (li.isCollinear())
193: //hasCollinear = true;
194: }
195: }
196: }
197:
198: private boolean isBoundaryPoint(LineIntersector li,
199: Collection[] bdyNodes) {
200: if (bdyNodes == null)
201: return false;
202: if (isBoundaryPoint(li, bdyNodes[0]))
203: return true;
204: if (isBoundaryPoint(li, bdyNodes[1]))
205: return true;
206: return false;
207: }
208:
209: private boolean isBoundaryPoint(LineIntersector li,
210: Collection bdyNodes) {
211: for (Iterator i = bdyNodes.iterator(); i.hasNext();) {
212: Node node = (Node) i.next();
213: Coordinate pt = node.getCoordinate();
214: if (li.isIntersection(pt))
215: return true;
216: }
217: return false;
218: }
219:
220: }
|