Class HotPixel

1	/*
2	* Copyright (c) 2016 Vivid Solutions.
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
13	package org.locationtech.jts.noding.snapround;
14
15	import org.locationtech.jts.algorithm.LineIntersector;
16	import org.locationtech.jts.geom.Coordinate;
17	import org.locationtech.jts.geom.Envelope;
18	import org.locationtech.jts.noding.NodedSegmentString;
19	import org.locationtech.jts.util.Assert;
20
21	/**
22	* Implements a "hot pixel" as used in the Snap Rounding algorithm.
23	* A hot pixel contains the interior of the tolerance square and
24	* the boundary
25	* <b>minus</b> the top and right segments.
26	* <p>
27	* The hot pixel operations are all computed in the integer domain
28	* to avoid rounding problems.
29	*
30	* @version 1.7
31	*/
32	public class HotPixel
33	{
34	// testing only
35	// public static int nTests = 0;
36
37	private LineIntersector li;
38
39	private Coordinate pt;
40	private Coordinate originalPt;
41	private Coordinate ptScaled;
42
43	private Coordinate p0Scaled;
44	private Coordinate p1Scaled;
45
46	private double scaleFactor;
47
48	private double minx;
49	private double maxx;
50	private double miny;
51	private double maxy;
52
53	/**
54	* The corners of the hot pixel, in the order:
55	* 10
56	* 23
57	*/
58	private Coordinate[] corner = new Coordinate[4];
59
60	private Envelope safeEnv = null;
61
62	/**
63	* Creates a new hot pixel, using a given scale factor.
64	* The scale factor must be strictly positive (non-zero).
65	*
66	* @param pt the coordinate at the centre of the pixel
67	* @param scaleFactor the scaleFactor determining the pixel size. Must be > 0
68	* @param li the intersector to use for testing intersection with line segments
69	*
70	*/
71	public HotPixel(Coordinate pt, double scaleFactor, LineIntersector li) {
72	originalPt = pt;
73	this.pt = pt;
74	this.scaleFactor = scaleFactor;
75	this.li = li;
76	//tolerance = 0.5;
77	if (scaleFactor <= 0)
78	throw new IllegalArgumentException("Scale factor must be non-zero");
79	if (scaleFactor != 1.0) {
80	this.pt = new Coordinate(scale(pt.x), scale(pt.y));
81	p0Scaled = new Coordinate();
82	p1Scaled = new Coordinate();
83	}
84	initCorners(this.pt);
85	}
86
87	/**
88	* Gets the coordinate this hot pixel is based at.
89	*
90	* @return the coordinate of the pixel
91	*/
92	public Coordinate getCoordinate() { return originalPt; }
93
94	private static final double SAFE_ENV_EXPANSION_FACTOR = 0.75;
95
96	/**
97	* Returns a "safe" envelope that is guaranteed to contain the hot pixel.
98	* The envelope returned will be larger than the exact envelope of the
99	* pixel.
100	*
101	* @return an envelope which contains the hot pixel
102	*/
103	public Envelope getSafeEnvelope()
104	{
105	if (safeEnv == null) {
106	double safeTolerance = SAFE_ENV_EXPANSION_FACTOR / scaleFactor;
107	safeEnv = new Envelope(originalPt.x - safeTolerance,
108	originalPt.x + safeTolerance,
109	originalPt.y - safeTolerance,
110	originalPt.y + safeTolerance
111	);
112	}
113	return safeEnv;
114	}
115
116	private void initCorners(Coordinate pt)
117	{
118	double tolerance = 0.5;
119	minx = pt.x - tolerance;
120	maxx = pt.x + tolerance;
121	miny = pt.y - tolerance;
122	maxy = pt.y + tolerance;
123
124	corner[0] = new Coordinate(maxx, maxy);
125	corner[1] = new Coordinate(minx, maxy);
126	corner[2] = new Coordinate(minx, miny);
127	corner[3] = new Coordinate(maxx, miny);
128	}
129
130	private double scale(double val)
131	{
132	return (double) Math.round(val * scaleFactor);
133	}
134
135	/**
136	* Tests whether the line segment (p0-p1)
137	* intersects this hot pixel.
138	*
139	* @param p0 the first coordinate of the line segment to test
140	* @param p1 the second coordinate of the line segment to test
141	* @return true if the line segment intersects this hot pixel
142	*/
143	public boolean intersects(Coordinate p0, Coordinate p1)
144	{
145	if (scaleFactor == 1.0)
146	return intersectsScaled(p0, p1);
147
148	copyScaled(p0, p0Scaled);
149	copyScaled(p1, p1Scaled);
150	return intersectsScaled(p0Scaled, p1Scaled);
151	}
152
153	private void copyScaled(Coordinate p, Coordinate pScaled)
154	{
155	pScaled.x = scale(p.x);
156	pScaled.y = scale(p.y);
157	}
158
159	private boolean intersectsScaled(Coordinate p0, Coordinate p1)
160	{
161	double segMinx = Math.min(p0.x, p1.x);
162	double segMaxx = Math.max(p0.x, p1.x);
163	double segMiny = Math.min(p0.y, p1.y);
164	double segMaxy = Math.max(p0.y, p1.y);
165
166	boolean isOutsidePixelEnv = maxx < segMinx
167	\|\| minx > segMaxx
168	\|\| maxy < segMiny
169	\|\| miny > segMaxy;
170	if (isOutsidePixelEnv)
171	return false;
172	boolean intersects = intersectsToleranceSquare(p0, p1);
173	// boolean intersectsPixelClosure = intersectsPixelClosure(p0, p1);
174
175	// if (intersectsPixel != intersects) {
176	// Debug.println("Found hot pixel intersection mismatch at " + pt);
177	// Debug.println("Test segment: " + p0 + " " + p1);
178	// }
179
180	/*
181	if (scaleFactor != 1.0) {
182	boolean intersectsScaled = intersectsScaledTest(p0, p1);
183	if (intersectsScaled != intersects) {
184	intersectsScaledTest(p0, p1);
185	// Debug.println("Found hot pixel scaled intersection mismatch at " + pt);
186	// Debug.println("Test segment: " + p0 + " " + p1);
187	}
188	return intersectsScaled;
189	}
190	*/
191
192	Assert.isTrue(! (isOutsidePixelEnv && intersects), "Found bad envelope test");
193	// if (isOutsideEnv && intersects) {
194	// Debug.println("Found bad envelope test");
195	// }
196
197	return intersects;
198	//return intersectsPixelClosure;
199	}
200
201	/**
202	* Tests whether the segment p0-p1 intersects the hot pixel tolerance square.
203	* Because the tolerance square point set is partially open (along the
204	* top and right) the test needs to be more sophisticated than
205	* simply checking for any intersection.
206	* However, it can take advantage of the fact that the hot pixel edges
207	* do not lie on the coordinate grid.
208	* It is sufficient to check if any of the following occur:
209	* <ul>
210	* <li>a proper intersection between the segment and any hot pixel edge
211	* <li>an intersection between the segment and <b>both</b> the left and bottom hot pixel edges
212	* (which detects the case where the segment intersects the bottom left hot pixel corner)
213	* <li>an intersection between a segment endpoint and the hot pixel coordinate
214	* </ul>
215	*
216	* @param p0
217	* @param p1
218	* @return
219	*/
220	private boolean intersectsToleranceSquare(Coordinate p0, Coordinate p1)
221	{
222	boolean intersectsLeft = false;
223	boolean intersectsBottom = false;
224	//System.out.println("Hot Pixel: " + WKTWriter.toLineString(corner));
225	//System.out.println("Line: " + WKTWriter.toLineString(p0, p1));
226
227	li.computeIntersection(p0, p1, corner[0], corner[1]);
228	if (li.isProper()) return true;
229
230	li.computeIntersection(p0, p1, corner[1], corner[2]);
231	if (li.isProper()) return true;
232	if (li.hasIntersection()) intersectsLeft = true;
233
234	li.computeIntersection(p0, p1, corner[2], corner[3]);
235	if (li.isProper()) return true;
236	if (li.hasIntersection()) intersectsBottom = true;
237
238	li.computeIntersection(p0, p1, corner[3], corner[0]);
239	if (li.isProper()) return true;
240
241	if (intersectsLeft && intersectsBottom) return true;
242
243	if (p0.equals(pt)) return true;
244	if (p1.equals(pt)) return true;
245
246	return false;
247	}
248	/**
249	* Test whether the given segment intersects
250	* the closure of this hot pixel.
251	* This is NOT the test used in the standard snap-rounding
252	* algorithm, which uses the partially closed tolerance square
253	* instead.
254	* This routine is provided for testing purposes only.
255	*
256	* @param p0 the start point of a line segment
257	* @param p1 the end point of a line segment
258	* @return <code>true</code> if the segment intersects the closure of the pixel's tolerance square
259	*/
260	private boolean intersectsPixelClosure(Coordinate p0, Coordinate p1)
261	{
262	li.computeIntersection(p0, p1, corner[0], corner[1]);
263	if (li.hasIntersection()) return true;
264	li.computeIntersection(p0, p1, corner[1], corner[2]);
265	if (li.hasIntersection()) return true;
266	li.computeIntersection(p0, p1, corner[2], corner[3]);
267	if (li.hasIntersection()) return true;
268	li.computeIntersection(p0, p1, corner[3], corner[0]);
269	if (li.hasIntersection()) return true;
270
271	return false;
272	}
273
274	/**
275	* Adds a new node (equal to the snap pt) to the specified segment
276	* if the segment passes through the hot pixel
277	*
278	* @param segStr
279	* @param segIndex
280	* @return true if a node was added to the segment
281	*/
282	public boolean addSnappedNode(
283	NodedSegmentString segStr,
284	int segIndex
285	)
286	{
287	Coordinate p0 = segStr.getCoordinate(segIndex);
288	Coordinate p1 = segStr.getCoordinate(segIndex + 1);
289
290	if (intersects(p0, p1)) {
291	//System.out.println("snapped: " + snapPt);
292	//System.out.println("POINT (" + snapPt.x + " " + snapPt.y + ")");
293	segStr.addIntersection(getCoordinate(), segIndex);
294
295	return true;
296	}
297	return false;
298	}
299
300	}
301