Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
Handle exact distances in curveSubstring
Fixes #41081

These exact distances may be obtained with distance_to_vertex.

Before this change, the code considered the line segments as open
intervals, so that vertices could not ever be considered as the start
of a substring.  This change considers them as semi-open intervals
(closed at the beginning) instead. (With a special case when starting
the substring at the last vertex)

Before this change, vertices could not be considered as the end of a
substring, so an other loop was required, adding a duplicate node.

Similar behaviour is observed for QgsCircularString and corrected
similarly.

Double equality is performed as exact equality, because it does not
matter on which segment the start of the substring is. Except where
startDistance is -0.0, which is already handled before the for loop,
or when startDistance is at the last vertex.

(cherry picked from commit 5b2685d)
  • Loading branch information
alkra authored and nyalldawson committed Feb 19, 2021
1 parent 6c5b035 commit 2bf2246
Show file tree
Hide file tree
Showing 3 changed files with 36 additions and 26 deletions.
29 changes: 16 additions & 13 deletions src/core/geometry/qgscircularstring.cpp
Expand Up @@ -1278,12 +1278,12 @@ QgsCircularString *QgsCircularString::curveSubstring( double startDistance, doub

endDistance = std::max( startDistance, endDistance );

double distanceTraversed = 0;
const int totalPoints = numPoints();
if ( totalPoints == 0 )
return clone();

QVector< QgsPoint > substringPoints;
substringPoints.reserve( totalPoints );

QgsWkbTypes::Type pointType = QgsWkbTypes::Point;
if ( is3D() )
Expand All @@ -1296,19 +1296,15 @@ QgsCircularString *QgsCircularString::curveSubstring( double startDistance, doub
const double *z = is3D() ? mZ.constData() : nullptr;
const double *m = isMeasure() ? mM.constData() : nullptr;

double distanceTraversed = 0;
double prevX = *x++;
double prevY = *y++;
double prevZ = z ? *z++ : 0.0;
double prevM = m ? *m++ : 0.0;
bool foundStart = false;

if ( qgsDoubleNear( startDistance, 0.0 ) || startDistance < 0 )
{
substringPoints << QgsPoint( pointType, prevX, prevY, prevZ, prevM );
foundStart = true;
}

substringPoints.reserve( totalPoints );
if ( startDistance < 0 )
startDistance = 0;

for ( int i = 0; i < ( totalPoints - 2 ) ; i += 2 )
{
Expand All @@ -1329,7 +1325,7 @@ QgsCircularString *QgsCircularString::curveSubstring( double startDistance, doub

bool addedSegmentEnd = false;
const double segmentLength = QgsGeometryUtils::circleLength( x1, y1, x2, y2, x3, y3 );
if ( distanceTraversed < startDistance && distanceTraversed + segmentLength > startDistance )
if ( distanceTraversed <= startDistance && startDistance < distanceTraversed + segmentLength )
{
// start point falls on this segment
const double distanceToStart = startDistance - distanceTraversed;
Expand Down Expand Up @@ -1383,14 +1379,21 @@ QgsCircularString *QgsCircularString::curveSubstring( double startDistance, doub
<< QgsPoint( pointType, x3, y3, z3, m3 );
}

distanceTraversed += segmentLength;
if ( distanceTraversed > endDistance )
break;

prevX = x3;
prevY = y3;
prevZ = z3;
prevM = m3;
distanceTraversed += segmentLength;
if ( distanceTraversed >= endDistance )
break;
}

// start point is the last node
if ( !foundStart && qgsDoubleNear( distanceTraversed, startDistance ) )
{
substringPoints << QgsPoint( pointType, prevX, prevY, prevZ, prevM )
<< QgsPoint( pointType, prevX, prevY, prevZ, prevM )
<< QgsPoint( pointType, prevX, prevY, prevZ, prevM );
}

std::unique_ptr< QgsCircularString > result = qgis::make_unique< QgsCircularString >();
Expand Down
29 changes: 16 additions & 13 deletions src/core/geometry/qgslinestring.cpp
Expand Up @@ -1030,12 +1030,12 @@ QgsLineString *QgsLineString::curveSubstring( double startDistance, double endDi

endDistance = std::max( startDistance, endDistance );

double distanceTraversed = 0;
const int totalPoints = numPoints();
if ( totalPoints == 0 )
return clone();

QVector< QgsPoint > substringPoints;
substringPoints.reserve( totalPoints );

QgsWkbTypes::Type pointType = QgsWkbTypes::Point;
if ( is3D() )
Expand All @@ -1048,19 +1048,15 @@ QgsLineString *QgsLineString::curveSubstring( double startDistance, double endDi
const double *z = is3D() ? mZ.constData() : nullptr;
const double *m = isMeasure() ? mM.constData() : nullptr;

double distanceTraversed = 0;
double prevX = *x++;
double prevY = *y++;
double prevZ = z ? *z++ : 0.0;
double prevM = m ? *m++ : 0.0;
bool foundStart = false;

if ( qgsDoubleNear( startDistance, 0.0 ) || startDistance < 0 )
{
substringPoints << QgsPoint( pointType, prevX, prevY, prevZ, prevM );
foundStart = true;
}

substringPoints.reserve( totalPoints );
if ( startDistance < 0 )
startDistance = 0;

for ( int i = 1; i < totalPoints; ++i )
{
Expand All @@ -1070,7 +1066,8 @@ QgsLineString *QgsLineString::curveSubstring( double startDistance, double endDi
double thisM = m ? *m++ : 0.0;

const double segmentLength = std::sqrt( ( thisX - prevX ) * ( thisX - prevX ) + ( thisY - prevY ) * ( thisY - prevY ) );
if ( distanceTraversed < startDistance && distanceTraversed + segmentLength > startDistance )

if ( distanceTraversed <= startDistance && startDistance < distanceTraversed + segmentLength )
{
// start point falls on this segment
const double distanceToStart = startDistance - distanceTraversed;
Expand Down Expand Up @@ -1100,14 +1097,20 @@ QgsLineString *QgsLineString::curveSubstring( double startDistance, double endDi
substringPoints << QgsPoint( pointType, thisX, thisY, thisZ, thisM );
}

distanceTraversed += segmentLength;
if ( distanceTraversed > endDistance )
break;

prevX = thisX;
prevY = thisY;
prevZ = thisZ;
prevM = thisM;
distanceTraversed += segmentLength;
if ( distanceTraversed >= endDistance )
break;
}

// start point is the last node
if ( !foundStart && qgsDoubleNear( distanceTraversed, startDistance ) )
{
substringPoints << QgsPoint( pointType, prevX, prevY, prevZ, prevM )
<< QgsPoint( pointType, prevX, prevY, prevZ, prevM );
}

return new QgsLineString( substringPoints );
Expand Down
4 changes: 4 additions & 0 deletions tests/src/core/testqgsgeometry.cpp
Expand Up @@ -2846,6 +2846,8 @@ void TestQgsGeometry::circularString()
QCOMPARE( substringResult->asWkt( 2 ), QStringLiteral( "CircularStringZM (13.51 -0.98 13 14, 14.01 -1 13.03 14.03, 14.5 -0.9 14.65 15.65)" ) );
substringResult.reset( substring.curveSubstring( 5, 1000 ) );
QCOMPARE( substringResult->asWkt( 2 ), QStringLiteral( "CircularStringZM (13.51 -0.98 13 14, 15.19 -0.53 17.2 18.2, 16 1 23 24)" ) );
substringResult.reset( substring.curveSubstring( QgsGeometryUtils::distanceToVertex( substring, QgsVertexId( 0, 0, 2 ) ), QgsGeometryUtils::distanceToVertex( substring, QgsVertexId( 0, 0, 4 ) ) ) );
QCOMPARE( substringResult->asWkt( 2 ), QStringLiteral( "CircularStringZM (12 0 13 14, 14.36 -0.94 14.19 15.19, 16 1 23 24)" ) );

substring.setPoints( QgsPointSequence() << QgsPoint( 10, 0, 1 ) << QgsPoint( 11, 1, 3 ) << QgsPoint( 12, 0, 13 )
<< QgsPoint( 14, -1, 13 ) << QgsPoint( 16, 1, 23 ) );
Expand Down Expand Up @@ -4930,6 +4932,8 @@ void TestQgsGeometry::lineString()
QCOMPARE( substringResult->asWkt( 2 ), QStringLiteral( "LineStringZM (11 3 4 5, 11 12 13 14, 111 12 23 24)" ) );
substringResult.reset( substring.curveSubstring( 1, 20 ) );
QCOMPARE( substringResult->asWkt( 2 ), QStringLiteral( "LineStringZM (11 3 4 5, 11 12 13 14, 21 12 14 15)" ) );
substringResult.reset( substring.curveSubstring( QgsGeometryUtils::distanceToVertex( substring, QgsVertexId( 0, 0, 1 ) ), QgsGeometryUtils::distanceToVertex( substring, QgsVertexId( 0, 0, 2 ) ) ) );
QCOMPARE( substringResult->asWkt( 2 ), QStringLiteral( "LineStringZM (11 12 13 14, 111 12 23 24)" ) );
substring.setPoints( QgsPointSequence() << QgsPoint( 11, 2, 3, 0, QgsWkbTypes::PointZ ) << QgsPoint( 11, 12, 13, 0, QgsWkbTypes::PointZ ) << QgsPoint( 111, 12, 23, 0, QgsWkbTypes::PointZ ) );
substringResult.reset( substring.curveSubstring( 1, 20 ) );
QCOMPARE( substringResult->asWkt( 2 ), QStringLiteral( "LineStringZ (11 3 4, 11 12 13, 21 12 14)" ) );
Expand Down

0 comments on commit 2bf2246

Please sign in to comment.