QGeoPath/QGeoPolygon: defer bbox computation

This patch introduces 2 versions of QGeoPath/polygon private:
a lazy version (default) and an eager version.
The reason is that certain classes such as MapItems make heavy use
of the bounding box of the geoshapes, as well as the contains
method, and in those cases it's beneficial to have it eagerly
computed and cached.

Other use cases do not see this feature so much in use, and the added
costs, both in terms of computation and in terms of memory requirements
for cached data can be avoided.

As the patch currently stands, using copy constructors for
QGeoPath and QGeoPolygon with a QGeoPathEager and a QGeoPolygonEager
(and vice-versa) changes the type of d_ptr.
This means that doing, for example, QGeoPath(someQGeoPathEager)
effectively returns a QGeoPath that behaves like a QGeoPathEager
(although not being one).

Change-Id: I8cfed1e0a747139d0fb6d5fb5236bf5f5fbf24c1
Reviewed-by: Alex Blasche <alexander.blasche@qt.io>

1 files changed, 182 insertions, 280 deletions

diff --git a/src/positioning/qgeopath.cpp b/src/positioning/qgeopath.cpp
index 31bff2f7..843b3f1b 100644
--- a/src/positioning/qgeopath.cpp
+++ b/src/positioning/qgeopath.cpp
@@ -114,7 +114,7 @@ Q_GLOBAL_STATIC(PathVariantConversions, initPathConversions)
     Constructs a new, empty geo path.
 */
 QGeoPath::QGeoPath()
-:   QGeoShape(new QGeoPathPrivate(QGeoShape::PathType))
+:   QGeoShape(new QGeoPathPrivate())
 {
     initPathConversions();
 }
@@ -124,7 +124,7 @@ QGeoPath::QGeoPath()
     (\a path and \a width).
 */
 QGeoPath::QGeoPath(const QList<QGeoCoordinate> &path, const qreal &width)
-:   QGeoShape(new QGeoPathPrivate(QGeoShape::PathType, path, width))
+:   QGeoShape(new QGeoPathPrivate(path, width))
 {
     initPathConversions();
 }
@@ -146,7 +146,7 @@ QGeoPath::QGeoPath(const QGeoShape &other)
 {
     initPathConversions();
     if (type() != QGeoShape::PathType)
-        d_ptr = new QGeoPathPrivate(QGeoShape::PathType);
+        d_ptr = new QGeoPathPrivate();
 }
 
 /*!
@@ -391,128 +391,70 @@ QString QGeoPath::toString() const
 }
 
 /*******************************************************************************
- * QGeoPathPrivate
+ *
+ * QGeoPathPrivate & friends
+ *
 *******************************************************************************/
 
-QGeoPathPrivate::QGeoPathPrivate(QGeoShape::ShapeType type)
-:   QGeoShapePrivate(type), m_width(0), m_clipperDirty(true)
+QGeoPathPrivate::QGeoPathPrivate()
+:   QGeoShapePrivate(QGeoShape::PathType)
 {
+
 }
 
-QGeoPathPrivate::QGeoPathPrivate(QGeoShape::ShapeType type, const QList<QGeoCoordinate> &path, const qreal width)
-:   QGeoShapePrivate(type), m_width(0), m_clipperDirty(true)
+QGeoPathPrivate::QGeoPathPrivate(const QList<QGeoCoordinate> &path, const qreal width)
+:   QGeoShapePrivate(QGeoShape::PathType)
 {
     setPath(path);
     setWidth(width);
 }
 
-QGeoPathPrivate::QGeoPathPrivate(const QGeoPathPrivate &other)
-:   QGeoShapePrivate(other.type), m_path(other.m_path),
-    m_deltaXs(other.m_deltaXs), m_minX(other.m_minX), m_maxX(other.m_maxX), m_minLati(other.m_minLati),
-    m_maxLati(other.m_maxLati), m_bbox(other.m_bbox), m_width(other.m_width), m_clipperDirty(true)
+QGeoPathPrivate::~QGeoPathPrivate()
 {
-}
 
-QGeoPathPrivate::~QGeoPathPrivate() {}
+}
 
 QGeoShapePrivate *QGeoPathPrivate::clone() const
 {
     return new QGeoPathPrivate(*this);
 }
 
-bool QGeoPathPrivate::operator==(const QGeoShapePrivate &other) const
-{
-    if (!QGeoShapePrivate::operator==(other))
-        return false;
-
-    const QGeoPathPrivate &otherPath = static_cast<const QGeoPathPrivate &>(other);
-    if (m_path.size() != otherPath.m_path.size())
-        return false;
-
-    if (type == QGeoShape::PathType)
-        return m_width == otherPath.m_width && m_path == otherPath.m_path;
-    else
-        return m_path == otherPath.m_path && m_holesList == otherPath.m_holesList;
-}
-
 bool QGeoPathPrivate::isValid() const
 {
-    if (type == QGeoShape::PathType)
-        return !isEmpty();
-    else
-        return m_path.size() > 2;
-
+    return !isEmpty();
 }
 
 bool QGeoPathPrivate::isEmpty() const
 {
-    return m_path.isEmpty(); // this should perhaps return geometric emptiness, less than 2 points for line, or empty polygon for polygons
-}
-
-const QList<QGeoCoordinate> &QGeoPathPrivate::path() const
-{
-    return m_path;
-}
-
-void QGeoPathPrivate::setPath(const QList<QGeoCoordinate> &path)
-{
-    for (const QGeoCoordinate &c: path)
-        if (!c.isValid())
-            return;
-    m_path = path;
-    computeBoundingBox();
-}
-
-void QGeoPathPrivate::clearPath()
-{
-    m_path.clear();
-    computeBoundingBox();
+    return path().isEmpty(); // this should perhaps return geometric emptiness, less than 2 points for line, or empty polygon for polygons
 }
 
-qreal QGeoPathPrivate::width() const
+QGeoCoordinate QGeoPathPrivate::center() const
 {
-    return m_width;
+    return boundingGeoRectangle().center();
 }
 
-void QGeoPathPrivate::setWidth(const qreal &width)
+void QGeoPathPrivate::extendShape(const QGeoCoordinate &coordinate)
 {
-    if (qIsNaN(width) || width < 0.0)
+    if (!coordinate.isValid() || contains(coordinate))
         return;
-    m_width = width;
+    addCoordinate(coordinate);
 }
 
-double QGeoPathPrivate::length(int indexFrom, int indexTo) const
+bool QGeoPathPrivate::operator==(const QGeoShapePrivate &other) const
 {
-    if (path().isEmpty())
-        return 0.0;
-
-    bool wrap = indexTo == -1;
-    if (indexTo < 0 || indexTo >= path().size())
-        indexTo = path().size() - 1;
-    double len = 0.0;
-    // TODO: consider calculating the length of the actual rhumb line segments
-    // instead of the shortest path from A to B.
-    for (int i = indexFrom; i < indexTo; i++)
-        len += m_path[i].distanceTo(m_path[i+1]);
-    if (wrap)
-        len += m_path.last().distanceTo(m_path.first());
-    return len;
-}
+    if (!QGeoShapePrivate::operator==(other))
+        return false;
 
-int QGeoPathPrivate::size() const
-{
-    return m_path.size();
+    const QGeoPathPrivate &otherPath = static_cast<const QGeoPathPrivate &>(other);
+    if (m_path.size() != otherPath.m_path.size())
+        return false;
+    return m_width == otherPath.m_width && m_path == otherPath.m_path;
 }
 
-/*!
-    Returns true if coordinate is present in m_path.
-*/
-bool QGeoPathPrivate::contains(const QGeoCoordinate &coordinate) const
+const QList<QGeoCoordinate> &QGeoPathPrivate::path() const
 {
-    if (type == QGeoShape::PathType)
-        return lineContains(coordinate);
-    else
-        return polygonContains(coordinate);
+    return m_path;
 }
 
 bool QGeoPathPrivate::lineContains(const QGeoCoordinate &coordinate) const
@@ -584,54 +526,67 @@ bool QGeoPathPrivate::lineContains(const QGeoCoordinate &coordinate) const
     return (m_path[0].distanceTo(coordinate) <= lineRadius);
 }
 
-/*!
-    modified version of polygonContains with holes support.
-*/
-bool QGeoPathPrivate::polygonContains(const QGeoCoordinate &coordinate) const
+bool QGeoPathPrivate::contains(const QGeoCoordinate &coordinate) const
 {
-    if (m_clipperDirty)
-        const_cast<QGeoPathPrivate *>(this)->updateClipperPath();
-
-    // iterates the holes List checking whether the point is contained inside the holes
-    for (const QList<QGeoCoordinate> &holePath : qAsConst(m_holesList)) {
+    return lineContains(coordinate);
+}
 
-        QGeoPolygon holePolygon;
-        holePolygon.setPath(holePath);
-        QGeoPath holeBoundary;
-        holeBoundary.setPath(holePath);
+qreal QGeoPathPrivate::width() const
+{
+    return m_width;
+}
 
-        if (holePolygon.contains(coordinate) && !(holeBoundary.contains(coordinate)))
-            return false;
-    }
+void QGeoPathPrivate::setWidth(const qreal &width)
+{
+    if (qIsNaN(width) || width < 0.0)
+        return;
+    m_width = width;
+}
 
-    QDoubleVector2D coord = QWebMercator::coordToMercator(coordinate);
-    double tlx = QWebMercator::coordToMercator(m_bbox.topLeft()).x();
-    if (coord.x() < tlx)
-        coord.setX(coord.x() + 1.0);
+double QGeoPathPrivate::length(int indexFrom, int indexTo) const
+{
+    if (path().isEmpty())
+        return 0.0;
 
-    IntPoint intCoord = QClipperUtils::toIntPoint(coord);
-    return c2t::clip2tri::pointInPolygon(intCoord, m_clipperPath) != 0;
+    bool wrap = indexTo == -1;
+    if (indexTo < 0 || indexTo >= path().size())
+        indexTo = path().size() - 1;
+    double len = 0.0;
+    // TODO: consider calculating the length of the actual rhumb line segments
+    // instead of the shortest path from A to B.
+    for (int i = indexFrom; i < indexTo; i++)
+        len += m_path[i].distanceTo(m_path[i+1]);
+    if (wrap)
+        len += m_path.last().distanceTo(m_path.first());
+    return len;
 }
 
-QGeoCoordinate QGeoPathPrivate::center() const
+int QGeoPathPrivate::size() const
 {
-    return boundingGeoRectangle().center();
+    return m_path.size();
 }
 
-QGeoRectangle QGeoPathPrivate::boundingGeoRectangle() const
+QGeoCoordinate QGeoPathPrivate::coordinateAt(int index) const
 {
-    return m_bbox;
+    if (index < 0 || index >= m_path.size())
+        return QGeoCoordinate();
+
+    return m_path.at(index);
 }
 
-void QGeoPathPrivate::extendShape(const QGeoCoordinate &coordinate)
+bool QGeoPathPrivate::containsCoordinate(const QGeoCoordinate &coordinate) const
 {
-    if (!coordinate.isValid() || contains(coordinate))
-        return;
-    addCoordinate(coordinate);
+    return m_path.indexOf(coordinate) > -1;
 }
 
 void QGeoPathPrivate::translate(double degreesLatitude, double degreesLongitude)
 {
+    // Need min/maxLati, so update bbox
+    QVector<double> m_deltaXs;
+    double m_minX, m_maxX, m_minLati, m_maxLati;
+    m_bboxDirty = false;
+    computeBBox(m_path, m_deltaXs, m_minX, m_maxX, m_minLati, m_maxLati, m_bbox);
+
     if (degreesLatitude > 0.0)
         degreesLatitude = qMin(degreesLatitude, 90.0 - m_maxLati);
     else
@@ -640,17 +595,29 @@ void QGeoPathPrivate::translate(double degreesLatitude, double degreesLongitude)
         p.setLatitude(p.latitude() + degreesLatitude);
         p.setLongitude(QLocationUtils::wrapLong(p.longitude() + degreesLongitude));
     }
-    if (!m_holesList.isEmpty()){
-        for (QList<QGeoCoordinate> &hole: m_holesList){
-            for (QGeoCoordinate &holeVertex: hole){
-                holeVertex.setLatitude(holeVertex.latitude() + degreesLatitude);
-                holeVertex.setLongitude(QLocationUtils::wrapLong(holeVertex.longitude() + degreesLongitude));
-            }
-        }
-    }
     m_bbox.translate(degreesLatitude, degreesLongitude);
-    m_minLati += degreesLatitude;
-    m_maxLati += degreesLatitude;
+}
+
+QGeoRectangle QGeoPathPrivate::boundingGeoRectangle() const
+{
+    if (m_bboxDirty)
+        const_cast<QGeoPathPrivate &>(*this).computeBoundingBox();
+    return m_bbox;
+}
+
+void QGeoPathPrivate::setPath(const QList<QGeoCoordinate> &path)
+{
+    for (const QGeoCoordinate &c: path)
+        if (!c.isValid())
+            return;
+    m_path = path;
+    markDirty();
+}
+
+void QGeoPathPrivate::clearPath()
+{
+    m_path.clear();
+    markDirty();
 }
 
 void QGeoPathPrivate::addCoordinate(const QGeoCoordinate &coordinate)
@@ -658,38 +625,23 @@ void QGeoPathPrivate::addCoordinate(const QGeoCoordinate &coordinate)
     if (!coordinate.isValid())
         return;
     m_path.append(coordinate);
-    updateBoundingBox();
+    markDirty();
 }
 
 void QGeoPathPrivate::insertCoordinate(int index, const QGeoCoordinate &coordinate)
 {
     if (index < 0 || index > m_path.size() || !coordinate.isValid())
         return;
-
     m_path.insert(index, coordinate);
-    computeBoundingBox();
+    markDirty();
 }
 
 void QGeoPathPrivate::replaceCoordinate(int index, const QGeoCoordinate &coordinate)
 {
     if (index < 0 || index >= m_path.size() || !coordinate.isValid())
         return;
-
     m_path[index] = coordinate;
-    computeBoundingBox();
-}
-
-QGeoCoordinate QGeoPathPrivate::coordinateAt(int index) const
-{
-    if (index < 0 || index >= m_path.size())
-        return QGeoCoordinate();
-
-    return m_path.at(index);
-}
-
-bool QGeoPathPrivate::containsCoordinate(const QGeoCoordinate &coordinate) const
-{
-    return m_path.indexOf(coordinate) > -1;
+    markDirty();
 }
 
 void QGeoPathPrivate::removeCoordinate(const QGeoCoordinate &coordinate)
@@ -702,171 +654,121 @@ void QGeoPathPrivate::removeCoordinate(int index)
 {
     if (index < 0 || index >= m_path.size())
         return;
-
     m_path.removeAt(index);
-    computeBoundingBox();
+    markDirty();
+}
+
+void QGeoPathPrivate::markDirty()
+{
+    m_bboxDirty = true;
 }
 
 void QGeoPathPrivate::computeBoundingBox()
 {
-    m_clipperDirty = true;
-    if (m_path.isEmpty()) {
-        m_deltaXs.clear();
-        m_minX = qInf();
-        m_maxX = -qInf();
-        m_minLati = qInf();
-        m_maxLati = -qInf();
-        m_bbox = QGeoRectangle();
-        return;
-    }
+    QVector<double> m_deltaXs;
+    double m_minX, m_maxX, m_minLati, m_maxLati;
+    m_bboxDirty = false;
+    computeBBox(m_path, m_deltaXs, m_minX, m_maxX, m_minLati, m_maxLati, m_bbox);
+}
 
-    m_minLati = m_maxLati = m_path.at(0).latitude();
-    int minId = 0;
-    int maxId = 0;
-    m_deltaXs.resize(m_path.size());
-    m_deltaXs[0] = m_minX = m_maxX = 0.0;
+QGeoPathPrivateEager::QGeoPathPrivateEager()
+:   QGeoPathPrivate()
+{
+    m_bboxDirty = false; // never dirty on the eager version
+}
 
-    for (int i = 1; i < m_path.size(); i++) {
-        const QGeoCoordinate &geoFrom = m_path.at(i-1);
-        const QGeoCoordinate &geoTo   = m_path.at(i);
-        double longiFrom    = geoFrom.longitude();
-        double longiTo      = geoTo.longitude();
-        double deltaLongi = longiTo - longiFrom;
-        if (qAbs(deltaLongi) > 180.0) {
-            if (longiTo > 0.0)
-                longiTo -= 360.0;
-            else
-                longiTo += 360.0;
-            deltaLongi =  longiTo - longiFrom;
-        }
-        m_deltaXs[i] = m_deltaXs[i-1] + deltaLongi;
-        if (m_deltaXs[i] < m_minX) {
-            m_minX = m_deltaXs[i];
-            minId = i;
-        }
-        if (m_deltaXs[i] > m_maxX) {
-            m_maxX = m_deltaXs[i];
-            maxId = i;
-        }
-        if (geoTo.latitude() > m_maxLati)
-            m_maxLati = geoTo.latitude();
-        if (geoTo.latitude() < m_minLati)
-            m_minLati = geoTo.latitude();
-    }
+QGeoPathPrivateEager::QGeoPathPrivateEager(const QList<QGeoCoordinate> &path, const qreal width)
+:   QGeoPathPrivate(path, width)
+{
+    m_bboxDirty = false; // never dirty on the eager version
+}
+
+QGeoPathPrivateEager::~QGeoPathPrivateEager()
+{
 
-    m_bbox = QGeoRectangle(QGeoCoordinate(m_maxLati, m_path.at(minId).longitude()),
-                           QGeoCoordinate(m_minLati, m_path.at(maxId).longitude()));
 }
 
-void QGeoPathPrivate::updateBoundingBox()
+QGeoShapePrivate *QGeoPathPrivateEager::clone() const
 {
-    m_clipperDirty = true;
-    if (m_path.isEmpty()) {
-        m_deltaXs.clear();
-        m_minX = qInf();
-        m_maxX = -qInf();
-        m_minLati = qInf();
-        m_maxLati = -qInf();
-        m_bbox = QGeoRectangle();
-        return;
-    } else if (m_path.size() == 1) { // was 0  now is 1
-        m_deltaXs.resize(1);
-        m_deltaXs[0] = m_minX = m_maxX = 0.0;
-        m_minLati = m_maxLati = m_path.at(0).latitude();
-        m_bbox = QGeoRectangle(QGeoCoordinate(m_maxLati, m_path.at(0).longitude()),
-                               QGeoCoordinate(m_minLati, m_path.at(0).longitude()));
-        return;
-    } else if ( m_path.size() != m_deltaXs.size() + 1 ) {  // this case should not happen
-        computeBoundingBox(); // something went wrong
-        return;
-    }
+    return new QGeoPathPrivateEager(*this);
+}
 
-    const QGeoCoordinate &geoFrom = m_path.at(m_path.size()-2);
-    const QGeoCoordinate &geoTo   = m_path.last();
-    double longiFrom    = geoFrom.longitude();
-    double longiTo      = geoTo.longitude();
-    double deltaLongi = longiTo - longiFrom;
-    if (qAbs(deltaLongi) > 180.0) {
-        if (longiTo > 0.0)
-            longiTo -= 360.0;
-        else
-            longiTo += 360.0;
-        deltaLongi =  longiTo - longiFrom;
-    }
+void QGeoPathPrivateEager::markDirty()
+{
+    computeBoundingBox();
+}
 
-    m_deltaXs.push_back(m_deltaXs.last() + deltaLongi);
-    double currentMinLongi = m_bbox.topLeft().longitude();
-    double currentMaxLongi = m_bbox.bottomRight().longitude();
-    if (m_deltaXs.last() < m_minX) {
-        m_minX = m_deltaXs.last();
-        currentMinLongi = geoTo.longitude();
-    }
-    if (m_deltaXs.last() > m_maxX) {
-        m_maxX = m_deltaXs.last();
-        currentMaxLongi = geoTo.longitude();
-    }
-    if (geoTo.latitude() > m_maxLati)
-        m_maxLati = geoTo.latitude();
-    if (geoTo.latitude() < m_minLati)
-        m_minLati = geoTo.latitude();
-    m_bbox = QGeoRectangle(QGeoCoordinate(m_maxLati, currentMinLongi),
-                           QGeoCoordinate(m_minLati, currentMaxLongi));
-}
-
-void QGeoPathPrivate::updateClipperPath()
-{
-    m_clipperDirty = false;
-    double tlx = QWebMercator::coordToMercator(m_bbox.topLeft()).x();
-    QList<QDoubleVector2D> preservedPath;
-    for (const QGeoCoordinate &c : m_path) {
-        QDoubleVector2D crd = QWebMercator::coordToMercator(c);
-        if (crd.x() < tlx)
-            crd.setX(crd.x() + 1.0);
-        preservedPath << crd;
+void QGeoPathPrivateEager::translate(double degreesLatitude, double degreesLongitude)
+{
+    if (degreesLatitude > 0.0)
+        degreesLatitude = qMin(degreesLatitude, 90.0 - m_maxLati);
+    else
+        degreesLatitude = qMax(degreesLatitude, -90.0 - m_minLati);
+    for (QGeoCoordinate &p: m_path) {
+        p.setLatitude(p.latitude() + degreesLatitude);
+        p.setLongitude(QLocationUtils::wrapLong(p.longitude() + degreesLongitude));
     }
-    m_clipperPath = QClipperUtils::qListToPath(preservedPath);
+    m_bbox.translate(degreesLatitude, degreesLongitude);
+    m_minLati += degreesLatitude;
+    m_maxLati += degreesLatitude;
 }
 
-
-/*!
-    Sets the \a path for an Hole inside the polygon.The hole has QList<QGeoCoordinate> type
-*/
-void QGeoPathPrivate::addHole(const QList<QGeoCoordinate> &holePath)
+void QGeoPathPrivateEager::addCoordinate(const QGeoCoordinate &coordinate)
 {
-    for (const QGeoCoordinate &holeVertex: holePath)
-        if (!holeVertex.isValid())
-            return;
+    if (!coordinate.isValid())
+        return;
+    m_path.append(coordinate);
+    //m_clipperDirty = true; // clipper not used in polylines
+    updateBoundingBox();
+}
 
-    m_holesList << holePath;
+void QGeoPathPrivateEager::QGeoPathPrivateEager::computeBoundingBox()
+{
+    computeBBox(m_path, m_deltaXs, m_minX, m_maxX, m_minLati, m_maxLati, m_bbox);
 }
 
-/*!
-    Returns a QVariant containing a QList<QGeoCoordinate> representing the hole at index
-*/
-const QList<QGeoCoordinate> QGeoPathPrivate::holePath(int index) const
+void QGeoPathPrivateEager::QGeoPathPrivateEager::updateBoundingBox()
 {
-    return m_holesList.at(index);
+    updateBBox(m_path, m_deltaXs, m_minX, m_maxX, m_minLati, m_maxLati, m_bbox);
 }
 
+QGeoPathEager::QGeoPathEager() : QGeoPath()
+{
+    initPathConversions();
+    d_ptr = new QGeoPathPrivateEager;
+}
 
-/*!
-    Removes element at position \a index from the holes QList.
-*/
-void QGeoPathPrivate::removeHole(int index)
+QGeoPathEager::QGeoPathEager(const QList<QGeoCoordinate> &path, const qreal &width) : QGeoPath()
 {
-    if (index < 0 || index >= m_holesList.size())
-        return;
+    initPathConversions();
+    d_ptr = new QGeoPathPrivateEager(path, width);
+}
 
-    m_holesList.removeAt(index);
+QGeoPathEager::QGeoPathEager(const QGeoPath &other) : QGeoPath()
+{
+    initPathConversions();
+    d_ptr = new QGeoPathPrivateEager;
+    setPath(other.path());
+    setWidth(other.width());
 }
 
-/*!
-    Returns the number of holes.
-*/
-int QGeoPathPrivate::holesCount() const
+QGeoPathEager::QGeoPathEager(const QGeoShape &other) : QGeoPath()
 {
-    return m_holesList.size();
+    initPathConversions();
+    if (other.type() == QGeoShape::PathType)
+        *this = QGeoPathEager(QGeoPath(other));
+    else
+        d_ptr = new QGeoPathPrivateEager;
 }
 
+QGeoPathEager::~QGeoPathEager() {}
+
 QT_END_NAMESPACE
 
+
+
+
+
+
+
+