Skip to content

Commit

Permalink
improve segmentIntersection
Browse files Browse the repository at this point in the history
  • Loading branch information
@lbartoletti
lbartoletti committed Dec 12, 2017
1 parent 3d021c4 commit 342985f
Show file tree
Hide file tree
Showing 8 changed files with 120 additions and 14 deletions.
4 changes: 3 additions & 1 deletion python/core/geometry/qgsgeometryutils.sip
View file
Expand Up @@ -98,15 +98,17 @@ class QgsGeometryUtils
:rtype: bool
%End

static bool segmentIntersection( const QgsPoint &p1, const QgsPoint &p2, const QgsPoint &q1, const QgsPoint &q2, QgsPoint &inter /Out/, double tolerance );
static bool segmentIntersection( const QgsPoint &p1, const QgsPoint &p2, const QgsPoint &q1, const QgsPoint &q2, QgsPoint &inter /Out/, bool &isIntersect /Out/, double tolerance, bool acceptImproperIntersection = false );
%Docstring
Compute the intersection between two segments
\param p1 First segment start point
\param p2 First segment end point
\param q1 Second segment start point
\param q2 Second segment end point
\param inter Output parameter, the intersection point
\param isIntersect Output parameter, return true if an intersection is found
\param tolerance The tolerance to use
\param acceptImproperIntersection By defaut this method return only intersection point if segments are not contigus. If set on true, return also contigus point as an intersection point.
:return: Whether the segments intersect
:rtype: bool
%End
Expand Down
3 changes: 2 additions & 1 deletion src/analysis/vector/geometry_checker/qgsgeometrycheckerutils.cpp
View file
Expand Up @@ -257,6 +257,7 @@ namespace QgsGeometryCheckerUtils
{
QList<QgsPoint> intersections;
QgsPoint inter;
bool intersection;
for ( int i = 0, n = line1->vertexCount() - 1; i < n; ++i )
{
for ( int j = 0, m = line2->vertexCount() - 1; j < m; ++j )
Expand All @@ -265,7 +266,7 @@ namespace QgsGeometryCheckerUtils
QgsPoint p2 = line1->vertexAt( QgsVertexId( 0, 0, i + 1 ) );
QgsPoint q1 = line2->vertexAt( QgsVertexId( 0, 0, j ) );
QgsPoint q2 = line2->vertexAt( QgsVertexId( 0, 0, j + 1 ) );
if ( QgsGeometryUtils::segmentIntersection( p1, p2, q1, q2, inter, tol ) )
if ( QgsGeometryUtils::segmentIntersection( p1, p2, q1, q2, inter, intersection, tol ) )
{
intersections.append( inter );
}
Expand Down
3 changes: 2 additions & 1 deletion src/analysis/vector/geometry_checker/qgsgeometryselfintersectioncheck.cpp
View file
Expand Up @@ -114,7 +114,8 @@ void QgsGeometrySelfIntersectionCheck::fixError( QgsGeometryCheckError *error, i
QgsPoint p2 = geom->vertexAt( QgsVertexId( vidx.part, vidx.ring, ( inter.segment1 + 1 ) % nVerts ) );
QgsPoint q2 = geom->vertexAt( QgsVertexId( vidx.part, vidx.ring, ( inter.segment2 + 1 ) % nVerts ) );
QgsPoint s;
if ( !QgsGeometryUtils::segmentIntersection( p1, p2, q1, q2, s, mContext->tolerance ) )
bool intersection;
if ( !QgsGeometryUtils::segmentIntersection( p1, p2, q1, q2, s, intersection, mContext->tolerance ) )
{
error->setObsolete();
return;
Expand Down
7 changes: 4 additions & 3 deletions src/core/geometry/qgscircle.cpp
View file
Expand Up @@ -182,9 +182,10 @@ QgsCircle QgsCircle::fromCenterPoint( const QgsPoint &center, const QgsPoint &pt
QgsCircle QgsCircle::from3Tangents( const QgsPoint &pt1_tg1, const QgsPoint &pt2_tg1, const QgsPoint &pt1_tg2, const QgsPoint &pt2_tg2, const QgsPoint &pt1_tg3, const QgsPoint &pt2_tg3, double epsilon )
{
QgsPoint p1, p2, p3;
QgsGeometryUtils::segmentIntersection( pt1_tg1, pt2_tg1, pt1_tg2, pt2_tg2, p1, epsilon );
QgsGeometryUtils::segmentIntersection( pt1_tg1, pt2_tg1, pt1_tg3, pt2_tg3, p2, epsilon );
QgsGeometryUtils::segmentIntersection( pt1_tg2, pt2_tg2, pt1_tg3, pt2_tg3, p3, epsilon );
bool intersection;
QgsGeometryUtils::segmentIntersection( pt1_tg1, pt2_tg1, pt1_tg2, pt2_tg2, p1, intersection, epsilon );
QgsGeometryUtils::segmentIntersection( pt1_tg1, pt2_tg1, pt1_tg3, pt2_tg3, p2, intersection, epsilon );
QgsGeometryUtils::segmentIntersection( pt1_tg2, pt2_tg2, pt1_tg3, pt2_tg3, p3, intersection, epsilon );

return QgsTriangle( p1, p2, p3 ).inscribedCircle();
}
Expand Down
26 changes: 23 additions & 3 deletions src/core/geometry/qgsgeometryutils.cpp
View file
Expand Up @@ -251,22 +251,41 @@ bool QgsGeometryUtils::lineIntersection( const QgsPoint &p1, QgsVector v, const
return true;
}

bool QgsGeometryUtils::segmentIntersection( const QgsPoint &p1, const QgsPoint &p2, const QgsPoint &q1, const QgsPoint &q2, QgsPoint &inter, double tolerance )
bool QgsGeometryUtils::segmentIntersection( const QgsPoint &p1, const QgsPoint &p2, const QgsPoint &q1, const QgsPoint &q2, QgsPoint &inter, bool &isIntersect, double tolerance, bool acceptImproperIntersection )
{
isIntersect = false;

QgsVector v( p2.x() - p1.x(), p2.y() - p1.y() );
QgsVector w( q2.x() - q1.x(), q2.y() - q1.y() );
double vl = v.length();
double wl = w.length();

if ( qgsDoubleNear( vl, 0, 0.000000000001 ) || qgsDoubleNear( wl, 0, 0.000000000001 ) )
if ( qgsDoubleNear( vl, 0.0, tolerance ) || qgsDoubleNear( wl, 0.0, tolerance ) )
{
return false;
}
v = v / vl;
w = w / wl;

if ( !QgsGeometryUtils::lineIntersection( p1, v, q1, w, inter ) )
{
return false;
}

isIntersect = true;
if ( acceptImproperIntersection )
{
if ( ( p1 == q1 ) || ( p1 == q2 ) )
{
inter = p1;
return true;
}
else if ( ( p2 == q1 ) || ( p2 == q2 ) )
{
inter == p2;
return true;
}
}

double lambdav = QgsVector( inter.x() - p1.x(), inter.y() - p1.y() ) * v;
if ( lambdav < 0. + tolerance || lambdav > vl - tolerance )
Expand Down Expand Up @@ -299,7 +318,8 @@ QVector<QgsGeometryUtils::SelfIntersection> QgsGeometryUtils::getSelfIntersectio
QgsPoint pl = geom->vertexAt( QgsVertexId( part, ring, l ) );

QgsPoint inter;
if ( !QgsGeometryUtils::segmentIntersection( pi, pj, pk, pl, inter, tolerance ) ) continue;
bool intersection;
if ( !QgsGeometryUtils::segmentIntersection( pi, pj, pk, pl, inter, intersection, tolerance ) ) continue;

SelfIntersection s;
s.segment1 = i;
Expand Down
4 changes: 3 additions & 1 deletion src/core/geometry/qgsgeometryutils.h
View file
Expand Up @@ -107,10 +107,12 @@ class CORE_EXPORT QgsGeometryUtils
* \param q1 Second segment start point
* \param q2 Second segment end point
* \param inter Output parameter, the intersection point
* \param isIntersect Output parameter, return true if an intersection is found
* \param tolerance The tolerance to use
* \param acceptImproperIntersection By defaut this method return only intersection point if segments are not contigus. If set on true, return also contigus point as an intersection point.
* \returns Whether the segments intersect
*/
static bool segmentIntersection( const QgsPoint &p1, const QgsPoint &p2, const QgsPoint &q1, const QgsPoint &q2, QgsPoint &inter SIP_OUT, double tolerance );
static bool segmentIntersection( const QgsPoint &p1, const QgsPoint &p2, const QgsPoint &q1, const QgsPoint &q2, QgsPoint &inter SIP_OUT, bool &isIntersect SIP_OUT, double tolerance, bool acceptImproperIntersection = false );

/**
* \brief Project the point on a segment
Expand Down
10 changes: 6 additions & 4 deletions src/core/geometry/qgstriangle.cpp
View file
Expand Up @@ -495,14 +495,15 @@ QVector<QgsLineString> QgsTriangle::bisectors( double lengthTolerance ) const
QgsLineString bis3;
QgsPoint incenter = inscribedCenter();
QgsPoint out;
bool intersection;

QgsGeometryUtils::segmentIntersection( vertexAt( 0 ), incenter, vertexAt( 1 ), vertexAt( 2 ), out, lengthTolerance );
QgsGeometryUtils::segmentIntersection( vertexAt( 0 ), incenter, vertexAt( 1 ), vertexAt( 2 ), out, intersection, lengthTolerance );
bis1.setPoints( QgsPointSequence() << vertexAt( 0 ) << out );

QgsGeometryUtils::segmentIntersection( vertexAt( 1 ), incenter, vertexAt( 0 ), vertexAt( 2 ), out, lengthTolerance );
QgsGeometryUtils::segmentIntersection( vertexAt( 1 ), incenter, vertexAt( 0 ), vertexAt( 2 ), out, intersection, lengthTolerance );
bis2.setPoints( QgsPointSequence() << vertexAt( 1 ) << out );

QgsGeometryUtils::segmentIntersection( vertexAt( 2 ), incenter, vertexAt( 0 ), vertexAt( 1 ), out, lengthTolerance );
QgsGeometryUtils::segmentIntersection( vertexAt( 2 ), incenter, vertexAt( 0 ), vertexAt( 1 ), out, intersection, lengthTolerance );
bis3.setPoints( QgsPointSequence() << vertexAt( 2 ) << out );

bis.append( bis1 );
Expand All @@ -529,7 +530,8 @@ QgsPoint QgsTriangle::orthocenter( double lengthTolerance ) const
return QgsPoint();
QVector<QgsLineString> alt = altitudes();
QgsPoint ortho;
QgsGeometryUtils::segmentIntersection( alt.at( 0 ).pointN( 0 ), alt.at( 0 ).pointN( 1 ), alt.at( 1 ).pointN( 0 ), alt.at( 1 ).pointN( 1 ), ortho, lengthTolerance );
bool intersection;
QgsGeometryUtils::segmentIntersection( alt.at( 0 ).pointN( 0 ), alt.at( 0 ).pointN( 1 ), alt.at( 1 ).pointN( 0 ), alt.at( 1 ).pointN( 1 ), ortho, intersection, lengthTolerance );

return ortho;
}
Expand Down
77 changes: 77 additions & 0 deletions tests/src/core/testqgsgeometryutils.cpp
View file
Expand Up @@ -54,6 +54,7 @@ class TestQgsGeometryUtils: public QObject
void testCoefficients();
void testPerpendicularSegment();
void testClosestPoint();
void testSegmentIntersection();
};


Expand Down Expand Up @@ -647,5 +648,81 @@ void TestQgsGeometryUtils::testClosestPoint()
QGSCOMPARENEAR( pt4.m(), 1, 0.0001 );
}

void TestQgsGeometryUtils::testSegmentIntersection()
{
const double epsilon = 1e-8;
bool intersection, isIntersect;
QgsPoint inter;
// parallel
intersection = QgsGeometryUtils::segmentIntersection( QgsPoint( 0, 0 ), QgsPoint( 0, 1 ), QgsPoint( 1, 1 ), QgsPoint( 1, 0 ), inter, isIntersect, epsilon );
QVERIFY( !intersection );
QVERIFY( !isIntersect );
QVERIFY( inter == QgsPoint() );
inter = QgsPoint();
intersection = QgsGeometryUtils::segmentIntersection( QgsPoint( 0, 0 ), QgsPoint( 0, 1 ), QgsPoint( 1, 1 ), QgsPoint( 1, 0 ), inter, isIntersect, epsilon, true );
QVERIFY( !intersection );
QVERIFY( !isIntersect );
QVERIFY( inter == QgsPoint() );
inter = QgsPoint();
intersection = QgsGeometryUtils::segmentIntersection( QgsPoint( 0, 0 ), QgsPoint( 1, 1 ), QgsPoint( 0, 1 ), QgsPoint( 1, 2 ), inter, isIntersect, epsilon );
QVERIFY( !intersection );
QVERIFY( !isIntersect );
QVERIFY( inter == QgsPoint() );
inter = QgsPoint();
intersection = QgsGeometryUtils::segmentIntersection( QgsPoint( 0, 0 ), QgsPoint( 5, 5 ), QgsPoint( 1, 1 ), QgsPoint( -1, -1 ), inter, isIntersect, epsilon );
QVERIFY( !intersection );
QVERIFY( !isIntersect );
QVERIFY( inter == QgsPoint() );
inter = QgsPoint();
intersection = QgsGeometryUtils::segmentIntersection( QgsPoint( 0, 0 ), QgsPoint( 5, 5 ), QgsPoint( 1, 1 ), QgsPoint( 0, 0 ), inter, isIntersect, epsilon );
QVERIFY( !intersection );
QVERIFY( !isIntersect );
QVERIFY( inter == QgsPoint() );
// contigus
inter = QgsPoint();
intersection = QgsGeometryUtils::segmentIntersection( QgsPoint( 0, 0 ), QgsPoint( 0, 5 ), QgsPoint( 0, 5 ), QgsPoint( 1, 5 ), inter, isIntersect, epsilon );
QVERIFY( !intersection );
QVERIFY( isIntersect );
QVERIFY( inter == QgsPoint( 0, 5 ) );
inter = QgsPoint();
intersection = QgsGeometryUtils::segmentIntersection( QgsPoint( 0, 0 ), QgsPoint( 0, 5 ), QgsPoint( 0, 5 ), QgsPoint( 1, 5 ), inter, isIntersect, epsilon, true );
QVERIFY( intersection );
QVERIFY( isIntersect );
QVERIFY( inter == QgsPoint( 0, 5 ) );
// colinear
inter = QgsPoint();
intersection = QgsGeometryUtils::segmentIntersection( QgsPoint( 0, 0 ), QgsPoint( 0, 5 ), QgsPoint( 0, 5 ), QgsPoint( 0, 6 ), inter, isIntersect, epsilon );
QVERIFY( !intersection );
QVERIFY( !isIntersect );
QVERIFY( inter == QgsPoint() );
inter = QgsPoint();
intersection = QgsGeometryUtils::segmentIntersection( QgsPoint( 0, 0 ), QgsPoint( 0, 5 ), QgsPoint( 0, 5 ), QgsPoint( 0, 6 ), inter, isIntersect, epsilon, true );
QVERIFY( !intersection );
QVERIFY( !isIntersect );
QVERIFY( inter == QgsPoint() );
// improper
inter = QgsPoint();
intersection = QgsGeometryUtils::segmentIntersection( QgsPoint( 0, 0 ), QgsPoint( 0, 5 ), QgsPoint( 0, 2 ), QgsPoint( 1, 5 ), inter, isIntersect, epsilon );
QVERIFY( !intersection );
QVERIFY( isIntersect );
QVERIFY( inter == QgsPoint( 0, 2 ) );
inter = QgsPoint();
intersection = QgsGeometryUtils::segmentIntersection( QgsPoint( 0, 0 ), QgsPoint( 0, 5 ), QgsPoint( 0, 5 ), QgsPoint( 1, 5 ), inter, isIntersect, epsilon, true );
QVERIFY( intersection );
QVERIFY( isIntersect );
QVERIFY( inter == QgsPoint( 0, 5 ) );
// normal
inter = QgsPoint();
intersection = QgsGeometryUtils::segmentIntersection( QgsPoint( 0, -5 ), QgsPoint( 0, 5 ), QgsPoint( 2, 0 ), QgsPoint( -1, 0 ), inter, isIntersect, epsilon );
QVERIFY( intersection );
QVERIFY( isIntersect );
QVERIFY( inter == QgsPoint( 0, 0 ) );
inter = QgsPoint();
intersection = QgsGeometryUtils::segmentIntersection( QgsPoint( 0, -5 ), QgsPoint( 0, 5 ), QgsPoint( 2, 0 ), QgsPoint( -1, 0 ), inter, isIntersect, epsilon, true );
QVERIFY( intersection );
QVERIFY( isIntersect );
QVERIFY( inter == QgsPoint( 0, 0 ) );
}

QGSTEST_MAIN( TestQgsGeometryUtils )
#include "testqgsgeometryutils.moc"

0 comments on commit 342985f

Please sign in to comment.