qgeopolygon.cpp

Go to the documentation of this file.

// Copyright (C) 2016 The Qt Company Ltd.
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
 
#include "qgeopolygon.h"
#include "qgeopolygon_p.h"
#include "qgeopath_p.h"
#include "qgeocircle.h"
 
#include "qgeocoordinate.h"
#include "qnumeric.h"
#include "qlocationutils_p.h"
#include "qwebmercator_p.h"
 
#include "qdoublevector2d_p.h"
#include "qdoublevector3d_p.h"
#include "qwebmercator_p.h"
 
QT_BEGIN_NAMESPACE
 
QT_IMPL_METATYPE_EXTERN(QGeoPolygon)
 
constexpr int kMaxInt = std::numeric_limits<int>::max();
constexpr auto kTooManyHoles = u"The polygon has more holes than fit into an int. "
                                "This can cause errors while querying holes from QML";
constexpr auto kTooManyElements = u"The polygon has more elements than fit into an int. "
                                   "This can cause errors while querying elements from QML";
 
/*
    \property QGeoPolygon::path
    \brief This property holds the list of coordinates for the geo polygon.
 
    The polygon is both invalid and empty if it contains no coordinate.
 
    A default constructed QGeoPolygon is therefore invalid.
*/
 
inline QGeoPolygonPrivate *QGeoPolygon::d_func()
{
    return static_cast<QGeoPolygonPrivate *>(d_ptr.data());
}
 
inline const QGeoPolygonPrivate *QGeoPolygon::d_func() const
{
    return static_cast<const QGeoPolygonPrivate *>(d_ptr.constData());
}
 
QGeoPolygon::QGeoPolygon()
:   QGeoShape(new QGeoPolygonPrivate())
{
}
 
QGeoPolygon::QGeoPolygon(const QList<QGeoCoordinate> &path)
:   QGeoShape(new QGeoPolygonPrivate(path))
{
}
 
QGeoPolygon::QGeoPolygon(const QGeoPolygon &other)
:   QGeoShape(other)
{
}
 
static void calculatePeripheralPoints(QList<QGeoCoordinate> &path,
                                      const QGeoCircle &circle,
                                      int steps)
{
    const QGeoCoordinate &center = circle.center();
    const qreal distance = circle.radius();
    // Calculate points based on great-circle distance
    // Calculation is the same as GeoCoordinate's atDistanceAndAzimuth function
    // but tweaked here for computing multiple points
 
    // pre-calculations
    steps = qMax(steps, 3);
    qreal centerLon = center.longitude();
    qreal latRad = QLocationUtils::radians(center.latitude());
    qreal lonRad = QLocationUtils::radians(centerLon);
    qreal cosLatRad = std::cos(latRad);
    qreal sinLatRad = std::sin(latRad);
    qreal ratio = (distance / QLocationUtils::earthMeanRadius());
    qreal cosRatio = std::cos(ratio);
    qreal sinRatio = std::sin(ratio);
    qreal sinLatRad_x_cosRatio = sinLatRad * cosRatio;
    qreal cosLatRad_x_sinRatio = cosLatRad * sinRatio;
    for (int i = 0; i < steps; ++i) {
        qreal azimuthRad = 2 * M_PI * i / steps;
        qreal resultLatRad = std::asin(sinLatRad_x_cosRatio
                                   + cosLatRad_x_sinRatio * std::cos(azimuthRad));
        qreal resultLonRad = lonRad + std::atan2(std::sin(azimuthRad) * cosLatRad_x_sinRatio,
                                       cosRatio - sinLatRad * std::sin(resultLatRad));
        qreal lat2 = QLocationUtils::degrees(resultLatRad);
        qreal lon2 = QLocationUtils::wrapLong(QLocationUtils::degrees(resultLonRad));
 
        path << QGeoCoordinate(lat2, lon2, center.altitude());
    }
}
 
QGeoPolygon::QGeoPolygon(const QGeoShape &other)
:   QGeoShape(other)
{
    if (type() != QGeoShape::PolygonType) {
        QGeoPolygonPrivate *poly = new QGeoPolygonPrivate();
        if (type() == QGeoShape::CircleType) {
            const QGeoCircle &circle = static_cast<const QGeoCircle &>(other);
            QList<QGeoCoordinate> perimeter;
            calculatePeripheralPoints(perimeter, circle, 128);
            poly->setPath(perimeter);
        } else if (type() == QGeoShape::RectangleType) {
            const QGeoRectangle &rect = static_cast<const QGeoRectangle &>(other);
            QList<QGeoCoordinate> perimeter;
            perimeter << rect.topLeft() << rect.topRight()
                      << rect.bottomRight() << rect.bottomLeft();
            poly->setPath(perimeter);
        }
        d_ptr = poly;
    }
}
 
QGeoPolygon::~QGeoPolygon() {}
 
QGeoPolygon &QGeoPolygon::operator=(const QGeoPolygon &other)
{
    QGeoShape::operator=(other);
    return *this;
}
 
void QGeoPolygon::setPerimeter(const QList<QGeoCoordinate> &path)
{
    Q_D(QGeoPolygon);
    return d->setPath(path);
}
 
const QList<QGeoCoordinate> &QGeoPolygon::perimeter() const
{
    Q_D(const QGeoPolygon);
    return d->path();
}
 
void QGeoPolygon::translate(double degreesLatitude, double degreesLongitude)
{
    Q_D(QGeoPolygon);
    d->translate(degreesLatitude, degreesLongitude);
}
 
QGeoPolygon QGeoPolygon::translated(double degreesLatitude, double degreesLongitude) const
{
    QGeoPolygon result(*this);
    result.translate(degreesLatitude, degreesLongitude);
    return result;
}
 
double QGeoPolygon::length(qsizetype indexFrom, qsizetype indexTo) const
{
    Q_D(const QGeoPolygon);
    return d->length(indexFrom, indexTo);
}
 
qsizetype QGeoPolygon::size() const
{
    Q_D(const QGeoPolygon);
    const qsizetype result = d->size();
    if (result > kMaxInt)
        qWarning() << kTooManyElements;
    return result;
}
 
void QGeoPolygon::addCoordinate(const QGeoCoordinate &coordinate)
{
    Q_D(QGeoPolygon);
    d->addCoordinate(coordinate);
    if (d->size() > kMaxInt)
        qWarning() << kTooManyElements;
}
 
void QGeoPolygon::insertCoordinate(qsizetype index, const QGeoCoordinate &coordinate)
{
    Q_D(QGeoPolygon);
    d->insertCoordinate(index, coordinate);
}
 
void QGeoPolygon::replaceCoordinate(qsizetype index, const QGeoCoordinate &coordinate)
{
    Q_D(QGeoPolygon);
    d->replaceCoordinate(index, coordinate);
}
 
QGeoCoordinate QGeoPolygon::coordinateAt(qsizetype index) const
{
    Q_D(const QGeoPolygon);
    return d->coordinateAt(index);
}
 
bool QGeoPolygon::containsCoordinate(const QGeoCoordinate &coordinate) const
{
    Q_D(const QGeoPolygon);
    return d->containsCoordinate(coordinate);
}
 
void QGeoPolygon::removeCoordinate(const QGeoCoordinate &coordinate)
{
    Q_D(QGeoPolygon);
    d->removeCoordinate(coordinate);
}
 
void QGeoPolygon::removeCoordinate(qsizetype index)
{
    Q_D(QGeoPolygon);
    d->removeCoordinate(index);
}
 
QString QGeoPolygon::toString() const
{
    if (type() != QGeoShape::PolygonType) {
        qWarning("Not a polygon");
        return QStringLiteral("QGeoPolygon(not a polygon)");
    }
 
    QString pathString;
    for (const auto &p : perimeter())
        pathString += p.toString() + QLatin1Char(',');
 
    return QStringLiteral("QGeoPolygon([ %1 ])").arg(pathString);
}
 
void QGeoPolygon::addHole(const QVariant &holePath)
{
    QList<QGeoCoordinate> qgcHolePath;
    if (holePath.canConvert<QVariantList>()) {
        const QVariantList qvlHolePath = holePath.toList();
        for (const QVariant &vertex : qvlHolePath) {
            if (vertex.canConvert<QGeoCoordinate>())
                qgcHolePath << vertex.value<QGeoCoordinate>();
        }
    }
    //ToDo: add QGeoShape support
    addHole(qgcHolePath);
}
 
void QGeoPolygon::addHole(const QList<QGeoCoordinate> &holePath)
{
    Q_D(QGeoPolygon);
    d->addHole(holePath);
    if (d->holesCount() > kMaxInt)
        qDebug() << kTooManyHoles;
}
 
const QVariantList QGeoPolygon::hole(qsizetype index) const
{
    Q_D(const QGeoPolygon);
    QVariantList holeCoordinates;
    for (const QGeoCoordinate &coords: d->holePath(index))
        holeCoordinates << QVariant::fromValue(coords);
    return holeCoordinates;
}
 
const QList<QGeoCoordinate> QGeoPolygon::holePath(qsizetype index) const
{
    Q_D(const QGeoPolygon);
    return d->holePath(index);
}
 
void QGeoPolygon::removeHole(qsizetype index)
{
    Q_D(QGeoPolygon);
    return d->removeHole(index);
}
 
qsizetype QGeoPolygon::holesCount() const
{
    Q_D(const QGeoPolygon);
    const qsizetype result = d->holesCount();
    if (result > kMaxInt)
        qWarning() << kTooManyHoles;
    return result;
}
 
/*******************************************************************************
 *
 * QGeoPathPrivate & friends
 *
*******************************************************************************/
 
QGeoPolygonPrivate::QGeoPolygonPrivate()
:   QGeoPathPrivate()
{
    type = QGeoShape::PolygonType;
}
 
QGeoPolygonPrivate::QGeoPolygonPrivate(const QList<QGeoCoordinate> &path)
:   QGeoPathPrivate(path)
{
    type = QGeoShape::PolygonType;
}
 
QGeoPolygonPrivate::~QGeoPolygonPrivate() {}
 
QGeoShapePrivate *QGeoPolygonPrivate::clone() const
{
    return new QGeoPolygonPrivate(*this);
}
 
bool QGeoPolygonPrivate::isValid() const
{
    return path().size() > 2;
}
 
bool QGeoPolygonPrivate::contains(const QGeoCoordinate &coordinate) const
{
    return polygonContains(coordinate);
}
 
inline static void translatePoly(   QList<QGeoCoordinate> &m_path,
                                    QList<QList<QGeoCoordinate>> &m_holesList,
                                    QGeoRectangle &m_bbox,
                                    double degreesLatitude,
                                    double degreesLongitude,
                                    double m_maxLati,
                                    double m_minLati)
{
    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));
    }
    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);
}
 
void QGeoPolygonPrivate::translate(double degreesLatitude, double degreesLongitude)
{
    // Need min/maxLati, so update bbox
    QList<double> m_deltaXs;
    double m_minX, m_maxX, m_minLati, m_maxLati;
    m_bboxDirty = false; // Updated in translatePoly
    computeBBox(m_path, m_deltaXs, m_minX, m_maxX, m_minLati, m_maxLati, m_bbox);
    translatePoly(m_path, m_holesList, m_bbox, degreesLatitude, degreesLongitude, m_maxLati, m_minLati);
    m_leftBoundWrapped = QWebMercator::coordToMercator(m_bbox.topLeft()).x();
    m_clipperDirty = true;
}
 
bool QGeoPolygonPrivate::operator==(const QGeoShapePrivate &other) const
{
    if (!QGeoShapePrivate::operator==(other)) // checks type
        return false;
 
    const QGeoPolygonPrivate &otherPath = static_cast<const QGeoPolygonPrivate &>(other);
    if (m_path.size() != otherPath.m_path.size()
            || m_holesList.size() != otherPath.m_holesList.size())
        return false;
    return  m_path == otherPath.m_path && m_holesList == otherPath.m_holesList;
}
 
size_t QGeoPolygonPrivate::hash(size_t seed) const
{
    const size_t pointsHash = qHashRange(m_path.cbegin(), m_path.cend(), seed);
    const size_t holesHash = qHashRange(m_holesList.cbegin(), m_holesList.cend(), seed);
    return qHashMulti(seed, pointsHash, holesHash);
}
 
void QGeoPolygonPrivate::addHole(const QList<QGeoCoordinate> &holePath)
{
    for (const QGeoCoordinate &holeVertex: holePath)
        if (!holeVertex.isValid())
            return;
 
    m_holesList << holePath;
    // ToDo: mark clipper dirty when hole caching gets added
}
 
const QList<QGeoCoordinate> QGeoPolygonPrivate::holePath(qsizetype index) const
{
    return m_holesList.at(index);
}
 
void QGeoPolygonPrivate::removeHole(qsizetype index)
{
    if (index < 0 || index >= m_holesList.size())
        return;
 
    m_holesList.removeAt(index);
    // ToDo: mark clipper dirty when hole caching gets added
}
 
qsizetype QGeoPolygonPrivate::holesCount() const
{
    return m_holesList.size();
}
 
bool QGeoPolygonPrivate::polygonContains(const QGeoCoordinate &coordinate) const
{
    if (m_clipperDirty)
        const_cast<QGeoPolygonPrivate *>(this)->updateClipperPath(); // this one updates bbox too if needed
 
    QDoubleVector2D coord = QWebMercator::coordToMercator(coordinate);
 
    if (coord.x() < m_leftBoundWrapped)
        coord.setX(coord.x() + 1.0);
 
    if (!m_clipperWrapper.pointInPolygon(coord))
        return false;
 
    // else iterates the holes List checking whether the point is contained inside the holes
    for (const QList<QGeoCoordinate> &holePath : std::as_const(m_holesList)) {
        // ToDo: cache these
        QGeoPolygon holePolygon;
        holePolygon.setPerimeter(holePath);
        if (holePolygon.contains(coordinate))
            return false;
    }
    return true;
}
 
void QGeoPolygonPrivate::markDirty()
{
    m_bboxDirty = m_clipperDirty = true;
}
 
void QGeoPolygonPrivate::updateClipperPath()
{
    if (m_bboxDirty)
        computeBoundingBox();
    m_clipperDirty = false;
 
    QList<QDoubleVector2D> preservedPath;
    for (const QGeoCoordinate &c : m_path) {
        QDoubleVector2D crd = QWebMercator::coordToMercator(c);
        if (crd.x() < m_leftBoundWrapped)
            crd.setX(crd.x() + 1.0);
        preservedPath << crd;
    }
    m_clipperWrapper.setPolygon(preservedPath);
}
 
QGeoPolygonPrivateEager::QGeoPolygonPrivateEager() : QGeoPolygonPrivate()
{
    m_bboxDirty = false; // never dirty on the eager version
}
 
QGeoPolygonPrivateEager::QGeoPolygonPrivateEager(const QList<QGeoCoordinate> &path) : QGeoPolygonPrivate(path)
{
    m_bboxDirty = false; // never dirty on the eager version
}
 
QGeoPolygonPrivateEager::~QGeoPolygonPrivateEager()
{
 
}
 
QGeoShapePrivate *QGeoPolygonPrivateEager::clone() const
{
    return new QGeoPolygonPrivate(*this);
}
 
void QGeoPolygonPrivateEager::translate(double degreesLatitude, double degreesLongitude)
{
    translatePoly(m_path, m_holesList, m_bbox, degreesLatitude, degreesLongitude, m_maxLati, m_minLati);
    m_leftBoundWrapped = QWebMercator::coordToMercator(m_bbox.topLeft()).x();
    m_clipperDirty = true;
}
 
void QGeoPolygonPrivateEager::markDirty()
{
    m_clipperDirty = true;
    computeBoundingBox();
}
 
void QGeoPolygonPrivateEager::addCoordinate(const QGeoCoordinate &coordinate)
{
    if (!coordinate.isValid())
        return;
    m_path.append(coordinate);
    m_clipperDirty = true;
    updateBoundingBox(); // do not markDirty as it uses computeBoundingBox instead
}
 
void QGeoPolygonPrivateEager::computeBoundingBox()
{
    computeBBox(m_path, m_deltaXs, m_minX, m_maxX, m_minLati, m_maxLati, m_bbox);
    m_leftBoundWrapped = QWebMercator::coordToMercator(m_bbox.topLeft()).x();
}
 
void QGeoPolygonPrivateEager::updateBoundingBox()
{
    updateBBox(m_path, m_deltaXs, m_minX, m_maxX, m_minLati, m_maxLati, m_bbox);
}
 
QGeoPolygonEager::QGeoPolygonEager() : QGeoPolygon()
{
    d_ptr = new QGeoPolygonPrivateEager;
}
 
QGeoPolygonEager::QGeoPolygonEager(const QList<QGeoCoordinate> &path) : QGeoPolygon()
{
    d_ptr = new QGeoPolygonPrivateEager(path);
}
 
QGeoPolygonEager::QGeoPolygonEager(const QGeoPolygon &other) : QGeoPolygon()
{
    // without being able to dynamic_cast the d_ptr, only way to be sure is to reconstruct a new QGeoPolygonPrivateEager
    d_ptr = new QGeoPolygonPrivateEager;
    setPerimeter(other.perimeter());
    for (qsizetype i = 0; i < other.holesCount(); i++)
        addHole(other.holePath(i));
}
 
QGeoPolygonEager::QGeoPolygonEager(const QGeoShape &other) : QGeoPolygon()
{
    if (other.type() == QGeoShape::PolygonType)
        *this = QGeoPolygonEager(QGeoPolygon(other));
    else
        d_ptr = new QGeoPolygonPrivateEager;
}
 
QGeoPolygonEager::~QGeoPolygonEager()
{
 
}
 
QT_END_NAMESPACE
 
#include "moc_qgeopolygon_p.cpp"
#include "moc_qgeopolygon.cpp"