/****************************************************************************
**
** Copyright (C) 2015 The Qt Company Ltd.
** Contact: http://www.qt.io/licensing/
**
** This file is part of the QtLocation module of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:LGPL3$
** Commercial License Usage
** Licensees holding valid commercial Qt licenses may use this file in
** accordance with the commercial license agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
** a written agreement between you and The Qt Company. For licensing terms
** and conditions see http://www.qt.io/terms-conditions. For further
** information use the contact form at http://www.qt.io/contact-us.
**
** GNU Lesser General Public License Usage
** Alternatively, this file may be used under the terms of the GNU Lesser
** General Public License version 3 as published by the Free Software
** Foundation and appearing in the file LICENSE.LGPLv3 included in the
** packaging of this file. Please review the following information to
** ensure the GNU Lesser General Public License version 3 requirements
** will be met: https://www.gnu.org/licenses/lgpl.html.
**
** GNU General Public License Usage
** Alternatively, this file may be used under the terms of the GNU
** General Public License version 2.0 or later as published by the Free
** Software Foundation and appearing in the file LICENSE.GPL included in
** the packaging of this file. Please review the following information to
** ensure the GNU General Public License version 2.0 requirements will be
** met: http://www.gnu.org/licenses/gpl-2.0.html.
**
** $QT_END_LICENSE$
**
****************************************************************************/
#include "qgeocameratiles_p.h"
#include "qgeocameratiles_p_p.h"
#include "qgeocameradata_p.h"
#include "qgeotilespec_p.h"
#include "qgeomaptype_p.h"

#include <QtPositioning/private/qwebmercator_p.h>
#include <QtPositioning/private/qdoublevector2d_p.h>
#include <QtPositioning/private/qdoublevector3d_p.h>
#include <QtPositioning/private/qlocationutils_p.h>
#include <QtGui/QMatrix4x4>
#include <QVector>
#include <QMap>
#include <QPair>
#include <QSet>
#include <QSize>
#include <cmath>
#include <limits>

static QVector3D toVector3D(const QDoubleVector3D& in)
{
    return QVector3D(in.x(), in.y(), in.z());
}

static QDoubleVector3D toDoubleVector3D(const QVector3D& in)
{
    return QDoubleVector3D(in.x(), in.y(), in.z());
}

QT_BEGIN_NAMESPACE

QGeoCameraTiles::QGeoCameraTiles()
    : d_ptr(new QGeoCameraTilesPrivate()) {}

QGeoCameraTiles::~QGeoCameraTiles()
{
}

void QGeoCameraTiles::setCameraData(const QGeoCameraData &camera)
{
    if (d_ptr->m_camera == camera)
        return;

    d_ptr->m_dirtyGeometry = true;
    d_ptr->m_camera = camera;
    d_ptr->m_intZoomLevel = static_cast<int>(std::floor(d_ptr->m_camera.zoomLevel()));
    d_ptr->m_sideLength = 1 << d_ptr->m_intZoomLevel;
}

QGeoCameraData QGeoCameraTiles::cameraData() const
{
    return d_ptr->m_camera;
}

void QGeoCameraTiles::setVisibleArea(const QRectF &visibleArea)
{
    if (d_ptr->m_visibleArea == visibleArea)
        return;

    d_ptr->m_visibleArea = visibleArea;
    d_ptr->m_dirtyGeometry = true;
}

void QGeoCameraTiles::setScreenSize(const QSize &size)
{
    if (d_ptr->m_screenSize == size)
        return;

    d_ptr->m_dirtyGeometry = true;
    d_ptr->m_screenSize = size;
}

void QGeoCameraTiles::setPluginString(const QString &pluginString)
{
    if (d_ptr->m_pluginString == pluginString)
        return;

    d_ptr->m_dirtyMetadata = true;
    d_ptr->m_pluginString = pluginString;
}

void QGeoCameraTiles::setMapType(const QGeoMapType &mapType)
{
    if (d_ptr->m_mapType == mapType)
        return;

    d_ptr->m_dirtyMetadata = true;
    d_ptr->m_mapType = mapType;
}

QGeoMapType QGeoCameraTiles::activeMapType() const
{
    return d_ptr->m_mapType;
}

void QGeoCameraTiles::setMapVersion(int mapVersion)
{
    if (d_ptr->m_mapVersion == mapVersion)
        return;

    d_ptr->m_dirtyMetadata = true;
    d_ptr->m_mapVersion = mapVersion;
}

void QGeoCameraTiles::setTileSize(int tileSize)
{
    if (d_ptr->m_tileSize == tileSize)
        return;

    d_ptr->m_dirtyGeometry = true;
    d_ptr->m_tileSize = tileSize;
}

void QGeoCameraTiles::setViewExpansion(double viewExpansion)
{
    d_ptr->m_viewExpansion = viewExpansion;
    d_ptr->m_dirtyGeometry = true;
}

int QGeoCameraTiles::tileSize() const
{
    return d_ptr->m_tileSize;
}

const QSet<QGeoTileSpec>& QGeoCameraTiles::createTiles()
{
    if (d_ptr->m_dirtyGeometry) {
        d_ptr->m_tiles.clear();
        d_ptr->updateGeometry();
        d_ptr->m_dirtyGeometry = false;
    }

    if (d_ptr->m_dirtyMetadata) {
        d_ptr->updateMetadata();
        d_ptr->m_dirtyMetadata = false;
    }

    return d_ptr->m_tiles;
}

QGeoCameraTilesPrivate::QGeoCameraTilesPrivate()
:   m_mapVersion(-1),
    m_tileSize(0),
    m_intZoomLevel(0),
    m_sideLength(0),
    m_dirtyGeometry(false),
    m_dirtyMetadata(false),
    m_viewExpansion(1.0)
{
}

QGeoCameraTilesPrivate::~QGeoCameraTilesPrivate() {}

void QGeoCameraTilesPrivate::updateMetadata()
{
    typedef QSet<QGeoTileSpec>::const_iterator iter;

    QSet<QGeoTileSpec> newTiles;

    iter i = m_tiles.constBegin();
    iter end = m_tiles.constEnd();

    for (; i != end; ++i) {
        QGeoTileSpec tile = *i;
        newTiles.insert(QGeoTileSpec(m_pluginString, m_mapType.mapId(), tile.zoom(), tile.x(), tile.y(), m_mapVersion));
    }

    m_tiles = newTiles;
}

void QGeoCameraTilesPrivate::updateGeometry()
{
    // Find the frustum from the camera / screen / viewport information
    // The larger frustum when stationary is a form of prefetching
    Frustum f = createFrustum(m_viewExpansion);
#ifdef QT_LOCATION_DEBUG
    m_frustum = f;
#endif

    // Find the polygon where the frustum intersects the plane of the map
    PolygonVector footprint = frustumFootprint(f);
#ifdef QT_LOCATION_DEBUG
    m_frustumFootprint = footprint;
#endif

    // Clip the polygon to the map, split it up if it cross the dateline
    ClippedFootprint polygons = clipFootprintToMap(footprint);
#ifdef QT_LOCATION_DEBUG
    m_clippedFootprint = polygons;
#endif


    if (!polygons.left.isEmpty()) {
        QSet<QGeoTileSpec> tilesLeft = tilesFromPolygon(polygons.left);
        m_tiles.unite(tilesLeft);
    }

    if (!polygons.right.isEmpty()) {
        QSet<QGeoTileSpec> tilesRight = tilesFromPolygon(polygons.right);
        m_tiles.unite(tilesRight);
    }

    if (!polygons.mid.isEmpty()) {
        QSet<QGeoTileSpec> tilesRight = tilesFromPolygon(polygons.mid);
        m_tiles.unite(tilesRight);
    }
}

Frustum QGeoCameraTilesPrivate::createFrustum(double viewExpansion) const
{
    double apertureSize = 1.0;
    if (m_camera.fieldOfView() != 90.0) //aperture(90 / 2) = 1
        apertureSize = tan(QLocationUtils::radians(m_camera.fieldOfView()) * 0.5);
    QDoubleVector3D center = m_sideLength * QWebMercator::coordToMercator(m_camera.center());
#ifdef QT_LOCATION_DEBUG
    m_createFrustum_center = center;
#endif


    double f = m_screenSize.height();

    double z = std::pow(2.0, m_camera.zoomLevel() - m_intZoomLevel) * m_tileSize; // between 1 and 2 * m_tileSize

    double altitude = (f / (2.0 * z)) / apertureSize;
    QDoubleVector3D eye = center;
    eye.setZ(altitude);

    QDoubleVector3D view = eye - center;
    QDoubleVector3D side = QDoubleVector3D::normal(view, QDoubleVector3D(0.0, 1.0, 0.0));
    QDoubleVector3D up = QDoubleVector3D::normal(side, view);

    QMatrix4x4 mBearing;
    // The rotation direction here is the opposite of QGeoTiledMapScene::setupCamera,
    // as this is basically rotating the map against a fixed view frustum.
    mBearing.rotate(1.0 * m_camera.bearing(), toVector3D(view));
    up = toDoubleVector3D(mBearing * toVector3D(up));

    // same for tilting
    QDoubleVector3D side2 = QDoubleVector3D::normal(up, view);
    QMatrix4x4 mTilt;
    mTilt.rotate(-1.0 * m_camera.tilt(), toVector3D(side2));
    eye = toDoubleVector3D((mTilt * toVector3D(view)) + toVector3D(center));

    view = eye - center;
    side = QDoubleVector3D::normal(view, QDoubleVector3D(0.0, 1.0, 0.0));
    up = QDoubleVector3D::normal(view, side2);

    double nearPlane =  1.0 / 32.0; // The denominator used to be (4.0 * m_tileSize ), which produces an extremely narrow and tiny near plane.
    // farPlane plays a role on how much gets clipped when the map gets tilted. It used to be altitude + 1.0
    // The value of 8.0 has been chosen as an acceptable compromise.
    // TODO: use m_camera.clipDistance(); when this will be introduced
    double farPlane = altitude + 8.0;

    double aspectRatio = 1.0 * m_screenSize.width() / m_screenSize.height();

    // Half values. Half width near, far, height near, far.
    double hhn,hwn,hhf,hwf = 0.0;

    // This used to fix the (half) field of view at 45 degrees
    // half because this assumed that viewSize = 2*nearPlane x 2*nearPlane
    viewExpansion *= apertureSize;

    hhn = viewExpansion * nearPlane;
    hwn = hhn * aspectRatio;

    hhf = viewExpansion * farPlane;
    hwf = hhf * aspectRatio;

    QDoubleVector3D d = center - eye;
    d.normalize();
    up.normalize();
    QDoubleVector3D right = QDoubleVector3D::normal(d, up);

    QDoubleVector3D cf = eye + d * farPlane;
    QDoubleVector3D cn = eye + d * nearPlane;

    Frustum frustum;

    frustum.apex = eye;
#ifdef QT_LOCATION_DEBUG
    m_createFrustum_eye = eye;
#endif

    QRectF va = m_visibleArea;
    if (va.isNull())
        va = QRectF(0, 0, m_screenSize.width(), m_screenSize.height());
    QRectF screen = QRectF(QPointF(0,0),m_screenSize);
    QPointF vaCenter = va.center();
    QPointF screenCenter = screen.center();
    QPointF diff = screenCenter - vaCenter;
    double xdiffpct = diff.x() / m_screenSize.width();
    double ydiffpct = -(diff.y() / m_screenSize.height());

    double wn = (2 * hwn) * xdiffpct;
    double hn = (2 * hhn) * ydiffpct;
    double wf = (2 * hwf) * xdiffpct;
    double hf = (2 * hhf) * ydiffpct;

    // TODO: fix eye

    frustum.topLeftFar = cf - (up * (hhf + hf)) - (right * (hwf + wf));
    frustum.topRightFar = cf - (up * (hhf + hf)) + (right * (hwf + wf));
    frustum.bottomLeftFar = cf + (up * (hhf + hf)) - (right * (hwf + wf));
    frustum.bottomRightFar = cf + (up * (hhf + hf)) + (right * (hwf + wf));

    frustum.topLeftNear = cn - (up * (hhn + hn)) - (right * (hwn + wn));
    frustum.topRightNear = cn - (up * (hhn + hn)) + (right * (hwn + wn));
    frustum.bottomLeftNear = cn + (up * (hhn + hn)) - (right * (hwn + wn));
    frustum.bottomRightNear = cn + (up * (hhn + hn)) + (right * (hwn + wn));

    return frustum;
}

static bool appendZIntersects(const QDoubleVector3D &start,
                                               const QDoubleVector3D &end,
                                               double z,
                                               QVector<QDoubleVector3D> &results)
{
    if (start.z() == end.z()) {
        return false;
    } else {
        double f = (start.z() - z) / (start.z() - end.z());
        if ((f >= 0) && (f <= 1.0)) {
            results.append((1 - f) * start + f * end);
            return true;
        }
    }
    return false;
}

// Returns the intersection of the plane of the map and the camera frustum as a right handed polygon
PolygonVector QGeoCameraTilesPrivate::frustumFootprint(const Frustum &frustum) const
{
    PolygonVector points;
    points.reserve(4);

    // The camera is always upright. Tilting angle never reach 90degrees.
    // Meaning: bottom frustum edges always intersect the map plane, top ones may not.

    // Top Right
    if (!appendZIntersects(frustum.apex, frustum.topRightFar, 0.0, points))
        appendZIntersects(frustum.topRightFar, frustum.bottomRightFar, 0.0, points);

    // Bottom Right
    appendZIntersects(frustum.apex, frustum.bottomRightFar, 0.0, points);

    // Bottom Left
    appendZIntersects(frustum.apex, frustum.bottomLeftFar, 0.0, points);

    // Top Left
    if (!appendZIntersects(frustum.apex, frustum.topLeftFar, 0.0, points))
        appendZIntersects(frustum.topLeftFar, frustum.bottomLeftFar, 0.0, points);

    return points;
}

QPair<PolygonVector, PolygonVector> QGeoCameraTilesPrivate::splitPolygonAtAxisValue(const PolygonVector &polygon, int axis, double value) const
{
    PolygonVector polygonBelow;
    PolygonVector polygonAbove;

    int size = polygon.size();

    if (size == 0) {
        return QPair<PolygonVector, PolygonVector>(polygonBelow, polygonAbove);
    }

    QVector<int> comparisons = QVector<int>(polygon.size());

    for (int i = 0; i < size; ++i) {
        double v = polygon.at(i).get(axis);
        if (qFuzzyCompare(v - value + 1.0, 1.0)) {
            comparisons[i] = 0;
        } else {
            if (v < value) {
                comparisons[i] = -1;
            } else if (value < v) {
                comparisons[i] = 1;
            }
        }
    }

    for (int index = 0; index < size; ++index) {
        int prevIndex = index - 1;
        if (prevIndex < 0)
            prevIndex += size;
        int nextIndex = (index + 1) % size;

        int prevComp = comparisons[prevIndex];
        int comp = comparisons[index];
        int nextComp = comparisons[nextIndex];

         if (comp == 0) {
            if (prevComp == -1) {
                polygonBelow.append(polygon.at(index));
                if (nextComp == 1) {
                    polygonAbove.append(polygon.at(index));
                }
            } else if (prevComp == 1) {
                polygonAbove.append(polygon.at(index));
                if (nextComp == -1) {
                    polygonBelow.append(polygon.at(index));
                }
            } else if (prevComp == 0) {
                if (nextComp == -1) {
                    polygonBelow.append(polygon.at(index));
                } else if (nextComp == 1) {
                    polygonAbove.append(polygon.at(index));
                } else if (nextComp == 0) {
                    // do nothing
                }
            }
        } else {
             if (comp == -1) {
                 polygonBelow.append(polygon.at(index));
             } else if (comp == 1) {
                 polygonAbove.append(polygon.at(index));
             }

             // there is a point between this and the next point
             // on the polygon that lies on the splitting line
             // and should be added to both the below and above
             // polygons
             if ((nextComp != 0) && (nextComp != comp)) {
                 QDoubleVector3D p1 = polygon.at(index);
                 QDoubleVector3D p2 = polygon.at(nextIndex);

                 double p1v = p1.get(axis);
                 double p2v = p2.get(axis);

                 double f = (p1v - value) / (p1v - p2v);

                 if (((0 <= f) && (f <= 1.0))
                         || qFuzzyCompare(f + 1.0, 1.0)
                         || qFuzzyCompare(f + 1.0, 2.0) ) {
                     QDoubleVector3D midPoint = (1.0 - f) * p1 + f * p2;
                     polygonBelow.append(midPoint);
                     polygonAbove.append(midPoint);
                 }
             }
        }
    }

    return QPair<PolygonVector, PolygonVector>(polygonBelow, polygonAbove);
}

static void addXOffset(PolygonVector &footprint, double xoff)
{
    for (QDoubleVector3D &v: footprint)
        v.setX(v.x() + xoff);
}

QGeoCameraTilesPrivate::ClippedFootprint QGeoCameraTilesPrivate::clipFootprintToMap(const PolygonVector &footprint) const
{
    bool clipX0 = false;
    bool clipX1 = false;
    bool clipY0 = false;
    bool clipY1 = false;

    double side = 1.0 * m_sideLength;
    double minX = std::numeric_limits<double>::max();
    double maxX = std::numeric_limits<double>::lowest();

    for (const QDoubleVector3D &p: footprint) {
        if (p.y() < 0.0)
            clipY0 = true;
        if (p.y() > side)
            clipY1 = true;
    }

    PolygonVector results = footprint;

    if (clipY0) {
        results = splitPolygonAtAxisValue(results, 1, 0.0).second;
    }

    if (clipY1) {
        results = splitPolygonAtAxisValue(results, 1, side).first;
    }

    for (const QDoubleVector3D &p: results) {
        if ((p.x() < 0.0) || (qFuzzyIsNull(p.x())))
            clipX0 = true;
        if ((p.x() > side) || (qFuzzyCompare(side, p.x())))
            clipX1 = true;
    }

    for (const QDoubleVector3D &v : results) {
        minX = qMin(v.x(), minX);
        maxX = qMax(v.x(), maxX);
    }

    double footprintWidth = maxX - minX;

    if (clipX0) {
        if (clipX1) {
            if (footprintWidth > side) {
                PolygonVector rightPart = splitPolygonAtAxisValue(results, 0, side).second;
                addXOffset(rightPart,  -side);
                rightPart = splitPolygonAtAxisValue(rightPart, 0, side).first; // clip it again, should it tend to infinite or so

                PolygonVector leftPart = splitPolygonAtAxisValue(results, 0, 0).first;
                addXOffset(leftPart,  side);
                leftPart = splitPolygonAtAxisValue(leftPart, 0, 0).second; // same here

                results = splitPolygonAtAxisValue(results, 0, 0.0).second;
                results = splitPolygonAtAxisValue(results, 0, side).first;
                return ClippedFootprint(leftPart, results, rightPart);
            } else { // fitting the WebMercator square exactly?
                results = splitPolygonAtAxisValue(results, 0, 0.0).second;
                results = splitPolygonAtAxisValue(results, 0, side).first;
                return ClippedFootprint(PolygonVector(), results, PolygonVector());
            }
        } else {
            QPair<PolygonVector, PolygonVector> pair = splitPolygonAtAxisValue(results, 0, 0.0);
            if (pair.first.isEmpty()) {
                // if we touched the line but didn't cross it...
                for (int i = 0; i < pair.second.size(); ++i) {
                    if (qFuzzyIsNull(pair.second.at(i).x()))
                        pair.first.append(pair.second.at(i));
                }
                if (pair.first.size() == 2) {
                    double y0 = pair.first[0].y();
                    double y1 = pair.first[1].y();
                    pair.first.clear();
                    pair.first.append(QDoubleVector3D(side, y0, 0.0));
                    pair.first.append(QDoubleVector3D(side - 0.001, y0, 0.0));
                    pair.first.append(QDoubleVector3D(side - 0.001, y1, 0.0));
                    pair.first.append(QDoubleVector3D(side, y1, 0.0));
                } else if (pair.first.size() == 1) {
                    // FIXME this is trickier
                    // - touching at one point on the tile boundary
                    // - probably need to build a triangular polygon across the edge
                    // - don't want to add another y tile if we can help it
                    //   - initial version doesn't care
                    double y = pair.first.at(0).y();
                    pair.first.clear();
                    pair.first.append(QDoubleVector3D(side - 0.001, y, 0.0));
                    pair.first.append(QDoubleVector3D(side, y + 0.001, 0.0));
                    pair.first.append(QDoubleVector3D(side, y - 0.001, 0.0));
                }
            } else {
                addXOffset(pair.first, side);
                if (footprintWidth > side)
                    pair.first = splitPolygonAtAxisValue(pair.first, 0, 0).second;
            }
            return ClippedFootprint(pair.first, pair.second, PolygonVector());
        }
    } else {
        if (clipX1) {
            QPair<PolygonVector, PolygonVector> pair = splitPolygonAtAxisValue(results, 0, side);
            if (pair.second.isEmpty()) {
                // if we touched the line but didn't cross it...
                for (int i = 0; i < pair.first.size(); ++i) {
                    if (qFuzzyCompare(side, pair.first.at(i).x()))
                        pair.second.append(pair.first.at(i));
                }
                if (pair.second.size() == 2) {
                    double y0 = pair.second[0].y();
                    double y1 = pair.second[1].y();
                    pair.second.clear();
                    pair.second.append(QDoubleVector3D(0, y0, 0.0));
                    pair.second.append(QDoubleVector3D(0.001, y0, 0.0));
                    pair.second.append(QDoubleVector3D(0.001, y1, 0.0));
                    pair.second.append(QDoubleVector3D(0, y1, 0.0));
                } else if (pair.second.size() == 1) {
                    // FIXME this is trickier
                    // - touching at one point on the tile boundary
                    // - probably need to build a triangular polygon across the edge
                    // - don't want to add another y tile if we can help it
                    //   - initial version doesn't care
                    double y = pair.second.at(0).y();
                    pair.second.clear();
                    pair.second.append(QDoubleVector3D(0.001, y, 0.0));
                    pair.second.append(QDoubleVector3D(0.0, y - 0.001, 0.0));
                    pair.second.append(QDoubleVector3D(0.0, y + 0.001, 0.0));
                }
            } else {
                addXOffset(pair.second, -side);
                if (footprintWidth > side)
                    pair.second = splitPolygonAtAxisValue(pair.second, 0, side).first;
            }
            return ClippedFootprint(PolygonVector(), pair.first, pair.second);
        } else {
            return ClippedFootprint(PolygonVector(), results, PolygonVector());
        }
    }

}

QList<QPair<double, int> > QGeoCameraTilesPrivate::tileIntersections(double p1, int t1, double p2, int t2) const
{
    if (t1 == t2) {
        QList<QPair<double, int> > results = QList<QPair<double, int> >();
        results.append(QPair<double, int>(0.0, t1));
        return results;
    }

    int step = 1;
    if (t1 > t2) {
        step = -1;
    }

    int size = 1 + ((t2 - t1) / step);

    QList<QPair<double, int> > results = QList<QPair<double, int> >();

    results.append(QPair<double, int>(0.0, t1));

    if (step == 1) {
        for (int i = 1; i < size; ++i) {
            double f = (t1 + i - p1) / (p2 - p1);
            results.append(QPair<double, int>(f, t1 + i));
        }
    } else {
        for (int i = 1; i < size; ++i) {
            double f = (t1 - i + 1 - p1) / (p2 - p1);
            results.append(QPair<double, int>(f, t1 - i));
        }
    }

    return results;
}

QSet<QGeoTileSpec> QGeoCameraTilesPrivate::tilesFromPolygon(const PolygonVector &polygon) const
{
    int numPoints = polygon.size();

    if (numPoints == 0)
        return QSet<QGeoTileSpec>();

    QVector<int> tilesX(polygon.size());
    QVector<int> tilesY(polygon.size());

    // grab tiles at the corners of the polygon
    for (int i = 0; i < numPoints; ++i) {

        QDoubleVector2D p = polygon.at(i).toVector2D();

        int x = 0;
        int y = 0;

        if (qFuzzyCompare(p.x(), m_sideLength * 1.0))
            x = m_sideLength - 1;
        else {
            x = static_cast<int>(p.x()) % m_sideLength;
            if ( !qFuzzyCompare(p.x(), 1.0 * x) && qFuzzyCompare(p.x(), 1.0 * (x + 1)) )
                x++;
        }

        if (qFuzzyCompare(p.y(), m_sideLength * 1.0))
            y = m_sideLength - 1;
        else {
            y = static_cast<int>(p.y()) % m_sideLength;
            if ( !qFuzzyCompare(p.y(), 1.0 * y) && qFuzzyCompare(p.y(), 1.0 * (y + 1)) )
                y++;
        }

        tilesX[i] = x;
        tilesY[i] = y;
    }

    QGeoCameraTilesPrivate::TileMap map;

    // walk along the edges of the polygon and add all tiles covered by them
    for (int i1 = 0; i1 < numPoints; ++i1) {
        int i2 = (i1 + 1) % numPoints;

        double x1 = polygon.at(i1).get(0);
        double x2 = polygon.at(i2).get(0);

        bool xFixed = qFuzzyCompare(x1, x2);
        bool xIntegral = qFuzzyCompare(x1, std::floor(x1)) || qFuzzyCompare(x1 + 1.0, std::floor(x1 + 1.0));

        QList<QPair<double, int> > xIntersects
                = tileIntersections(x1,
                                    tilesX.at(i1),
                                    x2,
                                    tilesX.at(i2));

        double y1 = polygon.at(i1).get(1);
        double y2 = polygon.at(i2).get(1);

        bool yFixed = qFuzzyCompare(y1, y2);
        bool yIntegral = qFuzzyCompare(y1, std::floor(y1)) || qFuzzyCompare(y1 + 1.0, std::floor(y1 + 1.0));

        QList<QPair<double, int> > yIntersects
                = tileIntersections(y1,
                                    tilesY.at(i1),
                                    y2,
                                    tilesY.at(i2));

        int x = xIntersects.takeFirst().second;
        int y = yIntersects.takeFirst().second;


        /*
          If the polygon coincides with the tile edges we must be
          inclusive and grab all tiles on both sides. We also need
          to handle tiles with corners coindent with the
          corners of the polygon.
          e.g. all tiles marked with 'x' will be added

              "+" - tile boundaries
              "O" - polygon boundary

                + + + + + + + + + + + + + + + + + + + + +
                +       +       +       +       +       +
                +       +   x   +   x   +   x   +       +
                +       +       +       +       +       +
                + + + + + + + + O O O O O + + + + + + + +
                +       +       O       0       +       +
                +       +   x   O   x   0   x   +       +
                +       +       O       0       +       +
                + + + + + + + + O 0 0 0 0 + + + + + + + +
                +       +       +       +       +       +
                +       +   x   +   x   +   x   +       +
                +       +       +       +       +       +
                + + + + + + + + + + + + + + + + + + + + +
        */


        int xOther = x;
        int yOther = y;

        if (xFixed && xIntegral) {
             if (y2 < y1) {
                 xOther = qMax(0, x - 1);
            }
        }

        if (yFixed && yIntegral) {
            if (x1 < x2) {
                yOther = qMax(0, y - 1);

            }
        }

        if (xIntegral) {
            map.add(xOther, y);
            if (yIntegral)
                map.add(xOther, yOther);

        }

        if (yIntegral)
            map.add(x, yOther);

        map.add(x,y);

        // top left corner
        int iPrev =  (i1 + numPoints - 1) % numPoints;
        double xPrevious = polygon.at(iPrev).get(0);
        double yPrevious = polygon.at(iPrev).get(1);
        bool xPreviousFixed = qFuzzyCompare(xPrevious, x1);
        if (xIntegral && xPreviousFixed && yIntegral && yFixed) {
            if ((x2 > x1) && (yPrevious > y1)) {
                if ((x - 1) > 0 && (y - 1) > 0)
                    map.add(x - 1, y - 1);
            } else if ((x2 < x1) && (yPrevious < y1)) {
                // what?
            }
        }

        // for the simple case where intersections do not coincide with
        // the boundaries, we move along the edge and add tiles until
        // the x and y intersection lists are exhausted

        while (!xIntersects.isEmpty() && !yIntersects.isEmpty()) {
            QPair<double, int> nextX = xIntersects.first();
            QPair<double, int> nextY = yIntersects.first();
            if (nextX.first < nextY.first) {
                x = nextX.second;
                map.add(x, y);
                xIntersects.removeFirst();

            } else if (nextX.first > nextY.first) {
                y = nextY.second;
                map.add(x, y);
                yIntersects.removeFirst();

            } else {
                map.add(x, nextY.second);
                map.add(nextX.second, y);
                x = nextX.second;
                y = nextY.second;
                map.add(x, y);
                xIntersects.removeFirst();
                yIntersects.removeFirst();
            }
        }

        while (!xIntersects.isEmpty()) {
            x = xIntersects.takeFirst().second;
            map.add(x, y);
            if (yIntegral && yFixed)
                map.add(x, yOther);

        }

        while (!yIntersects.isEmpty()) {
            y = yIntersects.takeFirst().second;
            map.add(x, y);
            if (xIntegral && xFixed)
                map.add(xOther, y);
        }
    }

    QSet<QGeoTileSpec> results;

    int z = m_intZoomLevel;

    typedef QMap<int, QPair<int, int> >::const_iterator iter;
    iter i = map.data.constBegin();
    iter end = map.data.constEnd();

    for (; i != end; ++i) {
        int y = i.key();
        int minX = i->first;
        int maxX = i->second;
        for (int x = minX; x <= maxX; ++x) {
            results.insert(QGeoTileSpec(m_pluginString, m_mapType.mapId(), z, x, y, m_mapVersion));
        }
    }

    return results;
}

QGeoCameraTilesPrivate::TileMap::TileMap() {}

void QGeoCameraTilesPrivate::TileMap::add(int tileX, int tileY)
{
    if (data.contains(tileY)) {
        int oldMinX = data.value(tileY).first;
        int oldMaxX = data.value(tileY).second;
        data.insert(tileY, QPair<int, int>(qMin(tileX, oldMinX), qMax(tileX, oldMaxX)));
    } else {
        data.insert(tileY, QPair<int, int>(tileX, tileX));
    }
}

QT_END_NAMESPACE