KOSMIndoorMap

poleofinaccessibilityfinder.cpp
1 /*
2  SPDX-FileCopyrightText: 2021 Volker Krause <[email protected]>
3 
4  SPDX-License-Identifier: LGPL-2.0-or-later
5 */
6 
7 #include "poleofinaccessibilityfinder_p.h"
8 #include "scenegeometry_p.h"
9 
10 #include <QDebug>
11 #include <QLineF>
12 #include <QPolygonF>
13 
14 #include <cmath>
15 #include <limits>
16 
17 using namespace KOSMIndoorMap;
18 
19 /** Signed distance from @p point to @p polygon, sign indicates inside/outside distance. */
20 static double pointToPolygonDistance(const QPointF &point, const QPolygonF &poly)
21 {
22  auto dist = std::numeric_limits<double>::max();
23  for (auto i = 0; i < poly.size(); ++i) {
24  const auto p1 = poly.at(i);
25  const auto p2 = poly.at((i + 1) % poly.size());
26  dist = std::min(dist, SceneGeometry::distanceToLine(QLineF(p1, p2), point));
27  }
28  return poly.containsPoint(point, Qt::OddEvenFill) ? dist : -dist;
29 }
30 
31 void PoleOfInaccessibilityFinder::CellPriorityQueue::clear()
32 {
33  c.clear();
34 }
35 
36 
37 PoleOfInaccessibilityFinder::Cell::Cell(const QPointF &_center, double _size, const QPolygonF &poly)
38  : center(_center)
39  , size(_size)
40  , distance(pointToPolygonDistance(_center, poly))
41 {
42 }
43 
44 double PoleOfInaccessibilityFinder::Cell::maximumDistance() const
45 {
46  return distance + size * std::sqrt(2.0);
47 }
48 
49 bool PoleOfInaccessibilityFinder::Cell::operator<(const PoleOfInaccessibilityFinder::Cell &other) const
50 {
51  return maximumDistance() < other.maximumDistance();
52 }
53 
54 
55 PoleOfInaccessibilityFinder::PoleOfInaccessibilityFinder() = default;
56 PoleOfInaccessibilityFinder::~PoleOfInaccessibilityFinder() = default;
57 
58 QPointF PoleOfInaccessibilityFinder::find(const QPolygonF &poly)
59 {
60  const auto boundingBox = poly.boundingRect();
61  const auto cellSize = std::min(boundingBox.width(), boundingBox.height());
62  auto h = cellSize / 2.0;
63  if (cellSize == 0.0) {
64  return boundingBox.center();
65  }
66 
67  // cover polygon with initial cells
68  for (auto x = boundingBox.left(); x < boundingBox.right(); x += cellSize) {
69  for (auto y = boundingBox.top(); y < boundingBox.bottom(); y += cellSize) {
70  m_queue.push(Cell(QPointF(x + h, y + h), h, poly));
71  }
72  }
73 
74  // initial guesses
75  auto bestCell = Cell(SceneGeometry::polygonCentroid(poly), 0, poly);
76  const auto bboxCell = Cell(boundingBox.center(), 0, poly);
77  if (bboxCell.distance > bestCell.distance) {
78  bestCell = bboxCell;
79  }
80 
81  while (!m_queue.empty()) {
82  auto cell = m_queue.top();
83  m_queue.pop();
84 
85  if (cell.distance > bestCell.distance) {
86  bestCell = cell;
87  }
88  // don't recurse into cells that can't provide a better result
89  if (cell.maximumDistance() - bestCell.distance <= 0.00002) {
90  continue;
91  }
92 
93  h = cell.size / 2.0;
94  m_queue.push(Cell(QPointF(cell.center.x() - h, cell.center.y() - h), h, poly));
95  m_queue.push(Cell(QPointF(cell.center.x() + h, cell.center.y() - h), h, poly));
96  m_queue.push(Cell(QPointF(cell.center.x() - h, cell.center.y() + h), h, poly));
97  m_queue.push(Cell(QPointF(cell.center.x() + h, cell.center.y() + h), h, poly));
98  }
99 
100  m_queue.clear();
101  return bestCell.center;
102 }
OSM-based multi-floor indoor maps for buildings.
OddEvenFill
QTextStream & center(QTextStream &stream)
QPointF center() const const
bool containsPoint(const QPointF &point, Qt::FillRule fillRule) const const
int distance(const GeoCoordinates &coord1, const GeoCoordinates &coord2)
const T & at(int i) const const
QRectF boundingRect() const const
int size() const const
This file is part of the KDE documentation.
Documentation copyright © 1996-2021 The KDE developers.
Generated on Sat Oct 23 2021 23:03:45 by doxygen 1.8.11 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.