From 2ab93acd9751b3ffe2c36a4a0e37dc792686a08f Mon Sep 17 00:00:00 2001 From: Paolo Angelelli Date: Fri, 7 Jul 2017 15:31:00 +0200 Subject: Fix dragging items out of map bounds In 5.9.0 map items are clipped against the visible region. This implies that their geometry is also clipped against the visible region. This is problematic in ::geometryChanged, since the old geometry is always clipped in this way. This patch clips items against a "projectable" region instead, that is the part of the map that is in front of the camera. Since this can produce very large vertices, mapbox earcut 3rd party library is pulled in, to replace qTriangulate that only supports coordinates up to 1<<21. Task-number: QTBUG-61727 Change-Id: I7449e755a4848a2b2107c5de4e27821e3e887bfb Reviewed-by: Paolo Angelelli --- src/3rdparty/earcut/LICENSE | 15 + src/3rdparty/earcut/earcut.hpp | 773 +++++++++++++++++++++ src/3rdparty/earcut/qt_attribution.json | 13 + .../declarativemaps/qdeclarativepolygonmapitem.cpp | 53 +- .../qdeclarativepolylinemapitem.cpp | 2 +- src/location/location.pro | 1 + src/location/maps/qgeoprojection.cpp | 57 +- src/location/maps/qgeoprojection_p.h | 4 +- 8 files changed, 895 insertions(+), 23 deletions(-) create mode 100644 src/3rdparty/earcut/LICENSE create mode 100644 src/3rdparty/earcut/earcut.hpp create mode 100644 src/3rdparty/earcut/qt_attribution.json diff --git a/src/3rdparty/earcut/LICENSE b/src/3rdparty/earcut/LICENSE new file mode 100644 index 00000000..8bafb577 --- /dev/null +++ b/src/3rdparty/earcut/LICENSE @@ -0,0 +1,15 @@ +ISC License + +Copyright (c) 2015, Mapbox + +Permission to use, copy, modify, and/or distribute this software for any purpose +with or without fee is hereby granted, provided that the above copyright notice +and this permission notice appear in all copies. + +THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH +REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND +FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, +INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS +OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER +TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF +THIS SOFTWARE. diff --git a/src/3rdparty/earcut/earcut.hpp b/src/3rdparty/earcut/earcut.hpp new file mode 100644 index 00000000..1f14b9f7 --- /dev/null +++ b/src/3rdparty/earcut/earcut.hpp @@ -0,0 +1,773 @@ +#pragma once + +#include +#include +#include +#include +#include + +namespace mapbox { + +namespace util { + +template struct nth { + inline static typename std::tuple_element::type + get(const T& t) { return std::get(t); }; +}; + +} + +namespace detail { + +template +class Earcut { +public: + std::vector indices; + N vertices = 0; + + template + void operator()(const Polygon& points); + +private: + struct Node { + Node(N index, double x_, double y_) : i(index), x(x_), y(y_) {} + Node(const Node&) = delete; + Node& operator=(const Node&) = delete; + Node(Node&&) = delete; + Node& operator=(Node&&) = delete; + + const N i; + const double x; + const double y; + + // previous and next vertice nodes in a polygon ring + Node* prev = nullptr; + Node* next = nullptr; + + // z-order curve value + int32_t z = 0; + + // previous and next nodes in z-order + Node* prevZ = nullptr; + Node* nextZ = nullptr; + + // indicates whether this is a steiner point + bool steiner = false; + }; + + template Node* linkedList(const Ring& points, const bool clockwise); + Node* filterPoints(Node* start, Node* end = nullptr); + void earcutLinked(Node* ear, int pass = 0); + bool isEar(Node* ear); + bool isEarHashed(Node* ear); + Node* cureLocalIntersections(Node* start); + void splitEarcut(Node* start); + template Node* eliminateHoles(const Polygon& points, Node* outerNode); + void eliminateHole(Node* hole, Node* outerNode); + Node* findHoleBridge(Node* hole, Node* outerNode); + void indexCurve(Node* start); + Node* sortLinked(Node* list); + int32_t zOrder(const double x_, const double y_); + Node* getLeftmost(Node* start); + bool pointInTriangle(double ax, double ay, double bx, double by, double cx, double cy, double px, double py) const; + bool isValidDiagonal(Node* a, Node* b); + double area(const Node* p, const Node* q, const Node* r) const; + bool equals(const Node* p1, const Node* p2); + bool intersects(const Node* p1, const Node* q1, const Node* p2, const Node* q2); + bool intersectsPolygon(const Node* a, const Node* b); + bool locallyInside(const Node* a, const Node* b); + bool middleInside(const Node* a, const Node* b); + Node* splitPolygon(Node* a, Node* b); + template Node* insertNode(N i, const Point& p, Node* last); + void removeNode(Node* p); + + bool hashing; + double minX, maxX; + double minY, maxY; + double size; + + template > + class ObjectPool { + public: + ObjectPool() { } + ObjectPool(std::size_t blockSize_) { + reset(blockSize_); + } + ~ObjectPool() { + clear(); + } + template + T* construct(Args&&... args) { + if (currentIndex >= blockSize) { + currentBlock = alloc.allocate(blockSize); + allocations.emplace_back(currentBlock); + currentIndex = 0; + } + T* object = ¤tBlock[currentIndex++]; + alloc.construct(object, std::forward(args)...); + return object; + } + void reset(std::size_t newBlockSize) { + for (auto allocation : allocations) alloc.deallocate(allocation, blockSize); + allocations.clear(); + blockSize = std::max(1, newBlockSize); + currentBlock = nullptr; + currentIndex = blockSize; + } + void clear() { reset(blockSize); } + private: + T* currentBlock = nullptr; + std::size_t currentIndex = 1; + std::size_t blockSize = 1; + std::vector allocations; + Alloc alloc; + }; + ObjectPool nodes; +}; + +template template +void Earcut::operator()(const Polygon& points) { + // reset + indices.clear(); + vertices = 0; + + if (points.empty()) return; + + double x; + double y; + size = 0; + int threshold = 80; + std::size_t len = 0; + + for (size_t i = 0; threshold >= 0 && i < points.size(); i++) { + threshold -= static_cast(points[i].size()); + len += points[i].size(); + } + + //estimate size of nodes and indices + nodes.reset(len * 3 / 2); + indices.reserve(len + points[0].size()); + + Node* outerNode = linkedList(points[0], true); + if (!outerNode) return; + + if (points.size() > 1) outerNode = eliminateHoles(points, outerNode); + + // if the shape is not too simple, we'll use z-order curve hash later; calculate polygon bbox + hashing = threshold < 0; + if (hashing) { + Node* p = outerNode->next; + minX = maxX = p->x; + minY = maxY = p->y; + do { + x = p->x; + y = p->y; + minX = (std::min)(minX, x); + minY = (std::min)(minY, y); + maxX = (std::max)(maxX, x); + maxY = (std::max)(maxY, y); + p = p->next; + } while (p != outerNode); + + // minX, minY and size are later used to transform coords into integers for z-order calculation + size = (std::max)(maxX - minX, maxY - minY); + } + + earcutLinked(outerNode); + + nodes.clear(); +} + +// create a circular doubly linked list from polygon points in the specified winding order +template template +typename Earcut::Node* +Earcut::linkedList(const Ring& points, const bool clockwise) { + using Point = typename Ring::value_type; + double sum = 0; + const int len = static_cast(points.size()); + int i, j; + Point p1, p2; + Node* last = nullptr; + + // calculate original winding order of a polygon ring + for (i = 0, j = len - 1; i < len; j = i++) { + p1 = points[i]; + p2 = points[j]; + const double p20 = util::nth<0, Point>::get(p2); + const double p10 = util::nth<0, Point>::get(p1); + const double p11 = util::nth<1, Point>::get(p1); + const double p21 = util::nth<1, Point>::get(p2); + sum += (p20 - p10) * (p11 + p21); + } + + // link points into circular doubly-linked list in the specified winding order + if (clockwise == (sum > 0)) { + for (i = 0; i < len; i++) last = insertNode(vertices + i, points[i], last); + } else { + for (i = len - 1; i >= 0; i--) last = insertNode(vertices + i, points[i], last); + } + + if (last && equals(last, last->next)) { + removeNode(last); + last = last->next; + } + + vertices += len; + + return last; +} + +// eliminate colinear or duplicate points +template +typename Earcut::Node* +Earcut::filterPoints(Node* start, Node* end) { + if (!end) end = start; + + Node* p = start; + bool again; + do { + again = false; + + if (!p->steiner && (equals(p, p->next) || area(p->prev, p, p->next) == 0)) { + removeNode(p); + p = end = p->prev; + + if (p == p->next) return nullptr; + again = true; + + } else { + p = p->next; + } + } while (again || p != end); + + return end; +} + +// main ear slicing loop which triangulates a polygon (given as a linked list) +template +void Earcut::earcutLinked(Node* ear, int pass) { + if (!ear) return; + + // interlink polygon nodes in z-order + if (!pass && hashing) indexCurve(ear); + + Node* stop = ear; + Node* prev; + Node* next; + + int iterations = 0; + + // iterate through ears, slicing them one by one + while (ear->prev != ear->next) { + iterations++; + prev = ear->prev; + next = ear->next; + + if (hashing ? isEarHashed(ear) : isEar(ear)) { + // cut off the triangle + indices.emplace_back(prev->i); + indices.emplace_back(ear->i); + indices.emplace_back(next->i); + + removeNode(ear); + + // skipping the next vertice leads to less sliver triangles + ear = next->next; + stop = next->next; + + continue; + } + + ear = next; + + // if we looped through the whole remaining polygon and can't find any more ears + if (ear == stop) { + // try filtering points and slicing again + if (!pass) earcutLinked(filterPoints(ear), 1); + + // if this didn't work, try curing all small self-intersections locally + else if (pass == 1) { + ear = cureLocalIntersections(ear); + earcutLinked(ear, 2); + + // as a last resort, try splitting the remaining polygon into two + } else if (pass == 2) splitEarcut(ear); + + break; + } + } +} + +// check whether a polygon node forms a valid ear with adjacent nodes +template +bool Earcut::isEar(Node* ear) { + const Node* a = ear->prev; + const Node* b = ear; + const Node* c = ear->next; + + if (area(a, b, c) >= 0) return false; // reflex, can't be an ear + + // now make sure we don't have other points inside the potential ear + Node* p = ear->next->next; + + while (p != ear->prev) { + if (pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) && + area(p->prev, p, p->next) >= 0) return false; + p = p->next; + } + + return true; +} + +template +bool Earcut::isEarHashed(Node* ear) { + const Node* a = ear->prev; + const Node* b = ear; + const Node* c = ear->next; + + if (area(a, b, c) >= 0) return false; // reflex, can't be an ear + + // triangle bbox; min & max are calculated like this for speed + const double minTX = (std::min)(a->x, (std::min)(b->x, c->x)); + const double minTY = (std::min)(a->y, (std::min)(b->y, c->y)); + const double maxTX = (std::max)(a->x, (std::max)(b->x, c->x)); + const double maxTY = (std::max)(a->y, (std::max)(b->y, c->y)); + + // z-order range for the current triangle bbox; + const int32_t minZ = zOrder(minTX, minTY); + const int32_t maxZ = zOrder(maxTX, maxTY); + + // first look for points inside the triangle in increasing z-order + Node* p = ear->nextZ; + + while (p && p->z <= maxZ) { + if (p != ear->prev && p != ear->next && + pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) && + area(p->prev, p, p->next) >= 0) return false; + p = p->nextZ; + } + + // then look for points in decreasing z-order + p = ear->prevZ; + + while (p && p->z >= minZ) { + if (p != ear->prev && p != ear->next && + pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) && + area(p->prev, p, p->next) >= 0) return false; + p = p->prevZ; + } + + return true; +} + +// go through all polygon nodes and cure small local self-intersections +template +typename Earcut::Node* +Earcut::cureLocalIntersections(Node* start) { + Node* p = start; + do { + Node* a = p->prev; + Node* b = p->next->next; + + // a self-intersection where edge (v[i-1],v[i]) intersects (v[i+1],v[i+2]) + if (!equals(a, b) && intersects(a, p, p->next, b) && locallyInside(a, b) && locallyInside(b, a)) { + indices.emplace_back(a->i); + indices.emplace_back(p->i); + indices.emplace_back(b->i); + + // remove two nodes involved + removeNode(p); + removeNode(p->next); + + p = start = b; + } + p = p->next; + } while (p != start); + + return p; +} + +// try splitting polygon into two and triangulate them independently +template +void Earcut::splitEarcut(Node* start) { + // look for a valid diagonal that divides the polygon into two + Node* a = start; + do { + Node* b = a->next->next; + while (b != a->prev) { + if (a->i != b->i && isValidDiagonal(a, b)) { + // split the polygon in two by the diagonal + Node* c = splitPolygon(a, b); + + // filter colinear points around the cuts + a = filterPoints(a, a->next); + c = filterPoints(c, c->next); + + // run earcut on each half + earcutLinked(a); + earcutLinked(c); + return; + } + b = b->next; + } + a = a->next; + } while (a != start); +} + +// link every hole into the outer loop, producing a single-ring polygon without holes +template template +typename Earcut::Node* +Earcut::eliminateHoles(const Polygon& points, Node* outerNode) { + const size_t len = points.size(); + + std::vector queue; + for (size_t i = 1; i < len; i++) { + Node* list = linkedList(points[i], false); + if (list) { + if (list == list->next) list->steiner = true; + queue.push_back(getLeftmost(list)); + } + } + std::sort(queue.begin(), queue.end(), [](const Node* a, const Node* b) { + return a->x < b->x; + }); + + // process holes from left to right + for (size_t i = 0; i < queue.size(); i++) { + eliminateHole(queue[i], outerNode); + outerNode = filterPoints(outerNode, outerNode->next); + } + + return outerNode; +} + +// find a bridge between vertices that connects hole with an outer ring and and link it +template +void Earcut::eliminateHole(Node* hole, Node* outerNode) { + outerNode = findHoleBridge(hole, outerNode); + if (outerNode) { + Node* b = splitPolygon(outerNode, hole); + filterPoints(b, b->next); + } +} + +// David Eberly's algorithm for finding a bridge between hole and outer polygon +template +typename Earcut::Node* +Earcut::findHoleBridge(Node* hole, Node* outerNode) { + Node* p = outerNode; + double hx = hole->x; + double hy = hole->y; + double qx = -std::numeric_limits::infinity(); + Node* m = nullptr; + + // find a segment intersected by a ray from the hole's leftmost Vertex to the left; + // segment's endpoint with lesser x will be potential connection Vertex + do { + if (hy <= p->y && hy >= p->next->y && p->next->y != p->y) { + double x = p->x + (hy - p->y) * (p->next->x - p->x) / (p->next->y - p->y); + if (x <= hx && x > qx) { + qx = x; + if (x == hx) { + if (hy == p->y) return p; + if (hy == p->next->y) return p->next; + } + m = p->x < p->next->x ? p : p->next; + } + } + p = p->next; + } while (p != outerNode); + + if (!m) return 0; + + if (hx == qx) return m->prev; + + // look for points inside the triangle of hole Vertex, segment intersection and endpoint; + // if there are no points found, we have a valid connection; + // otherwise choose the Vertex of the minimum angle with the ray as connection Vertex + + const Node* stop = m; + double tanMin = std::numeric_limits::infinity(); + double tanCur = 0; + + p = m->next; + double mx = m->x; + double my = m->y; + + while (p != stop) { + if (hx >= p->x && p->x >= mx && hx != p->x && + pointInTriangle(hy < my ? hx : qx, hy, mx, my, hy < my ? qx : hx, hy, p->x, p->y)) { + + tanCur = std::abs(hy - p->y) / (hx - p->x); // tangential + + if ((tanCur < tanMin || (tanCur == tanMin && p->x > m->x)) && locallyInside(p, hole)) { + m = p; + tanMin = tanCur; + } + } + + p = p->next; + } + + return m; +} + +// interlink polygon nodes in z-order +template +void Earcut::indexCurve(Node* start) { + assert(start); + Node* p = start; + + do { + p->z = p->z ? p->z : zOrder(p->x, p->y); + p->prevZ = p->prev; + p->nextZ = p->next; + p = p->next; + } while (p != start); + + p->prevZ->nextZ = nullptr; + p->prevZ = nullptr; + + sortLinked(p); +} + +// Simon Tatham's linked list merge sort algorithm +// http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html +template +typename Earcut::Node* +Earcut::sortLinked(Node* list) { + assert(list); + Node* p; + Node* q; + Node* e; + Node* tail; + int i, numMerges, pSize, qSize; + int inSize = 1; + + while (true) { + p = list; + list = nullptr; + tail = nullptr; + numMerges = 0; + + while (p) { + numMerges++; + q = p; + pSize = 0; + for (i = 0; i < inSize; i++) { + pSize++; + q = q->nextZ; + if (!q) break; + } + + qSize = inSize; + + while (pSize > 0 || (qSize > 0 && q)) { + + if (pSize == 0) { + e = q; + q = q->nextZ; + qSize--; + } else if (qSize == 0 || !q) { + e = p; + p = p->nextZ; + pSize--; + } else if (p->z <= q->z) { + e = p; + p = p->nextZ; + pSize--; + } else { + e = q; + q = q->nextZ; + qSize--; + } + + if (tail) tail->nextZ = e; + else list = e; + + e->prevZ = tail; + tail = e; + } + + p = q; + } + + tail->nextZ = nullptr; + + if (numMerges <= 1) return list; + + inSize *= 2; + } +} + +// z-order of a Vertex given coords and size of the data bounding box +template +int32_t Earcut::zOrder(const double x_, const double y_) { + // coords are transformed into non-negative 15-bit integer range + int32_t x = static_cast(32767.0 * (x_ - minX) / size); + int32_t y = static_cast(32767.0 * (y_ - minY) / size); + + x = (x | (x << 8)) & 0x00FF00FF; + x = (x | (x << 4)) & 0x0F0F0F0F; + x = (x | (x << 2)) & 0x33333333; + x = (x | (x << 1)) & 0x55555555; + + y = (y | (y << 8)) & 0x00FF00FF; + y = (y | (y << 4)) & 0x0F0F0F0F; + y = (y | (y << 2)) & 0x33333333; + y = (y | (y << 1)) & 0x55555555; + + return x | (y << 1); +} + +// find the leftmost node of a polygon ring +template +typename Earcut::Node* +Earcut::getLeftmost(Node* start) { + Node* p = start; + Node* leftmost = start; + do { + if (p->x < leftmost->x) leftmost = p; + p = p->next; + } while (p != start); + + return leftmost; +} + +// check if a point lies within a convex triangle +template +bool Earcut::pointInTriangle(double ax, double ay, double bx, double by, double cx, double cy, double px, double py) const { + return (cx - px) * (ay - py) - (ax - px) * (cy - py) >= 0 && + (ax - px) * (by - py) - (bx - px) * (ay - py) >= 0 && + (bx - px) * (cy - py) - (cx - px) * (by - py) >= 0; +} + +// check if a diagonal between two polygon nodes is valid (lies in polygon interior) +template +bool Earcut::isValidDiagonal(Node* a, Node* b) { + return a->next->i != b->i && a->prev->i != b->i && !intersectsPolygon(a, b) && + locallyInside(a, b) && locallyInside(b, a) && middleInside(a, b); +} + +// signed area of a triangle +template +double Earcut::area(const Node* p, const Node* q, const Node* r) const { + return (q->y - p->y) * (r->x - q->x) - (q->x - p->x) * (r->y - q->y); +} + +// check if two points are equal +template +bool Earcut::equals(const Node* p1, const Node* p2) { + return p1->x == p2->x && p1->y == p2->y; +} + +// check if two segments intersect +template +bool Earcut::intersects(const Node* p1, const Node* q1, const Node* p2, const Node* q2) { + if ((equals(p1, q1) && equals(p2, q2)) || + (equals(p1, q2) && equals(p2, q1))) return true; + return (area(p1, q1, p2) > 0) != (area(p1, q1, q2) > 0) && + (area(p2, q2, p1) > 0) != (area(p2, q2, q1) > 0); +} + +// check if a polygon diagonal intersects any polygon segments +template +bool Earcut::intersectsPolygon(const Node* a, const Node* b) { + const Node* p = a; + do { + if (p->i != a->i && p->next->i != a->i && p->i != b->i && p->next->i != b->i && + intersects(p, p->next, a, b)) return true; + p = p->next; + } while (p != a); + + return false; +} + +// check if a polygon diagonal is locally inside the polygon +template +bool Earcut::locallyInside(const Node* a, const Node* b) { + return area(a->prev, a, a->next) < 0 ? + area(a, b, a->next) >= 0 && area(a, a->prev, b) >= 0 : + area(a, b, a->prev) < 0 || area(a, a->next, b) < 0; +} + +// check if the middle Vertex of a polygon diagonal is inside the polygon +template +bool Earcut::middleInside(const Node* a, const Node* b) { + const Node* p = a; + bool inside = false; + double px = (a->x + b->x) / 2; + double py = (a->y + b->y) / 2; + do { + if (((p->y > py) != (p->next->y > py)) && p->next->y != p->y && + (px < (p->next->x - p->x) * (py - p->y) / (p->next->y - p->y) + p->x)) + inside = !inside; + p = p->next; + } while (p != a); + + return inside; +} + +// link two polygon vertices with a bridge; if the vertices belong to the same ring, it splits +// polygon into two; if one belongs to the outer ring and another to a hole, it merges it into a +// single ring +template +typename Earcut::Node* +Earcut::splitPolygon(Node* a, Node* b) { + Node* a2 = nodes.construct(a->i, a->x, a->y); + Node* b2 = nodes.construct(b->i, b->x, b->y); + Node* an = a->next; + Node* bp = b->prev; + + a->next = b; + b->prev = a; + + a2->next = an; + an->prev = a2; + + b2->next = a2; + a2->prev = b2; + + bp->next = b2; + b2->prev = bp; + + return b2; +} + +// create a node and util::optionally link it with previous one (in a circular doubly linked list) +template template +typename Earcut::Node* +Earcut::insertNode(N i, const Point& pt, Node* last) { + Node* p = nodes.construct(i, util::nth<0, Point>::get(pt), util::nth<1, Point>::get(pt)); + + if (!last) { + p->prev = p; + p->next = p; + + } else { + assert(last); + p->next = last->next; + p->prev = last; + last->next->prev = p; + last->next = p; + } + return p; +} + +template +void Earcut::removeNode(Node* p) { + p->next->prev = p->prev; + p->prev->next = p->next; + + if (p->prevZ) p->prevZ->nextZ = p->nextZ; + if (p->nextZ) p->nextZ->prevZ = p->prevZ; +} +} + +template +std::vector earcut(const Polygon& poly) { + mapbox::detail::Earcut earcut; + earcut(poly); + return earcut.indices; +} +} diff --git a/src/3rdparty/earcut/qt_attribution.json b/src/3rdparty/earcut/qt_attribution.json new file mode 100644 index 00000000..0e52989c --- /dev/null +++ b/src/3rdparty/earcut/qt_attribution.json @@ -0,0 +1,13 @@ +{ + "Id": "earcut", + "Name": "Earcut Polygon Triangulation Library", + "QDocModule": "qtlocation", + "QtUsage": "Used in the QML plugin of Qt Location.", + + "Description": "A C++ port of earcut.js, a fast, header-only polygon triangulation library.", + "Homepage": "https://github.com/mapbox/earcut.hpp", + "LicenseId": "ISC", + "License": "ISC License", + "LicenseFile": "LICENSE", + "Copyright": "Copyright (c) 2015 Mapbox" +} diff --git a/src/location/declarativemaps/qdeclarativepolygonmapitem.cpp b/src/location/declarativemaps/qdeclarativepolygonmapitem.cpp index daa1a9fc..3218f9f1 100644 --- a/src/location/declarativemaps/qdeclarativepolygonmapitem.cpp +++ b/src/location/declarativemaps/qdeclarativepolygonmapitem.cpp @@ -53,6 +53,8 @@ /* poly2tri triangulator includes */ #include +#include +#include QT_BEGIN_NAMESPACE @@ -185,7 +187,7 @@ void QGeoMapPolygonGeometry::updateSourcePoints(const QGeoMap &map, // 2) QList > clippedPaths; - const QList &visibleRegion = map.geoProjection().visibleRegion(); + const QList &visibleRegion = map.geoProjection().projectableRegion(); if (visibleRegion.size()) { c2t::clip2tri clipper; clipper.addSubjectPath(QClipperUtils::qListToPath(wrappedPath), true); @@ -306,23 +308,42 @@ void QGeoMapPolygonGeometry::updateScreenPoints(const QGeoMap &map) screenOutline_ = ppi; - QTriangleSet ts = qTriangulate(ppi); - qreal *vx = ts.vertices.data(); - - screenIndices_.reserve(ts.indices.size()); - screenVertices_.reserve(ts.vertices.size()); + using Coord = double; + using N = uint32_t; + using Point = std::array; + + std::vector> polygon; + polygon.push_back(std::vector()); + std::vector &poly = polygon.front(); + // ... fill polygon structure with actual data + + for (int i = 0; i < ppi.elementCount(); ++i) { + const QPainterPath::Element e = ppi.elementAt(i); + if (e.isMoveTo() || i == ppi.elementCount() - 1 + || (qAbs(e.x - poly.front()[0]) < 0.1 + && qAbs(e.y - poly.front()[1]) < 0.1)) { + Point p = { e.x, e.y }; + poly.push_back( p ); + } else if (e.isLineTo()) { + Point p = { e.x, e.y }; + poly.push_back( p ); + } else { + qWarning("Unhandled element type in polygon painterpath"); + } + } - if (ts.indices.type() == QVertexIndexVector::UnsignedInt) { - const quint32 *ix = reinterpret_cast(ts.indices.data()); - for (int i = 0; i < (ts.indices.size()/3*3); ++i) - screenIndices_ << ix[i]; - } else { - const quint16 *ix = reinterpret_cast(ts.indices.data()); - for (int i = 0; i < (ts.indices.size()/3*3); ++i) - screenIndices_ << ix[i]; + if (poly.size() > 2) { + // Run tessellation + // Returns array of indices that refer to the vertices of the input polygon. + // Three subsequent indices form a triangle. + screenVertices_.clear(); + screenIndices_.clear(); + for (const auto &p : poly) + screenVertices_ << QPointF(p[0], p[1]); + std::vector indices = mapbox::earcut(polygon); + for (const auto &i: indices) + screenIndices_ << quint32(i); } - for (int i = 0; i < (ts.vertices.size()/2*2); i += 2) - screenVertices_ << QPointF(vx[i], vx[i + 1]); screenBounds_ = ppi.boundingRect(); } diff --git a/src/location/declarativemaps/qdeclarativepolylinemapitem.cpp b/src/location/declarativemaps/qdeclarativepolylinemapitem.cpp index aedb9811..26f030b0 100644 --- a/src/location/declarativemaps/qdeclarativepolylinemapitem.cpp +++ b/src/location/declarativemaps/qdeclarativepolylinemapitem.cpp @@ -226,7 +226,7 @@ QList > QGeoMapPolylineGeometry::clipPath(const QGeoMap & // 2) QList > clippedPaths; - const QList &visibleRegion = map.geoProjection().visibleRegion(); + const QList &visibleRegion = map.geoProjection().projectableRegion(); if (visibleRegion.size()) { c2t::clip2tri clipper; clipper.addSubjectPath(QClipperUtils::qListToPath(wrappedPath), false); diff --git a/src/location/location.pro b/src/location/location.pro index 5dc89a63..a951ebd6 100644 --- a/src/location/location.pro +++ b/src/location/location.pro @@ -10,6 +10,7 @@ CONFIG += simd optimize_full # 3rdparty headers produce warnings with MSVC msvc: CONFIG -= warning_clean +INCLUDEPATH += ../3rdparty/earcut INCLUDEPATH += ../3rdparty/poly2tri INCLUDEPATH += ../3rdparty/clipper INCLUDEPATH += ../3rdparty/clip2tri diff --git a/src/location/maps/qgeoprojection.cpp b/src/location/maps/qgeoprojection.cpp index 07747a31..609fb934 100644 --- a/src/location/maps/qgeoprojection.cpp +++ b/src/location/maps/qgeoprojection.cpp @@ -317,6 +317,13 @@ QList QGeoProjectionWebMercator::visibleRegion() const return m_visibleRegion; } +QList QGeoProjectionWebMercator::projectableRegion() const +{ + if (m_visibleRegionDirty) + const_cast(this)->updateVisibleRegion(); + return m_projectableRegion; +} + QDoubleVector2D QGeoProjectionWebMercator::viewportToWrappedMapProjection(const QDoubleVector2D &itemPosition) const { double s; @@ -350,6 +357,8 @@ void QGeoProjectionWebMercator::setupCamera() int intZoomLevel = static_cast(std::floor(m_cameraData.zoomLevel())); m_sideLength = (1 << intZoomLevel) * defaultTileSize; m_center = m_centerMercator * m_sideLength; + //aperture(90 / 2) = 1 + m_aperture = tan(QLocationUtils::radians(m_cameraData.fieldOfView()) * 0.5); double f = m_viewportHeight; double z = std::pow(2.0, m_cameraData.zoomLevel() - intZoomLevel) * defaultTileSize; @@ -358,15 +367,13 @@ void QGeoProjectionWebMercator::setupCamera() double z_mercator = std::pow(2.0, m_cameraData.zoomLevel()) * defaultTileSize; double altitude_mercator = f / (2.0 * z_mercator); - //aperture(90 / 2) = 1 - m_aperture = tan(QLocationUtils::radians(m_cameraData.fieldOfView()) * 0.5); // calculate eye m_eye = m_center; m_eye.setZ(altitude * defaultTileSize / m_aperture); // And in mercator space m_eyeMercator = m_centerMercator; - m_eyeMercator.setZ(altitude_mercator); + m_eyeMercator.setZ(altitude_mercator / m_aperture); m_view = m_eye - m_center; QDoubleVector3D side = QDoubleVector3D::normal(m_view, QDoubleVector3D(0.0, 1.0, 0.0)); @@ -402,7 +409,7 @@ void QGeoProjectionWebMercator::setupCamera() m_eyeMercator = mTiltMercator * m_viewMercator + m_centerMercator; } - m_view = m_eye - m_center; + m_view = m_eye - m_center; // ToDo: this should be inverted (center - eye), and the rest should follow m_viewNormalized = m_view.normalized(); m_up = QDoubleVector3D::normal(m_view, m_side); @@ -455,7 +462,7 @@ void QGeoProjectionWebMercator::setupCamera() m_transformation.scale(m_sideLength, m_sideLength, 1.0); m_centerNearPlane = m_eye + m_viewNormalized; - m_centerNearPlaneMercator = m_eyeMercator + m_viewNormalized * m_nearPlaneMercator; + m_centerNearPlaneMercator = m_eyeMercator - m_viewNormalized * m_nearPlaneMercator; // The method does not support tilting angles >= 90.0 or < 0. @@ -505,6 +512,46 @@ void QGeoProjectionWebMercator::updateVisibleRegion() m_visibleRegion.clear(); if (res.size()) m_visibleRegion = QClipperUtils::pathToQList(res[0]); // Intersection between two convex quadrilaterals should always be a single polygon + + m_projectableRegion.clear(); + if (m_cameraData.tilt() == 0) { + m_projectableRegion = mapRect; + } else { + QGeoProjectionWebMercator::Plane nearPlane(m_centerNearPlaneMercator, m_viewNormalized); + Line2D nearPlaneXYIntersection = nearPlane.planeXYIntersection(); + double squareHalfSide = qMax(5.0, nearPlaneXYIntersection.m_point.length()); + QDoubleVector2D viewDirectionProjected = -m_viewNormalized.toVector2D().normalized(); + + + QDoubleVector2D tl = nearPlaneXYIntersection.m_point + - squareHalfSide * nearPlaneXYIntersection.m_direction + + 2 * squareHalfSide * viewDirectionProjected; + QDoubleVector2D tr = nearPlaneXYIntersection.m_point + + squareHalfSide * nearPlaneXYIntersection.m_direction + + 2 * squareHalfSide * viewDirectionProjected; + QDoubleVector2D bl = nearPlaneXYIntersection.m_point + - squareHalfSide * nearPlaneXYIntersection.m_direction; + QDoubleVector2D br = nearPlaneXYIntersection.m_point + + squareHalfSide * nearPlaneXYIntersection.m_direction; + + QList projectableRect; + projectableRect.push_back(bl); + projectableRect.push_back(br); + projectableRect.push_back(tr); + projectableRect.push_back(tl); + + + c2t::clip2tri clipperProjectable; + clipperProjectable.clearClipper(); + clipperProjectable.addSubjectPath(QClipperUtils::qListToPath(mapRect), true); + clipperProjectable.addClipPolygon(QClipperUtils::qListToPath(projectableRect)); + + Paths resProjectable = clipperProjectable.execute(c2t::clip2tri::Intersection); + if (resProjectable.size()) + m_projectableRegion = QClipperUtils::pathToQList(resProjectable[0]); // Intersection between two convex quadrilaterals should always be a single polygon + else + m_projectableRegion = viewportRect; + } } /* diff --git a/src/location/maps/qgeoprojection_p.h b/src/location/maps/qgeoprojection_p.h index 7d306eea..76e11af0 100644 --- a/src/location/maps/qgeoprojection_p.h +++ b/src/location/maps/qgeoprojection_p.h @@ -73,6 +73,7 @@ public: virtual bool isProjectable(const QDoubleVector2D &wrappedProjection) const = 0; virtual QList visibleRegion() const = 0; + virtual QList projectableRegion() const = 0; // Conversion methods for QGeoCoordinate <-> screen. // This currently assumes that the "MapProjection" space is [0, 1][0, 1] for every type of possibly supported map projection @@ -126,7 +127,7 @@ public: bool isProjectable(const QDoubleVector2D &wrappedProjection) const Q_DECL_OVERRIDE; QList visibleRegion() const Q_DECL_OVERRIDE; - + QList projectableRegion() const Q_DECL_OVERRIDE; inline QDoubleVector2D viewportToWrappedMapProjection(const QDoubleVector2D &itemPosition) const; inline QDoubleVector2D viewportToWrappedMapProjection(const QDoubleVector2D &itemPosition, double &s) const; private: @@ -202,6 +203,7 @@ private: Line2D m_nearPlaneMapIntersection; QList m_visibleRegion; + QList m_projectableRegion; bool m_visibleRegionDirty; Q_DISABLE_COPY(QGeoProjectionWebMercator) -- cgit v1.2.1