Marble

AlternativeRoutesModel.cpp
1// SPDX-License-Identifier: LGPL-2.1-or-later
2//
3// SPDX-FileCopyrightText: 2010 Dennis Nienhüser <nienhueser@kde.org>
4//
5
6#include "AlternativeRoutesModel.h"
7
8#include "GeoDataLatLonAltBox.h"
9#include "GeoDataDocument.h"
10#include "GeoDataFolder.h"
11#include "GeoDataExtendedData.h"
12#include "GeoDataLineString.h"
13#include "GeoDataPlacemark.h"
14
15#include <QElapsedTimer>
16#include <QTimer>
17#include <QPainter>
18
19namespace Marble {
20
21class Q_DECL_HIDDEN AlternativeRoutesModel::Private
22{
23public:
24 Private();
25
26 /**
27 * Returns true if there exists a route with high similarity to the given one
28 */
29 bool filter( const GeoDataDocument* document ) const;
30
31 /**
32 * Returns a similarity measure in the range of [0..1]. Two routes with a similarity of 0 can
33 * be treated as totally different (e.g. different route requests), two routes with a similarity
34 * of 1 are considered equal. Otherwise the routes overlap to an extent indicated by the
35 * similarity value -- the higher, the more they do overlap.
36 * @note: The direction of routes is important; reversed routes are not considered equal
37 */
38 static qreal similarity( const GeoDataDocument* routeA, const GeoDataDocument* routeB );
39
40 /**
41 * Returns the distance between the given polygon and the given point
42 */
43 static qreal distance( const GeoDataLineString &wayPoints, const GeoDataCoordinates &position );
44
45 /**
46 * Returns the bearing of the great circle path defined by the coordinates one and two
47 * Based on https://www.movable-type.co.uk/scripts/latlong.html
48 */
49 static qreal bearing( const GeoDataCoordinates &one, const GeoDataCoordinates &two );
50
51 /**
52 * Returns the distance between the given point and the line segment (not line) defined
53 * by the two coordinates lineA and lineB
54 */
55 static qreal distance( const GeoDataCoordinates &satellite, const GeoDataCoordinates &lineA, const GeoDataCoordinates &lineB );
56
57 /**
58 * Returns the point reached when traveling the given distance from start with the given direction
59 */
60 static GeoDataCoordinates coordinates( const GeoDataCoordinates &start, qreal distance, qreal bearing );
61
62 /**
63 * Returns the similarity between routeA and routeB. This method is not symmetric, i.e. in
64 * general unidirectionalSimilarity(a,b) != unidirectionalSimilarity(b,a)
65 */
66 static qreal unidirectionalSimilarity( const GeoDataDocument* routeA, const GeoDataDocument* routeB );
67
68 /**
69 * (Primitive) scoring for routes
70 */
71 static bool higherScore( const GeoDataDocument* one, const GeoDataDocument* two );
72
73 /**
74 * Returns true if the given route contains instructions (placemarks with turn instructions)
75 */
76 static qreal instructionScore( const GeoDataDocument* document );
77
78 static const GeoDataLineString* waypoints( const GeoDataDocument* document );
79
80 static int nonZero( const QImage &image );
81
82 static QPolygonF polygon( const GeoDataLineString &lineString, qreal x, qreal y, qreal sx, qreal sy );
83
84 /** The currently shown alternative routes (model data) */
86
87 /** Pending route data (waiting for other results to come in) */
88 QVector<GeoDataDocument*> m_restrainedRoutes;
89
90 /** Counts the time between route request and first result */
91 QElapsedTimer m_responseTime;
92
93 int m_currentIndex;
94};
95
96
97AlternativeRoutesModel::Private::Private() :
98 m_currentIndex( -1 )
99{
100 // nothing to do
101}
102
103int AlternativeRoutesModel::Private::nonZero( const QImage &image )
104{
105 QRgb const black = qRgb( 0, 0, 0 );
106 int count = 0;
107 for ( int y = 0; y < image.height(); ++y ) {
108 QRgb* destLine = (QRgb*) image.scanLine( y );
109 for ( int x = 0; x < image.width(); ++x ) {
110 count += destLine[x] == black ? 0 : 1;
111 }
112 }
113 return count;
114}
115
116QPolygonF AlternativeRoutesModel::Private::polygon( const GeoDataLineString &lineString, qreal x, qreal y, qreal sx, qreal sy )
117{
118 QPolygonF poly;
119 for ( int i = 0; i < lineString.size(); ++i ) {
120 poly << QPointF( qAbs( ( lineString)[i].longitude() - x ) * sx,
121 qAbs( ( lineString)[i].latitude() - y ) * sy );
122 }
123 return poly;
124}
125
126bool AlternativeRoutesModel::Private::filter( const GeoDataDocument* document ) const
127{
128 for ( int i=0; i<m_routes.size(); ++i ) {
129 qreal similarity = Private::similarity( document, m_routes.at( i ) );
130 if ( similarity > 0.8 ) {
131 return true;
132 }
133 }
134
135 return false;
136}
137
138qreal AlternativeRoutesModel::Private::similarity( const GeoDataDocument* routeA, const GeoDataDocument* routeB )
139{
140 return qMax<qreal>( unidirectionalSimilarity( routeA, routeB ),
141 unidirectionalSimilarity( routeB, routeA ) );
142}
143
144qreal AlternativeRoutesModel::Private::distance( const GeoDataLineString &wayPoints, const GeoDataCoordinates &position )
145{
146 Q_ASSERT( !wayPoints.isEmpty() );
147 qreal minDistance = 0;
148 for ( int i = 1; i < wayPoints.size(); ++i ) {
149 qreal dist = distance( position, wayPoints.at( i-1 ), wayPoints.at( i ) );
150 if ( minDistance <= 0 || dist < minDistance ) {
151 minDistance = dist;
152 }
153 }
154
155 return minDistance;
156}
157
158qreal AlternativeRoutesModel::Private::bearing( const GeoDataCoordinates &one, const GeoDataCoordinates &two )
159{
160 qreal delta = two.longitude() - one.longitude();
161 qreal lat1 = one.latitude();
162 qreal lat2 = two.latitude();
163 return fmod( atan2( sin ( delta ) * cos ( lat2 ),
164 cos( lat1 ) * sin( lat2 ) - sin( lat1 ) * cos( lat2 ) * cos ( delta ) ), 2 * M_PI );
165}
166
167GeoDataCoordinates AlternativeRoutesModel::Private::coordinates( const GeoDataCoordinates &start, qreal distance, qreal bearing )
168{
169 qreal lat1 = start.latitude();
170 qreal lon1 = start.longitude();
171 qreal lat2 = asin( sin( lat1 ) * cos( distance ) + cos( lat1 ) * sin( distance ) * cos( bearing ) );
172 qreal lon2 = lon1 + atan2( sin( bearing ) * sin( distance ) * cos( lat1 ), cos( distance ) - sin( lat1 ) * sin( lat2 ) );
173 return GeoDataCoordinates( lon2, lat2 );
174}
175
176qreal AlternativeRoutesModel::Private::distance( const GeoDataCoordinates &satellite, const GeoDataCoordinates &lineA, const GeoDataCoordinates &lineB )
177{
178 const qreal dist = lineA.sphericalDistanceTo(satellite);
179 qreal bearA = bearing( lineA, satellite );
180 qreal bearB = bearing( lineA, lineB );
181 qreal result = asin( sin ( dist ) * sin( bearB - bearA ) );
182 Q_ASSERT(qMax<qreal>(satellite.sphericalDistanceTo(lineA), satellite.sphericalDistanceTo(lineB)) >= qAbs<qreal>(result));
183
184 result = acos( cos( dist ) / cos( result ) );
185 /** @todo: This is a naive approach. Look into the maths. */
186 const qreal final = qMin<qreal>(satellite.sphericalDistanceTo(lineA), satellite.sphericalDistanceTo(lineB));
187 if ( result >= 0 && result <= lineA.sphericalDistanceTo(lineB)) {
188 GeoDataCoordinates nearest = coordinates( lineA, result, bearB );
189 return qMin<qreal>(final, satellite.sphericalDistanceTo(nearest));
190 } else {
191 return final;
192 }
193}
194
195qreal AlternativeRoutesModel::Private::unidirectionalSimilarity( const GeoDataDocument* routeA, const GeoDataDocument* routeB )
196{
197 const GeoDataLineString* waypointsA = waypoints( routeA );
198 const GeoDataLineString* waypointsB = waypoints( routeB );
199 if ( !waypointsA || !waypointsB )
200 {
201 return 0.0;
202 }
203
205 image.fill( qRgb( 0, 0, 0 ) );
206 GeoDataLatLonBox box = GeoDataLatLonBox::fromLineString( *waypointsA );
207 box = box.united( GeoDataLatLonBox::fromLineString( *waypointsB ) );
208 if ( !box.width() || !box.height() ) {
209 return 0.0;
210 }
211
212 qreal const sw = image.width() / box.width();
213 qreal const sh = image.height() / box.height();
214
215 QPainter painter( &image );
216 painter.setPen( QColor( Qt::white ) );
217
218 painter.drawPoints( Private::polygon( *waypointsA, box.west(), box.north(), sw, sh ) );
219 int const countA = Private::nonZero( image );
220
221 painter.drawPoints( Private::polygon( *waypointsB, box.west(), box.north(), sw, sh ) );
222 int const countB = Private::nonZero( image );
223 Q_ASSERT( countA <= countB );
224 return countB ? 1.0 - qreal( countB - countA ) / countB : 0;
225}
226
227bool AlternativeRoutesModel::Private::higherScore( const GeoDataDocument* one, const GeoDataDocument* two )
228{
229 qreal instructionScoreA = instructionScore( one );
230 qreal instructionScoreB = instructionScore( two );
231 if ( instructionScoreA != instructionScoreB ) {
232 return instructionScoreA > instructionScoreB;
233 }
234
235 qreal lengthA = waypoints( one )->length( EARTH_RADIUS );
236 qreal lengthB = waypoints( two )->length( EARTH_RADIUS );
237
238 return lengthA < lengthB;
239}
240
241qreal AlternativeRoutesModel::Private::instructionScore( const GeoDataDocument* document )
242{
243 bool hasInstructions = false;
244
245 QStringList blacklist = QStringList() << "" << "Route" << "Tessellated";
246 QVector<GeoDataFolder*> folders = document->folderList();
247 for( const GeoDataFolder *folder: folders ) {
248 for( const GeoDataPlacemark *placemark: folder->placemarkList() ) {
249 if ( !blacklist.contains( placemark->name() ) ) {
250 hasInstructions = true;
251 break;
252 }
253 }
254 }
255
256 for( const GeoDataPlacemark *placemark: document->placemarkList() ) {
257 if ( !blacklist.contains( placemark->name() ) ) {
258 hasInstructions = true;
259
260 if (placemark->extendedData().contains(QStringLiteral("turnType"))) {
261 return 1.0;
262 }
263 }
264 }
265
266 return hasInstructions ? 0.5 : 0.0;
267}
268
269const GeoDataLineString* AlternativeRoutesModel::Private::waypoints( const GeoDataDocument* document )
270{
271 QVector<GeoDataFolder*> folders = document->folderList();
272 for( const GeoDataFolder *folder: folders ) {
273 for( const GeoDataPlacemark *placemark: folder->placemarkList() ) {
274 const GeoDataGeometry* geometry = placemark->geometry();
275 const GeoDataLineString* lineString = dynamic_cast<const GeoDataLineString*>( geometry );
276 if ( lineString ) {
277 return lineString;
278 }
279 }
280 }
281
282 for( const GeoDataPlacemark *placemark: document->placemarkList() ) {
283 const GeoDataGeometry* geometry = placemark->geometry();
284 const GeoDataLineString* lineString = dynamic_cast<const GeoDataLineString*>( geometry );
285 if ( lineString ) {
286 return lineString;
287 }
288 }
289
290 return nullptr;
291}
292
293AlternativeRoutesModel::AlternativeRoutesModel( QObject *parent ) :
294 QAbstractListModel( parent ),
295 d( new Private() )
296{
297 // nothing to do
298}
299
300AlternativeRoutesModel::~AlternativeRoutesModel()
301{
302 clear();
303 delete d;
304}
305
306int AlternativeRoutesModel::rowCount ( const QModelIndex & ) const
307{
308 return d->m_routes.size();
309}
310
311QVariant AlternativeRoutesModel::headerData ( int, Qt::Orientation, int ) const
312{
313 return QVariant();
314}
315
316QVariant AlternativeRoutesModel::data ( const QModelIndex &index, int role ) const
317{
318 QVariant result;
319
320 if ( role == Qt::DisplayRole && index.column() == 0 && index.row() >= 0 && index.row() < d->m_routes.size() ) {
321 result = d->m_routes.at( index.row() )->name();
322 }
323
324 return result;
325}
326
327const GeoDataDocument *AlternativeRoutesModel::route(int index) const
328{
329 if ( index >= 0 && index < d->m_routes.size() ) {
330 return d->m_routes.at(index);
331 }
332
333 return nullptr;
334}
335
336void AlternativeRoutesModel::newRequest( RouteRequest * )
337{
338 d->m_responseTime.start();
339 d->m_currentIndex = -1;
340 clear();
341}
342
343void AlternativeRoutesModel::addRestrainedRoutes()
344{
345 Q_ASSERT( d->m_routes.isEmpty() );
346 std::sort( d->m_restrainedRoutes.begin(), d->m_restrainedRoutes.end(), Private::higherScore );
347
348 for( GeoDataDocument* route: d->m_restrainedRoutes ) {
349 if ( !d->filter( route ) ) {
350 int affected = d->m_routes.size();
351 beginInsertRows( QModelIndex(), affected, affected );
352// GeoDataDocument* base = d->m_routes.isEmpty() ? 0 : d->m_routes.first();
353 d->m_routes.push_back( route );
354 endInsertRows();
355 }
356 }
357
358 d->m_restrainedRoutes.clear();
359 Q_ASSERT( !d->m_routes.isEmpty() );
360 setCurrentRoute( 0 );
361}
362
363void AlternativeRoutesModel::addRoute( GeoDataDocument* document, WritePolicy policy )
364{
365 if (policy != Instant) {
366 if (d->m_routes.isEmpty()) {
367 d->m_restrainedRoutes.push_back(document);
368
369 if (d->m_restrainedRoutes.isEmpty()) {
370 // First
371 const int responseTime = d->m_responseTime.elapsed();
372 const int timeout = qMin<int>(500, qMax<int>(50, responseTime * 2));
373 QTimer::singleShot(timeout, this, SLOT(addRestrainedRoutes()));
374
375 return;
376 }
377 }
378
379 for ( int i=0; i<d->m_routes.size(); ++i ) {
380 qreal similarity = Private::similarity( document, d->m_routes.at( i ) );
381 if ( similarity > 0.8 ) {
382 if ( Private::higherScore( document, d->m_routes.at( i ) ) ) {
383 d->m_routes[i] = document;
384 QModelIndex changed = index( i );
385 emit dataChanged( changed, changed );
386 }
387
388 return;
389 }
390 }
391 }
392
393 const int affected = d->m_routes.size();
394 beginInsertRows(QModelIndex(), affected, affected);
395 d->m_routes.push_back(document);
396 endInsertRows();
397}
398
399const GeoDataLineString* AlternativeRoutesModel::waypoints( const GeoDataDocument* document )
400{
401 return Private::waypoints( document );
402}
403
404void AlternativeRoutesModel::setCurrentRoute( int index )
405{
406 if ( index >= 0 && index < rowCount() && d->m_currentIndex != index ) {
407 d->m_currentIndex = index;
408 emit currentRouteChanged( currentRoute() );
409 emit currentRouteChanged( d->m_currentIndex );
410 }
411}
412
413const GeoDataDocument *AlternativeRoutesModel::currentRoute() const
414{
415 const GeoDataDocument *result = nullptr;
416 if ( d->m_currentIndex >= 0 && d->m_currentIndex < rowCount() ) {
417 result = d->m_routes[d->m_currentIndex];
418 }
419
420 return result;
421}
422
423void AlternativeRoutesModel::clear()
424{
425 beginResetModel();
426 QVector<GeoDataDocument*> routes = d->m_routes;
427 d->m_currentIndex = -1;
428 d->m_routes.clear();
429 qDeleteAll(routes);
430 endResetModel();
431}
432
433} // namespace Marble
434
435#include "moc_AlternativeRoutesModel.cpp"
Q_SCRIPTABLE Q_NOREPLY void start()
KGuiItem clear()
Binds a QML item to a specific geodetic location in screen coordinates.
KOSM_EXPORT double distance(const std::vector< const OSM::Node * > &path, Coordinate coord)
Format_ARGB32_Premultiplied
void fill(Qt::GlobalColor color)
int height() const const
uchar * scanLine(int i)
int width() const const
void clear()
int column() const const
int row() const const
bool contains(QLatin1StringView str, Qt::CaseSensitivity cs) const const
DisplayRole
Orientation
QFuture< void > filter(QThreadPool *pool, Sequence &sequence, KeepFunctor &&filterFunction)
This file is part of the KDE documentation.
Documentation copyright © 1996-2024 The KDE developers.
Generated on Tue Mar 26 2024 11:18:17 by doxygen 1.10.0 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.