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