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