From 5779661ba629eff1ffaf3a38c842b74250100bb1 Mon Sep 17 00:00:00 2001 From: Paolo Angelelli Date: Tue, 27 Feb 2018 17:24:33 +0100 Subject: Fix Clipper screwing polyline topology during clipping This fix uses a different polyline clipping algorithm to do line-polygon clipping which uses Clipper internally only to do inside/outside testing. Among other things, this method appears to be much faster than the older one. Task-number: QTBUG-66692 Task-number: QTBUG-66830 Change-Id: I2ed6f46c5d9d426a740611bec13aff69be49eb2a Reviewed-by: Qt CI Bot Reviewed-by: Eskil Abrahamsen Blomfeldt --- .../qdeclarativepolylinemapitem.cpp | 188 ++++++++++++++++++++- src/location/maps/qgeoprojection.cpp | 29 ++++ src/location/maps/qgeoprojection_p.h | 2 + 3 files changed, 213 insertions(+), 6 deletions(-) (limited to 'src/location') diff --git a/src/location/declarativemaps/qdeclarativepolylinemapitem.cpp b/src/location/declarativemaps/qdeclarativepolylinemapitem.cpp index 473c92ff..5e843dd1 100644 --- a/src/location/declarativemaps/qdeclarativepolylinemapitem.cpp +++ b/src/location/declarativemaps/qdeclarativepolylinemapitem.cpp @@ -54,9 +54,189 @@ #include #include +#include QT_BEGIN_NAMESPACE + +static const double kClipperScaleFactor = 281474976710656.0; // 48 bits of precision +static const double kClipperScaleFactorInv = 1.0 / kClipperScaleFactor; + +static inline IntPoint toIntPoint(const double x, const double y) +{ + return IntPoint(cInt(x * kClipperScaleFactor), cInt(y * kClipperScaleFactor)); +} + +static IntPoint toIntPoint(const QDoubleVector2D &p) +{ + return toIntPoint(p.x(), p.y()); +} + +static bool get_line_intersection(const double p0_x, + const double p0_y, + const double p1_x, + const double p1_y, + const double p2_x, + const double p2_y, + const double p3_x, + const double p3_y, + double *i_x, + double *i_y, + double *i_t) +{ + const double s10_x = p1_x - p0_x; + const double s10_y = p1_y - p0_y; + const double s32_x = p3_x - p2_x; + const double s32_y = p3_y - p2_y; + + const double denom = s10_x * s32_y - s32_x * s10_y; + if (denom == 0.0) + return false; // Collinear + const bool denomPositive = denom > 0; + + const double s02_x = p0_x - p2_x; + const double s02_y = p0_y - p2_y; + const double s_numer = s10_x * s02_y - s10_y * s02_x; + if ((s_numer < 0.0) == denomPositive) + return false; // No collision + + const double t_numer = s32_x * s02_y - s32_y * s02_x; + if ((t_numer < 0.0) == denomPositive) + return false; // No collision + + if (((s_numer > denom) == denomPositive) || ((t_numer > denom) == denomPositive)) + return false; // No collision + // Collision detected + *i_t = t_numer / denom; + *i_x = p0_x + (*i_t * s10_x); + *i_y = p0_y + (*i_t * s10_y); + + return true; +} + +enum SegmentType { + NoIntersection, + OneIntersection, + TwoIntersections +}; + +static QList > clipLine( + const QList &l, + const QList &poly) +{ + QList > res; + if (poly.size() < 3 || l.size() < 2) + return res; + + // Step 1: build edges + std::vector > edges; + for (int i = 1; i < poly.size(); i++) + edges.push_back({ { poly.at(i-1).x(), poly.at(i-1).y(), poly.at(i).x(), poly.at(i).y() } }); + edges.push_back({ { poly.at(poly.size()-1).x(), poly.at(poly.size()-1).y(), poly.at(0).x(), poly.at(0).y() } }); + + // Build Path to check for containment, for edges not intersecting + // This step could be speeded up by forcing the orientation of the polygon, and testing the cross products in the step + // below, thus avoiding to resort to clipper. + Path clip; + for (const auto &v: poly) + clip.push_back(toIntPoint(v)); + + // Step 2: check each segment against each edge + QList subLine; + std::array intersections = { { 0.0, 0.0, 0.0, 0.0 } }; + + for (int i = 0; i < l.size() - 1; ++i) { + SegmentType type = NoIntersection; + double t = -1; // valid values are in [0, 1]. Only written if intersects + double previousT = t; + double i_x, i_y; + + const int firstContained = c2t::clip2tri::pointInPolygon(toIntPoint(l.at(i).x(), l.at(i).y()), clip); + const int secondContained = c2t::clip2tri::pointInPolygon(toIntPoint(l.at(i+1).x(), l.at(i+1).y()), clip); + + if (firstContained && secondContained) { // Second most common condition, test early and skip inner loop if possible + if (!subLine.size()) + subLine.push_back(l.at(i)); // the initial element has to be pushed now. + subLine.push_back(l.at(i+1)); + continue; + } + + for (unsigned int j = 0; j < edges.size(); ++j) { + const bool intersects = get_line_intersection(l.at(i).x(), + l.at(i).y(), + l.at(i+1).x(), + l.at(i+1).y(), + edges.at(j).at(0), + edges.at(j).at(1), + edges.at(j).at(2), + edges.at(j).at(3), + &i_x, + &i_y, + &t); + if (intersects) { + if (previousT >= 0.0) { //One intersection already hit + if (t < previousT) { // Reorder + intersections[2] = intersections[0]; + intersections[3] = intersections[1]; + intersections[0] = i_x; + intersections[1] = i_y; + } else { + intersections[2] = i_x; + intersections[3] = i_y; + } + + type = TwoIntersections; + break; // no need to check anything else + } else { // First intersection + intersections[0] = i_x; + intersections[1] = i_y; + type = OneIntersection; + } + previousT = t; + } + } + + if (type == NoIntersection) { + if (!firstContained && !secondContained) { // Both outside + subLine.clear(); + } else if (firstContained && secondContained) { + // Handled above already. + } else { // Mismatch between PointInPolygon and get_line_intersection. Treat it as no intersection + if (subLine.size()) + res.push_back(subLine); + subLine.clear(); + } + } else if (type == OneIntersection) { // Need to check the following cases to avoid mismatch with PointInPolygon result. + if (firstContained <= 0 && secondContained > 0) { // subLine MUST be empty + if (!subLine.size()) + subLine.push_back(QDoubleVector2D(intersections[0], intersections[1])); + subLine.push_back(l.at(i+1)); + } else if (firstContained > 0 && secondContained <= 0) { // subLine MUST NOT be empty + if (!subLine.size()) + subLine.push_back(l.at(i)); + subLine.push_back(QDoubleVector2D(intersections[0], intersections[1])); + res.push_back(subLine); + subLine.clear(); + } else { + if (subLine.size()) + res.push_back(subLine); + subLine.clear(); + } + } else { // Two + // restart strip + subLine.clear(); + subLine.push_back(QDoubleVector2D(intersections[0], intersections[1])); + subLine.push_back(QDoubleVector2D(intersections[2], intersections[3])); + res.push_back(subLine); + subLine.clear(); + } + } + + if (subLine.size()) + res.push_back(subLine); + return res; +} + /*! \qmltype MapPolyline \instantiates QDeclarativePolylineMapItem @@ -226,13 +406,9 @@ QList > QGeoMapPolylineGeometry::clipPath(const QGeoMap & // 2) QList > clippedPaths; - const QList &visibleRegion = p.projectableGeometry(); + const QList &visibleRegion = p.visibleGeometryExpanded(); if (visibleRegion.size()) { - c2t::clip2tri clipper; - clipper.addSubjectPath(QClipperUtils::qListToPath(wrappedPath), false); - clipper.addClipPolygon(QClipperUtils::qListToPath(visibleRegion)); - Paths res = clipper.execute(c2t::clip2tri::Intersection); - clippedPaths = QClipperUtils::pathsToQList(res); + clippedPaths = clipLine(wrappedPath, visibleRegion); // 2.1) update srcOrigin_ and leftBoundWrapped with the point with minimum X QDoubleVector2D lb(qInf(), qInf()); diff --git a/src/location/maps/qgeoprojection.cpp b/src/location/maps/qgeoprojection.cpp index 1ab9970b..a99656c6 100644 --- a/src/location/maps/qgeoprojection.cpp +++ b/src/location/maps/qgeoprojection.cpp @@ -385,6 +385,13 @@ QList QGeoProjectionWebMercator::visibleGeometry() const return m_visibleRegion; } +QList QGeoProjectionWebMercator::visibleGeometryExpanded() const +{ + if (m_visibleRegionDirty) + const_cast(this)->updateVisibleRegion(); + return m_visibleRegionExpanded; +} + QList QGeoProjectionWebMercator::projectableGeometry() const { if (m_visibleRegionDirty) @@ -668,6 +675,28 @@ void QGeoProjectionWebMercator::updateVisibleRegion() else m_projectableRegion = viewportRect; } + + // Compute m_visibleRegionExpanded as a clipped expanded version of m_visibleRegion + QDoubleVector2D centroid; + for (const QDoubleVector2D &v: qAsConst(m_visibleRegion)) + centroid += v; + centroid /= m_visibleRegion.size(); + + m_visibleRegionExpanded.clear(); + for (const QDoubleVector2D &v: qAsConst(m_visibleRegion)) { + const QDoubleVector2D vc = v - centroid; + m_visibleRegionExpanded.push_back(centroid + vc * 1.05); // fixing expansion factor to 1.05 + } + + c2t::clip2tri clipperExpanded; + clipperExpanded.clearClipper(); + clipperExpanded.addSubjectPath(QClipperUtils::qListToPath(m_visibleRegionExpanded), true); + clipperExpanded.addClipPolygon(QClipperUtils::qListToPath(m_projectableRegion)); + Paths resVisibleExpanded = clipperExpanded.execute(c2t::clip2tri::Intersection); + if (resVisibleExpanded.size()) + m_visibleRegionExpanded = QClipperUtils::pathToQList(resVisibleExpanded[0]); // Intersection between two convex quadrilaterals should always be a single polygon + else + m_visibleRegionExpanded = m_visibleRegion; } QGeoCameraData QGeoProjectionWebMercator::cameraData() const diff --git a/src/location/maps/qgeoprojection_p.h b/src/location/maps/qgeoprojection_p.h index dc05d4d1..b0fffa28 100644 --- a/src/location/maps/qgeoprojection_p.h +++ b/src/location/maps/qgeoprojection_p.h @@ -152,6 +152,7 @@ public: bool isProjectable(const QDoubleVector2D &wrappedProjection) const; QList visibleGeometry() const; + QList visibleGeometryExpanded() const; QList projectableGeometry() const; inline QDoubleVector2D viewportToWrappedMapProjection(const QDoubleVector2D &itemPosition) const; @@ -230,6 +231,7 @@ private: Line2D m_nearPlaneMapIntersection; QList m_visibleRegion; + QList m_visibleRegionExpanded; QList m_projectableRegion; bool m_visibleRegionDirty; -- cgit v1.2.1