Coverage Report

Created: 2026-10-31 06:47

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/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