summaryrefslogtreecommitdiff
path: root/src/mbgl/util/geometry_util.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/mbgl/util/geometry_util.cpp')
-rw-r--r--src/mbgl/util/geometry_util.cpp62
1 files changed, 49 insertions, 13 deletions
diff --git a/src/mbgl/util/geometry_util.cpp b/src/mbgl/util/geometry_util.cpp
index df4119ce6a..4a90c75582 100644
--- a/src/mbgl/util/geometry_util.cpp
+++ b/src/mbgl/util/geometry_util.cpp
@@ -5,13 +5,31 @@
namespace mbgl {
template <typename T>
-bool GeometryUtil<T>::rayIntersect(const Point<T>& p, const Point<T>& p1, const Point<T>& p2) {
+void updateBBox(GeometryBBox<T>& bbox, const Point<T>& p) {
+ bbox[0] = std::min(p.x, bbox[0]);
+ bbox[1] = std::min(p.y, bbox[1]);
+ bbox[2] = std::max(p.x, bbox[2]);
+ bbox[3] = std::max(p.y, bbox[3]);
+}
+
+// check if bbox1 is within bbox2
+template <typename T>
+bool boxWithinBox(const GeometryBBox<T>& bbox1, const GeometryBBox<T>& bbox2) {
+ if (bbox1[0] <= bbox2[0]) return false;
+ if (bbox1[2] >= bbox2[2]) return false;
+ if (bbox1[1] <= bbox2[1]) return false;
+ if (bbox1[3] >= bbox2[3]) return false;
+ return true;
+}
+
+template <typename T>
+bool rayIntersect(const Point<T>& p, const Point<T>& p1, const Point<T>& p2) {
return ((p1.y > p.y) != (p2.y > p.y)) && (p.x < (p2.x - p1.x) * (p.y - p1.y) / (p2.y - p1.y) + p1.x);
}
// check if point p is on line segment with end points p1 and p2
template <typename T>
-bool GeometryUtil<T>::pointOnBoundary(const Point<T>& p, const Point<T>& p1, const Point<T>& p2) {
+bool pointOnBoundary(const Point<T>& p, const Point<T>& p1, const Point<T>& p2) {
// requirements of point p on line segment:
// 1. colinear: cross product of vector p->p1(x1, y1) and vector p->p2(x2, y2) equals to 0
// 2. p is between p1 and p2
@@ -23,10 +41,7 @@ bool GeometryUtil<T>::pointOnBoundary(const Point<T>& p, const Point<T>& p1, con
}
template <typename T>
-bool GeometryUtil<T>::segmentIntersectSegment(const Point<T>& a,
- const Point<T>& b,
- const Point<T>& c,
- const Point<T>& d) {
+bool segmentIntersectSegment(const Point<T>& a, const Point<T>& b, const Point<T>& c, const Point<T>& d) {
// a, b are end points for line segment1, c and d are end points for line segment2
const auto perp = [](const Point<T>& v1, const Point<T>& v2) { return (v1.x * v2.y - v1.y * v2.x); };
@@ -58,7 +73,7 @@ bool GeometryUtil<T>::segmentIntersectSegment(const Point<T>& a,
}
template <typename T>
-bool GeometryUtil<T>::lineIntersectPolygon(const Point<T>& p1, const Point<T>& p2, const Polygon<T>& polygon) {
+bool lineIntersectPolygon(const Point<T>& p1, const Point<T>& p2, const Polygon<T>& polygon) {
for (auto ring : polygon) {
auto length = ring.size();
// loop through every edge of the ring
@@ -73,7 +88,7 @@ bool GeometryUtil<T>::lineIntersectPolygon(const Point<T>& p1, const Point<T>& p
// ray casting algorithm for detecting if point is in polygon
template <typename T>
-bool GeometryUtil<T>::pointWithinPolygon(const Point<T>& point, const Polygon<T>& polygon, bool trueOnBoundary) {
+bool pointWithinPolygon(const Point<T>& point, const Polygon<T>& polygon, bool trueOnBoundary) {
bool within = false;
for (const auto& ring : polygon) {
const auto length = ring.size();
@@ -89,7 +104,7 @@ bool GeometryUtil<T>::pointWithinPolygon(const Point<T>& point, const Polygon<T>
}
template <typename T>
-bool GeometryUtil<T>::pointWithinPolygons(const Point<T>& point, const MultiPolygon<T>& polygons, bool trueOnBoundary) {
+bool pointWithinPolygons(const Point<T>& point, const MultiPolygon<T>& polygons, bool trueOnBoundary) {
for (const auto& polygon : polygons) {
if (pointWithinPolygon(point, polygon, trueOnBoundary)) return true;
}
@@ -97,7 +112,7 @@ bool GeometryUtil<T>::pointWithinPolygons(const Point<T>& point, const MultiPoly
}
template <typename T>
-bool GeometryUtil<T>::lineStringWithinPolygon(const LineString<T>& line, const Polygon<T>& polygon) {
+bool lineStringWithinPolygon(const LineString<T>& line, const Polygon<T>& polygon) {
const auto length = line.size();
// First, check if geometry points of line segments are all inside polygon
for (std::size_t i = 0; i < length; ++i) {
@@ -116,14 +131,35 @@ bool GeometryUtil<T>::lineStringWithinPolygon(const LineString<T>& line, const P
}
template <typename T>
-bool GeometryUtil<T>::lineStringWithinPolygons(const LineString<T>& line, const MultiPolygon<T>& polygons) {
+bool lineStringWithinPolygons(const LineString<T>& line, const MultiPolygon<T>& polygons) {
for (const auto& polygon : polygons) {
if (lineStringWithinPolygon(line, polygon)) return true;
}
return false;
}
-template struct GeometryUtil<double>;
-template struct GeometryUtil<int64_t>;
+template void updateBBox(GeometryBBox<int64_t>& bbox, const Point<int64_t>& p);
+template bool boxWithinBox(const GeometryBBox<int64_t>& bbox1, const GeometryBBox<int64_t>& bbox2);
+template bool segmentIntersectSegment(const Point<int64_t>& a,
+ const Point<int64_t>& b,
+ const Point<int64_t>& c,
+ const Point<int64_t>& d);
+template bool rayIntersect(const Point<int64_t>& p, const Point<int64_t>& p1, const Point<int64_t>& p2);
+template bool pointOnBoundary(const Point<int64_t>& p, const Point<int64_t>& p1, const Point<int64_t>& p2);
+template bool lineIntersectPolygon(const Point<int64_t>& p1, const Point<int64_t>& p2, const Polygon<int64_t>& polygon);
+template bool pointWithinPolygon(const Point<int64_t>& point,
+ const Polygon<int64_t>& polygon,
+ bool trueOnBoundary = false);
+template bool pointWithinPolygons(const Point<int64_t>& point,
+ const MultiPolygon<int64_t>& polygons,
+ bool trueOnBoundary = false);
+template bool lineStringWithinPolygon(const LineString<int64_t>& line, const Polygon<int64_t>& polygon);
+template bool lineStringWithinPolygons(const LineString<int64_t>& line, const MultiPolygon<int64_t>& polygons);
+
+template void updateBBox(GeometryBBox<double>& bbox, const Point<double>& p);
+template bool segmentIntersectSegment(const Point<double>& a,
+ const Point<double>& b,
+ const Point<double>& c,
+ const Point<double>& d);
} // namespace mbgl
View Lorry Controller Status