Class SweepLineIndex

1
2
3	/*
4	* Copyright (c) 2016 Vivid Solutions.
5	*
6	* All rights reserved. This program and the accompanying materials
7	* are made available under the terms of the Eclipse Public License 2.0
8	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
9	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
10	* and the Eclipse Distribution License is available at
11	*
12	* http://www.eclipse.org/org/documents/edl-v10.php.
13	*/
14	package org.locationtech.jts.index.sweepline;
15
16	import java.util.ArrayList;
17	import java.util.Collections;
18	import java.util.List;
19
20	/**
21	* A sweepline implements a sorted index on a set of intervals.
22	* It is used to compute all overlaps between the interval in the index.
23	*
24	* @version 1.7
25	*/
26	public class SweepLineIndex {
27
28	List events = new ArrayList();
29	private boolean indexBuilt;
30	// statistics information
31	private int nOverlaps;
32
33	public SweepLineIndex() {
34	}
35
36	public void add(SweepLineInterval sweepInt)
37	{
38	SweepLineEvent insertEvent = new SweepLineEvent(sweepInt.getMin(), null, sweepInt);
39	events.add(insertEvent);
40	events.add(new SweepLineEvent(sweepInt.getMax(), insertEvent, sweepInt));
41	}
42
43	/**
44	* Because Delete Events have a link to their corresponding Insert event,
45	* it is possible to compute exactly the range of events which must be
46	* compared to a given Insert event object.
47	*/
48	private void buildIndex()
49	{
50	if (indexBuilt) return;
51	Collections.sort(events);
52	for (int i = 0; i < events.size(); i++ )
53	{
54	SweepLineEvent ev = (SweepLineEvent) events.get(i);
55	if (ev.isDelete()) {
56	ev.getInsertEvent().setDeleteEventIndex(i);
57	}
58	}
59	indexBuilt = true;
60	}
61
62	public void computeOverlaps(SweepLineOverlapAction action)
63	{
64	nOverlaps = 0;
65	buildIndex();
66
67	for (int i = 0; i < events.size(); i++ )
68	{
69	SweepLineEvent ev = (SweepLineEvent) events.get(i);
70	if (ev.isInsert()) {
71	processOverlaps(i, ev.getDeleteEventIndex(), ev.getInterval(), action);
72	}
73	}
74	}
75
76	private void processOverlaps(int start, int end, SweepLineInterval s0, SweepLineOverlapAction action)
77	{
78	/**
79	* Since we might need to test for self-intersections,
80	* include current insert event object in list of event objects to test.
81	* Last index can be skipped, because it must be a Delete event.
82	*/
83	for (int i = start; i < end; i++ ) {
84	SweepLineEvent ev = (SweepLineEvent) events.get(i);
85	if (ev.isInsert()) {
86	SweepLineInterval s1 = ev.getInterval();
87	action.overlap(s0, s1);
88	nOverlaps++;
89	}
90	}
91
92	}
93
94
95	}
96