Class Vertex

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.triangulate.quadedge;
14
15
16	import org.locationtech.jts.algorithm.HCoordinate;
17	import org.locationtech.jts.algorithm.NotRepresentableException;
18	import org.locationtech.jts.geom.Coordinate;
19
20	/**
21	* Models a site (node) in a {@link QuadEdgeSubdivision}.
22	* The sites can be points on a line string representing a
23	* linear site.
24	* <p>
25	* The vertex can be considered as a vector with a norm, length, inner product, cross
26	* product, etc. Additionally, point relations (e.g., is a point to the left of a line, the circle
27	* defined by this point and two others, etc.) are also defined in this class.
28	* <p>
29	* It is common to want to attach user-defined data to
30	* the vertices of a subdivision.
31	* One way to do this is to subclass <tt>Vertex</tt>
32	* to carry any desired information.
33	*
34	* @author David Skea
35	* @author Martin Davis
36	*/
37	public class Vertex
38	{
39	public static final int LEFT = 0;
40	public static final int RIGHT = 1;
41	public static final int BEYOND = 2;
42	public static final int BEHIND = 3;
43	public static final int BETWEEN = 4;
44	public static final int ORIGIN = 5;
45	public static final int DESTINATION = 6;
46
47	private Coordinate p;
48	// private int edgeNumber = -1;
49
50	public Vertex(double _x, double _y) {
51	p = new Coordinate(_x, _y);
52	}
53
54	public Vertex(double _x, double _y, double _z) {
55	p = new Coordinate(_x, _y, _z);
56	}
57
58	public Vertex(Coordinate _p) {
59	p = new Coordinate(_p);
60	}
61
62	public double getX() {
63	return p.x;
64	}
65
66	public double getY() {
67	return p.y;
68	}
69
70	public double getZ() {
71	return p.getZ();
72	}
73
74	public void setZ(double _z) {
75	p.setZ(_z);
76	}
77
78	public Coordinate getCoordinate() {
79	return p;
80	}
81
82	public String toString() {
83	return "POINT (" + p.x + " " + p.y + ")";
84	}
85
86	public boolean equals(Vertex _x) {
87	if (p.x == _x.getX() && p.y == _x.getY()) {
88	return true;
89	} else {
90	return false;
91	}
92	}
93
94	public boolean equals(Vertex _x, double tolerance) {
95	if (p.distance(_x.getCoordinate()) < tolerance) {
96	return true;
97	} else {
98	return false;
99	}
100	}
101
102	public int classify(Vertex p0, Vertex p1) {
103	Vertex p2 = this;
104	Vertex a = p1.sub(p0);
105	Vertex b = p2.sub(p0);
106	double sa = a.crossProduct(b);
107	if (sa > 0.0)
108	return LEFT;
109	if (sa < 0.0)
110	return RIGHT;
111	if ((a.getX() * b.getX() < 0.0) \|\| (a.getY() * b.getY() < 0.0))
112	return BEHIND;
113	if (a.magn() < b.magn())
114	return BEYOND;
115	if (p0.equals(p2))
116	return ORIGIN;
117	if (p1.equals(p2))
118	return DESTINATION;
119	return BETWEEN;
120	}
121
122	/**
123	* Computes the cross product k = u X v.
124	*
125	* @param v a vertex
126	* @return returns the magnitude of u X v
127	*/
128	double crossProduct(Vertex v) {
129	return (p.x * v.getY() - p.y * v.getX());
130	}
131
132	/**
133	* Computes the inner or dot product
134	*
135	* @param v a vertex
136	* @return returns the dot product u.v
137	*/
138	double dot(Vertex v) {
139	return (p.x * v.getX() + p.y * v.getY());
140	}
141
142	/**
143	* Computes the scalar product c(v)
144	*
145	* @param v a vertex
146	* @return returns the scaled vector
147	*/
148	Vertex times(double c) {
149	return (new Vertex(c * p.x, c * p.y));
150	}
151
152	/* Vector addition */
153	Vertex sum(Vertex v) {
154	return (new Vertex(p.x + v.getX(), p.y + v.getY()));
155	}
156
157	/* and subtraction */
158	Vertex sub(Vertex v) {
159	return (new Vertex(p.x - v.getX(), p.y - v.getY()));
160	}
161
162	/* magnitude of vector */
163	double magn() {
164	return (Math.sqrt(p.x * p.x + p.y * p.y));
165	}
166
167	/* returns k X v (cross product). this is a vector perpendicular to v */
168	Vertex cross() {
169	return (new Vertex(p.y, -p.x));
170	}
171
172	/ *********************************************************** */
173	/***********************************************************************************************
174	* Geometric primitives /
175	**********************************************************************************************/
176
177	/**
178	* Tests if the vertex is inside the circle defined by
179	* the triangle with vertices a, b, c (oriented counter-clockwise).
180	*
181	* @param a a vertex of the triangle
182	* @param b a vertex of the triangle
183	* @param c a vertex of the triangle
184	* @return true if this vertex is in the circumcircle of (a,b,c)
185	*/
186	public boolean isInCircle(Vertex a, Vertex b, Vertex c)
187	{
188	return TrianglePredicate.isInCircleRobust(a.p, b.p, c.p, this.p);
189	// non-robust - best to not use
190	//return TrianglePredicate.isInCircle(a.p, b.p, c.p, this.p);
191	}
192
193	/**
194	* Tests whether the triangle formed by this vertex and two
195	* other vertices is in CCW orientation.
196	*
197	* @param b a vertex
198	* @param c a vertex
199	* @return true if the triangle is oriented CCW
200	*/
201	public final boolean isCCW(Vertex b, Vertex c)
202	{
203	/*
204	// test code used to check for robustness of triArea
205	boolean isCCW = (b.p.x - p.x) * (c.p.y - p.y)
206	- (b.p.y - p.y) * (c.p.x - p.x) > 0;
207	//boolean isCCW = triArea(this, b, c) > 0;
208	boolean isCCWRobust = CGAlgorithms.orientationIndex(p, b.p, c.p) == CGAlgorithms.COUNTERCLOCKWISE;
209	if (isCCWRobust != isCCW)
210	System.out.println("CCW failure");
211	//*/
212
213	// is equal to the signed area of the triangle
214
215	return (b.p.x - p.x) * (c.p.y - p.y)
216	- (b.p.y - p.y) * (c.p.x - p.x) > 0;
217
218	// original rolled code
219	//boolean isCCW = triArea(this, b, c) > 0;
220	//return isCCW;
221
222	}
223
224	public final boolean rightOf(QuadEdge e) {
225	return isCCW(e.dest(), e.orig());
226	}
227
228	public final boolean leftOf(QuadEdge e) {
229	return isCCW(e.orig(), e.dest());
230	}
231
232	private HCoordinate bisector(Vertex a, Vertex b) {
233	// returns the perpendicular bisector of the line segment ab
234	double dx = b.getX() - a.getX();
235	double dy = b.getY() - a.getY();
236	HCoordinate l1 = new HCoordinate(a.getX() + dx / 2.0, a.getY() + dy / 2.0, 1.0);
237	HCoordinate l2 = new HCoordinate(a.getX() - dy + dx / 2.0, a.getY() + dx + dy / 2.0, 1.0);
238	return new HCoordinate(l1, l2);
239	}
240
241	private double distance(Vertex v1, Vertex v2) {
242	return Math.sqrt(Math.pow(v2.getX() - v1.getX(), 2.0)
243	+ Math.pow(v2.getY() - v1.getY(), 2.0));
244	}
245
246	/**
247	* Computes the value of the ratio of the circumradius to shortest edge. If smaller than some
248	* given tolerance B, the associated triangle is considered skinny. For an equal lateral
249	* triangle this value is 0.57735. The ratio is related to the minimum triangle angle theta by:
250	* circumRadius/shortestEdge = 1/(2sin(theta)).
251	*
252	* @param b second vertex of the triangle
253	* @param c third vertex of the triangle
254	* @return ratio of circumradius to shortest edge.
255	*/
256	public double circumRadiusRatio(Vertex b, Vertex c) {
257	Vertex x = this.circleCenter(b, c);
258	double radius = distance(x, b);
259	double edgeLength = distance(this, b);
260	double el = distance(b, c);
261	if (el < edgeLength) {
262	edgeLength = el;
263	}
264	el = distance(c, this);
265	if (el < edgeLength) {
266	edgeLength = el;
267	}
268	return radius / edgeLength;
269	}
270
271	/**
272	* returns a new vertex that is mid-way between this vertex and another end point.
273	*
274	* @param a the other end point.
275	* @return the point mid-way between this and that.
276	*/
277	public Vertex midPoint(Vertex a) {
278	double xm = (p.x + a.getX()) / 2.0;
279	double ym = (p.y + a.getY()) / 2.0;
280	double zm = (p.getZ() + a.getZ()) / 2.0;
281	return new Vertex(xm, ym, zm);
282	}
283
284	/**
285	* Computes the centre of the circumcircle of this vertex and two others.
286	*
287	* @param b
288	* @param c
289	* @return the Coordinate which is the circumcircle of the 3 points.
290	*/
291	public Vertex circleCenter(Vertex b, Vertex c) {
292	Vertex a = new Vertex(this.getX(), this.getY());
293	// compute the perpendicular bisector of cord ab
294	HCoordinate cab = bisector(a, b);
295	// compute the perpendicular bisector of cord bc
296	HCoordinate cbc = bisector(b, c);
297	// compute the intersection of the bisectors (circle radii)
298	HCoordinate hcc = new HCoordinate(cab, cbc);
299	Vertex cc = null;
300	try {
301	cc = new Vertex(hcc.getX(), hcc.getY());
302	} catch (NotRepresentableException nre) {
303	System.err.println("a: " + a + " b: " + b + " c: " + c);
304	System.err.println(nre);
305	}
306	return cc;
307	}
308
309	/**
310	* For this vertex enclosed in a triangle defined by three vertices v0, v1 and v2, interpolate
311	* a z value from the surrounding vertices.
312	*/
313	public double interpolateZValue(Vertex v0, Vertex v1, Vertex v2) {
314	double x0 = v0.getX();
315	double y0 = v0.getY();
316	double a = v1.getX() - x0;
317	double b = v2.getX() - x0;
318	double c = v1.getY() - y0;
319	double d = v2.getY() - y0;
320	double det = a * d - b * c;
321	double dx = this.getX() - x0;
322	double dy = this.getY() - y0;
323	double t = (d * dx - b * dy) / det;
324	double u = (-c * dx + a * dy) / det;
325	double z = v0.getZ() + t * (v1.getZ() - v0.getZ()) + u * (v2.getZ() - v0.getZ());
326	return z;
327	}
328
329	/**
330	* Interpolates the Z-value (height) of a point enclosed in a triangle
331	* whose vertices all have Z values.
332	* The containing triangle must not be degenerate
333	* (in other words, the three vertices must enclose a
334	* non-zero area).
335	*
336	* @param p the point to interpolate the Z value of
337	* @param v0 a vertex of a triangle containing the p
338	* @param v1 a vertex of a triangle containing the p
339	* @param v2 a vertex of a triangle containing the p
340	* @return the interpolated Z-value (height) of the point
341	*/
342	public static double interpolateZ(Coordinate p, Coordinate v0, Coordinate v1, Coordinate v2) {
343	double x0 = v0.x;
344	double y0 = v0.y;
345	double a = v1.x - x0;
346	double b = v2.x - x0;
347	double c = v1.y - y0;
348	double d = v2.y - y0;
349	double det = a * d - b * c;
350	double dx = p.x - x0;
351	double dy = p.y - y0;
352	double t = (d * dx - b * dy) / det;
353	double u = (-c * dx + a * dy) / det;
354	double z = v0.getZ() + t * (v1.getZ() - v0.getZ()) + u * (v2.getZ() - v0.getZ());
355	return z;
356	}
357
358	/**
359	* Computes the interpolated Z-value for a point p lying on the segment p0-p1
360	*
361	* @param p
362	* @param p0
363	* @param p1
364	* @return the interpolated Z value
365	*/
366	public static double interpolateZ(Coordinate p, Coordinate p0, Coordinate p1) {
367	double segLen = p0.distance(p1);
368	double ptLen = p.distance(p0);
369	double dz = p1.getZ() - p0.getZ();
370	double pz = p0.getZ() + dz * (ptLen / segLen);
371	return pz;
372	}
373
374
375
376
377
378
379
380	}
381