Class SimpleSweepLineIntersector

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.geom.Coordinate;
26	import org.locationtech.jts.geomgraph.Edge;
27
28	/**
29	* Finds all intersections in one or two sets of edges,
30	* using a simple x-axis sweepline algorithm.
31	* While still O(n^2) in the worst case, this algorithm
32	* drastically improves the average-case time.
33	*
34	* @version 1.7
35	*/
36	public class SimpleSweepLineIntersector
37	extends EdgeSetIntersector
38	{
39
40	List events = new ArrayList();
41	// statistics information
42	int nOverlaps;
43
44	public SimpleSweepLineIntersector() {
45	}
46
47	public void computeIntersections(List edges, SegmentIntersector si, boolean testAllSegments)
48	{
49	if (testAllSegments)
50	add(edges, null);
51	else
52	add(edges);
53	computeIntersections(si);
54	}
55
56	public void computeIntersections(List edges0, List edges1, SegmentIntersector si)
57	{
58	add(edges0, edges0);
59	add(edges1, edges1);
60	computeIntersections(si);
61	}
62
63	private void add(List edges)
64	{
65	for (Iterator i = edges.iterator(); i.hasNext(); ) {
66	Edge edge = (Edge) i.next();
67	// edge is its own group
68	add(edge, edge);
69	}
70	}
71	private void add(List edges, Object edgeSet)
72	{
73	for (Iterator i = edges.iterator(); i.hasNext(); ) {
74	Edge edge = (Edge) i.next();
75	add(edge, edgeSet);
76	}
77	}
78
79
80	private void add(Edge edge, Object edgeSet)
81	{
82	Coordinate[] pts = edge.getCoordinates();
83	for (int i = 0; i < pts.length - 1; i++) {
84	SweepLineSegment ss = new SweepLineSegment(edge, i);
85	SweepLineEvent insertEvent = new SweepLineEvent(edgeSet, ss.getMinX(), null);
86	events.add(insertEvent);
87	events.add(new SweepLineEvent(ss.getMaxX(), insertEvent));
88	}
89	}
90
91	/**
92	* Because DELETE events have a link to their corresponding INSERT event,
93	* it is possible to compute exactly the range of events which must be
94	* compared to a given INSERT event object.
95	*/
96	private void prepareEvents()
97	{
98	Collections.sort(events);
99	// set DELETE event indexes
100	for (int i = 0; i < events.size(); i++ )
101	{
102	SweepLineEvent ev = (SweepLineEvent) events.get(i);
103	if (ev.isDelete()) {
104	ev.getInsertEvent().setDeleteEventIndex(i);
105	}
106	}
107	}
108
109	private void computeIntersections(SegmentIntersector si)
110	{
111	nOverlaps = 0;
112	prepareEvents();
113
114	for (int i = 0; i < events.size(); i++ )
115	{
116	SweepLineEvent ev = (SweepLineEvent) events.get(i);
117	if (ev.isInsert()) {
118	processOverlaps(i, ev.getDeleteEventIndex(), ev, si);
119	}
120	}
121	}
122
123	private void processOverlaps(int start, int end, SweepLineEvent ev0, SegmentIntersector si)
124	{
125	SweepLineSegment ss0 = (SweepLineSegment) ev0.getObject();
126	/**
127	* Since we might need to test for self-intersections,
128	* include current INSERT event object in list of event objects to test.
129	* Last index can be skipped, because it must be a Delete event.
130	*/
131	for (int i = start; i < end; i++ ) {
132	SweepLineEvent ev1 = (SweepLineEvent) events.get(i);
133	if (ev1.isInsert()) {
134	SweepLineSegment ss1 = (SweepLineSegment) ev1.getObject();
135	// don't compare edges in same group, if labels are present
136	if (! ev0.isSameLabel(ev1)) {
137	ss0.computeIntersections(ss1, si);
138	nOverlaps++;
139	}
140	}
141	}
142
143	}
144	}
145