| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /* | ||
| 2 | * Copyright (c) 2000-2023 Inria | ||
| 3 | * All rights reserved. | ||
| 4 | * | ||
| 5 | * Redistribution and use in source and binary forms, with or without | ||
| 6 | * modification, are permitted provided that the following conditions are met: | ||
| 7 | * | ||
| 8 | * * Redistributions of source code must retain the above copyright notice, | ||
| 9 | * this list of conditions and the following disclaimer. | ||
| 10 | * * Redistributions in binary form must reproduce the above copyright notice, | ||
| 11 | * this list of conditions and the following disclaimer in the documentation | ||
| 12 | * and/or other materials provided with the distribution. | ||
| 13 | * * Neither the name of the ALICE Project-Team nor the names of its | ||
| 14 | * contributors may be used to endorse or promote products derived from this | ||
| 15 | * software without specific prior written permission. | ||
| 16 | * | ||
| 17 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" | ||
| 18 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | ||
| 19 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | ||
| 20 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE | ||
| 21 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR | ||
| 22 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF | ||
| 23 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS | ||
| 24 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN | ||
| 25 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | ||
| 26 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | ||
| 27 | * POSSIBILITY OF SUCH DAMAGE. | ||
| 28 | * | ||
| 29 | * Contact: Bruno Levy | ||
| 30 | * | ||
| 31 | * https://www.inria.fr/fr/bruno-levy | ||
| 32 | * | ||
| 33 | * Inria, | ||
| 34 | * Domaine de Voluceau, | ||
| 35 | * 78150 Le Chesnay - Rocquencourt | ||
| 36 | * FRANCE | ||
| 37 | * | ||
| 38 | */ | ||
| 39 | |||
| 40 | #ifndef GEOGRAM_NUMERICS_EXACT_GEOMETRY | ||
| 41 | #define GEOGRAM_NUMERICS_EXACT_GEOMETRY | ||
| 42 | |||
| 43 | #include <geogram/basic/common.h> | ||
| 44 | #include <geogram/basic/geometry.h> | ||
| 45 | #include <geogram/basic/vechg.h> | ||
| 46 | #include <geogram/numerics/expansion_nt.h> | ||
| 47 | #include <geogram/numerics/interval_nt.h> | ||
| 48 | |||
| 49 | // #include <geogram/numerics/predicates.h> | ||
| 50 | #include <geogram/numerics/exact_geometry.h> | ||
| 51 | |||
| 52 | #ifdef GEOGRAM_WITH_GEOGRAMPLUS | ||
| 53 | #include <geogram/geogramplus/numerics/exact_geometry.h> | ||
| 54 | #endif | ||
| 55 | |||
| 56 | /** | ||
| 57 | * \file geogram/numerics/exact_geometry.h | ||
| 58 | * \brief Exact predicates and constructs | ||
| 59 | * \details Implements vector types with expansion | ||
| 60 | * coordinates (vec2E, vec3E), vector types with | ||
| 61 | * homogeneous expansion coordinates (vec2HE, vec3HE), | ||
| 62 | * 2d orientation predicate, incircle predicate | ||
| 63 | * and constructions for intersections. | ||
| 64 | */ | ||
| 65 | |||
| 66 | // If Tessael's geogramplus is available, use exact_nt coordinates, | ||
| 67 | // else use expansion_nt coordinates. | ||
| 68 | // exact_nt coordinates makes the algorithm 10x to 20x faster | ||
| 69 | // and have no risk of underflow / overflow. | ||
| 70 | #ifdef GEOGRAM_WITH_GEOGRAMPLUS | ||
| 71 | #define GEOGRAM_USE_EXACT_NT | ||
| 72 | #endif | ||
| 73 | |||
| 74 | namespace GEO { | ||
| 75 | |||
| 76 | /** | ||
| 77 | * \brief vec2 with coordinates as expansions | ||
| 78 | * \details Coordinates support +,-,* | ||
| 79 | */ | ||
| 80 | typedef vecng<2,expansion_nt> vec2E; | ||
| 81 | |||
| 82 | /** | ||
| 83 | * \brief vec3 with coordinates as expansions | ||
| 84 | * \details Coordinates support +,-,* | ||
| 85 | */ | ||
| 86 | typedef vecng<3,expansion_nt> vec3E; | ||
| 87 | |||
| 88 | /** | ||
| 89 | * \brief vec2 with coordinates as interval_nt | ||
| 90 | * \details Used to write arithmetic filters | ||
| 91 | * for geometric predicates. | ||
| 92 | */ | ||
| 93 | typedef vecng<2,interval_nt> vec2I; | ||
| 94 | |||
| 95 | /** | ||
| 96 | * \brief vec3 with coordinates as interval_nt | ||
| 97 | * \details Used to write arithmetic filters | ||
| 98 | * for geometric predicates. | ||
| 99 | */ | ||
| 100 | typedef vecng<3,interval_nt> vec3I; | ||
| 101 | |||
| 102 | /** | ||
| 103 | * \brief 2D vector in homogeneous coordinates | ||
| 104 | * with coordinates as expansions | ||
| 105 | * \details Coordinates support +,-,* and / by | ||
| 106 | * multiplying w. | ||
| 107 | */ | ||
| 108 | typedef vec2Hg<expansion_nt> vec2HE; | ||
| 109 | |||
| 110 | /** | ||
| 111 | * \brief 3D vector in homogeneous coordinates | ||
| 112 | * with coordinates as expansions | ||
| 113 | * \details Coordinates support +,-,* and / by | ||
| 114 | * multiplying w. | ||
| 115 | */ | ||
| 116 | typedef vec3Hg<expansion_nt> vec3HE; | ||
| 117 | |||
| 118 | /** | ||
| 119 | * \brief 2D vector in homogeneous coordinates | ||
| 120 | * with coordinates as intervals. | ||
| 121 | * \details Used to write arithmetic filters | ||
| 122 | * for geometric predicates. | ||
| 123 | */ | ||
| 124 | typedef vec2Hg<interval_nt> vec2HI; | ||
| 125 | |||
| 126 | /** | ||
| 127 | * \brief 3D vector in homogeneous coordinates | ||
| 128 | * with coordinates as intervals. | ||
| 129 | * \details Used to write arithmetic filters | ||
| 130 | * for geometric predicates. | ||
| 131 | */ | ||
| 132 | typedef vec3Hg<interval_nt> vec3HI; | ||
| 133 | |||
| 134 | /***********************************************************************/ | ||
| 135 | |||
| 136 | /** | ||
| 137 | * \brief Creates a vector with coordinates of arbitrary type | ||
| 138 | * from two points with double coordinates | ||
| 139 | * \param[in] p1 , p2 the two vectors | ||
| 140 | * \return The vector \p p2 - \p p1 | ||
| 141 | * \tparam VEC3 the type of the returned vector | ||
| 142 | */ | ||
| 143 | template <class VEC3 = vec3> | ||
| 144 | inline VEC3 make_vec3(const vec3& p1, const vec3& p2) { | ||
| 145 | typedef typename VEC3::value_type value_type; | ||
| 146 | return VEC3( | ||
| 147 | value_type(p2.x) - value_type(p1.x), | ||
| 148 | value_type(p2.y) - value_type(p1.y), | ||
| 149 | value_type(p2.z) - value_type(p1.z) | ||
| 150 | ); | ||
| 151 | } | ||
| 152 | |||
| 153 | /** | ||
| 154 | * \brief Creates a vector with coordinates of arbitrary type | ||
| 155 | * from two points with double coordinates | ||
| 156 | * \param[in] p1 , p2 the two vectors | ||
| 157 | * \return The vector \p p2 - \p p1 | ||
| 158 | * \tparam VEC2 the type of the returned vector | ||
| 159 | */ | ||
| 160 | template <class VEC2> | ||
| 161 | inline VEC2 make_vec2( | ||
| 162 | const vec2& p1, const vec2& p2 | ||
| 163 | ) { | ||
| 164 | typedef typename VEC2::value_type value_type; | ||
| 165 | return VEC2( | ||
| 166 | value_type(p2.x) - value_type(p1.x), | ||
| 167 | value_type(p2.y) - value_type(p1.y) | ||
| 168 | ); | ||
| 169 | } | ||
| 170 | |||
| 171 | /** | ||
| 172 | * \brief Computes the normal to a triangle from its three | ||
| 173 | * vertices | ||
| 174 | * \param[in] p1 , p2 , p3 the three vertices of the triangle | ||
| 175 | * \return the normal to the triangle with coordinates of | ||
| 176 | * arbitrary type | ||
| 177 | * \tparam VEC3 the type of the returned vector | ||
| 178 | */ | ||
| 179 | template <class VEC3> | ||
| 180 | inline VEC3 triangle_normal( | ||
| 181 | const vec3& p1, const vec3& p2, const vec3& p3 | ||
| 182 | ) { | ||
| 183 | return cross( | ||
| 184 | make_vec3<VEC3>(p1,p2), | ||
| 185 | make_vec3<VEC3>(p1,p3) | ||
| 186 | ); | ||
| 187 | } | ||
| 188 | |||
| 189 | /***********************************************************************/ | ||
| 190 | |||
| 191 | namespace PCK { | ||
| 192 | |||
| 193 | /** | ||
| 194 | * \brief Computes the orientation predicate in 2d. | ||
| 195 | * \details Computes the sign of the signed area of | ||
| 196 | * the triangle p0, p1, p2. | ||
| 197 | * \param[in] p0 , p1 , p2 vertices of the triangle | ||
| 198 | * as 2d vectors with homogeneous coordinates stored as | ||
| 199 | * expansion_nt (arbitrary precision). | ||
| 200 | * \retval POSITIVE if the triangle is oriented counter-clockwise | ||
| 201 | * \retval ZERO if the triangle is flat | ||
| 202 | * \retval NEGATIVE if the triangle is oriented clockwise | ||
| 203 | */ | ||
| 204 | Sign GEOGRAM_API orient_2d( | ||
| 205 | const vec2HE& p0, const vec2HE& p1, const vec2HE& p2 | ||
| 206 | ); | ||
| 207 | |||
| 208 | /** | ||
| 209 | * \brief Computes the orientation predicate in 2d projected along an | ||
| 210 | * axis | ||
| 211 | * \details Computes the sign of the signed area of | ||
| 212 | * the triangle p0, p1, p2 projected onto a given axis. | ||
| 213 | * The used coordinates are (axis + 1) modulo 3 and | ||
| 214 | * (axis + 2) modulo 3. | ||
| 215 | * \param[in] p0 , p1 , p2 vertices of the triangle | ||
| 216 | * as 3d vectors with homogeneous coordinates stored as | ||
| 217 | * expansion_nt (arbitrary precision). | ||
| 218 | * \retval POSITIVE if the projected triangle is | ||
| 219 | * oriented counter-clockwise | ||
| 220 | * \retval ZERO if the projected triangle is flat | ||
| 221 | * \retval NEGATIVE if the projected triangle is oriented clockwise | ||
| 222 | */ | ||
| 223 | Sign GEOGRAM_API orient_2d_projected( | ||
| 224 | const vec3HE& p0, const vec3HE& p1, const vec3HE& p2, | ||
| 225 | coord_index_t axis | ||
| 226 | ); | ||
| 227 | |||
| 228 | /** | ||
| 229 | * \brief Computes the orientation predicate in 3d. | ||
| 230 | * \details Computes the sign of the signed volume of | ||
| 231 | * the tetrahedron p0, p1, p2, p3. | ||
| 232 | * \param[in] p0 , p1 , p2 , p3 vertices of the tetrahedron | ||
| 233 | * as 3d vectors with homogeneous coordinates stored as | ||
| 234 | * expansion_nt (arbitrary precision). | ||
| 235 | * \retval POSITIVE if the tetrahedron is oriented positively | ||
| 236 | * \retval ZERO if the tetrahedron is flat | ||
| 237 | * \retval NEGATIVE if the tetrahedron is oriented negatively | ||
| 238 | */ | ||
| 239 | Sign GEOGRAM_API orient_3d( | ||
| 240 | const vec3HE& p0, const vec3HE& p1, | ||
| 241 | const vec3HE& p2, const vec3HE& p3 | ||
| 242 | ); | ||
| 243 | |||
| 244 | /** | ||
| 245 | * \brief Computes the sign of the dot product between | ||
| 246 | * two vectors defined by three points. | ||
| 247 | * \param[in] p0 , p1 , p2 the three points as 2d vectors | ||
| 248 | * with homogeneous coordinates stored as | ||
| 249 | * expansion_nt (arbitrary precision). | ||
| 250 | * \return the sign of(p1-p0)*(p2-p0) | ||
| 251 | */ | ||
| 252 | Sign GEOGRAM_API dot_2d( | ||
| 253 | const vec2HE& p0, const vec2HE& p1, const vec2HE& p2 | ||
| 254 | ); | ||
| 255 | |||
| 256 | /** | ||
| 257 | * \brief Tests whether a point is in the circumscribed circle of | ||
| 258 | * three other points. | ||
| 259 | * \details If the triangle \p p0 , \p p1 , \p p2 is oriented | ||
| 260 | * clockwise instead of counter-clockwise, then the result is inversed. | ||
| 261 | * \param[in] p0 , p1 , p2 , p3 the four points, | ||
| 262 | * in homogeneous coordinates,represented in exact form. | ||
| 263 | * \param[in] l0 , l1 , l2 , l3 the four approximated pre-computed | ||
| 264 | * lengths li = (xi^2 + yi^2) / wi^2 as double coordinates | ||
| 265 | * \retval POSITIVE if p3 is inside | ||
| 266 | * the circumscribed circle of p0, p1, p2 | ||
| 267 | * \retval NEGATIVE if p3 is outside | ||
| 268 | * the circumscribed circle of p0, p1, p2 | ||
| 269 | * \retval a coherent perturbation otherwise | ||
| 270 | */ | ||
| 271 | Sign GEOGRAM_API incircle_2d_SOS_with_lengths( | ||
| 272 | const vec2HE& p0, const vec2HE& p1, | ||
| 273 | const vec2HE& p2, const vec2HE& p3, | ||
| 274 | double l0, double l1, double l2, double l3 | ||
| 275 | ); | ||
| 276 | |||
| 277 | /** | ||
| 278 | * \brief Tests whether a point is in the circumscribed circle of | ||
| 279 | * three other points. | ||
| 280 | * \details If the triangle \p p0 , \p p1 , \p p2 is oriented | ||
| 281 | * clockwise instead of counter-clockwise, then the result is inversed. | ||
| 282 | * \param[in] p0 , p1 , p2 , p3 the four points, | ||
| 283 | * in homogeneous coordinates,represented in exact form. | ||
| 284 | * \param[in] l0 , l1 , l2 , l3 the four approximated pre-computed | ||
| 285 | * lengths li = (xi^2 + yi^2) / wi^2 as double coordinates | ||
| 286 | * \retval POSITIVE if p3 is inside | ||
| 287 | * the circumscribed circle of p0, p1, p2 | ||
| 288 | * \retval NEGATIVE if p3 is outside | ||
| 289 | * the circumscribed circle of p0, p1, p2 | ||
| 290 | * \retval a coherent perturbation otherwise | ||
| 291 | */ | ||
| 292 | Sign GEOGRAM_API incircle_2d_SOS_with_lengths( | ||
| 293 | const vec2HE& p0, const vec2HE& p1, | ||
| 294 | const vec2HE& p2, const vec2HE& p3, | ||
| 295 | double l0, double l1, double l2, double l3 | ||
| 296 | ); | ||
| 297 | |||
| 298 | /** | ||
| 299 | * \brief Tests whether a point is in the circumscribed circle of | ||
| 300 | * three other points. | ||
| 301 | * \details If the triangle \p p0 , \p p1 , \p p2 is oriented | ||
| 302 | * clockwise instead of counter-clockwise, then the result is inversed. | ||
| 303 | * One can use instead the incircle_2d_SOS_with_lengths() that is | ||
| 304 | * faster and that uses cached lengths. | ||
| 305 | * \see incircle_2d_SOS_with_lengths() | ||
| 306 | * \param[in] p0 , p1 , p2 , p3 the four points, | ||
| 307 | * in homogeneous coordinates,represented in exact form. | ||
| 308 | * \retval POSITIVE if p3 is inside | ||
| 309 | * the circumscribed circle of p0, p1, p2 | ||
| 310 | * \retval NEGATIVE if p3 is outside | ||
| 311 | * the circumscribed circle of p0, p1, p2 | ||
| 312 | * \retval a coherent perturbation otherwise | ||
| 313 | */ | ||
| 314 | inline Sign incircle_2d_SOS( | ||
| 315 | const vec2HE& p0, const vec2HE& p1, | ||
| 316 | const vec2HE& p2, const vec2HE& p3 | ||
| 317 | ) { | ||
| 318 | double l0 = (geo_sqr(p0.x) + geo_sqr(p0.y)).estimate() / | ||
| 319 | geo_sqr(p0.w).estimate(); | ||
| 320 | double l1 = (geo_sqr(p1.x) + geo_sqr(p1.y)).estimate() / | ||
| 321 | geo_sqr(p1.w).estimate(); | ||
| 322 | double l2 = (geo_sqr(p2.x) + geo_sqr(p2.y)).estimate() / | ||
| 323 | geo_sqr(p2.w).estimate(); | ||
| 324 | double l3 = (geo_sqr(p3.x) + geo_sqr(p3.y)).estimate() / | ||
| 325 | geo_sqr(p3.w).estimate(); | ||
| 326 | return incircle_2d_SOS_with_lengths(p0,p1,p2,p3,l0,l1,l2,l3); | ||
| 327 | } | ||
| 328 | |||
| 329 | /** | ||
| 330 | * \brief Gets the axis that is most normal to a triangle | ||
| 331 | * \details Fires an assertion fail if triangle is | ||
| 332 | * degenerate (that is, with its three vertices exactly | ||
| 333 | * aligned). | ||
| 334 | * \param[in] p1 , p2 , p3 the three vertices of the | ||
| 335 | * triangle | ||
| 336 | * \return the coordinate of the normal vector with the | ||
| 337 | * greatest absolute value | ||
| 338 | */ | ||
| 339 | coord_index_t GEOGRAM_API triangle_normal_axis( | ||
| 340 | const vec3& p1, const vec3& p2, const vec3& p3 | ||
| 341 | ); | ||
| 342 | |||
| 343 | /** | ||
| 344 | * \brief Tests whether three 3d points are aligned | ||
| 345 | * \param[in] p0 , p1 , p2 the three points, | ||
| 346 | * in homogeneous coordinates, represented in exact form. | ||
| 347 | * \retval true if the three points are aligned (or if two | ||
| 348 | * of them or more are identical) | ||
| 349 | * \retval false otherwise | ||
| 350 | */ | ||
| 351 | bool GEOGRAM_API aligned_3d( | ||
| 352 | const vec3HE& p0, const vec3HE& p1, const vec3HE& p2 | ||
| 353 | ); | ||
| 354 | |||
| 355 | /** | ||
| 356 | * \brief Tests whether a point is on a segment | ||
| 357 | * \param[in] p the point in homogeneous coordinates, in exact form | ||
| 358 | * \param[in] q1 , q2 the two extremities of the segment in homogeneous | ||
| 359 | * coordinates, in exact form | ||
| 360 | * \retval true if \p p is on the segment \p q1 , \p q2 | ||
| 361 | * \retval false otherwise | ||
| 362 | */ | ||
| 363 | bool GEOGRAM_API on_segment_3d( | ||
| 364 | const vec3HE& p, const vec3HE& q1, const vec3HE& q2 | ||
| 365 | ); | ||
| 366 | |||
| 367 | /** | ||
| 368 | * \brief Gets a 3D floating-point approximation of a 3D point | ||
| 369 | * with exact coordinates. | ||
| 370 | * \param[in] p a const reference to the point with homogeneous | ||
| 371 | * exact coordinates as expansion_nt | ||
| 372 | * \return a floating-point approximation of \p p | ||
| 373 | */ | ||
| 374 | vec3 GEOGRAM_API approximate(const vec3HE& p); | ||
| 375 | |||
| 376 | /** | ||
| 377 | * \brief Gets a 2D floating-point approximation of a 2D point | ||
| 378 | * with exact coordinates. | ||
| 379 | * \param[in] p a const reference to the point with homogeneous | ||
| 380 | * exact coordinates as expansion_nt | ||
| 381 | * \return a floating-point approximation of \p p | ||
| 382 | */ | ||
| 383 | vec2 GEOGRAM_API approximate(const vec2HE& p); | ||
| 384 | |||
| 385 | } | ||
| 386 | |||
| 387 | /************************************************************************/ | ||
| 388 | |||
| 389 | /** | ||
| 390 | * \brief Specialization of make_vec2() for vec2E | ||
| 391 | */ | ||
| 392 | template <> | ||
| 393 | 465855 | inline vec2E make_vec2<vec2E>(const vec2& p1, const vec2& p2) { | |
| 394 | return vec2E( | ||
| 395 |
1/2✓ Branch 1 taken 465855 times.
✗ Branch 2 not taken.
|
931710 | expansion_nt(expansion_nt::DIFF, p2.x, p1.x), |
| 396 | 465855 | expansion_nt(expansion_nt::DIFF, p2.y, p1.y) | |
| 397 | 465855 | ); | |
| 398 | } | ||
| 399 | |||
| 400 | /** | ||
| 401 | * \brief Specialization of make_vec3() for vec3E | ||
| 402 | */ | ||
| 403 | template <> | ||
| 404 | 949750 | inline vec3E make_vec3<vec3E>(const vec3& p1, const vec3& p2) { | |
| 405 | return vec3E( | ||
| 406 |
1/2✓ Branch 1 taken 949750 times.
✗ Branch 2 not taken.
|
1899500 | expansion_nt(expansion_nt::DIFF, p2.x, p1.x), |
| 407 |
1/2✓ Branch 1 taken 949750 times.
✗ Branch 2 not taken.
|
1899500 | expansion_nt(expansion_nt::DIFF, p2.y, p1.y), |
| 408 | 949750 | expansion_nt(expansion_nt::DIFF, p2.z, p1.z) | |
| 409 | 949750 | ); | |
| 410 | } | ||
| 411 | |||
| 412 | // Under Linux we got 10 Mb of stack (!) Then some operations can be | ||
| 413 | // made faster by using the low-level expansion API (that allocates | ||
| 414 | // intermediary multiprecision values on stack rather than in the heap). | ||
| 415 | // These optimized functions are written as template specializations | ||
| 416 | // (used automatically). | ||
| 417 | |||
| 418 | #ifdef GEO_HAS_BIG_STACK | ||
| 419 | |||
| 420 | /** | ||
| 421 | * \brief Specialization of det() optimized using low-level API | ||
| 422 | */ | ||
| 423 | template<> expansion_nt GEOGRAM_API det(const vec2E& v1, const vec2E& v2); | ||
| 424 | |||
| 425 | /** | ||
| 426 | * \brief Specialization of dot() optimized using low-level API | ||
| 427 | */ | ||
| 428 | template<> expansion_nt GEOGRAM_API dot(const vec2E& v1, const vec2E& v2); | ||
| 429 | |||
| 430 | /** | ||
| 431 | * \brief Specialization of dot() optimized using low-level API | ||
| 432 | */ | ||
| 433 | template<> expansion_nt GEOGRAM_API dot(const vec3E& v1, const vec3E& v2); | ||
| 434 | |||
| 435 | /** | ||
| 436 | * \brief Specialization of mix() optimized using low-level API | ||
| 437 | */ | ||
| 438 | template<> vec2Hg<expansion_nt> GEOGRAM_API mix( | ||
| 439 | const rationalg<expansion_nt>& t, | ||
| 440 | const vecng<2,double>& p1, const vecng<2,double>& p2 | ||
| 441 | ); | ||
| 442 | |||
| 443 | /** | ||
| 444 | * \brief Specialization of mix() optimized using low-level API | ||
| 445 | */ | ||
| 446 | template<> vec3Hg<expansion_nt> GEOGRAM_API mix( | ||
| 447 | const rationalg<expansion_nt>& t, | ||
| 448 | const vecng<3,double>& p1, const vecng<3,double>& p2 | ||
| 449 | ); | ||
| 450 | |||
| 451 | /** | ||
| 452 | * \brief Specialization of triangle_normal() for vec3E | ||
| 453 | */ | ||
| 454 | template <> GEOGRAM_API vec3E triangle_normal<vec3E>( | ||
| 455 | const vec3& p1, const vec3& p2, const vec3& p3 | ||
| 456 | ); | ||
| 457 | |||
| 458 | #endif | ||
| 459 | |||
| 460 | /************************************************************************/ | ||
| 461 | |||
| 462 | /** | ||
| 463 | * \brief Exact geometric types | ||
| 464 | * \details If Tessael's geogramplus is available, uses exact_nt, or | ||
| 465 | * the (slower and limited) expansion_nt type otherwise. | ||
| 466 | */ | ||
| 467 | namespace exact { | ||
| 468 | #ifdef GEOGRAM_USE_EXACT_NT | ||
| 469 | typedef exact_nt scalar; /**< exact number type for scalars */ | ||
| 470 | #else | ||
| 471 | typedef expansion_nt scalar; /**< exact number type for scalars */ | ||
| 472 | #endif | ||
| 473 | typedef vecng<2,scalar> vec2; /**< 2d vector with exact coordinates */ | ||
| 474 | typedef vecng<3,scalar> vec3; /**< 3d vector with exact coordinates */ | ||
| 475 | |||
| 476 | /** | ||
| 477 | * \brief 2d vector with exact homogeneous coordinates | ||
| 478 | */ | ||
| 479 | typedef vec2Hg<scalar> vec2h; | ||
| 480 | |||
| 481 | /** | ||
| 482 | * \brief 3d vector with exact homogeneous coordinates | ||
| 483 | */ | ||
| 484 | typedef vec3Hg<scalar> vec3h; | ||
| 485 | |||
| 486 | /** | ||
| 487 | * \brief rational with exact numerator and denominator | ||
| 488 | */ | ||
| 489 | typedef rationalg<scalar> rational; | ||
| 490 | } | ||
| 491 | |||
| 492 | #ifndef GEOGRAM_PSM | ||
| 493 | namespace PCK { | ||
| 494 | /** | ||
| 495 | * \brief Computes the orientation predicate in 3d. | ||
| 496 | * \details Computes the sign of the signed volume of | ||
| 497 | * the tetrahedron p0, p1, p2, p3. | ||
| 498 | * \param[in] p0 , p1 , p2 , p3 vertices of the tetrahedron as | ||
| 499 | * points with homogeneous coordinates represented in arbitrary | ||
| 500 | * precision (expansion_nt or exact_nt if geogram+ is available). | ||
| 501 | * \retval POSITIVE if the tetrahedron is oriented positively | ||
| 502 | * \retval NEGATIVE if the tetrahedron is oriented negatively | ||
| 503 | * \retval perturb() if the tetrahedron is flat, | ||
| 504 | * where \c perturb() denotes a globally | ||
| 505 | * consistent perturbation, that returns either POSITIVE or NEGATIVE | ||
| 506 | */ | ||
| 507 | Sign GEOGRAM_API orient_3d_SOS( | ||
| 508 | const exact::vec3h& p0, const exact::vec3h& p1, | ||
| 509 | const exact::vec3h& p2, const exact::vec3h& p3 | ||
| 510 | ); | ||
| 511 | } | ||
| 512 | #endif | ||
| 513 | |||
| 514 | } | ||
| 515 | |||
| 516 | #endif | ||
| 517 |