bool QgsCompoundCurve::removeDuplicateNodes( double epsilon, bool useZValues )
{
  bool result = false;
  const QVector< QgsCurve * > curves = mCurves;
  int i = 0;
  QgsPoint lastEnd;
  for ( QgsCurve *curve : curves )
  {
    result = result || curve->removeDuplicateNodes( epsilon, useZValues );
    if ( curve->numPoints() == 0 || qgsDoubleNear( curve->length(), 0.0, epsilon ) )
    {
      // empty curve, remove it
      delete mCurves.takeAt( i );
      result = true;
    }
    else
    {
      // ensure this line starts exactly where previous line ended
      if ( i > 0 )
      {
        curve->moveVertex( QgsVertexId( -1, -1, 0 ), lastEnd );
      }
      lastEnd = curve->vertexAt( QgsVertexId( -1, -1, curve->numPoints() - 1 ) );
    }
    i++;
  }
  return result;
}

bool QgsLocatorProxyModel::lessThan( const QModelIndex &left, const QModelIndex &right ) const
{
  // first go by filter priority
  int leftFilterPriority = sourceModel()->data( left, QgsLocatorModel::ResultFilterPriorityRole ).toInt();
  int rightFilterPriority  = sourceModel()->data( right, QgsLocatorModel::ResultFilterPriorityRole ).toInt();
  if ( leftFilterPriority != rightFilterPriority )
    return leftFilterPriority < rightFilterPriority;

  // then filter name
  QString leftFilter = sourceModel()->data( left, QgsLocatorModel::ResultFilterNameRole ).toString();
  QString rightFilter = sourceModel()->data( right, QgsLocatorModel::ResultFilterNameRole ).toString();
  if ( leftFilter != rightFilter )
    return QString::localeAwareCompare( leftFilter, rightFilter ) < 0;

  // then make sure filter title appears before filter's results
  int leftTypeRole = sourceModel()->data( left, QgsLocatorModel::ResultTypeRole ).toInt();
  int rightTypeRole = sourceModel()->data( right, QgsLocatorModel::ResultTypeRole ).toInt();
  if ( leftTypeRole != rightTypeRole )
    return leftTypeRole < rightTypeRole;

  // sort filter's results by score
  double leftScore = sourceModel()->data( left, QgsLocatorModel::ResultScoreRole ).toDouble();
  double rightScore = sourceModel()->data( right, QgsLocatorModel::ResultScoreRole ).toDouble();
  if ( !qgsDoubleNear( leftScore, rightScore ) )
    return leftScore > rightScore;

  // lastly sort filter's results by string
  leftFilter = sourceModel()->data( left, Qt::DisplayRole ).toString();
  rightFilter = sourceModel()->data( right, Qt::DisplayRole ).toString();
  return QString::localeAwareCompare( leftFilter, rightFilter ) < 0;
}

QgsSymbol *QgsGraduatedSymbolRendererWidget::findSymbolForRange( double lowerBound, double upperBound, const QgsRangeList &ranges ) const
{
  int decimalPlaces = mRenderer->labelFormat().precision() + 2;
  if ( decimalPlaces < 0 )
    decimalPlaces = 0;
  double precision = 1.0 / std::pow( 10, decimalPlaces );

  for ( QgsRangeList::const_iterator it = ranges.begin(); it != ranges.end(); ++it )
  {
    if ( qgsDoubleNear( lowerBound, it->lowerValue(), precision ) && qgsDoubleNear( upperBound, it->upperValue(), precision ) )
    {
      return it->symbol();
    }
  }
  return nullptr;
}

void QgsMarkerSymbolV2::setDataDefinedSize( const QgsDataDefined &dd )
{
  const double symbolSize = size();

  for ( QgsSymbolLayerV2List::iterator it = mLayers.begin(); it != mLayers.end(); ++it )
  {
    QgsMarkerSymbolLayerV2* layer = static_cast<QgsMarkerSymbolLayerV2 *>( *it );

    if ( dd.hasDefaultValues() )
    {
      layer->removeDataDefinedProperty( "size" );
      layer->removeDataDefinedProperty( "offset" );
    }
    else
    {
      if ( symbolSize == 0 || qgsDoubleNear( layer->size(), symbolSize ) )
      {
        layer->setDataDefinedProperty( "size", new QgsDataDefined( dd ) );
      }
      else
      {
        layer->setDataDefinedProperty( "size", scaleWholeSymbol( layer->size() / symbolSize, dd ) );
      }

      if ( layer->offset().x() || layer->offset().y() )
      {
        layer->setDataDefinedProperty( "offset", scaleWholeSymbol(
                                         layer->offset().x() / symbolSize,
                                         layer->offset().y() / symbolSize, dd ) );
      }
    }
  }
}

void QgsMapToPixel::updateMatrix()
{
  double rotation = mapRotation();

#if 0 // debugging
  QgsDebugMsg( QString( "XXX %7 -- xCent:%1 yCent:%2 mWidth:%3 mHeight:%4 uPP:%5 rot:%6" )
               .arg( xCenter ).arg( yCenter ).arg( mWidth ).arg( mHeight )
               .arg( mMapUnitsPerPixel ).arg( rotation ).arg(( quintptr )this, QT_POINTER_SIZE *2, 15, QChar( '0' ) ) );
#endif

  // NOTE: operations are done in the reverse order in which
  //       they are configured, so translation to geographical
  //       center happens first, then scaling, then rotation
  //       and finally translation to output viewport center

  if ( qgsDoubleNear( rotation, 0.0 ) )
  {
    //no rotation, return a simplified matrix
    mMatrix = QTransform::fromScale( 1.0 / mMapUnitsPerPixel, -1.0 / mMapUnitsPerPixel )
              .translate( -xMin, - ( yMin + mHeight * mMapUnitsPerPixel ) );
    return;
  }

  double cy = mapHeight() / 2.0;
  double cx = mapWidth() / 2.0;
  mMatrix = QTransform::fromTranslate( cx, cy )
            .rotate( rotation )
            .scale( 1 / mMapUnitsPerPixel, -1 / mMapUnitsPerPixel )
            .translate( -xCenter, -yCenter )
            ;
}

void QgsScaleComboBox::fixupScale()
{
  if ( mAllowNull && currentText().trimmed().isEmpty() )
  {
    setScale( std::numeric_limits< double >::quiet_NaN() );
    return;
  }

  QStringList txtList = currentText().split( ':' );
  bool userSetScale = txtList.size() != 2;

  bool ok;
  double newScale = toDouble( currentText(), &ok );

  // Valid string representation
  if ( ok )
  {
    // if a user types scale = 2345, we transform to 1:2345
    if ( userSetScale && newScale < 1.0 && !qgsDoubleNear( newScale, 0.0 ) )
    {
      newScale = 1 / newScale;
    }
    setScale( newScale );
  }
  else
  {
    setScale( mScale );
  }
}

void QgsLineSymbolV2::setDataDefinedWidth( const QgsDataDefined& dd )
{
  const double symbolWidth = width();

  for ( QgsSymbolLayerV2List::iterator it = mLayers.begin(); it != mLayers.end(); ++it )
  {
    QgsLineSymbolLayerV2* layer = static_cast<QgsLineSymbolLayerV2*>( *it );

    if ( dd.hasDefaultValues() )
    {
      layer->removeDataDefinedProperty( "width" );
      layer->removeDataDefinedProperty( "offset" );
    }
    else
    {
      if ( symbolWidth == 0 || qgsDoubleNear( layer->width(), symbolWidth ) )
      {
        layer->setDataDefinedProperty( "width", new QgsDataDefined( dd ) );
      }
      else
      {
        layer->setDataDefinedProperty( "width", scaleWholeSymbol( layer->width() / symbolWidth, dd ) );
      }

      if ( layer->offset() )
      {
        layer->setDataDefinedProperty( "offset", scaleWholeSymbol( layer->offset() / symbolWidth, dd ) );
      }
    }
  }
}

void QgsMarkerSymbolV2::setDataDefinedAngle( const QgsDataDefined& dd )
{
  const double symbolRotation = angle();

  for ( QgsSymbolLayerV2List::iterator it = mLayers.begin(); it != mLayers.end(); ++it )
  {
    QgsMarkerSymbolLayerV2* layer = static_cast<QgsMarkerSymbolLayerV2 *>( *it );
    if ( dd.hasDefaultValues() )
    {
      layer->removeDataDefinedProperty( "angle" );
    }
    else
    {
      if ( qgsDoubleNear( layer->angle(), symbolRotation ) )
      {
        layer->setDataDefinedProperty( "angle", new QgsDataDefined( dd ) );
      }
      else
      {
        QgsDataDefined* rotatedDD = rotateWholeSymbol( layer->angle() - symbolRotation, dd );
        layer->setDataDefinedProperty( "angle", rotatedDD );
      }
    }
  }
}

void QgsPointMarkerItem::paint( QPainter * painter )
{
  if ( !painter )
  {
    return;
  }

  QgsRenderContext rc = renderContext( painter );

  bool useEffect = !qgsDoubleNear( mOpacityEffect->transparency(), 0.0 );
  if ( useEffect )
  {
    //use a paint effect to reduce opacity. If we directly set the opacity on the painter, then the symbol will NOT
    //be correctly "flattened" and parts of the symbol which should be obscured will show through
    mOpacityEffect->begin( rc );
  }

  mMarkerSymbol->startRender( rc, mFeature.fields() );
  mMarkerSymbol->renderPoint( mLocation - pos(), &mFeature, rc );
  mMarkerSymbol->stopRender( rc );

  if ( useEffect )
  {
    mOpacityEffect->end( rc );
  }
}

void QgsAtlasComposition::readXmlMapSettings( const QDomElement &elem, const QDomDocument &doc )
{
  Q_UNUSED( doc );
  //look for stored composer map, to upgrade pre 2.1 projects
  int composerMapNo = elem.attribute( "composerMap", "-1" ).toInt();
  QgsComposerMap * composerMap = nullptr;
  if ( composerMapNo != -1 )
  {
    QList<QgsComposerMap*> maps;
    mComposition->composerItems( maps );
    for ( QList<QgsComposerMap*>::iterator it = maps.begin(); it != maps.end(); ++it )
    {
      if (( *it )->id() == composerMapNo )
      {
        composerMap = ( *it );
        composerMap->setAtlasDriven( true );
        break;
      }
    }
  }

  //upgrade pre 2.1 projects
  double margin = elem.attribute( "margin", "0.0" ).toDouble();
  if ( composerMap && !qgsDoubleNear( margin, 0.0 ) )
  {
    composerMap->setAtlasMargin( margin );
  }
  bool fixedScale = elem.attribute( "fixedScale", "false" ) == "true" ? true : false;
  if ( composerMap && fixedScale )
  {
    composerMap->setAtlasScalingMode( QgsComposerMap::Fixed );
  }
}

int QgsCoordinateUtils::calculateCoordinatePrecision( double mapUnitsPerPixel, const QgsCoordinateReferenceSystem& mapCrs )
{
  // Get the display precision from the project settings
  bool automatic = QgsProject::instance()->readBoolEntry( "PositionPrecision", "/Automatic" );
  int dp = 0;

  if ( automatic )
  {
    QString format = QgsProject::instance()->readEntry( "PositionPrecision", "/DegreeFormat", "D" );
    bool formatGeographic = ( format == "DM" || format == "DMS" || format == "D" );

    // we can only calculate an automatic precision if both map CRS and format are geographic or both not geographic
    if ( mapCrs.geographicFlag() == formatGeographic )
    {
      // Work out a suitable number of decimal places for the coordinates with the aim of always
      // having enough decimal places to show the difference in position between adjacent pixels.
      // Also avoid taking the log of 0.
      if ( !qgsDoubleNear( mapUnitsPerPixel, 0.0 ) )
        dp = static_cast<int>( ceil( -1.0 * log10( mapUnitsPerPixel ) ) );
    }
    else
    {
      dp = format == "D" ? 4 : 2; //guess sensible fallback
    }
  }
  else
    dp = QgsProject::instance()->readNumEntry( "PositionPrecision", "/DecimalPlaces" );

  // Keep dp sensible
  if ( dp < 0 )
    dp = 0;

  return dp;
}

bool QgsComposerNodesItem::readXml( const QDomElement& itemElem,
                                    const QDomDocument& doc )
{
  // restore general composer item properties
  const QDomNodeList composerItemList = itemElem.elementsByTagName( QStringLiteral( "ComposerItem" ) );
  if ( !composerItemList.isEmpty() )
  {
    QDomElement composerItemElem = composerItemList.at( 0 ).toElement();

    if ( !qgsDoubleNear( composerItemElem.attribute( QStringLiteral( "rotation" ), QStringLiteral( "0" ) ).toDouble(), 0.0 ) )
      setItemRotation( composerItemElem.attribute( QStringLiteral( "rotation" ), QStringLiteral( "0" ) ).toDouble() );

    _readXml( composerItemElem, doc );
  }

  // restore style
  QDomElement styleSymbolElem = itemElem.firstChildElement( QStringLiteral( "symbol" ) );
  if ( !styleSymbolElem.isNull() )
    _readXmlStyle( styleSymbolElem );

  // restore nodes
  mPolygon.clear();
  QDomNodeList nodesList = itemElem.elementsByTagName( QStringLiteral( "node" ) );
  for ( int i = 0; i < nodesList.size(); i++ )
  {
    QDomElement nodeElem = nodesList.at( i ).toElement();
    QPointF newPt;
    newPt.setX( nodeElem.attribute( QStringLiteral( "x" ) ).toDouble() );
    newPt.setY( nodeElem.attribute( QStringLiteral( "y" ) ).toDouble() );
    mPolygon.append( newPt );
  }

  emit itemChanged();
  return true;
}

QgsSvgCacheEntry* QgsSvgCache::cacheEntry( const QString& file, double size, const QColor& fill, const QColor& outline, double outlineWidth,
    double widthScaleFactor )
{
  //search entries in mEntryLookup
  QgsSvgCacheEntry* currentEntry = nullptr;
  QList<QgsSvgCacheEntry*> entries = mEntryLookup.values( file );

  QList<QgsSvgCacheEntry*>::iterator entryIt = entries.begin();
  for ( ; entryIt != entries.end(); ++entryIt )
  {
    QgsSvgCacheEntry* cacheEntry = *entryIt;
    if ( qgsDoubleNear( cacheEntry->size, size ) && cacheEntry->fill == fill && cacheEntry->outline == outline &&
         qgsDoubleNear( cacheEntry->outlineWidth, outlineWidth ) && qgsDoubleNear( cacheEntry->widthScaleFactor, widthScaleFactor ) )
    {
      currentEntry = cacheEntry;
      break;
    }
  }

  //if not found: create new entry
  //cache and replace params in svg content
  if ( !currentEntry )
  {
    currentEntry = insertSVG( file, size, fill, outline, outlineWidth, widthScaleFactor );
  }
  else
  {
    takeEntryFromList( currentEntry );
    if ( !mMostRecentEntry ) //list is empty
    {
      mMostRecentEntry = currentEntry;
      mLeastRecentEntry = currentEntry;
    }
    else
    {
      mMostRecentEntry->nextEntry = currentEntry;
      currentEntry->previousEntry = mMostRecentEntry;
      currentEntry->nextEntry = nullptr;
      mMostRecentEntry = currentEntry;
    }
  }

  //debugging
  //printEntryList();

  return currentEntry;
}

void QgsQuickPositionKit::onPositionUpdated( const QGeoPositionInfo &info )
{
  bool hasPosition = info.coordinate().isValid();
  if ( hasPosition != mHasPosition )
  {
    mHasPosition = hasPosition;
    emit hasPositionChanged();
  }

  // Calculate position
  QgsPoint position = QgsPoint(
                        info.coordinate().longitude(),
                        info.coordinate().latitude(),
                        info.coordinate().altitude() ); // can be NaN

  if ( position != mPosition )
  {
    mPosition = position;
    emit positionChanged();
  }
  // calculate accuracy
  double accuracy;
  if ( info.hasAttribute( QGeoPositionInfo::HorizontalAccuracy ) )
    accuracy = info.attribute( QGeoPositionInfo::HorizontalAccuracy );
  else
    accuracy = -1;
  if ( !qgsDoubleNear( accuracy, mAccuracy ) )
  {
    mAccuracy = accuracy;
    emit accuracyChanged();
  }

  // calculate direction
  double direction;
  if ( info.hasAttribute( QGeoPositionInfo::Direction ) )
    direction = info.attribute( QGeoPositionInfo::Direction );
  else
    direction = -1;
  if ( !qgsDoubleNear( direction, mDirection ) )
  {
    mDirection = direction;
    emit directionChanged();
  }

  // recalculate projected/screen variables
  onMapSettingsUpdated();
}

double QgsCurve::sinuosity() const
{
  double d = straightDistance2d();
  if ( qgsDoubleNear( d, 0.0 ) )
    return std::numeric_limits<double>::quiet_NaN();

  return length() / d;
}

inline
QgsRenderContext * QgsSymbolV2LegendNode::createTemporaryRenderContext() const
{
  double scale = 0.0;
  double mupp = 0.0;
  int dpi = 0;
  if ( model() )
    model()->legendMapViewData( &mupp, &dpi, &scale );
  bool validData = !qgsDoubleNear( mupp, 0.0 ) && dpi != 0 && !qgsDoubleNear( scale, 0.0 );

  // setup temporary render context
  QScopedPointer<QgsRenderContext> context( new QgsRenderContext );
  context->setScaleFactor( dpi / 25.4 );
  context->setRendererScale( scale );
  context->setMapToPixel( QgsMapToPixel( mupp ) );
  return validData ? context.take() : nullptr;
}

void QgsQuickIdentifyKit::setSearchRadiusMm( double searchRadiusMm )
{
  if ( qgsDoubleNear( mSearchRadiusMm, searchRadiusMm ) )
    return;

  mSearchRadiusMm = searchRadiusMm;
  emit searchRadiusMmChanged();
}

double QgsMeshCalcUtils::ffilter( double val1, double filter ) const
{
  Q_ASSERT( !std::isnan( val1 ) );

  if ( qgsDoubleNear( filter, D_TRUE ) )
    return val1;
  else
    return D_NODATA;
}

//
// distance of point q from line through p in direction v
// return >0  => q lies left of the line
//        <0  => q lies right of the line
//
double QgsGeometryValidator::distLine2Point( const QgsPoint& p, QgsVector v, const QgsPoint& q )
{
  if ( qgsDoubleNear( v.length(), 0 ) )
  {
    throw QgsException( QObject::tr( "invalid line" ) );
  }

  return ( v.x()*( q.y() - p.y() ) - v.y()*( q.x() - p.x() ) ) / v.length();
}

QgsRenderContext *QgsLayerTreeModelLegendNode::createTemporaryRenderContext() const
{
  double scale = 0.0;
  double mupp = 0.0;
  int dpi = 0;
  if ( model() )
    model()->legendMapViewData( &mupp, &dpi, &scale );

  if ( qgsDoubleNear( mupp, 0.0 ) || dpi == 0 || qgsDoubleNear( scale, 0.0 ) )
    return nullptr;

  // setup temporary render context
  std::unique_ptr<QgsRenderContext> context = qgis::make_unique<QgsRenderContext>( );
  context->setScaleFactor( dpi / 25.4 );
  context->setRendererScale( scale );
  context->setMapToPixel( QgsMapToPixel( mupp ) );
  return context.release();
}