Class SimpleMCSweepLineIntersector

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	*/
49	public SimpleMCSweepLineIntersector() {
50	}
51
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
61	public void computeIntersections(List edges0, List edges1, SegmentIntersector si)
62	{
63	addEdges(edges0, edges0);
64	addEdges(edges1, edges1);
65	computeIntersections(si);
66	}
67
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	}
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
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	*/
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
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
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