1 | /**************************************************************************** |
2 | ** |
3 | ** Copyright (C) 2015 The Qt Company Ltd. |
4 | ** Contact: http://www.qt.io/licensing/ |
5 | ** |
6 | ** This file is part of the QtLocation module of the Qt Toolkit. |
7 | ** |
8 | ** $QT_BEGIN_LICENSE:LGPL3$ |
9 | ** Commercial License Usage |
10 | ** Licensees holding valid commercial Qt licenses may use this file in |
11 | ** accordance with the commercial license agreement provided with the |
12 | ** Software or, alternatively, in accordance with the terms contained in |
13 | ** a written agreement between you and The Qt Company. For licensing terms |
14 | ** and conditions see http://www.qt.io/terms-conditions. For further |
15 | ** information use the contact form at http://www.qt.io/contact-us. |
16 | ** |
17 | ** GNU Lesser General Public License Usage |
18 | ** Alternatively, this file may be used under the terms of the GNU Lesser |
19 | ** General Public License version 3 as published by the Free Software |
20 | ** Foundation and appearing in the file LICENSE.LGPLv3 included in the |
21 | ** packaging of this file. Please review the following information to |
22 | ** ensure the GNU Lesser General Public License version 3 requirements |
23 | ** will be met: https://www.gnu.org/licenses/lgpl.html. |
24 | ** |
25 | ** GNU General Public License Usage |
26 | ** Alternatively, this file may be used under the terms of the GNU |
27 | ** General Public License version 2.0 or later as published by the Free |
28 | ** Software Foundation and appearing in the file LICENSE.GPL included in |
29 | ** the packaging of this file. Please review the following information to |
30 | ** ensure the GNU General Public License version 2.0 requirements will be |
31 | ** met: http://www.gnu.org/licenses/gpl-2.0.html. |
32 | ** |
33 | ** $QT_END_LICENSE$ |
34 | ** |
35 | ****************************************************************************/ |
36 | #include "qgeocameratiles_p.h" |
37 | #include "qgeocameratiles_p_p.h" |
38 | #include "qgeocameradata_p.h" |
39 | #include "qgeotilespec_p.h" |
40 | #include "qgeomaptype_p.h" |
41 | |
42 | #include <QtPositioning/private/qwebmercator_p.h> |
43 | #include <QtPositioning/private/qdoublevector2d_p.h> |
44 | #include <QtPositioning/private/qdoublevector3d_p.h> |
45 | #include <QtPositioning/private/qlocationutils_p.h> |
46 | #include <QtGui/QMatrix4x4> |
47 | #include <QVector> |
48 | #include <QMap> |
49 | #include <QPair> |
50 | #include <QSet> |
51 | #include <QSize> |
52 | #include <cmath> |
53 | #include <limits> |
54 | |
55 | static QVector3D toVector3D(const QDoubleVector3D& in) |
56 | { |
57 | return QVector3D(in.x(), in.y(), in.z()); |
58 | } |
59 | |
60 | static QDoubleVector3D toDoubleVector3D(const QVector3D& in) |
61 | { |
62 | return QDoubleVector3D(in.x(), in.y(), in.z()); |
63 | } |
64 | |
65 | QT_BEGIN_NAMESPACE |
66 | |
67 | QGeoCameraTiles::QGeoCameraTiles() |
68 | : d_ptr(new QGeoCameraTilesPrivate()) {} |
69 | |
70 | QGeoCameraTiles::~QGeoCameraTiles() |
71 | { |
72 | } |
73 | |
74 | void QGeoCameraTiles::setCameraData(const QGeoCameraData &camera) |
75 | { |
76 | if (d_ptr->m_camera == camera) |
77 | return; |
78 | |
79 | d_ptr->m_dirtyGeometry = true; |
80 | d_ptr->m_camera = camera; |
81 | d_ptr->m_intZoomLevel = static_cast<int>(std::floor(x: d_ptr->m_camera.zoomLevel())); |
82 | d_ptr->m_sideLength = 1 << d_ptr->m_intZoomLevel; |
83 | } |
84 | |
85 | QGeoCameraData QGeoCameraTiles::cameraData() const |
86 | { |
87 | return d_ptr->m_camera; |
88 | } |
89 | |
90 | void QGeoCameraTiles::setVisibleArea(const QRectF &visibleArea) |
91 | { |
92 | if (d_ptr->m_visibleArea == visibleArea) |
93 | return; |
94 | |
95 | d_ptr->m_visibleArea = visibleArea; |
96 | d_ptr->m_dirtyGeometry = true; |
97 | } |
98 | |
99 | void QGeoCameraTiles::setScreenSize(const QSize &size) |
100 | { |
101 | if (d_ptr->m_screenSize == size) |
102 | return; |
103 | |
104 | d_ptr->m_dirtyGeometry = true; |
105 | d_ptr->m_screenSize = size; |
106 | } |
107 | |
108 | void QGeoCameraTiles::setPluginString(const QString &pluginString) |
109 | { |
110 | if (d_ptr->m_pluginString == pluginString) |
111 | return; |
112 | |
113 | d_ptr->m_dirtyMetadata = true; |
114 | d_ptr->m_pluginString = pluginString; |
115 | } |
116 | |
117 | void QGeoCameraTiles::setMapType(const QGeoMapType &mapType) |
118 | { |
119 | if (d_ptr->m_mapType == mapType) |
120 | return; |
121 | |
122 | d_ptr->m_dirtyMetadata = true; |
123 | d_ptr->m_mapType = mapType; |
124 | } |
125 | |
126 | QGeoMapType QGeoCameraTiles::activeMapType() const |
127 | { |
128 | return d_ptr->m_mapType; |
129 | } |
130 | |
131 | void QGeoCameraTiles::setMapVersion(int mapVersion) |
132 | { |
133 | if (d_ptr->m_mapVersion == mapVersion) |
134 | return; |
135 | |
136 | d_ptr->m_dirtyMetadata = true; |
137 | d_ptr->m_mapVersion = mapVersion; |
138 | } |
139 | |
140 | void QGeoCameraTiles::setTileSize(int tileSize) |
141 | { |
142 | if (d_ptr->m_tileSize == tileSize) |
143 | return; |
144 | |
145 | d_ptr->m_dirtyGeometry = true; |
146 | d_ptr->m_tileSize = tileSize; |
147 | } |
148 | |
149 | void QGeoCameraTiles::setViewExpansion(double viewExpansion) |
150 | { |
151 | d_ptr->m_viewExpansion = viewExpansion; |
152 | d_ptr->m_dirtyGeometry = true; |
153 | } |
154 | |
155 | int QGeoCameraTiles::tileSize() const |
156 | { |
157 | return d_ptr->m_tileSize; |
158 | } |
159 | |
160 | const QSet<QGeoTileSpec>& QGeoCameraTiles::createTiles() |
161 | { |
162 | if (d_ptr->m_dirtyGeometry) { |
163 | d_ptr->m_tiles.clear(); |
164 | d_ptr->updateGeometry(); |
165 | d_ptr->m_dirtyGeometry = false; |
166 | } |
167 | |
168 | if (d_ptr->m_dirtyMetadata) { |
169 | d_ptr->updateMetadata(); |
170 | d_ptr->m_dirtyMetadata = false; |
171 | } |
172 | |
173 | return d_ptr->m_tiles; |
174 | } |
175 | |
176 | QGeoCameraTilesPrivate::QGeoCameraTilesPrivate() |
177 | : m_mapVersion(-1), |
178 | m_tileSize(0), |
179 | m_intZoomLevel(0), |
180 | m_sideLength(0), |
181 | m_dirtyGeometry(false), |
182 | m_dirtyMetadata(false), |
183 | m_viewExpansion(1.0) |
184 | { |
185 | } |
186 | |
187 | QGeoCameraTilesPrivate::~QGeoCameraTilesPrivate() {} |
188 | |
189 | void QGeoCameraTilesPrivate::updateMetadata() |
190 | { |
191 | typedef QSet<QGeoTileSpec>::const_iterator iter; |
192 | |
193 | QSet<QGeoTileSpec> newTiles; |
194 | |
195 | iter i = m_tiles.constBegin(); |
196 | iter end = m_tiles.constEnd(); |
197 | |
198 | for (; i != end; ++i) { |
199 | QGeoTileSpec tile = *i; |
200 | newTiles.insert(value: QGeoTileSpec(m_pluginString, m_mapType.mapId(), tile.zoom(), tile.x(), tile.y(), m_mapVersion)); |
201 | } |
202 | |
203 | m_tiles = newTiles; |
204 | } |
205 | |
206 | void QGeoCameraTilesPrivate::updateGeometry() |
207 | { |
208 | // Find the frustum from the camera / screen / viewport information |
209 | // The larger frustum when stationary is a form of prefetching |
210 | Frustum f = createFrustum(viewExpansion: m_viewExpansion); |
211 | #ifdef QT_LOCATION_DEBUG |
212 | m_frustum = f; |
213 | #endif |
214 | |
215 | // Find the polygon where the frustum intersects the plane of the map |
216 | PolygonVector = frustumFootprint(frustum: f); |
217 | #ifdef QT_LOCATION_DEBUG |
218 | m_frustumFootprint = footprint; |
219 | #endif |
220 | |
221 | // Clip the polygon to the map, split it up if it cross the dateline |
222 | ClippedFootprint polygons = clipFootprintToMap(footprint); |
223 | #ifdef QT_LOCATION_DEBUG |
224 | m_clippedFootprint = polygons; |
225 | #endif |
226 | |
227 | |
228 | if (!polygons.left.isEmpty()) { |
229 | QSet<QGeoTileSpec> tilesLeft = tilesFromPolygon(polygon: polygons.left); |
230 | m_tiles.unite(other: tilesLeft); |
231 | } |
232 | |
233 | if (!polygons.right.isEmpty()) { |
234 | QSet<QGeoTileSpec> tilesRight = tilesFromPolygon(polygon: polygons.right); |
235 | m_tiles.unite(other: tilesRight); |
236 | } |
237 | |
238 | if (!polygons.mid.isEmpty()) { |
239 | QSet<QGeoTileSpec> tilesRight = tilesFromPolygon(polygon: polygons.mid); |
240 | m_tiles.unite(other: tilesRight); |
241 | } |
242 | } |
243 | |
244 | Frustum QGeoCameraTilesPrivate::createFrustum(double viewExpansion) const |
245 | { |
246 | double apertureSize = 1.0; |
247 | if (m_camera.fieldOfView() != 90.0) //aperture(90 / 2) = 1 |
248 | apertureSize = tan(x: QLocationUtils::radians(degrees: m_camera.fieldOfView()) * 0.5); |
249 | QDoubleVector3D center = m_sideLength * QWebMercator::coordToMercator(coord: m_camera.center()); |
250 | #ifdef QT_LOCATION_DEBUG |
251 | m_createFrustum_center = center; |
252 | #endif |
253 | |
254 | |
255 | double f = m_screenSize.height(); |
256 | |
257 | double z = std::pow(x: 2.0, y: m_camera.zoomLevel() - m_intZoomLevel) * m_tileSize; // between 1 and 2 * m_tileSize |
258 | |
259 | double altitude = (f / (2.0 * z)) / apertureSize; |
260 | QDoubleVector3D eye = center; |
261 | eye.setZ(altitude); |
262 | |
263 | QDoubleVector3D view = eye - center; |
264 | QDoubleVector3D side = QDoubleVector3D::normal(v1: view, v2: QDoubleVector3D(0.0, 1.0, 0.0)); |
265 | QDoubleVector3D up = QDoubleVector3D::normal(v1: side, v2: view); |
266 | |
267 | QMatrix4x4 mBearing; |
268 | // The rotation direction here is the opposite of QGeoTiledMapScene::setupCamera, |
269 | // as this is basically rotating the map against a fixed view frustum. |
270 | mBearing.rotate(angle: 1.0 * m_camera.bearing(), vector: toVector3D(in: view)); |
271 | up = toDoubleVector3D(in: mBearing * toVector3D(in: up)); |
272 | |
273 | // same for tilting |
274 | QDoubleVector3D side2 = QDoubleVector3D::normal(v1: up, v2: view); |
275 | QMatrix4x4 mTilt; |
276 | mTilt.rotate(angle: -1.0 * m_camera.tilt(), vector: toVector3D(in: side2)); |
277 | eye = toDoubleVector3D(in: (mTilt * toVector3D(in: view)) + toVector3D(in: center)); |
278 | |
279 | view = eye - center; |
280 | side = QDoubleVector3D::normal(v1: view, v2: QDoubleVector3D(0.0, 1.0, 0.0)); |
281 | up = QDoubleVector3D::normal(v1: view, v2: side2); |
282 | |
283 | double nearPlane = 1.0 / 32.0; // The denominator used to be (4.0 * m_tileSize ), which produces an extremely narrow and tiny near plane. |
284 | // farPlane plays a role on how much gets clipped when the map gets tilted. It used to be altitude + 1.0 |
285 | // The value of 8.0 has been chosen as an acceptable compromise. |
286 | // TODO: use m_camera.clipDistance(); when this will be introduced |
287 | double farPlane = altitude + 8.0; |
288 | |
289 | double aspectRatio = 1.0 * m_screenSize.width() / m_screenSize.height(); |
290 | |
291 | // Half values. Half width near, far, height near, far. |
292 | double hhn,hwn,hhf,hwf = 0.0; |
293 | |
294 | // This used to fix the (half) field of view at 45 degrees |
295 | // half because this assumed that viewSize = 2*nearPlane x 2*nearPlane |
296 | viewExpansion *= apertureSize; |
297 | |
298 | hhn = viewExpansion * nearPlane; |
299 | hwn = hhn * aspectRatio; |
300 | |
301 | hhf = viewExpansion * farPlane; |
302 | hwf = hhf * aspectRatio; |
303 | |
304 | QDoubleVector3D d = center - eye; |
305 | d.normalize(); |
306 | up.normalize(); |
307 | QDoubleVector3D right = QDoubleVector3D::normal(v1: d, v2: up); |
308 | |
309 | QDoubleVector3D cf = eye + d * farPlane; |
310 | QDoubleVector3D cn = eye + d * nearPlane; |
311 | |
312 | Frustum frustum; |
313 | |
314 | frustum.apex = eye; |
315 | #ifdef QT_LOCATION_DEBUG |
316 | m_createFrustum_eye = eye; |
317 | #endif |
318 | |
319 | QRectF va = m_visibleArea; |
320 | if (va.isNull()) |
321 | va = QRectF(0, 0, m_screenSize.width(), m_screenSize.height()); |
322 | QRectF screen = QRectF(QPointF(0,0),m_screenSize); |
323 | QPointF vaCenter = va.center(); |
324 | QPointF screenCenter = screen.center(); |
325 | QPointF diff = screenCenter - vaCenter; |
326 | double xdiffpct = diff.x() / m_screenSize.width(); |
327 | double ydiffpct = -(diff.y() / m_screenSize.height()); |
328 | |
329 | double wn = (2 * hwn) * xdiffpct; |
330 | double hn = (2 * hhn) * ydiffpct; |
331 | double wf = (2 * hwf) * xdiffpct; |
332 | double hf = (2 * hhf) * ydiffpct; |
333 | |
334 | // TODO: fix eye |
335 | |
336 | frustum.topLeftFar = cf - (up * (hhf + hf)) - (right * (hwf + wf)); |
337 | frustum.topRightFar = cf - (up * (hhf + hf)) + (right * (hwf + wf)); |
338 | frustum.bottomLeftFar = cf + (up * (hhf + hf)) - (right * (hwf + wf)); |
339 | frustum.bottomRightFar = cf + (up * (hhf + hf)) + (right * (hwf + wf)); |
340 | |
341 | frustum.topLeftNear = cn - (up * (hhn + hn)) - (right * (hwn + wn)); |
342 | frustum.topRightNear = cn - (up * (hhn + hn)) + (right * (hwn + wn)); |
343 | frustum.bottomLeftNear = cn + (up * (hhn + hn)) - (right * (hwn + wn)); |
344 | frustum.bottomRightNear = cn + (up * (hhn + hn)) + (right * (hwn + wn)); |
345 | |
346 | return frustum; |
347 | } |
348 | |
349 | static bool appendZIntersects(const QDoubleVector3D &start, |
350 | const QDoubleVector3D &end, |
351 | double z, |
352 | QVector<QDoubleVector3D> &results) |
353 | { |
354 | if (start.z() == end.z()) { |
355 | return false; |
356 | } else { |
357 | double f = (start.z() - z) / (start.z() - end.z()); |
358 | if ((f >= 0) && (f <= 1.0)) { |
359 | results.append(t: (1 - f) * start + f * end); |
360 | return true; |
361 | } |
362 | } |
363 | return false; |
364 | } |
365 | |
366 | // Returns the intersection of the plane of the map and the camera frustum as a right handed polygon |
367 | PolygonVector QGeoCameraTilesPrivate::(const Frustum &frustum) const |
368 | { |
369 | PolygonVector points; |
370 | points.reserve(asize: 4); |
371 | |
372 | // The camera is always upright. Tilting angle never reach 90degrees. |
373 | // Meaning: bottom frustum edges always intersect the map plane, top ones may not. |
374 | |
375 | // Top Right |
376 | if (!appendZIntersects(start: frustum.apex, end: frustum.topRightFar, z: 0.0, results&: points)) |
377 | appendZIntersects(start: frustum.topRightFar, end: frustum.bottomRightFar, z: 0.0, results&: points); |
378 | |
379 | // Bottom Right |
380 | appendZIntersects(start: frustum.apex, end: frustum.bottomRightFar, z: 0.0, results&: points); |
381 | |
382 | // Bottom Left |
383 | appendZIntersects(start: frustum.apex, end: frustum.bottomLeftFar, z: 0.0, results&: points); |
384 | |
385 | // Top Left |
386 | if (!appendZIntersects(start: frustum.apex, end: frustum.topLeftFar, z: 0.0, results&: points)) |
387 | appendZIntersects(start: frustum.topLeftFar, end: frustum.bottomLeftFar, z: 0.0, results&: points); |
388 | |
389 | return points; |
390 | } |
391 | |
392 | QPair<PolygonVector, PolygonVector> QGeoCameraTilesPrivate::splitPolygonAtAxisValue(const PolygonVector &polygon, int axis, double value) const |
393 | { |
394 | PolygonVector polygonBelow; |
395 | PolygonVector polygonAbove; |
396 | |
397 | int size = polygon.size(); |
398 | |
399 | if (size == 0) { |
400 | return QPair<PolygonVector, PolygonVector>(polygonBelow, polygonAbove); |
401 | } |
402 | |
403 | QVector<int> comparisons = QVector<int>(polygon.size()); |
404 | |
405 | for (int i = 0; i < size; ++i) { |
406 | double v = polygon.at(i).get(i: axis); |
407 | if (qFuzzyCompare(p1: v - value + 1.0, p2: 1.0)) { |
408 | comparisons[i] = 0; |
409 | } else { |
410 | if (v < value) { |
411 | comparisons[i] = -1; |
412 | } else if (value < v) { |
413 | comparisons[i] = 1; |
414 | } |
415 | } |
416 | } |
417 | |
418 | for (int index = 0; index < size; ++index) { |
419 | int prevIndex = index - 1; |
420 | if (prevIndex < 0) |
421 | prevIndex += size; |
422 | int nextIndex = (index + 1) % size; |
423 | |
424 | int prevComp = comparisons[prevIndex]; |
425 | int comp = comparisons[index]; |
426 | int nextComp = comparisons[nextIndex]; |
427 | |
428 | if (comp == 0) { |
429 | if (prevComp == -1) { |
430 | polygonBelow.append(t: polygon.at(i: index)); |
431 | if (nextComp == 1) { |
432 | polygonAbove.append(t: polygon.at(i: index)); |
433 | } |
434 | } else if (prevComp == 1) { |
435 | polygonAbove.append(t: polygon.at(i: index)); |
436 | if (nextComp == -1) { |
437 | polygonBelow.append(t: polygon.at(i: index)); |
438 | } |
439 | } else if (prevComp == 0) { |
440 | if (nextComp == -1) { |
441 | polygonBelow.append(t: polygon.at(i: index)); |
442 | } else if (nextComp == 1) { |
443 | polygonAbove.append(t: polygon.at(i: index)); |
444 | } else if (nextComp == 0) { |
445 | // do nothing |
446 | } |
447 | } |
448 | } else { |
449 | if (comp == -1) { |
450 | polygonBelow.append(t: polygon.at(i: index)); |
451 | } else if (comp == 1) { |
452 | polygonAbove.append(t: polygon.at(i: index)); |
453 | } |
454 | |
455 | // there is a point between this and the next point |
456 | // on the polygon that lies on the splitting line |
457 | // and should be added to both the below and above |
458 | // polygons |
459 | if ((nextComp != 0) && (nextComp != comp)) { |
460 | QDoubleVector3D p1 = polygon.at(i: index); |
461 | QDoubleVector3D p2 = polygon.at(i: nextIndex); |
462 | |
463 | double p1v = p1.get(i: axis); |
464 | double p2v = p2.get(i: axis); |
465 | |
466 | double f = (p1v - value) / (p1v - p2v); |
467 | |
468 | if (((0 <= f) && (f <= 1.0)) |
469 | || qFuzzyCompare(p1: f + 1.0, p2: 1.0) |
470 | || qFuzzyCompare(p1: f + 1.0, p2: 2.0) ) { |
471 | QDoubleVector3D midPoint = (1.0 - f) * p1 + f * p2; |
472 | polygonBelow.append(t: midPoint); |
473 | polygonAbove.append(t: midPoint); |
474 | } |
475 | } |
476 | } |
477 | } |
478 | |
479 | return QPair<PolygonVector, PolygonVector>(polygonBelow, polygonAbove); |
480 | } |
481 | |
482 | static void addXOffset(PolygonVector &, double xoff) |
483 | { |
484 | for (QDoubleVector3D &v: footprint) |
485 | v.setX(v.x() + xoff); |
486 | } |
487 | |
488 | QGeoCameraTilesPrivate::ClippedFootprint QGeoCameraTilesPrivate::(const PolygonVector &) const |
489 | { |
490 | bool clipX0 = false; |
491 | bool clipX1 = false; |
492 | bool clipY0 = false; |
493 | bool clipY1 = false; |
494 | |
495 | double side = 1.0 * m_sideLength; |
496 | double minX = std::numeric_limits<double>::max(); |
497 | double maxX = std::numeric_limits<double>::lowest(); |
498 | |
499 | for (const QDoubleVector3D &p: footprint) { |
500 | if (p.y() < 0.0) |
501 | clipY0 = true; |
502 | if (p.y() > side) |
503 | clipY1 = true; |
504 | } |
505 | |
506 | PolygonVector results = footprint; |
507 | |
508 | if (clipY0) { |
509 | results = splitPolygonAtAxisValue(polygon: results, axis: 1, value: 0.0).second; |
510 | } |
511 | |
512 | if (clipY1) { |
513 | results = splitPolygonAtAxisValue(polygon: results, axis: 1, value: side).first; |
514 | } |
515 | |
516 | for (const QDoubleVector3D &p: results) { |
517 | if ((p.x() < 0.0) || (qFuzzyIsNull(d: p.x()))) |
518 | clipX0 = true; |
519 | if ((p.x() > side) || (qFuzzyCompare(p1: side, p2: p.x()))) |
520 | clipX1 = true; |
521 | } |
522 | |
523 | for (const QDoubleVector3D &v : results) { |
524 | minX = qMin(a: v.x(), b: minX); |
525 | maxX = qMax(a: v.x(), b: maxX); |
526 | } |
527 | |
528 | double = maxX - minX; |
529 | |
530 | if (clipX0) { |
531 | if (clipX1) { |
532 | if (footprintWidth > side) { |
533 | PolygonVector rightPart = splitPolygonAtAxisValue(polygon: results, axis: 0, value: side).second; |
534 | addXOffset(footprint&: rightPart, xoff: -side); |
535 | rightPart = splitPolygonAtAxisValue(polygon: rightPart, axis: 0, value: side).first; // clip it again, should it tend to infinite or so |
536 | |
537 | PolygonVector leftPart = splitPolygonAtAxisValue(polygon: results, axis: 0, value: 0).first; |
538 | addXOffset(footprint&: leftPart, xoff: side); |
539 | leftPart = splitPolygonAtAxisValue(polygon: leftPart, axis: 0, value: 0).second; // same here |
540 | |
541 | results = splitPolygonAtAxisValue(polygon: results, axis: 0, value: 0.0).second; |
542 | results = splitPolygonAtAxisValue(polygon: results, axis: 0, value: side).first; |
543 | return ClippedFootprint(leftPart, results, rightPart); |
544 | } else { // fitting the WebMercator square exactly? |
545 | results = splitPolygonAtAxisValue(polygon: results, axis: 0, value: 0.0).second; |
546 | results = splitPolygonAtAxisValue(polygon: results, axis: 0, value: side).first; |
547 | return ClippedFootprint(PolygonVector(), results, PolygonVector()); |
548 | } |
549 | } else { |
550 | QPair<PolygonVector, PolygonVector> pair = splitPolygonAtAxisValue(polygon: results, axis: 0, value: 0.0); |
551 | if (pair.first.isEmpty()) { |
552 | // if we touched the line but didn't cross it... |
553 | for (int i = 0; i < pair.second.size(); ++i) { |
554 | if (qFuzzyIsNull(d: pair.second.at(i).x())) |
555 | pair.first.append(t: pair.second.at(i)); |
556 | } |
557 | if (pair.first.size() == 2) { |
558 | double y0 = pair.first[0].y(); |
559 | double y1 = pair.first[1].y(); |
560 | pair.first.clear(); |
561 | pair.first.append(t: QDoubleVector3D(side, y0, 0.0)); |
562 | pair.first.append(t: QDoubleVector3D(side - 0.001, y0, 0.0)); |
563 | pair.first.append(t: QDoubleVector3D(side - 0.001, y1, 0.0)); |
564 | pair.first.append(t: QDoubleVector3D(side, y1, 0.0)); |
565 | } else if (pair.first.size() == 1) { |
566 | // FIXME this is trickier |
567 | // - touching at one point on the tile boundary |
568 | // - probably need to build a triangular polygon across the edge |
569 | // - don't want to add another y tile if we can help it |
570 | // - initial version doesn't care |
571 | double y = pair.first.at(i: 0).y(); |
572 | pair.first.clear(); |
573 | pair.first.append(t: QDoubleVector3D(side - 0.001, y, 0.0)); |
574 | pair.first.append(t: QDoubleVector3D(side, y + 0.001, 0.0)); |
575 | pair.first.append(t: QDoubleVector3D(side, y - 0.001, 0.0)); |
576 | } |
577 | } else { |
578 | addXOffset(footprint&: pair.first, xoff: side); |
579 | if (footprintWidth > side) |
580 | pair.first = splitPolygonAtAxisValue(polygon: pair.first, axis: 0, value: 0).second; |
581 | } |
582 | return ClippedFootprint(pair.first, pair.second, PolygonVector()); |
583 | } |
584 | } else { |
585 | if (clipX1) { |
586 | QPair<PolygonVector, PolygonVector> pair = splitPolygonAtAxisValue(polygon: results, axis: 0, value: side); |
587 | if (pair.second.isEmpty()) { |
588 | // if we touched the line but didn't cross it... |
589 | for (int i = 0; i < pair.first.size(); ++i) { |
590 | if (qFuzzyCompare(p1: side, p2: pair.first.at(i).x())) |
591 | pair.second.append(t: pair.first.at(i)); |
592 | } |
593 | if (pair.second.size() == 2) { |
594 | double y0 = pair.second[0].y(); |
595 | double y1 = pair.second[1].y(); |
596 | pair.second.clear(); |
597 | pair.second.append(t: QDoubleVector3D(0, y0, 0.0)); |
598 | pair.second.append(t: QDoubleVector3D(0.001, y0, 0.0)); |
599 | pair.second.append(t: QDoubleVector3D(0.001, y1, 0.0)); |
600 | pair.second.append(t: QDoubleVector3D(0, y1, 0.0)); |
601 | } else if (pair.second.size() == 1) { |
602 | // FIXME this is trickier |
603 | // - touching at one point on the tile boundary |
604 | // - probably need to build a triangular polygon across the edge |
605 | // - don't want to add another y tile if we can help it |
606 | // - initial version doesn't care |
607 | double y = pair.second.at(i: 0).y(); |
608 | pair.second.clear(); |
609 | pair.second.append(t: QDoubleVector3D(0.001, y, 0.0)); |
610 | pair.second.append(t: QDoubleVector3D(0.0, y - 0.001, 0.0)); |
611 | pair.second.append(t: QDoubleVector3D(0.0, y + 0.001, 0.0)); |
612 | } |
613 | } else { |
614 | addXOffset(footprint&: pair.second, xoff: -side); |
615 | if (footprintWidth > side) |
616 | pair.second = splitPolygonAtAxisValue(polygon: pair.second, axis: 0, value: side).first; |
617 | } |
618 | return ClippedFootprint(PolygonVector(), pair.first, pair.second); |
619 | } else { |
620 | return ClippedFootprint(PolygonVector(), results, PolygonVector()); |
621 | } |
622 | } |
623 | |
624 | } |
625 | |
626 | QList<QPair<double, int> > QGeoCameraTilesPrivate::tileIntersections(double p1, int t1, double p2, int t2) const |
627 | { |
628 | if (t1 == t2) { |
629 | QList<QPair<double, int> > results = QList<QPair<double, int> >(); |
630 | results.append(t: QPair<double, int>(0.0, t1)); |
631 | return results; |
632 | } |
633 | |
634 | int step = 1; |
635 | if (t1 > t2) { |
636 | step = -1; |
637 | } |
638 | |
639 | int size = 1 + ((t2 - t1) / step); |
640 | |
641 | QList<QPair<double, int> > results = QList<QPair<double, int> >(); |
642 | |
643 | results.append(t: QPair<double, int>(0.0, t1)); |
644 | |
645 | if (step == 1) { |
646 | for (int i = 1; i < size; ++i) { |
647 | double f = (t1 + i - p1) / (p2 - p1); |
648 | results.append(t: QPair<double, int>(f, t1 + i)); |
649 | } |
650 | } else { |
651 | for (int i = 1; i < size; ++i) { |
652 | double f = (t1 - i + 1 - p1) / (p2 - p1); |
653 | results.append(t: QPair<double, int>(f, t1 - i)); |
654 | } |
655 | } |
656 | |
657 | return results; |
658 | } |
659 | |
660 | QSet<QGeoTileSpec> QGeoCameraTilesPrivate::tilesFromPolygon(const PolygonVector &polygon) const |
661 | { |
662 | int numPoints = polygon.size(); |
663 | |
664 | if (numPoints == 0) |
665 | return QSet<QGeoTileSpec>(); |
666 | |
667 | QVector<int> tilesX(polygon.size()); |
668 | QVector<int> tilesY(polygon.size()); |
669 | |
670 | // grab tiles at the corners of the polygon |
671 | for (int i = 0; i < numPoints; ++i) { |
672 | |
673 | QDoubleVector2D p = polygon.at(i).toVector2D(); |
674 | |
675 | int x = 0; |
676 | int y = 0; |
677 | |
678 | if (qFuzzyCompare(p1: p.x(), p2: m_sideLength * 1.0)) |
679 | x = m_sideLength - 1; |
680 | else { |
681 | x = static_cast<int>(p.x()) % m_sideLength; |
682 | if ( !qFuzzyCompare(p1: p.x(), p2: 1.0 * x) && qFuzzyCompare(p1: p.x(), p2: 1.0 * (x + 1)) ) |
683 | x++; |
684 | } |
685 | |
686 | if (qFuzzyCompare(p1: p.y(), p2: m_sideLength * 1.0)) |
687 | y = m_sideLength - 1; |
688 | else { |
689 | y = static_cast<int>(p.y()) % m_sideLength; |
690 | if ( !qFuzzyCompare(p1: p.y(), p2: 1.0 * y) && qFuzzyCompare(p1: p.y(), p2: 1.0 * (y + 1)) ) |
691 | y++; |
692 | } |
693 | |
694 | tilesX[i] = x; |
695 | tilesY[i] = y; |
696 | } |
697 | |
698 | QGeoCameraTilesPrivate::TileMap map; |
699 | |
700 | // walk along the edges of the polygon and add all tiles covered by them |
701 | for (int i1 = 0; i1 < numPoints; ++i1) { |
702 | int i2 = (i1 + 1) % numPoints; |
703 | |
704 | double x1 = polygon.at(i: i1).get(i: 0); |
705 | double x2 = polygon.at(i: i2).get(i: 0); |
706 | |
707 | bool xFixed = qFuzzyCompare(p1: x1, p2: x2); |
708 | bool xIntegral = qFuzzyCompare(p1: x1, p2: std::floor(x: x1)) || qFuzzyCompare(p1: x1 + 1.0, p2: std::floor(x: x1 + 1.0)); |
709 | |
710 | QList<QPair<double, int> > xIntersects |
711 | = tileIntersections(p1: x1, |
712 | t1: tilesX.at(i: i1), |
713 | p2: x2, |
714 | t2: tilesX.at(i: i2)); |
715 | |
716 | double y1 = polygon.at(i: i1).get(i: 1); |
717 | double y2 = polygon.at(i: i2).get(i: 1); |
718 | |
719 | bool yFixed = qFuzzyCompare(p1: y1, p2: y2); |
720 | bool yIntegral = qFuzzyCompare(p1: y1, p2: std::floor(x: y1)) || qFuzzyCompare(p1: y1 + 1.0, p2: std::floor(x: y1 + 1.0)); |
721 | |
722 | QList<QPair<double, int> > yIntersects |
723 | = tileIntersections(p1: y1, |
724 | t1: tilesY.at(i: i1), |
725 | p2: y2, |
726 | t2: tilesY.at(i: i2)); |
727 | |
728 | int x = xIntersects.takeFirst().second; |
729 | int y = yIntersects.takeFirst().second; |
730 | |
731 | |
732 | /* |
733 | If the polygon coincides with the tile edges we must be |
734 | inclusive and grab all tiles on both sides. We also need |
735 | to handle tiles with corners coindent with the |
736 | corners of the polygon. |
737 | e.g. all tiles marked with 'x' will be added |
738 | |
739 | "+" - tile boundaries |
740 | "O" - polygon boundary |
741 | |
742 | + + + + + + + + + + + + + + + + + + + + + |
743 | + + + + + + |
744 | + + x + x + x + + |
745 | + + + + + + |
746 | + + + + + + + + O O O O O + + + + + + + + |
747 | + + O 0 + + |
748 | + + x O x 0 x + + |
749 | + + O 0 + + |
750 | + + + + + + + + O 0 0 0 0 + + + + + + + + |
751 | + + + + + + |
752 | + + x + x + x + + |
753 | + + + + + + |
754 | + + + + + + + + + + + + + + + + + + + + + |
755 | */ |
756 | |
757 | |
758 | int xOther = x; |
759 | int yOther = y; |
760 | |
761 | if (xFixed && xIntegral) { |
762 | if (y2 < y1) { |
763 | xOther = qMax(a: 0, b: x - 1); |
764 | } |
765 | } |
766 | |
767 | if (yFixed && yIntegral) { |
768 | if (x1 < x2) { |
769 | yOther = qMax(a: 0, b: y - 1); |
770 | |
771 | } |
772 | } |
773 | |
774 | if (xIntegral) { |
775 | map.add(tileX: xOther, tileY: y); |
776 | if (yIntegral) |
777 | map.add(tileX: xOther, tileY: yOther); |
778 | |
779 | } |
780 | |
781 | if (yIntegral) |
782 | map.add(tileX: x, tileY: yOther); |
783 | |
784 | map.add(tileX: x,tileY: y); |
785 | |
786 | // top left corner |
787 | int iPrev = (i1 + numPoints - 1) % numPoints; |
788 | double xPrevious = polygon.at(i: iPrev).get(i: 0); |
789 | double yPrevious = polygon.at(i: iPrev).get(i: 1); |
790 | bool xPreviousFixed = qFuzzyCompare(p1: xPrevious, p2: x1); |
791 | if (xIntegral && xPreviousFixed && yIntegral && yFixed) { |
792 | if ((x2 > x1) && (yPrevious > y1)) { |
793 | if ((x - 1) > 0 && (y - 1) > 0) |
794 | map.add(tileX: x - 1, tileY: y - 1); |
795 | } else if ((x2 < x1) && (yPrevious < y1)) { |
796 | // what? |
797 | } |
798 | } |
799 | |
800 | // for the simple case where intersections do not coincide with |
801 | // the boundaries, we move along the edge and add tiles until |
802 | // the x and y intersection lists are exhausted |
803 | |
804 | while (!xIntersects.isEmpty() && !yIntersects.isEmpty()) { |
805 | QPair<double, int> nextX = xIntersects.first(); |
806 | QPair<double, int> nextY = yIntersects.first(); |
807 | if (nextX.first < nextY.first) { |
808 | x = nextX.second; |
809 | map.add(tileX: x, tileY: y); |
810 | xIntersects.removeFirst(); |
811 | |
812 | } else if (nextX.first > nextY.first) { |
813 | y = nextY.second; |
814 | map.add(tileX: x, tileY: y); |
815 | yIntersects.removeFirst(); |
816 | |
817 | } else { |
818 | map.add(tileX: x, tileY: nextY.second); |
819 | map.add(tileX: nextX.second, tileY: y); |
820 | x = nextX.second; |
821 | y = nextY.second; |
822 | map.add(tileX: x, tileY: y); |
823 | xIntersects.removeFirst(); |
824 | yIntersects.removeFirst(); |
825 | } |
826 | } |
827 | |
828 | while (!xIntersects.isEmpty()) { |
829 | x = xIntersects.takeFirst().second; |
830 | map.add(tileX: x, tileY: y); |
831 | if (yIntegral && yFixed) |
832 | map.add(tileX: x, tileY: yOther); |
833 | |
834 | } |
835 | |
836 | while (!yIntersects.isEmpty()) { |
837 | y = yIntersects.takeFirst().second; |
838 | map.add(tileX: x, tileY: y); |
839 | if (xIntegral && xFixed) |
840 | map.add(tileX: xOther, tileY: y); |
841 | } |
842 | } |
843 | |
844 | QSet<QGeoTileSpec> results; |
845 | |
846 | int z = m_intZoomLevel; |
847 | |
848 | typedef QMap<int, QPair<int, int> >::const_iterator iter; |
849 | iter i = map.data.constBegin(); |
850 | iter end = map.data.constEnd(); |
851 | |
852 | for (; i != end; ++i) { |
853 | int y = i.key(); |
854 | int minX = i->first; |
855 | int maxX = i->second; |
856 | for (int x = minX; x <= maxX; ++x) { |
857 | results.insert(value: QGeoTileSpec(m_pluginString, m_mapType.mapId(), z, x, y, m_mapVersion)); |
858 | } |
859 | } |
860 | |
861 | return results; |
862 | } |
863 | |
864 | QGeoCameraTilesPrivate::TileMap::TileMap() {} |
865 | |
866 | void QGeoCameraTilesPrivate::TileMap::add(int tileX, int tileY) |
867 | { |
868 | if (data.contains(akey: tileY)) { |
869 | int oldMinX = data.value(akey: tileY).first; |
870 | int oldMaxX = data.value(akey: tileY).second; |
871 | data.insert(akey: tileY, avalue: QPair<int, int>(qMin(a: tileX, b: oldMinX), qMax(a: tileX, b: oldMaxX))); |
872 | } else { |
873 | data.insert(akey: tileY, avalue: QPair<int, int>(tileX, tileX)); |
874 | } |
875 | } |
876 | |
877 | QT_END_NAMESPACE |
878 | |