/src/geos/include/geos/triangulate/quadedge/Vertex.h
Line | Count | Source |
1 | | /********************************************************************** |
2 | | * |
3 | | * GEOS - Geometry Engine Open Source |
4 | | * http://geos.osgeo.org |
5 | | * |
6 | | * Copyright (C) 2012 Excensus LLC. |
7 | | * |
8 | | * This is free software; you can redistribute and/or modify it under |
9 | | * the terms of the GNU Lesser General Licence as published |
10 | | * by the Free Software Foundation. |
11 | | * See the COPYING file for more information. |
12 | | * |
13 | | ********************************************************************** |
14 | | * |
15 | | * Last port: triangulate/quadedge/Vertex.java r705 |
16 | | * |
17 | | **********************************************************************/ |
18 | | |
19 | | #pragma once |
20 | | |
21 | | #include <cmath> |
22 | | #include <memory> |
23 | | #include <cstring> |
24 | | |
25 | | #include <geos/geom/Coordinate.h> |
26 | | #include <geos/algorithm/HCoordinate.h> |
27 | | #include <geos/triangulate/quadedge/TrianglePredicate.h> |
28 | | |
29 | | |
30 | | //fwd declarations |
31 | | namespace geos { |
32 | | namespace triangulate { |
33 | | namespace quadedge { |
34 | | class QuadEdge; |
35 | | } |
36 | | } |
37 | | } |
38 | | |
39 | | namespace geos { |
40 | | namespace triangulate { //geos.triangulate |
41 | | namespace quadedge { //geos.triangulate.quadedge |
42 | | |
43 | | /** \brief |
44 | | * Models a site (node) in a QuadEdgeSubdivision. |
45 | | * |
46 | | * The sites can be points on a line string representing a linear site. |
47 | | * |
48 | | * The vertex can be considered as a vector with a norm, length, inner product, cross |
49 | | * product, etc. Additionally, point relations (e.g., is a point to the left of a line, the circle |
50 | | * defined by this point and two others, etc.) are also defined in this class. |
51 | | * |
52 | | * It is common to want to attach user-defined data to the vertices of a subdivision. |
53 | | * One way to do this is to subclass `Vertex` to carry any desired information. |
54 | | * |
55 | | * @author JTS: David Skea |
56 | | * @author JTS: Martin Davis |
57 | | * @author Benjamin Campbell |
58 | | * */ |
59 | | |
60 | | class GEOS_DLL Vertex { |
61 | | public: |
62 | | static const int LEFT = 0; |
63 | | static const int RIGHT = 1; |
64 | | static const int BEYOND = 2; |
65 | | static const int BEHIND = 3; |
66 | | static const int BETWEEN = 4; |
67 | | static const int ORIGIN = 5; |
68 | | static const int DESTINATION = 6; |
69 | | private: |
70 | | geom::Coordinate p; |
71 | | |
72 | | public: |
73 | | Vertex(double _x, double _y); |
74 | | |
75 | | Vertex(double _x, double _y, double _z); |
76 | | |
77 | | Vertex(const geom::Coordinate& _p); |
78 | | |
79 | | Vertex(); |
80 | 8.02M | ~Vertex() {}; |
81 | | |
82 | | inline double |
83 | | getX() const |
84 | 0 | { |
85 | 0 | return p.x; |
86 | 0 | } |
87 | | |
88 | | inline double |
89 | | getY() const |
90 | 0 | { |
91 | 0 | return p.y; |
92 | 0 | } |
93 | | |
94 | | inline double |
95 | | getZ() const |
96 | 0 | { |
97 | 0 | return p.z; |
98 | 0 | } |
99 | | |
100 | | inline void |
101 | | setZ(double _z) |
102 | 0 | { |
103 | 0 | p.z = _z; |
104 | 0 | } |
105 | | |
106 | | inline const geom::Coordinate& |
107 | | getCoordinate() const |
108 | 28.4M | { |
109 | 28.4M | return p; |
110 | 28.4M | } |
111 | | |
112 | | inline bool |
113 | | equals(const Vertex& _x) const |
114 | 15.1M | { |
115 | 15.1M | return p.equals2D(_x.p); |
116 | 15.1M | } |
117 | | |
118 | | inline bool |
119 | | equals(const Vertex& _x, double tolerance) const |
120 | 722k | { |
121 | 722k | if(p.distance(_x.getCoordinate()) < tolerance) { |
122 | 124k | return true; |
123 | 124k | } |
124 | 597k | return false; |
125 | 722k | } |
126 | | |
127 | | int classify(const Vertex& p0, const Vertex& p1); |
128 | | |
129 | | /** |
130 | | * Computes the cross product k = u X v. |
131 | | * |
132 | | * @param v a vertex |
133 | | * @return returns the magnitude of u X v |
134 | | */ |
135 | | inline double |
136 | | crossProduct(const Vertex& v) const |
137 | 0 | { |
138 | 0 | return (p.x * v.getY() - p.y * v.getX()); |
139 | 0 | } |
140 | | |
141 | | /** |
142 | | * Computes the inner or dot product |
143 | | * |
144 | | * @param v a vertex |
145 | | * @return returns the dot product u.v |
146 | | */ |
147 | | inline double |
148 | | dot(Vertex v) const |
149 | 0 | { |
150 | 0 | return (p.x * v.getX() + p.y * v.getY()); |
151 | 0 | } |
152 | | |
153 | | /** |
154 | | * Computes the scalar product c(v) |
155 | | * |
156 | | * @param c scaling factor |
157 | | * @return returns the scaled vector |
158 | | */ |
159 | | inline std::unique_ptr<Vertex> |
160 | | times(double c) const |
161 | 0 | { |
162 | 0 | return std::unique_ptr<Vertex>(new Vertex(c * p.x, c * p.y)); |
163 | 0 | } |
164 | | |
165 | | /* Vector addition */ |
166 | | inline std::unique_ptr<Vertex> |
167 | | sum(Vertex v) const |
168 | 0 | { |
169 | 0 | return std::unique_ptr<Vertex>(new Vertex(p.x + v.getX(), p.y + v.getY())); |
170 | 0 | } |
171 | | |
172 | | /* and subtraction */ |
173 | | inline std::unique_ptr<Vertex> |
174 | | sub(const Vertex& v) const |
175 | 0 | { |
176 | 0 | return std::unique_ptr<Vertex>(new Vertex(p.x - v.getX(), p.y - v.getY())); |
177 | 0 | } |
178 | | |
179 | | /* magnitude of vector */ |
180 | | inline double |
181 | | magn() const |
182 | 0 | { |
183 | 0 | return (std::sqrt(p.x * p.x + p.y * p.y)); |
184 | 0 | } |
185 | | |
186 | | /* returns k X v (cross product). this is a vector perpendicular to v */ |
187 | | inline std::unique_ptr<Vertex> |
188 | | cross() const |
189 | 0 | { |
190 | 0 | return std::unique_ptr<Vertex>(new Vertex(p.y, -p.x)); |
191 | 0 | } |
192 | | |
193 | | /** ************************************************************* */ |
194 | | /*********************************************************************************************** |
195 | | * Geometric primitives / |
196 | | **********************************************************************************************/ |
197 | | |
198 | | /** |
199 | | * Tests if the vertex is inside the circle defined by |
200 | | * the triangle with vertices a, b, c (oriented counter-clockwise). |
201 | | * |
202 | | * @param a a vertex of the triangle |
203 | | * @param b a vertex of the triangle |
204 | | * @param c a vertex of the triangle |
205 | | * @return true if this vertex is in the circumcircle of (a,b,c) |
206 | | */ |
207 | 1.24M | bool isInCircle(const Vertex& a, const Vertex& b, const Vertex& c) const { |
208 | 1.24M | return triangulate::quadedge::TrianglePredicate::isInCircleRobust(a.p, b.p, c.p, this->p) == geom::Location::INTERIOR; |
209 | 1.24M | } |
210 | | |
211 | | /** |
212 | | * Tests whether the triangle formed by this vertex and two |
213 | | * other vertices is in CCW orientation. |
214 | | * |
215 | | * @param b a vertex |
216 | | * @param c a vertex |
217 | | * @returns true if the triangle is oriented CCW |
218 | | */ |
219 | | inline bool |
220 | | isCCW(const Vertex& b, const Vertex& c) const |
221 | 5.38M | { |
222 | | // check if signed area is positive |
223 | 5.38M | return (b.p.x - p.x) * (c.p.y - p.y) |
224 | 5.38M | > (b.p.y - p.y) * (c.p.x - p.x); |
225 | 5.38M | } |
226 | | |
227 | | bool rightOf(const QuadEdge& e) const; |
228 | | bool leftOf(const QuadEdge& e) const; |
229 | | |
230 | | private: |
231 | | static std::unique_ptr<algorithm::HCoordinate> bisector(const Vertex& a, const Vertex& b); |
232 | | |
233 | | inline double |
234 | | distance(const Vertex& v1, const Vertex& v2) |
235 | 0 | { |
236 | 0 | return std::sqrt(pow(v2.getX() - v1.getX(), 2.0) + |
237 | 0 | pow(v2.getY() - v1.getY(), 2.0)); |
238 | 0 | } |
239 | | |
240 | | /** |
241 | | * Computes the value of the ratio of the circumradius to shortest edge. If smaller than some |
242 | | * given tolerance B, the associated triangle is considered skinny. For an equal lateral |
243 | | * triangle this value is 0.57735. The ratio is related to the minimum triangle angle theta by: |
244 | | * circumRadius/shortestEdge = 1/(2sin(theta)). |
245 | | * |
246 | | * @param b second vertex of the triangle |
247 | | * @param c third vertex of the triangle |
248 | | * @return ratio of circumradius to shortest edge. |
249 | | */ |
250 | | double circumRadiusRatio(const Vertex& b, const Vertex& c); |
251 | | |
252 | | /** |
253 | | * returns a new vertex that is mid-way between this vertex and another end point. |
254 | | * |
255 | | * @param a the other end point. |
256 | | * @return the point mid-way between this and that. |
257 | | */ |
258 | | std::unique_ptr<Vertex> midPoint(const Vertex& a); |
259 | | |
260 | | /** |
261 | | * Computes the centre of the circumcircle of this vertex and two others. |
262 | | * |
263 | | * @param b |
264 | | * @param c |
265 | | * @return the Coordinate which is the circumcircle of the 3 points. |
266 | | */ |
267 | | std::unique_ptr<Vertex> circleCenter(const Vertex& b, const Vertex& c) const; |
268 | | |
269 | | /** |
270 | | * For this vertex enclosed in a triangle defined by three vertices v0, v1 and v2, interpolate |
271 | | * a z value from the surrounding vertices. |
272 | | */ |
273 | | double interpolateZValue(const Vertex& v0, const Vertex& v1, const Vertex& v2) const; |
274 | | |
275 | | /** |
276 | | * Interpolates the Z-value (height) of a point enclosed in a triangle |
277 | | * whose vertices all have Z values. |
278 | | * The containing triangle must not be degenerate |
279 | | * (in other words, the three vertices must enclose a |
280 | | * non-zero area). |
281 | | * |
282 | | * @param p the point to interpolate the Z value of |
283 | | * @param v0 a vertex of a triangle containing the p |
284 | | * @param v1 a vertex of a triangle containing the p |
285 | | * @param v2 a vertex of a triangle containing the p |
286 | | * @return the interpolated Z-value (height) of the point |
287 | | */ |
288 | | static double interpolateZ(const geom::Coordinate& p, const geom::Coordinate& v0, |
289 | | const geom::Coordinate& v1, const geom::Coordinate& v2); |
290 | | |
291 | | /** |
292 | | * Computes the interpolated Z-value for a point p lying on the segment p0-p1 |
293 | | * |
294 | | * @param p |
295 | | * @param p0 |
296 | | * @param p1 |
297 | | * @return the interpolated Z value |
298 | | */ |
299 | | static double interpolateZ(const geom::Coordinate& p, const geom::Coordinate& p0, |
300 | | const geom::Coordinate& p1); |
301 | | }; |
302 | | |
303 | | inline bool |
304 | | operator<(const Vertex& v1, const Vertex& v2) |
305 | 9.91M | { |
306 | 9.91M | return v1.getCoordinate() < v2.getCoordinate(); |
307 | 9.91M | } |
308 | | |
309 | | } //namespace geos.triangulate.quadedge |
310 | | } //namespace geos.triangulate |
311 | | } //namespace geos |
312 | | |