GEOS  3.14.0dev
CGAlgorithmsDD.h
1 /**********************************************************************
2  *
3  * GEOS - Geometry Engine Open Source
4  * http://geos.osgeo.org
5  *
6  * Copyright (C) 2014 Mateusz Loskot <mateusz@loskot.net>
7  *
8  * This is free software; you can redistribute and/or modify it under
9  * the terms of the GNU Lesser General Public Licence as published
10  * by the Free Software Foundation.
11  * See the COPYING file for more information.
12  *
13  **********************************************************************
14  *
15  * Last port: algorithm/CGAlgorithmsDD.java r789 (JTS-1.14)
16  *
17  **********************************************************************/
18 
19 #pragma once
20 
21 #include <geos/export.h>
22 #include <geos/math/DD.h>
23 
24 // Forward declarations
25 namespace geos {
26 namespace geom {
27 class CoordinateXY;
28 class CoordinateSequence;
29 }
30 }
31 
32 using namespace geos::math;
33 
34 namespace geos {
35 namespace algorithm { // geos::algorithm
36 
38 class GEOS_DLL CGAlgorithmsDD {
39 
40 public:
41 
42  enum {
43  CLOCKWISE = -1,
44  COLLINEAR = 0,
45  COUNTERCLOCKWISE = 1
46  };
47 
48  enum {
49  RIGHT = -1,
50  LEFT = 1,
51  STRAIGHT = 0,
52  FAILURE = 2
53  };
54 
67  static int orientationIndex(const geom::CoordinateXY& p1,
68  const geom::CoordinateXY& p2,
69  const geom::CoordinateXY& q);
70 
71 
72  static int orientationIndex(double p1x, double p1y,
73  double p2x, double p2y,
74  double qx, double qy);
75 
90  static inline int orientationIndexFilter(
91  double pax, double pay,
92  double pbx, double pby,
93  double pcx, double pcy)
94  {
99  double constexpr DP_SAFE_EPSILON = 1e-15;
100 
101  double detsum;
102  double const detleft = (pax - pcx) * (pby - pcy);
103  double const detright = (pay - pcy) * (pbx - pcx);
104  double const det = detleft - detright;
105 
106  if(detleft > 0.0) {
107  if(detright <= 0.0) {
108  return orientation(det);
109  }
110  else {
111  detsum = detleft + detright;
112  }
113  }
114  else if(detleft < 0.0) {
115  if(detright >= 0.0) {
116  return orientation(det);
117  }
118  else {
119  detsum = -detleft - detright;
120  }
121  }
122  else {
123  return orientation(det);
124  }
125 
126  double const errbound = DP_SAFE_EPSILON * detsum;
127  if((det >= errbound) || (-det >= errbound)) {
128  return orientation(det);
129  }
130  return CGAlgorithmsDD::FAILURE;
131  };
132 
133  static int
134  orientation(double x)
135  {
136  if(x < 0) {
137  return CGAlgorithmsDD::RIGHT;
138  }
139  if(x > 0) {
140  return CGAlgorithmsDD::LEFT;
141  }
142  return CGAlgorithmsDD::STRAIGHT;
143  };
144 
154  static geom::CoordinateXY intersection(const geom::CoordinateXY& p1, const geom::CoordinateXY& p2,
155  const geom::CoordinateXY& q1, const geom::CoordinateXY& q2);
156 
157  static int signOfDet2x2(double dx1, double dy1, double dx2, double dy2);
158 
159  static DD detDD(double x1, double y1, double x2, double y2);
160  static DD detDD(const DD& x1, const DD& y1, const DD& x2, const DD& y2);
161 
181  static geom::CoordinateXY circumcentreDD(const geom::CoordinateXY& a, const geom::CoordinateXY& b, const geom::CoordinateXY& c);
182 
183 protected:
184 
185  static int signOfDet2x2(const DD& x1, const DD& y1, const DD& x2, const DD& y2);
186 
187 };
188 
189 } // namespace geos::algorithm
190 } // namespace geos
191 
192 
193 
Implements basic computational geometry algorithms using extended precision float-point arithmetic.
Definition: CGAlgorithmsDD.h:38
static int orientationIndexFilter(double pax, double pay, double pbx, double pby, double pcx, double pcy)
Definition: CGAlgorithmsDD.h:90
static int orientationIndex(const geom::CoordinateXY &p1, const geom::CoordinateXY &p2, const geom::CoordinateXY &q)
Returns the index of the direction of the point q relative to a vector specified by p1-p2.
static geom::CoordinateXY circumcentreDD(const geom::CoordinateXY &a, const geom::CoordinateXY &b, const geom::CoordinateXY &c)
Computes the circumcentre of a triangle.
static geom::CoordinateXY intersection(const geom::CoordinateXY &p1, const geom::CoordinateXY &p2, const geom::CoordinateXY &q1, const geom::CoordinateXY &q2)
Wrapper for DoubleDouble higher precision mathematics operations.
Definition: DD.h:108
Basic namespace for all GEOS functionalities.
Definition: Angle.h:25