1 2 3 4 /* 5 * Copyright (c) 2016 Vivid Solutions. 6 * 7 * All rights reserved. This program and the accompanying materials 8 * are made available under the terms of the Eclipse Public License 2.0 9 * and Eclipse Distribution License v. 1.0 which accompanies this distribution. 10 * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html 11 * and the Eclipse Distribution License is available at 12 * 13 * http://www.eclipse.org/org/documents/edl-v10.php. 14 */ 15 package org.locationtech.jts.geomgraph.index; 16 17 /** 18 * @version 1.7 19 */ 20 import java.util.ArrayList; 21 import java.util.Collections; 22 import java.util.Iterator; 23 import java.util.List; 24 25 import org.locationtech.jts.geomgraph.Edge; 26 27 /** 28 * Finds all intersections in one or two sets of edges, 29 * using an x-axis sweepline algorithm in conjunction with Monotone Chains. 30 * While still O(n^2) in the worst case, this algorithm 31 * drastically improves the average-case time. 32 * The use of MonotoneChains as the items in the index 33 * seems to offer an improvement in performance over a sweep-line alone. 34 * 35 * @version 1.7 36 */ 37 public class SimpleMCSweepLineIntersector 38 extends EdgeSetIntersector 39 { 40 41 List events = new ArrayList(); 42 // statistics information 43 int nOverlaps; 44 45 /** 46 * A SimpleMCSweepLineIntersector creates monotone chains from the edges 47 * and compares them using a simple sweep-line along the x-axis. 48 */ SimpleMCSweepLineIntersector()49 public SimpleMCSweepLineIntersector() { 50 } 51 computeIntersections(List edges, SegmentIntersector si, boolean testAllSegments)52 public void computeIntersections(List edges, SegmentIntersector si, boolean testAllSegments) 53 { 54 if (testAllSegments) 55 addEdges(edges, null); 56 else 57 addEdges(edges); 58 computeIntersections(si); 59 } 60 computeIntersections(List edges0, List edges1, SegmentIntersector si)61 public void computeIntersections(List edges0, List edges1, SegmentIntersector si) 62 { 63 addEdges(edges0, edges0); 64 addEdges(edges1, edges1); 65 computeIntersections(si); 66 } 67 addEdges(List edges)68 private void addEdges(List edges) 69 { 70 for (Iterator i = edges.iterator(); i.hasNext(); ) { 71 Edge edge = (Edge) i.next(); 72 // edge is its own group 73 addEdge(edge, edge); 74 } 75 } addEdges(List edges, Object edgeSet)76 private void addEdges(List edges, Object edgeSet) 77 { 78 for (Iterator i = edges.iterator(); i.hasNext(); ) { 79 Edge edge = (Edge) i.next(); 80 addEdge(edge, edgeSet); 81 } 82 } 83 addEdge(Edge edge, Object edgeSet)84 private void addEdge(Edge edge, Object edgeSet) 85 { 86 MonotoneChainEdge mce = edge.getMonotoneChainEdge(); 87 int[] startIndex = mce.getStartIndexes(); 88 for (int i = 0; i < startIndex.length - 1; i++) { 89 MonotoneChain mc = new MonotoneChain(mce, i); 90 SweepLineEvent insertEvent = new SweepLineEvent(edgeSet, mce.getMinX(i), mc); 91 events.add(insertEvent); 92 events.add(new SweepLineEvent(mce.getMaxX(i), insertEvent)); 93 } 94 } 95 96 /** 97 * Because Delete Events have a link to their corresponding Insert event, 98 * it is possible to compute exactly the range of events which must be 99 * compared to a given Insert event object. 100 */ prepareEvents()101 private void prepareEvents() 102 { 103 Collections.sort(events); 104 // set DELETE event indexes 105 for (int i = 0; i < events.size(); i++ ) 106 { 107 SweepLineEvent ev = (SweepLineEvent) events.get(i); 108 if (ev.isDelete()) { 109 ev.getInsertEvent().setDeleteEventIndex(i); 110 } 111 } 112 } 113 computeIntersections(SegmentIntersector si)114 private void computeIntersections(SegmentIntersector si) 115 { 116 nOverlaps = 0; 117 prepareEvents(); 118 119 for (int i = 0; i < events.size(); i++ ) 120 { 121 SweepLineEvent ev = (SweepLineEvent) events.get(i); 122 if (ev.isInsert()) { 123 processOverlaps(i, ev.getDeleteEventIndex(), ev, si); 124 } 125 if (si.isDone()) { 126 break; 127 } 128 } 129 } 130 processOverlaps(int start, int end, SweepLineEvent ev0, SegmentIntersector si)131 private void processOverlaps(int start, int end, SweepLineEvent ev0, SegmentIntersector si) 132 { 133 MonotoneChain mc0 = (MonotoneChain) ev0.getObject(); 134 /** 135 * Since we might need to test for self-intersections, 136 * include current INSERT event object in list of event objects to test. 137 * Last index can be skipped, because it must be a Delete event. 138 */ 139 for (int i = start; i < end; i++ ) { 140 SweepLineEvent ev1 = (SweepLineEvent) events.get(i); 141 if (ev1.isInsert()) { 142 MonotoneChain mc1 = (MonotoneChain) ev1.getObject(); 143 // don't compare edges in same group, if labels are present 144 if (! ev0.isSameLabel(ev1)) { 145 mc0.computeIntersections(mc1, si); 146 nOverlaps++; 147 } 148 } 149 } 150 } 151 } 152