Fix the fitViewportToGeoShape calculation

The current implementation is calculating the bounding box of
a geocircle based on moving along a circle of latitude by the
distance of a circle's radius. Unfortunately the distances
on a small circle of a sphere are greater than great circle
distances. Reimplement the calculation using tangential
points between a geocircle and meridians.

Do not center the viewport in the center of the geoshape,
use the center of the bounding box instead.

Simplify zoom level adjustment calculations, use the reference
world plane to get rid of longitude wrapping and rounding
erros.

Finally update a viewport unit test, adjust the minimum map
size to 256x256, so fitToViewport calls have chance to succeed.
Fix out of order test execution.

Task-number: QTBUG-54337
Change-Id: I61726a4eb7183470c493ceb03d101f3a75305121
Reviewed-by: Alex Blasche <alexander.blasche@qt.io>

5 files changed, 217 insertions, 102 deletions

diff --git a/src/imports/location/qdeclarativegeomap.cpp b/src/imports/location/qdeclarativegeomap.cpp
index 7647a70b..082eaf98 100644
--- a/src/imports/location/qdeclarativegeomap.cpp
+++ b/src/imports/location/qdeclarativegeomap.cpp
@@ -168,6 +168,8 @@ QT_BEGIN_NAMESPACE
     application should open the link in a browser or display its contents to the user.
 */
 
+static const qreal EARTH_MEAN_RADIUS = 6371007.2;
+
 QDeclarativeGeoMap::QDeclarativeGeoMap(QQuickItem *parent)
         : QQuickItem(parent),
         m_plugin(0),
@@ -771,32 +773,63 @@ QColor QDeclarativeGeoMap::color() const
 
 void QDeclarativeGeoMap::fitViewportToGeoShape()
 {
-    if (!m_map) return;
+    int margins  = 10;
+    if (!m_map || width() <= margins || height() <= margins)
+        return;
 
-    double bboxWidth;
-    double bboxHeight;
-    QGeoCoordinate centerCoordinate;
+    QGeoCoordinate topLeft;
+    QGeoCoordinate bottomRight;
 
     switch (m_region.type()) {
     case QGeoShape::RectangleType:
     {
         QGeoRectangle rect = m_region;
-        QDoubleVector2D topLeftPoint = m_map->coordinateToItemPosition(rect.topLeft(), false);
-        QDoubleVector2D botRightPoint = m_map->coordinateToItemPosition(rect.bottomRight(), false);
-        bboxWidth = qAbs(topLeftPoint.x() - botRightPoint.x());
-        bboxHeight = qAbs(topLeftPoint.y() - botRightPoint.y());
-        centerCoordinate = rect.center();
+        topLeft = rect.topLeft();
+        bottomRight = rect.bottomRight();
         break;
     }
     case QGeoShape::CircleType:
     {
+        const double pi = M_PI;
         QGeoCircle circle = m_region;
-        centerCoordinate = circle.center();
-        QGeoCoordinate edge = centerCoordinate.atDistanceAndAzimuth(circle.radius(), 90);
-        QDoubleVector2D centerPoint = m_map->coordinateToItemPosition(centerCoordinate, false);
-        QDoubleVector2D edgePoint = m_map->coordinateToItemPosition(edge, false);
-        bboxWidth = qAbs(centerPoint.x() - edgePoint.x()) * 2;
-        bboxHeight = bboxWidth;
+        QGeoCoordinate centerCoordinate = circle.center();
+
+        // calculate geo bounding box of the circle
+        // circle tangential points with meridians and the north pole create
+        // spherical triangle, we use spherical law of sines
+        // sin(lon_delta_in_rad)/sin(r_in_rad) =
+        // sin(alpha_in_rad)/sin(pi/2 - lat_in_rad), where:
+        // * lon_delta_in_rad - delta of longitudes of circle center
+        //   and tangential points
+        // * r_in_rad - angular radius of the circle
+        // * lat_in_rad - latitude of circle center
+        // * alpha_in_rad - angle between meridian and radius to the circle =>
+        //   this is tangential point => sin(alpha) = 1
+        // * lat_delta_in_rad - delta of latitudes of circle center and
+        //   latitude of points where great circle (going through circle
+        //   center) crosses circle and the pole
+
+        double r_in_rad = circle.radius() / EARTH_MEAN_RADIUS; // angular r
+        double lat_delta_in_deg = r_in_rad * 180 / pi;
+        double lon_delta_in_deg = std::asin(std::sin(r_in_rad) /
+               std::cos(centerCoordinate.latitude() * pi / 180)) * 180 / pi;
+
+        topLeft.setLatitude(centerCoordinate.latitude() + lat_delta_in_deg);
+        topLeft.setLongitude(centerCoordinate.longitude() - lon_delta_in_deg);
+        bottomRight.setLatitude(centerCoordinate.latitude()
+                                - lat_delta_in_deg);
+        bottomRight.setLongitude(centerCoordinate.longitude()
+                                 + lon_delta_in_deg);
+
+        // adjust if circle reaches poles => cross all meridians and
+        // fit into Mercator projection bounds
+        if (topLeft.latitude() > 90 || bottomRight.latitude() < -90) {
+            topLeft.setLatitude(qMin(topLeft.latitude(), 85.05113));
+            topLeft.setLongitude(-180.0);
+            bottomRight.setLatitude(qMax(bottomRight.latitude(),
+                                                 -85.05113));
+            bottomRight.setLongitude(180.0);
+        }
         break;
     }
     case QGeoShape::UnknownType:
@@ -805,28 +838,36 @@ void QDeclarativeGeoMap::fitViewportToGeoShape()
         return;
     }
 
-    // position camera to the center of bounding box
-    setProperty("center", QVariant::fromValue(centerCoordinate));
+    // adjust zoom, use reference world to keep things simple
+    // otherwise we would need to do the error prone longitudes
+    // wrapping
+    QDoubleVector2D topLeftPoint =
+            m_map->referenceCoordinateToItemPosition(topLeft);
+    QDoubleVector2D bottomRightPoint =
+            m_map->referenceCoordinateToItemPosition(bottomRight);
 
-    //If the shape is empty we just change centerposition, not zoom
-    if (bboxHeight == 0 && bboxWidth == 0)
-        return;
+    double bboxWidth = bottomRightPoint.x() - topLeftPoint.x();
+    double bboxHeight = bottomRightPoint.y() - topLeftPoint.y();
 
-    // adjust zoom
-    double bboxWidthRatio = bboxWidth / (bboxWidth + bboxHeight);
-    double mapWidthRatio = width() / (width() + height());
-    double zoomRatio;
+    // find center of the bounding box
+    QGeoCoordinate centerCoordinate =
+            m_map->referenceItemPositionToCoordinate(
+                (topLeftPoint + bottomRightPoint)/2);
 
-    if (bboxWidthRatio > mapWidthRatio)
-        zoomRatio = bboxWidth / width();
-    else
-        zoomRatio = bboxHeight / height();
-
-    qreal newZoom = std::log10(zoomRatio) / std::log10(0.5);
+    // position camera to the center of bounding box
+    setCenter(centerCoordinate);
 
-    newZoom = std::floor(qMax(minimumZoomLevel(), (m_map->mapController()->zoom() + newZoom)));
-    setProperty("zoomLevel", QVariant::fromValue(newZoom));
+    // if the shape is empty we just change center position, not zoom
+    if (bboxHeight == 0 && bboxWidth == 0)
+        return;
 
+    double zoomRatio = qMax(bboxWidth / (width() - margins),
+                            bboxHeight / (height() - margins));
+    // fixme: use log2 with c++11
+    zoomRatio = std::log(zoomRatio) / std::log(2.0);
+    double newZoom = qMax(minimumZoomLevel(), m_map->mapController()->zoom()
+                          - zoomRatio);
+    setZoomLevel(newZoom);
     m_validRegion = true;
 }
 
diff --git a/src/location/maps/qgeomap_p.h b/src/location/maps/qgeomap_p.h
index acc928ea..9f3043aa 100644
--- a/src/location/maps/qgeomap_p.h
+++ b/src/location/maps/qgeomap_p.h
@@ -83,6 +83,8 @@ public:
 
     virtual QGeoCoordinate itemPositionToCoordinate(const QDoubleVector2D &pos, bool clipToViewport = true) const = 0;
     virtual QDoubleVector2D coordinateToItemPosition(const QGeoCoordinate &coordinate, bool clipToViewport = true) const = 0;
+    virtual QDoubleVector2D referenceCoordinateToItemPosition(const QGeoCoordinate &coordinate) const = 0;
+    virtual QGeoCoordinate referenceItemPositionToCoordinate(const QDoubleVector2D &pos) const = 0;
     virtual void prefetchData();
     virtual void clearData();
 
diff --git a/src/location/maps/qgeotiledmap.cpp b/src/location/maps/qgeotiledmap.cpp
index 97747049..869a6f08 100644
--- a/src/location/maps/qgeotiledmap.cpp
+++ b/src/location/maps/qgeotiledmap.cpp
@@ -154,6 +154,20 @@ QDoubleVector2D QGeoTiledMap::coordinateToItemPosition(const QGeoCoordinate &coo
     return pos;
 }
 
+QDoubleVector2D QGeoTiledMap::referenceCoordinateToItemPosition(const QGeoCoordinate &coordinate) const
+{
+    Q_D(const QGeoTiledMap);
+    QDoubleVector2D point = QGeoProjection::coordToMercator(coordinate);
+    return point * std::pow(2.0, d->m_cameraData.zoomLevel()) * d->m_cameraTiles->tileSize();
+}
+
+QGeoCoordinate QGeoTiledMap::referenceItemPositionToCoordinate(const QDoubleVector2D &pos) const
+{
+    Q_D(const QGeoTiledMap);
+    QDoubleVector2D point = pos / (std::pow(2.0, d->m_cameraData.zoomLevel()) * d->m_cameraTiles->tileSize());
+    return QGeoProjection::mercatorToCoord(point);
+}
+
 QGeoTiledMapPrivate::QGeoTiledMapPrivate(QGeoTiledMappingManagerEngine *engine)
     : QGeoMapPrivate(engine),
       m_cache(engine->tileCache()),
diff --git a/src/location/maps/qgeotiledmap_p.h b/src/location/maps/qgeotiledmap_p.h
index 87dac5d1..0eb1574c 100644
--- a/src/location/maps/qgeotiledmap_p.h
+++ b/src/location/maps/qgeotiledmap_p.h
@@ -85,6 +85,8 @@ public:
 
     QGeoCoordinate itemPositionToCoordinate(const QDoubleVector2D &pos, bool clipToViewport = true) const Q_DECL_OVERRIDE;
     QDoubleVector2D coordinateToItemPosition(const QGeoCoordinate &coordinate, bool clipToViewport = true) const Q_DECL_OVERRIDE;
+    QDoubleVector2D referenceCoordinateToItemPosition(const QGeoCoordinate &coordinate) const Q_DECL_OVERRIDE;
+    QGeoCoordinate referenceItemPositionToCoordinate(const QDoubleVector2D &pos) const Q_DECL_OVERRIDE;
     void prefetchData() Q_DECL_OVERRIDE;
     void clearData() Q_DECL_OVERRIDE;
 
diff --git a/tests/auto/declarative_ui/tst_map_item_fit_viewport.qml b/tests/auto/declarative_ui/tst_map_item_fit_viewport.qml
index 4cbef945..4724d459 100644
--- a/tests/auto/declarative_ui/tst_map_item_fit_viewport.qml
+++ b/tests/auto/declarative_ui/tst_map_item_fit_viewport.qml
@@ -39,10 +39,10 @@ import QtLocation.Test 5.5
 
     /*
 
-     (0,0)   ---------------------------------------------------- (240,0)
+     (0,0)   ---------------------------------------------------- (296,0)
              | no map                                           |
              |    (20,20)                                       |
-     (0,20)  |    ------------------------------------------    | (240,20)
+     (0,20)  |    ------------------------------------------    | (296,20)
              |    |                                        |    |
              |    |  map                                   |    |
              |    |                                        |    |
@@ -57,15 +57,15 @@ import QtLocation.Test 5.5
              |    |                                        |    |
              |    ------------------------------------------    |
              |                                                  |
-     (0,240) ---------------------------------------------------- (240,240)
+     (0,296) ---------------------------------------------------- (296,296)
 
      */
 
 Item {
     id: page
     x: 0; y: 0;
-    width: 240
-    height: 240
+    width: 296
+    height: 296
     Plugin { id: testPlugin; name : "qmlgeo.test.plugin"; allowExperimental: true }
 
     property variant mapDefaultCenter: QtPositioning.coordinate(20, 20)
@@ -102,11 +102,8 @@ Item {
     property variant mapPolylineBottomRight: QtPositioning.coordinate(0, 0)
     property variant mapRouteTopLeft: QtPositioning.coordinate(0, 0)
     property variant mapRouteBottomRight: QtPositioning.coordinate(0, 0)
-
-    property variant boundingBox: QtPositioning.rectangle(QtPositioning.coordinate(0, 0),
-                                                       QtPositioning.coordinate(0, 0))
-
-    property variant fitRect: QtPositioning.rectangle(QtPositioning.coordinate(80, 80), QtPositioning.coordinate(78, 82))
+    property variant fitRect: QtPositioning.rectangle(QtPositioning.coordinate(80, 80),
+                                                      QtPositioning.coordinate(78, 82))
     property variant fitEmptyRect: QtPositioning.rectangle(QtPositioning.coordinate(79, 79),-1, -1)
     property variant fitCircle: QtPositioning.circle(QtPositioning.coordinate(-50, -100), 1500)
     property variant fitInvalidShape: QtPositioning.shape()
@@ -116,7 +113,7 @@ Item {
 
     Map {
         id: map;
-        x: 20; y: 20; width: 200; height: 200
+        x: 20; y: 20; width: 256; height: 256
         zoomLevel: 3
         center: mapDefaultCenter
         plugin: testPlugin;
@@ -227,16 +224,58 @@ Item {
         name: "MapItemsFitViewport"
         when: windowShown
 
-        function test_aa_visible_basic() { // aa et al. for execution order
-            wait(10)
-            // sanity check that the coordinate conversion works, as
-            // rest of the case relies on it. for robustness cut
-            // a little slack with fuzzy compare
+        function initTestCase()
+        {
+            // sanity check that the coordinate conversion works
             var mapcenter = map.fromCoordinate(map.center)
-            verify (fuzzy_compare(mapcenter.x, 100, 2))
-            verify (fuzzy_compare(mapcenter.y, 100, 2))
+            verify (fuzzy_compare(mapcenter.x, 128, 2))
+            verify (fuzzy_compare(mapcenter.y, 128, 2))
+        }
 
-            reset()
+        function init()
+        {
+            preMapRect.topLeft.latitude = 20
+            preMapRect.topLeft.longitude = 20
+            preMapRect.bottomRight.latitude = 10
+            preMapRect.bottomRight.longitude = 30
+            preMapCircle.center.latitude = 10
+            preMapCircle.center.longitude = 30
+            preMapQuickItem.coordinate.latitude = 35
+            preMapQuickItem.coordinate.longitude = 3
+            var i
+            for (i = 0; i < preMapPolygon.path.length; ++i) {
+                preMapPolygon.path[i].latitude = preMapPolygonDefaultPath[i].latitude
+                preMapPolygon.path[i].longitude = preMapPolygonDefaultPath[i].longitude
+            }
+            for (i = 0; i < preMapPolyline.path.length; ++i) {
+                preMapPolyline.path[i].latitude = preMapPolylineDefaultPath[i].latitude
+                preMapPolyline.path[i].longitude = preMapPolylineDefaultPath[i].longitude
+            }
+            for (i = 0; i < preMapRoute.route.path.length; ++i) {
+                preMapRoute.route.path[i].latitude = preMapRouteDefaultPath[i].latitude
+                preMapRoute.route.path[i].longitude = preMapRouteDefaultPath[i].longitude
+            }
+            // remove items
+            map.clearMapItems()
+            //clear_data()
+            compare (map.mapItems.length, 0)
+            // reset map
+            map.center.latitude = 20
+            map.center.longitude = 20
+            map.zoomLevel = 3
+            // re-add items and verify they are back (without needing to pan map etc.)
+            map.addMapItem(preMapRect)
+            map.addMapItem(preMapCircle)
+            map.addMapItem(preMapQuickItem)
+            map.addMapItem(preMapPolygon)
+            map.addMapItem(preMapPolyline)
+            map.addMapItem(preMapRoute)
+            compare (map.mapItems.length, 6)
+            calculate_bounds()
+        }
+
+        function test_visible_itmes()
+        {
             // normal case - fit viewport to items which are all already visible
             verify_visibility_all_items()
             map.fitViewportToMapItems()
@@ -244,21 +283,23 @@ Item {
             verify_visibility_all_items()
         }
 
-        function test_ab_visible_zoom() {
-            var i
+        function test_visible_zoom_in()
+        {
             // zoom in (clipping also occurs)
             var z = map.zoomLevel
-            for (i = (z + 1); i < map.maximumZoomLevel; ++i ) {
-                reset()
+            for (var i = (z + 1); i < map.maximumZoomLevel; ++i ) {
                 map.zoomLevel = i
                 visualInspectionPoint()
                 map.fitViewportToMapItems()
                 visualInspectionPoint()
                 verify_visibility_all_items()
             }
+        }
+
+        function test_visible_zoom_out()
+        {
             // zoom out
-            for (i = (z - 1); i >= 0; --i ) {
-                reset()
+            for (var i = (z - 1); i >= 0; --i ) {
                 map.zoomLevel = i
                 visualInspectionPoint()
                 verify_visibility_all_items()
@@ -268,7 +309,7 @@ Item {
             }
         }
 
-        function test_ac_visible_map_move() {
+        function test_visible_map_move() {
             // move map so all items are out of screen
             // then fit viewport
             var xDir = 1
@@ -277,7 +318,6 @@ Item {
             var yDirChange = 1
             var dir = 0
             for (dir = 0; dir < 4; dir++) {
-                reset()
                 verify_visibility_all_items()
                 var i = 0
                 var panX = map.width * xDir * 0.5
@@ -312,8 +352,7 @@ Item {
             }
         }
 
-        function test_ad_fit_to_geoshape() {
-            reset()
+        function test_fit_to_geoshape() {
             visualInspectionPoint()
             calculate_fit_circle_bounds()
             //None should be visible
@@ -371,7 +410,7 @@ Item {
             verify(is_coord_on_screen(fitRect.topLeft))
             verify(is_coord_on_screen(fitRect.bottomRight))
             //zoom map
-            map.zoomLevel++;
+            map.zoomLevel++
             verify(!is_coord_on_screen(fitRect.topLeft))
             verify(!is_coord_on_screen(fitRect.bottomRight))
             // recheck
@@ -380,6 +419,63 @@ Item {
             verify(is_coord_on_screen(fitRect.bottomRight))
         }
 
+        // checks that circles belongs to the view port
+        function circle_in_viewport(center, radius, visible)
+        {
+            for (var i = 0; i < 128; ++i) {
+                var azimuth = 360.0 * i / 128.0;
+                var coord = center.atDistanceAndAzimuth(radius,azimuth)
+                if (coord.isValid)
+                    verify(is_coord_on_screen(coord) === visible, visible ?
+                               "circle not visible" : "circle visible")
+            }
+        }
+
+        function test_fit_circle_to_viewport(data)
+        {
+            verify(!is_coord_on_screen(data.center))
+            circle_in_viewport(data.center, data.radius, false)
+            map.visibleRegion = QtPositioning.circle(data.center, data.radius)
+            circle_in_viewport(data.center, data.radius, true)
+        }
+
+        function test_fit_circle_to_viewport_data()
+        {
+            return [
+                        { tag: "circle 1", center:
+                            QtPositioning.coordinate(70,70), radius: 10 },
+                        { tag: "circle 2", center:
+                            QtPositioning.coordinate(80,30), radius: 2000000 },
+                        { tag: "circle 3", center:
+                            QtPositioning.coordinate(-82,30), radius: 2000000 },
+                        { tag: "circle 4", center:
+                            QtPositioning.coordinate(60,179), radius: 20000 },
+                        { tag: "circle 5", center:
+                            QtPositioning.coordinate(60,-179), radius: 20000 },
+                    ]
+        }
+
+        function test_fit_rectangle_to_viewport(data)
+        {
+            verify(!is_coord_on_screen(data.topLeft),"rectangle visible")
+            verify(!is_coord_on_screen(data.bottomRight),"rectangle visible")
+            map.visibleRegion = QtPositioning.rectangle(data.topLeft,data.bottomRight)
+            verify(is_coord_on_screen(data.topLeft),"rectangle not visible")
+            verify(is_coord_on_screen(data.bottomRight),"rectangle not visible")
+        }
+
+        function test_fit_rectangle_to_viewport_data()
+        {
+            return [
+                        { tag: "rectangle 1",
+                            topLeft: QtPositioning.coordinate(80, 80),
+                            bottomRight: QtPositioning.coordinate(78, 82) },
+                        { tag: "rectangle 2",
+                            topLeft: QtPositioning.coordinate(30,-130),
+                            bottomRight: QtPositioning.coordinate(0,-100)}
+                    ]
+        }
+
         /*function test_ad_visible_items_move() {
             // move different individual items out of screen
             // then fit viewport
@@ -561,46 +657,6 @@ Item {
             verify(is_coord_on_screen(mapRouteBottomRight))
         }
 
-        function reset(){
-            preMapRect.topLeft.latitude = 20
-            preMapRect.topLeft.longitude = 20
-            preMapRect.bottomRight.latitude = 10
-            preMapRect.bottomRight.longitude = 30
-            preMapCircle.center.latitude = 10
-            preMapCircle.center.longitude = 30
-            preMapQuickItem.coordinate.latitude = 35
-            preMapQuickItem.coordinate.longitude = 3
-            var i
-            for (i=0; i< preMapPolygon.path.length; ++i) {
-                preMapPolygon.path[i].latitude = preMapPolygonDefaultPath[i].latitude
-                preMapPolygon.path[i].longitude = preMapPolygonDefaultPath[i].longitude
-            }
-            for (i=0; i< preMapPolyline.path.length; ++i) {
-                preMapPolyline.path[i].latitude = preMapPolylineDefaultPath[i].latitude
-                preMapPolyline.path[i].longitude = preMapPolylineDefaultPath[i].longitude
-            }
-            for (i=0; i< preMapRoute.route.path.length; ++i) {
-                preMapRoute.route.path[i].latitude = preMapRouteDefaultPath[i].latitude
-                preMapRoute.route.path[i].longitude = preMapRouteDefaultPath[i].longitude
-            }
-            // remove items
-            map.clearMapItems()
-            //clear_data()
-            compare (map.mapItems.length, 0)
-            // reset map
-            map.center.latitude = 20
-            map.center.longitude = 20
-            map.zoomLevel = 3
-            // re-add items and verify they are back (without needing to pan map etc.)
-            map.addMapItem(preMapRect)
-            map.addMapItem(preMapCircle)
-            map.addMapItem(preMapQuickItem)
-            map.addMapItem(preMapPolygon)
-            map.addMapItem(preMapPolyline)
-            map.addMapItem(preMapRoute)
-            compare (map.mapItems.length, 6)
-            calculate_bounds()
-        }
 
         function is_coord_on_screen(coord) {
             return is_point_on_screen(map.fromCoordinate(coord))