diff --git a/autotests/scenegeometrytest.cpp b/autotests/scenegeometrytest.cpp index 77a9c19..fbc94c7 100644 --- a/autotests/scenegeometrytest.cpp +++ b/autotests/scenegeometrytest.cpp @@ -1,79 +1,103 @@ /* Copyright (C) 2020 Volker Krause This program is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see . */ #include #include #include +#include + using namespace KOSMIndoorMap; class SceneGeometryTest: public QObject { Q_OBJECT private Q_SLOTS: void testPolygonCenter() { QPolygonF p1{{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}}; QCOMPARE(SceneGeometry::polygonCentroid(p1), QPointF(0, 0)); QPolygonF p2{{{0, 1}, {1, 1}, {1, 0}, {0, 0}}}; QCOMPARE(SceneGeometry::polygonCentroid(p2), QPointF(0.5, 0.5)); QPolygonF p3{{{0, 1}, {1, 0}, {0, -1}, {-0.5, -0.5}, {-1, 0}}}; QCOMPARE(SceneGeometry::polygonCentroid(p3), QPointF(0, 0)); QPolygonF p4{{{0.273, 0.146}, {0.423, 0.496}, {0.415, 0.499}, {0.266, 0.149}}}; // QCOMPARE((SceneGeometry::polygonCentroid(p4) * 1000000).toPoint(), QPoint(345669, 325821)); // make the test pass on 32bit platforms too QCOMPARE((SceneGeometry::polygonCentroid(p4) * 1000000).toPoint().x(), 345669); QVERIFY((SceneGeometry::polygonCentroid(p4) * 1000000).toPoint().y() >= 325821); QVERIFY((SceneGeometry::polygonCentroid(p4) * 1000000).toPoint().y() <= 325822); QPolygonF p5{{{273, 146}, {423, 496}, {415, 499}, {266, 149}}}; // QCOMPARE((SceneGeometry::polygonCentroid(p5) * 1000).toPoint(), QPoint(345669, 325821)); // make the test pass on 32bit platforms too QCOMPARE((SceneGeometry::polygonCentroid(p5) * 1000).toPoint().x(), 345669); QVERIFY((SceneGeometry::polygonCentroid(p5) * 1000).toPoint().y() >= 325821); QVERIFY((SceneGeometry::polygonCentroid(p5) * 1000).toPoint().y() <= 325822); } void testLineMidPoint() { QPolygonF p1{{{1,1}, {2,2}, {2,2}}}; QCOMPARE(SceneGeometry::polylineMidPoint(p1), QPointF(1.5, 1.5)); QPolygonF p2{{{1,1}, {2,2}, {3,3}}}; QCOMPARE(SceneGeometry::polylineMidPoint(p2), QPointF(2, 2)); QPolygonF p3{{{1,1}, {2,2}, {21,21}}}; QCOMPARE(SceneGeometry::polylineMidPoint(p3), QPointF(11, 11)); } void testPathAngle() { QPolygonF p1{{{1,1}, {2,2}, {2,2}}}; QCOMPARE(SceneGeometry::polylineMidPointAngle(p1), 45.0); QPolygonF p2{{{1,1}, {2,2}, {2,20}}}; QCOMPARE(SceneGeometry::polylineMidPointAngle(p2), 90.0); } + + void testDistanceToLine() + { + QLineF line({1,1}, {3, 1}); + QCOMPARE(SceneGeometry::distanceToLine(line, {0, 1}), 1.0); + QCOMPARE(SceneGeometry::distanceToLine(line, {1, 1}), 0.0); + QCOMPARE(SceneGeometry::distanceToLine(line, {2, 1}), 0.0); + QCOMPARE(SceneGeometry::distanceToLine(line, {3, 1}), 0.0); + QCOMPARE(SceneGeometry::distanceToLine(line, {4, 1}), 1.0); + + QCOMPARE(SceneGeometry::distanceToLine(line, {0, 2}), std::sqrt(2.0)); + QCOMPARE(SceneGeometry::distanceToLine(line, {1, 2}), 1.0); + QCOMPARE(SceneGeometry::distanceToLine(line, {2, 2}), 1.0); + QCOMPARE(SceneGeometry::distanceToLine(line, {3, 2}), 1.0); + QCOMPARE(SceneGeometry::distanceToLine(line, {4, 2}), std::sqrt(2.0)); + + QCOMPARE(SceneGeometry::distanceToLine(line, {0, 0}), std::sqrt(2.0)); + QCOMPARE(SceneGeometry::distanceToLine(line, {1, 0}), 1.0); + QCOMPARE(SceneGeometry::distanceToLine(line, {2, 0}), 1.0); + QCOMPARE(SceneGeometry::distanceToLine(line, {3, 0}), 1.0); + QCOMPARE(SceneGeometry::distanceToLine(line, {4, 0}), std::sqrt(2.0)); + } }; QTEST_GUILESS_MAIN(SceneGeometryTest) #include "scenegeometrytest.moc" diff --git a/src/map/renderer/hitdetector.cpp b/src/map/renderer/hitdetector.cpp index 3e0fe6c..d0a3cb6 100644 --- a/src/map/renderer/hitdetector.cpp +++ b/src/map/renderer/hitdetector.cpp @@ -1,88 +1,111 @@ /* Copyright (C) 2020 Volker Krause This program is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see . */ #include "hitdetector.h" #include "../scene/scenegraph.h" #include "../scene/scenegraphitem.h" +#include "../scene/scenegeometry.h" #include "view.h" using namespace KOSMIndoorMap; const SceneGraphItem* HitDetector::itemAt(QPointF pos, const SceneGraph& sg, const View* view) const { for (auto it = sg.items().rbegin(); it != sg.items().rend(); ++it) { if (!(*it).payload->boundingRect().contains(view->mapScreenToScene(pos))) { continue; } if (!itemContainsPoint((*it), pos, view)) { continue; } return &(*it); } return nullptr; } std::vector HitDetector::itemsAt(QPointF pos, const SceneGraph &sg, const View *view) const { std::vector result; for (const auto &item : sg.items()) { if (!item.payload->boundingRect().contains(view->mapScreenToScene(pos))) { continue; } if (!itemContainsPoint(item, pos, view)) { continue; } result.push_back(&item); } return result; } bool HitDetector::itemContainsPoint(const SceneGraphItem &item, QPointF screenPos, const View *view) const { if (const auto i = dynamic_cast(item.payload.get())) { return itemContainsPoint(i, view->mapScreenToScene(screenPos)); } if (const auto i = dynamic_cast(item.payload.get())) { return itemContainsPoint(i, view->mapScreenToScene(screenPos)); } + if (const auto i = dynamic_cast(item.payload.get())) { + return itemContainsPoint(i, view->mapScreenToScene(screenPos), view); + } if (const auto i = dynamic_cast(item.payload.get())) { return itemContainsPoint(i, screenPos, view); } // TODO polyline return true; } bool HitDetector::itemContainsPoint(const MultiPolygonItem *item, QPointF scenePos) const { return item->path.contains(scenePos); } bool HitDetector::itemContainsPoint(const PolygonItem *item, QPointF scenePos) const { return item->polygon.containsPoint(scenePos, Qt::OddEvenFill); } +bool HitDetector::itemContainsPoint(const PolylineItem *item, QPointF scenePos, const View *view) const +{ + if (item->path.size() < 2) { + return false; + } + + const auto lineWidth = view->mapMetersToScene(item->pen.widthF()) + + view->mapScreenDistanceToSceneDistance(item->casingPen.widthF()); + + double dist = std::numeric_limits::max(); + // TODO do we need to wrap around here for closed lines? + for (auto it = std::next(item->path.begin()); it != item->path.end(); ++it) { + QLineF line(*std::prev(it), *it); + dist = std::min(dist, SceneGeometry::distanceToLine(line, scenePos)); + } + + return dist <= lineWidth; +} + bool HitDetector::itemContainsPoint(const LabelItem *item, QPointF screenPos, const View *view) const { auto hitBox = item->bbox; hitBox.moveCenter(view->mapSceneToScreen(hitBox.center())); return hitBox.contains(screenPos); } diff --git a/src/map/renderer/hitdetector.h b/src/map/renderer/hitdetector.h index b8f1f61..4be7451 100644 --- a/src/map/renderer/hitdetector.h +++ b/src/map/renderer/hitdetector.h @@ -1,56 +1,58 @@ /* Copyright (C) 2020 Volker Krause This program is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see . */ #ifndef KOSMINDOORMAP_HITDETECTOR_H #define KOSMINDOORMAP_HITDETECTOR_H #include class QPointF; namespace KOSMIndoorMap { class LabelItem; class MultiPolygonItem; class PolygonItem; +class PolylineItem; class SceneGraph; class SceneGraphItem; class View; /** Picking hit detector. * Ie. find scene graph items at a given screen position. */ class HitDetector { public: /** Highest (in z-order) item at the given screen position. */ const SceneGraphItem* itemAt(QPointF pos, const SceneGraph &sg, const View *view) const; /** All items (in z-order) at the given screen position. */ std::vector itemsAt(QPointF pos, const SceneGraph &sg, const View *view) const; private: /** Precise bounds check for @p item. */ bool itemContainsPoint(const SceneGraphItem &item, QPointF screenPos, const View *view) const; bool itemContainsPoint(const MultiPolygonItem *item, QPointF scenePos) const; bool itemContainsPoint(const PolygonItem *item, QPointF scenePos) const; + bool itemContainsPoint(const PolylineItem *item, QPointF scenePos, const View *view) const; bool itemContainsPoint(const LabelItem *item, QPointF screenPos, const View *view) const; }; } #endif // KOSMINDOORMAP_HITDETECTOR_H diff --git a/src/map/scene/scenegeometry.cpp b/src/map/scene/scenegeometry.cpp index 9607f99..0d6fb4a 100644 --- a/src/map/scene/scenegeometry.cpp +++ b/src/map/scene/scenegeometry.cpp @@ -1,163 +1,177 @@ /* Copyright (C) 2020 Volker Krause This program is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see . */ #include "scenegeometry.h" #include #include #include #include #include using namespace KOSMIndoorMap; double SceneGeometry::polylineLength(const QPolygonF &poly) { if (poly.size() <= 1) { return 0.0; } double lineLength = 0.0; QPointF p1 = poly.at(0); for (auto it = std::next(poly.begin()); it != poly.end(); ++it) { lineLength += QLineF(p1, *it).length(); p1 = *it; } return lineLength; } QPointF SceneGeometry::polylineMidPoint(const QPolygonF &poly) { const auto lineLength = polylineLength(poly); if (lineLength <= 0.0) { return {}; } double length = 0.0; auto p1 = poly.at(0); for (auto it = std::next(poly.begin()); it != poly.end(); ++it) { const QLineF line(p1, *it); const auto l = line.length(); if (length + l < lineLength / 2.0) { length += l; } else { const auto r = ((length + l) - lineLength / 2.0) / l; return line.pointAt(1 - r); } p1 = *it; } return {}; } double SceneGeometry::polylineMidPointAngle(const QPolygonF &path) { const auto lineLength = polylineLength(path); if (lineLength <= 0.0) { return 0.0; } double length = 0.0; auto p1 = path.at(0); for (auto it = std::next(path.begin()); it != path.end(); ++it) { const QLineF line(p1, *it); const auto l = line.length(); if (length + l < lineLength / 2.0) { length += l; } else { const auto r = ((length + l) - lineLength / 2.0) / l; auto a = - std::remainder(line.angle(), 360.0); if (a < -90.0 || a > 90.0) { a += 180.0; } return a; } p1 = *it; } return 0.0; } /* the algorithm in here would be pretty simple (see https://en.wikipedia.org/wiki/Polygon#Centroid) * if it weren't for numeric stability. We need something that keeps sufficient precision (~7 digits) * in the range of +/- m * n² for n being the largest coordinate value, and m the polygon size. * To help with that we: * - move the polygon bbox center to 0/0. This works as we usually only look at very small areas. * - scale the value by the bbox size, to enable the use of 64bit integers for the intermediate values. * - use 64 bit integers for the intermediate values, as those contain squares of the coordinates * and thus become very large. As we don't use divisions on the intermediate values, integers work for this. */ QPointF SceneGeometry::polygonCentroid(const QPolygonF &poly) { if (poly.size() < 3) { return {}; } const auto bbox = poly.boundingRect(); const auto offset = bbox.center(); const auto scale = 1.0e6 / std::max(bbox.width(), bbox.height()); int64_t a = 0.0; int64_t cx = 0.0; int64_t cy = 0.0; for (int i = 0; i < poly.size(); ++i) { const auto p1 = poly.at(i) - offset; const int64_t x1 = p1.x() * scale; const int64_t y1 = p1.y() * scale; const auto p2 = poly.at((i + 1) % poly.size()) - offset; const int64_t x2 = p2.x() * scale; const int64_t y2 = p2.y() * scale; a += (x1 * y2) - (x2 * y1); cx += (x1 + x2) * (x1 * y2 - x2 * y1); cy += (y1 + y2) * (x1 * y2 - x2 * y1); } if (a == 0) { return {}; } cx /= 3 * a; cy /= 3 * a; return QPointF((double)cx / scale, (double)cy / scale) + offset; } void SceneGeometry::outerPolygonFromPath(const QPainterPath &path, QPolygonF &poly) { if (path.isEmpty()) { return; } poly.clear(); poly.reserve(path.elementCount()); poly.push_back(path.elementAt(0)); for (int i = 1; i < path.elementCount(); ++i) { const auto e = path.elementAt(i); if (e.type != QPainterPath::LineToElement) { return; } poly.push_back(e); } } + +double SceneGeometry::distanceToLine(const QLineF &line, QPointF p) +{ + const auto len = line.length(); + if (len == 0.0) { + return QLineF(line.p1(), p).length(); + } + + // project p on a line extending the line segment given by @p line, and clamp to that to the segment + const auto r = qBound(0.0, QPointF::dotProduct(p - line.p1(), line.p2() - line.p1()) / (len*len), 1.0); + const auto intersection = line.p1() + r * (line.p2() - line.p1()); + return QLineF(intersection, p).length(); + +} diff --git a/src/map/scene/scenegeometry.h b/src/map/scene/scenegeometry.h index 82be577..eba92e8 100644 --- a/src/map/scene/scenegeometry.h +++ b/src/map/scene/scenegeometry.h @@ -1,53 +1,57 @@ /* Copyright (C) 2020 Volker Krause This program is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see . */ #ifndef KOSMINDOORMAP_SCENEGEOMETRY_H #define KOSMINDOORMAP_SCENEGEOMETRY_H +class QLineF; class QPainterPath; class QPointF; class QPolygonF; namespace KOSMIndoorMap { /** Geometry related functions. */ namespace SceneGeometry { /** Centroid of a polygon. * @see https://en.wikipedia.org/wiki/Polygon#Centroid */ QPointF polygonCentroid(const QPolygonF &poly); /** Returns the lengths of the given polyline. */ double polylineLength(const QPolygonF &poly); /** Returns the point at equal distance between the ends on the given polygon. */ QPointF polylineMidPoint(const QPolygonF &poly); /** Rotation angle for a label placed at the middle of @p path. */ double polylineMidPointAngle(const QPolygonF &path); /** Returns the outer polygon of a painter path. * @note This is not generic, but makes assumptions about the painter path * structure that happen to hold of OSM input data. */ void outerPolygonFromPath(const QPainterPath &path, QPolygonF &poly); + + /** Computes the distance of the given line to the given point. */ + double distanceToLine(const QLineF &line, QPointF p); } } #endif // KOSMINDOORMAP_SCENEGEOMETRY_H