Marble

AlternativeRoutesModel.cpp
1 // SPDX-License-Identifier: LGPL-2.1-or-later
2 //
3 // SPDX-FileCopyrightText: 2010 Dennis Nienhüser <[email protected]>
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 
19 namespace Marble {
20 
21 class Q_DECL_HIDDEN AlternativeRoutesModel::Private
22 {
23 public:
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 
97 AlternativeRoutesModel::Private::Private() :
98  m_currentIndex( -1 )
99 {
100  // nothing to do
101 }
102 
103 int 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 
116 QPolygonF 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 
126 bool 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 
138 qreal AlternativeRoutesModel::Private::similarity( const GeoDataDocument* routeA, const GeoDataDocument* routeB )
139 {
140  return qMax<qreal>( unidirectionalSimilarity( routeA, routeB ),
141  unidirectionalSimilarity( routeB, routeA ) );
142 }
143 
144 qreal 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 
158 qreal 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 
167 GeoDataCoordinates 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 
176 qreal 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 
195 qreal 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 
227 bool 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 
241 qreal 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 
269 const 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 
293 AlternativeRoutesModel::AlternativeRoutesModel( QObject *parent ) :
294  QAbstractListModel( parent ),
295  d( new Private() )
296 {
297  // nothing to do
298 }
299 
300 AlternativeRoutesModel::~AlternativeRoutesModel()
301 {
302  clear();
303  delete d;
304 }
305 
306 int AlternativeRoutesModel::rowCount ( const QModelIndex & ) const
307 {
308  return d->m_routes.size();
309 }
310 
311 QVariant AlternativeRoutesModel::headerData ( int, Qt::Orientation, int ) const
312 {
313  return QVariant();
314 }
315 
316 QVariant 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 
327 const 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 
336 void AlternativeRoutesModel::newRequest( RouteRequest * )
337 {
338  d->m_responseTime.start();
339  d->m_currentIndex = -1;
340  clear();
341 }
342 
343 void 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 
363 void 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 
399 const GeoDataLineString* AlternativeRoutesModel::waypoints( const GeoDataDocument* document )
400 {
401  return Private::waypoints( document );
402 }
403 
404 void 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 
413 const 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 
423 void 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"
DisplayRole
Format_ARGB32_Premultiplied
int height() const const
void fill(uint pixelValue)
int column() const const
bool contains(const QString &str, Qt::CaseSensitivity cs) const const
Q_SCRIPTABLE Q_NOREPLY void start()
void clear()
KOSM_EXPORT double distance(const std::vector< const OSM::Node * > &path, Coordinate coord)
Orientation
QFuture< void > filter(Sequence &sequence, KeepFunctor filterFunction)
Binds a QML item to a specific geodetic location in screen coordinates.
uchar * scanLine(int i)
int row() const const
QAction * clear(const QObject *recvr, const char *slot, QObject *parent)
@ Instant
Change camera position immediately (no interpolation)
Definition: MarbleGlobal.h:164
static GeoDataLatLonBox fromLineString(const GeoDataLineString &lineString)
Create the smallest bounding box from a line string.
int width() const const
This file is part of the KDE documentation.
Documentation copyright © 1996-2023 The KDE developers.
Generated on Wed Oct 4 2023 04:09:40 by doxygen 1.8.17 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.