Class BoundablePair

1	/*
2	* Copyright (c) 2016 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.index.strtree;
13
14	import java.util.Iterator;
15	import java.util.List;
16	import java.util.PriorityQueue;
17
18	import org.locationtech.jts.geom.Envelope;
19
20
21	/**
22	* A pair of {@link Boundable}s, whose leaf items
23	* support a distance metric between them.
24	* Used to compute the distance between the members,
25	* and to expand a member relative to the other
26	* in order to produce new branches of the
27	* Branch-and-Bound evaluation tree.
28	* Provides an ordering based on the distance between the members,
29	* which allows building a priority queue by minimum distance.
30	*
31	* @author Martin Davis
32	*
33	*/
34	class BoundablePair
35	implements Comparable
36	{
37	private Boundable boundable1;
38	private Boundable boundable2;
39	private double distance;
40	private ItemDistance itemDistance;
41	//private double maxDistance = -1.0;
42
43	public BoundablePair(Boundable boundable1, Boundable boundable2, ItemDistance itemDistance)
44	{
45	this.boundable1 = boundable1;
46	this.boundable2 = boundable2;
47	this.itemDistance = itemDistance;
48	distance = distance();
49	}
50
51	/**
52	* Gets one of the member {@link Boundable}s in the pair
53	* (indexed by [0, 1]).
54	*
55	* @param i the index of the member to return (0 or 1)
56	* @return the chosen member
57	*/
58	public Boundable getBoundable(int i)
59	{
60	if (i == 0) return boundable1;
61	return boundable2;
62	}
63
64	/**
65	* Computes the maximum distance between any
66	* two items in the pair of nodes.
67	*
68	* @return the maximum distance between items in the pair
69	*/
70	public double maximumDistance()
71	{
72	return EnvelopeDistance.maximumDistance(
73	(Envelope) boundable1.getBounds(),
74	(Envelope) boundable2.getBounds());
75	}
76
77	/**
78	* Computes the distance between the {@link Boundable}s in this pair.
79	* The boundables are either composites or leaves.
80	* If either is composite, the distance is computed as the minimum distance
81	* between the bounds.
82	* If both are leaves, the distance is computed by {@link #itemDistance(ItemBoundable, ItemBoundable)}.
83	*
84	* @return
85	*/
86	private double distance()
87	{
88	// if items, compute exact distance
89	if (isLeaves()) {
90	return itemDistance.distance((ItemBoundable) boundable1,
91	(ItemBoundable) boundable2);
92	}
93	// otherwise compute distance between bounds of boundables
94	return ((Envelope) boundable1.getBounds()).distance(
95	((Envelope) boundable2.getBounds()));
96	}
97
98	/**
99	* Gets the minimum possible distance between the Boundables in
100	* this pair.
101	* If the members are both items, this will be the
102	* exact distance between them.
103	* Otherwise, this distance will be a lower bound on
104	* the distances between the items in the members.
105	*
106	* @return the exact or lower bound distance for this pair
107	*/
108	public double getDistance() { return distance; }
109
110	/**
111	* Compares two pairs based on their minimum distances
112	*/
113	public int compareTo(Object o)
114	{
115	BoundablePair nd = (BoundablePair) o;
116	if (distance < nd.distance) return -1;
117	if (distance > nd.distance) return 1;
118	return 0;
119	}
120
121	/**
122	* Tests if both elements of the pair are leaf nodes
123	*
124	* @return true if both pair elements are leaf nodes
125	*/
126	public boolean isLeaves()
127	{
128	return ! (isComposite(boundable1) \|\| isComposite(boundable2));
129	}
130
131	public static boolean isComposite(Object item)
132	{
133	return (item instanceof AbstractNode);
134	}
135
136	private static double area(Boundable b)
137	{
138	return ((Envelope) b.getBounds()).getArea();
139	}
140
141	/**
142	* For a pair which is not a leaf
143	* (i.e. has at least one composite boundable)
144	* computes a list of new pairs
145	* from the expansion of the larger boundable
146	* with distance less than minDistance
147	* and adds them to a priority queue.
148	* <p>
149	* Note that expanded pairs may contain
150	* the same item/node on both sides.
151	* This must be allowed to support distance
152	* functions which have non-zero distances
153	* between the item and itself (non-zero reflexive distance).
154	*
155	* @param priQ the priority queue to add the new pairs to
156	* @param minDistance the limit on the distance between added pairs
157	*
158	*/
159	public void expandToQueue(PriorityQueue priQ, double minDistance)
160	{
161	boolean isComp1 = isComposite(boundable1);
162	boolean isComp2 = isComposite(boundable2);
163
164	/**
165	* HEURISTIC: If both boundable are composite,
166	* choose the one with largest area to expand.
167	* Otherwise, simply expand whichever is composite.
168	*/
169	if (isComp1 && isComp2) {
170	if (area(boundable1) > area(boundable2)) {
171	expand(boundable1, boundable2, false, priQ, minDistance);
172	return;
173	}
174	else {
175	expand(boundable2, boundable1, true, priQ, minDistance);
176	return;
177	}
178	}
179	else if (isComp1) {
180	expand(boundable1, boundable2, false, priQ, minDistance);
181	return;
182	}
183	else if (isComp2) {
184	expand(boundable2, boundable1, true, priQ, minDistance);
185	return;
186	}
187
188	throw new IllegalArgumentException("neither boundable is composite");
189	}
190
191	private void expand(Boundable bndComposite, Boundable bndOther, boolean isFlipped,
192	PriorityQueue priQ, double minDistance)
193	{
194	List children = ((AbstractNode) bndComposite).getChildBoundables();
195	for (Iterator i = children.iterator(); i.hasNext(); ) {
196	Boundable child = (Boundable) i.next();
197	BoundablePair bp;
198	if (isFlipped) {
199	bp = new BoundablePair(bndOther, child, itemDistance);
200	}
201	else {
202	bp = new BoundablePair(child, bndOther, itemDistance);
203	}
204	// only add to queue if this pair might contain the closest points
205	// MD - it's actually faster to construct the object rather than called distance(child, bndOther)!
206	if (bp.getDistance() < minDistance) {
207	priQ.add(bp);
208	}
209	}
210	}
211	}
212