KOSMIndoorMap

scenegeometry.cpp
1 /*
2  SPDX-FileCopyrightText: 2020 Volker Krause <[email protected]>
3 
4  SPDX-License-Identifier: LGPL-2.0-or-later
5 */
6 
7 #include "scenegeometry_p.h"
8 
9 #include <QDebug>
10 #include <QLineF>
11 #include <QPainterPath>
12 #include <QPolygonF>
13 
14 #include <cmath>
15 
16 using namespace KOSMIndoorMap;
17 
18 double SceneGeometry::polylineLength(const QPolygonF &poly)
19 {
20  if (poly.size() <= 1) {
21  return 0.0;
22  }
23 
24  double lineLength = 0.0;
25  QPointF p1 = poly.at(0);
26  for (auto it = std::next(poly.begin()); it != poly.end(); ++it) {
27  lineLength += QLineF(p1, *it).length();
28  p1 = *it;
29  }
30  return lineLength;
31 }
32 
33 QPointF SceneGeometry::polylineMidPoint(const QPolygonF &poly)
34 {
35  const auto lineLength = polylineLength(poly);
36  if (lineLength <= 0.0) {
37  return {};
38  }
39 
40  double length = 0.0;
41  auto p1 = poly.at(0);
42  for (auto it = std::next(poly.begin()); it != poly.end(); ++it) {
43  const QLineF line(p1, *it);
44  const auto l = line.length();
45 
46  if (length + l < lineLength / 2.0) {
47  length += l;
48  } else {
49  const auto r = ((length + l) - lineLength / 2.0) / l;
50  return line.pointAt(1 - r);
51  }
52 
53  p1 = *it;
54  }
55 
56  return {};
57 }
58 
59 double SceneGeometry::polylineMidPointAngle(const QPolygonF &path)
60 {
61  const auto lineLength = polylineLength(path);
62  if (lineLength <= 0.0) {
63  return 0.0;
64  }
65 
66  double length = 0.0;
67  auto p1 = path.at(0);
68  for (auto it = std::next(path.begin()); it != path.end(); ++it) {
69  const QLineF line(p1, *it);
70  const auto l = line.length();
71 
72  if (length + l < lineLength / 2.0) {
73  length += l;
74  } else {
75  auto a = - std::remainder(line.angle(), 360.0);
76  if (a < -90.0 || a > 90.0) {
77  a += 180.0;
78  }
79  return a;
80  }
81 
82  p1 = *it;
83  }
84 
85  return 0.0;
86 }
87 
88 /* the algorithm in here would be pretty simple (see https://en.wikipedia.org/wiki/Polygon#Centroid)
89  * if it weren't for numeric stability. We need something that keeps sufficient precision (~7 digits)
90  * in the range of +/- m * n² for n being the largest coordinate value, and m the polygon size.
91  * To help with that we:
92  * - move the polygon bbox center to 0/0. This works as we usually only look at very small areas.
93  * - scale the value by the bbox size, to enable the use of 64bit integers for the intermediate values.
94  * - use 64 bit integers for the intermediate values, as those contain squares of the coordinates
95  * and thus become very large. As we don't use divisions on the intermediate values, integers work for this.
96  */
97 QPointF SceneGeometry::polygonCentroid(const QPolygonF &poly)
98 {
99  if (poly.size() < 3) {
100  return {};
101  }
102 
103  const auto bbox = poly.boundingRect();
104  const auto offset = bbox.center();
105  const auto scale = 1.0e6 / std::max(bbox.width(), bbox.height());
106 
107  int64_t a = 0.0;
108  int64_t cx = 0.0;
109  int64_t cy = 0.0;
110 
111  for (int i = 0; i < poly.size(); ++i) {
112  const auto p1 = poly.at(i) - offset;
113  const int64_t x1 = p1.x() * scale;
114  const int64_t y1 = p1.y() * scale;
115 
116  const auto p2 = poly.at((i + 1) % poly.size()) - offset;
117  const int64_t x2 = p2.x() * scale;
118  const int64_t y2 = p2.y() * scale;
119 
120  a += (x1 * y2) - (x2 * y1);
121  cx += (x1 + x2) * (x1 * y2 - x2 * y1);
122  cy += (y1 + y2) * (x1 * y2 - x2 * y1);
123  }
124 
125  if (a == 0) {
126  return {};
127  }
128 
129  cx /= 3 * a;
130  cy /= 3 * a;
131 
132  return QPointF((double)cx / scale, (double)cy / scale) + offset;
133 }
134 
135 void SceneGeometry::outerPolygonFromPath(const QPainterPath &path, QPolygonF &poly)
136 {
137  if (path.isEmpty()) {
138  return;
139  }
140 
141  poly.clear();
142  poly.reserve(path.elementCount());
143  poly.push_back(path.elementAt(0));
144  for (int i = 1; i < path.elementCount(); ++i) {
145  const auto e = path.elementAt(i);
146  if (e.type != QPainterPath::LineToElement) {
147  return;
148  }
149  poly.push_back(e);
150  }
151 }
152 
153 double SceneGeometry::distanceToLine(const QLineF &line, QPointF p)
154 {
155  const auto len = line.length();
156  if (len == 0.0) {
157  return QLineF(line.p1(), p).length();
158  }
159 
160  // project p on a line extending the line segment given by @p line, and clamp to that to the segment
161  const auto r = qBound(0.0, QPointF::dotProduct(p - line.p1(), line.p2() - line.p1()) / (len*len), 1.0);
162  const auto intersection = line.p1() + r * (line.p2() - line.p1());
163  return QLineF(intersection, p).length();
164 
165 }
OSM-based multi-floor indoor maps for buildings.
QVector::iterator begin()
QPainterPath::Element elementAt(int index) const const
int elementCount() const const
void clear()
qreal length() const const
qreal x() const const
qreal y() const const
QPointF p1() const const
QPointF p2() const const
QPointF center() const const
void reserve(int size)
const T & at(int i) const const
QRectF boundingRect() const const
bool isEmpty() const const
void push_back(const T &value)
qreal dotProduct(const QPointF &p1, const QPointF &p2)
int size() const const
QVector::iterator end()
This file is part of the KDE documentation.
Documentation copyright © 1996-2021 The KDE developers.
Generated on Mon Oct 25 2021 23:04:00 by doxygen 1.8.11 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.