Class HoleAssigner

1	/*
2	* Copyright (c) 2019 Martin Davis.
3	*
4	* All rights reserved. This program and the accompanying materials
5	* are made available under the terms of the Eclipse Public License 2.0
6	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
7	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
8	* and the Eclipse Distribution License is available at
9	*
10	* http://www.eclipse.org/org/documents/edl-v10.php.
11	*/
12	package org.locationtech.jts.operation.polygonize;
13
14	import java.util.Iterator;
15	import java.util.List;
16
17	import org.locationtech.jts.geom.Envelope;
18	import org.locationtech.jts.index.SpatialIndex;
19	import org.locationtech.jts.index.strtree.STRtree;
20
21	/**
22	* Assigns hole rings to shell rings
23	* during polygonization.
24	* Uses spatial indexing to improve performance
25	* of shell lookup.
26	*
27	* @author mdavis
28	*
29	*/
30	public class HoleAssigner
31	{
32	/**
33	* Assigns hole rings to shell rings.
34	*
35	* @param holes list of hole rings to assign
36	* @param shells list of shell rings
37	*/
38	public static void assignHolesToShells(List holes, List shells) {
39	HoleAssigner assigner = new HoleAssigner(shells);
40	assigner.assignHolesToShells(holes);
41	}
42
43	private List<EdgeRing> shells;
44	private SpatialIndex shellIndex;
45
46	/**
47	* Creates a new hole assigner.
48	*
49	* @param shells the shells to be assigned to
50	*/
51	public HoleAssigner(List<EdgeRing> shells) {
52	this.shells = shells;
53	buildIndex();
54	}
55
56	private void buildIndex() {
57	shellIndex = new STRtree();
58	for (EdgeRing shell : shells) {
59	shellIndex.insert(shell.getRing().getEnvelopeInternal(), shell);
60	}
61	}
62
63	/**
64	* Assigns holes to the shells.
65	*
66	* @param holeList list of hole rings to assign
67	*/
68	public void assignHolesToShells(List<EdgeRing> holeList)
69	{
70	for (Iterator i = holeList.iterator(); i.hasNext(); ) {
71	EdgeRing holeER = (EdgeRing) i.next();
72	assignHoleToShell(holeER);
73	}
74	}
75
76	private void assignHoleToShell(EdgeRing holeER)
77	{
78	EdgeRing shell = findShellContaining(holeER);
79	if (shell != null) {
80	shell.addHole(holeER);
81	}
82	}
83
84	private List<EdgeRing> queryOverlappingShells(Envelope ringEnv) {
85	return (List<EdgeRing>) shellIndex.query(ringEnv);
86	}
87
88	/**
89	* Find the innermost enclosing shell EdgeRing containing the argument EdgeRing, if any.
90	* The innermost enclosing ring is the <i>smallest</i> enclosing ring.
91	* The algorithm used depends on the fact that:
92	* <br>
93	* ring A contains ring B iff envelope(ring A) contains envelope(ring B)
94	* <br>
95	* This routine is only safe to use if the chosen point of the hole
96	* is known to be properly contained in a shell
97	* (which is guaranteed to be the case if the hole does not touch its shell)
98	*
99	* @return containing shell EdgeRing, if there is one
100	* or null if no containing EdgeRing is found
101	*/
102	private EdgeRing findShellContaining(EdgeRing testEr)
103	{
104	Envelope testEnv = testEr.getRing().getEnvelopeInternal();
105	List<EdgeRing> candidateShells = queryOverlappingShells(testEnv);
106	return EdgeRing.findEdgeRingContaining(testEr, candidateShells);
107	}
108	}
109