6 #include "AlternativeRoutesModel.h"
8 #include "GeoDataLatLonAltBox.h"
9 #include "GeoDataDocument.h"
10 #include "GeoDataFolder.h"
11 #include "GeoDataExtendedData.h"
12 #include "GeoDataLineString.h"
13 #include "GeoDataPlacemark.h"
15 #include <QElapsedTimer>
21 class Q_DECL_HIDDEN AlternativeRoutesModel::Private
29 bool filter(
const GeoDataDocument* document )
const;
38 static qreal similarity(
const GeoDataDocument* routeA,
const GeoDataDocument* routeB );
43 static qreal
distance(
const GeoDataLineString &wayPoints,
const GeoDataCoordinates &position );
49 static qreal bearing(
const GeoDataCoordinates &one,
const GeoDataCoordinates &two );
55 static qreal
distance(
const GeoDataCoordinates &satellite,
const GeoDataCoordinates &lineA,
const GeoDataCoordinates &lineB );
60 static GeoDataCoordinates coordinates(
const GeoDataCoordinates &
start, qreal distance, qreal bearing );
66 static qreal unidirectionalSimilarity(
const GeoDataDocument* routeA,
const GeoDataDocument* routeB );
71 static bool higherScore(
const GeoDataDocument* one,
const GeoDataDocument* two );
76 static qreal instructionScore(
const GeoDataDocument* document );
78 static const GeoDataLineString* waypoints(
const GeoDataDocument* document );
80 static int nonZero(
const QImage &image );
82 static QPolygonF polygon(
const GeoDataLineString &lineString, qreal x, qreal y, qreal sx, qreal sy );
97 AlternativeRoutesModel::Private::Private() :
103 int AlternativeRoutesModel::Private::nonZero(
const QImage &image )
105 QRgb
const black = qRgb( 0, 0, 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;
116 QPolygonF AlternativeRoutesModel::Private::polygon(
const GeoDataLineString &lineString, qreal x, qreal y, qreal sx, qreal sy )
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 );
126 bool AlternativeRoutesModel::Private::filter(
const GeoDataDocument* document )
const
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 ) {
138 qreal AlternativeRoutesModel::Private::similarity(
const GeoDataDocument* routeA,
const GeoDataDocument* routeB )
140 return qMax<qreal>( unidirectionalSimilarity( routeA, routeB ),
141 unidirectionalSimilarity( routeB, routeA ) );
144 qreal AlternativeRoutesModel::Private::distance(
const GeoDataLineString &wayPoints,
const GeoDataCoordinates &position )
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 ) {
158 qreal AlternativeRoutesModel::Private::bearing(
const GeoDataCoordinates &one,
const GeoDataCoordinates &two )
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 );
167 GeoDataCoordinates AlternativeRoutesModel::Private::coordinates(
const GeoDataCoordinates &
start, qreal distance, qreal bearing )
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 );
176 qreal AlternativeRoutesModel::Private::distance(
const GeoDataCoordinates &satellite,
const GeoDataCoordinates &lineA,
const GeoDataCoordinates &lineB )
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));
184 result = acos( cos( dist ) / cos( result ) );
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));
195 qreal AlternativeRoutesModel::Private::unidirectionalSimilarity(
const GeoDataDocument* routeA,
const GeoDataDocument* routeB )
197 const GeoDataLineString* waypointsA = waypoints( routeA );
198 const GeoDataLineString* waypointsB = waypoints( routeB );
199 if ( !waypointsA || !waypointsB )
205 image.
fill( qRgb( 0, 0, 0 ) );
208 if ( !box.width() || !box.height() ) {
212 qreal
const sw = image.
width() / box.width();
213 qreal
const sh = image.
height() / box.height();
218 painter.drawPoints( Private::polygon( *waypointsA, box.west(), box.north(), sw, sh ) );
219 int const countA = Private::nonZero( image );
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;
227 bool AlternativeRoutesModel::Private::higherScore(
const GeoDataDocument* one,
const GeoDataDocument* two )
229 qreal instructionScoreA = instructionScore( one );
230 qreal instructionScoreB = instructionScore( two );
231 if ( instructionScoreA != instructionScoreB ) {
232 return instructionScoreA > instructionScoreB;
235 qreal lengthA = waypoints( one )->length( EARTH_RADIUS );
236 qreal lengthB = waypoints( two )->length( EARTH_RADIUS );
238 return lengthA < lengthB;
241 qreal AlternativeRoutesModel::Private::instructionScore(
const GeoDataDocument* document )
243 bool hasInstructions =
false;
247 for(
const GeoDataFolder *folder: folders ) {
248 for(
const GeoDataPlacemark *placemark: folder->placemarkList() ) {
249 if ( !blacklist.
contains( placemark->name() ) ) {
250 hasInstructions =
true;
256 for(
const GeoDataPlacemark *placemark: document->placemarkList() ) {
257 if ( !blacklist.
contains( placemark->name() ) ) {
258 hasInstructions =
true;
260 if (placemark->extendedData().contains(QStringLiteral(
"turnType"))) {
266 return hasInstructions ? 0.5 : 0.0;
269 const GeoDataLineString* AlternativeRoutesModel::Private::waypoints(
const GeoDataDocument* document )
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 );
282 for(
const GeoDataPlacemark *placemark: document->placemarkList() ) {
283 const GeoDataGeometry* geometry = placemark->geometry();
284 const GeoDataLineString* lineString =
dynamic_cast<const GeoDataLineString*
>( geometry );
293 AlternativeRoutesModel::AlternativeRoutesModel(
QObject *parent ) :
300 AlternativeRoutesModel::~AlternativeRoutesModel()
306 int AlternativeRoutesModel::rowCount (
const QModelIndex & )
const
308 return d->m_routes.size();
321 result = d->m_routes.at( index.
row() )->name();
327 const GeoDataDocument *AlternativeRoutesModel::route(
int index)
const
329 if ( index >= 0 && index < d->m_routes.size() ) {
330 return d->m_routes.at(index);
336 void AlternativeRoutesModel::newRequest( RouteRequest * )
338 d->m_responseTime.start();
339 d->m_currentIndex = -1;
343 void AlternativeRoutesModel::addRestrainedRoutes()
345 Q_ASSERT( d->m_routes.isEmpty() );
346 std::sort( d->m_restrainedRoutes.begin(), d->m_restrainedRoutes.end(), Private::higherScore );
348 for( GeoDataDocument* route: d->m_restrainedRoutes ) {
349 if ( !d->filter( route ) ) {
350 int affected = d->m_routes.size();
351 beginInsertRows(
QModelIndex(), affected, affected );
353 d->m_routes.push_back( route );
358 d->m_restrainedRoutes.clear();
359 Q_ASSERT( !d->m_routes.isEmpty() );
360 setCurrentRoute( 0 );
363 void AlternativeRoutesModel::addRoute( GeoDataDocument* document, WritePolicy policy )
366 if (d->m_routes.isEmpty()) {
367 d->m_restrainedRoutes.push_back(document);
369 if (d->m_restrainedRoutes.isEmpty()) {
371 const int responseTime = d->m_responseTime.elapsed();
372 const int timeout = qMin<int>(500, qMax<int>(50, responseTime * 2));
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;
385 emit dataChanged( changed, changed );
393 const int affected = d->m_routes.size();
394 beginInsertRows(
QModelIndex(), affected, affected);
395 d->m_routes.push_back(document);
399 const GeoDataLineString* AlternativeRoutesModel::waypoints(
const GeoDataDocument* document )
401 return Private::waypoints( document );
404 void AlternativeRoutesModel::setCurrentRoute(
int index )
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 );
413 const GeoDataDocument *AlternativeRoutesModel::currentRoute()
const
415 const GeoDataDocument *result =
nullptr;
416 if ( d->m_currentIndex >= 0 && d->m_currentIndex < rowCount() ) {
417 result = d->m_routes[d->m_currentIndex];
423 void AlternativeRoutesModel::clear()
427 d->m_currentIndex = -1;
435 #include "moc_AlternativeRoutesModel.cpp"