Skip to content

Commit

Permalink
Add class for comparing angles to points in a clockwise fashion
Browse files Browse the repository at this point in the history
  • Loading branch information
@nyalldawson
nyalldawson committed Apr 23, 2018
1 parent fa9f62f commit cd3b976
Show file tree
Hide file tree
Showing 3 changed files with 148 additions and 14 deletions.
40 changes: 40 additions & 0 deletions src/core/geometry/qgsinternalgeometryengine.cpp
View file
Expand Up @@ -711,6 +711,7 @@ QgsGeometry QgsInternalGeometryEngine::densifyByDistance( double distance ) cons
}
}

///@cond PRIVATE
//
// QgsLineSegmentDistanceComparer
//
Expand Down Expand Up @@ -764,6 +765,45 @@ bool QgsLineSegmentDistanceComparer::operator()( QgsLineSegment2D ab, QgsLineSeg
}
}

//
// QgsClockwiseAngleComparer
//

bool QgsClockwiseAngleComparer::operator()( const QgsPointXY &a, const QgsPointXY &b ) const
{
const bool aIsLeft = a.x() < mVertex.x();
const bool bIsLeft = b.x() < mVertex.x();
if ( aIsLeft != bIsLeft )
return bIsLeft;

if ( qgsDoubleNear( a.x(), mVertex.x() ) && qgsDoubleNear( b.x(), mVertex.x() ) )
{
if ( a.y() >= mVertex.y() || b.y() >= mVertex.y() )
{
return b.y() < a.y();
}
else
{
return a.y() < b.y();
}
}
else
{
const QgsVector oa = a - mVertex;
const QgsVector ob = b - mVertex;
const double det = oa.crossProduct( ob );
if ( qgsDoubleNear( det, 0.0 ) )
{
return oa.lengthSquared() < ob.lengthSquared();
}
else
{
return det < 0;
}
}
}

///@endcond PRIVATE

//
// QgsRay2D
Expand Down
25 changes: 25 additions & 0 deletions src/core/geometry/qgsinternalgeometryengine.h
View file
Expand Up @@ -149,6 +149,8 @@ class CORE_EXPORT QgsRay2D
* Assumes: (1) the line segments are intersected by some ray from the origin
* (2) the line segments do not intersect except at their endpoints
* (3) no line segment is collinear with the origin
* \ingroup core
* \since QGIS 3.2
*/
class CORE_EXPORT QgsLineSegmentDistanceComparer
{
Expand Down Expand Up @@ -177,6 +179,29 @@ class CORE_EXPORT QgsLineSegmentDistanceComparer

};


// adapted for QGIS geometry classes from original work at https://github.com/trylock/visibility by trylock

/**
* Compares angles from an origin to points clockwise, starting at the positive y-axis.
* \ingroup core
* \since QGIS 3.2
*/
class CORE_EXPORT QgsClockwiseAngleComparer
{
public:
explicit QgsClockwiseAngleComparer( const QgsPointXY &origin )
: mVertex( origin )
{}

bool operator()( const QgsPointXY &a, const QgsPointXY &b ) const;

private:

QgsPointXY mVertex;

};

///@endcond PRIVATE

#endif // QGSINTERNALGEOMETRYENGINE_H
97 changes: 83 additions & 14 deletions tests/src/core/testqgsinternalgeometryengine.cpp
View file
Expand Up @@ -30,7 +30,9 @@ class TestQgsInternalGeometryEngine : public QObject
void init();// will be called before each testfunction is executed.
void cleanup();// will be called after every testfunction.
void ray();
void lineSegmentDistanceComparer();
void testLineSegmentDistanceComparer_data();
void testLineSegmentDistanceComparer();
void clockwiseAngleComparer();

};

Expand Down Expand Up @@ -94,24 +96,69 @@ void TestQgsInternalGeometryEngine::ray()
QCOMPARE( intersect.x(), 2.0 );
QCOMPARE( intersect.y(), 6.0 );

ray = QgsRay2D( QgsPointXY( 0, 0 ), QgsVector( 1, 0 ) );
QVERIFY( !ray.intersects( QgsLineSegment2D( QgsPointXY( -1, 1 ), QgsPointXY( -1, -1 ) ), intersect ) );
QVERIFY( !ray.intersects( QgsLineSegment2D( QgsPointXY( -1e-3, 1 ), QgsPointXY( -1e-3, -1 ) ), intersect ) );
QVERIFY( !ray.intersects( QgsLineSegment2D( QgsPointXY( -2, 0 ), QgsPointXY( -1, 0 ) ), intersect ) );
QVERIFY( ray.intersects( QgsLineSegment2D( QgsPointXY( 0, 1 ), QgsPointXY( 0, -1 ) ), intersect ) );
QCOMPARE( intersect.x(), 0.0 );
QCOMPARE( intersect.y(), 0.0 );
QVERIFY( ray.intersects( QgsLineSegment2D( QgsPointXY( -1, 0 ), QgsPointXY( 0, 0 ) ), intersect ) );
QCOMPARE( intersect.x(), 0.0 );
QCOMPARE( intersect.y(), 0.0 );
QVERIFY( ray.intersects( QgsLineSegment2D( QgsPointXY( 0, 0 ), QgsPointXY( -1, 0 ) ), intersect ) );
QCOMPARE( intersect.x(), 0.0 );
QCOMPARE( intersect.y(), 0.0 );
QVERIFY( ray.intersects( QgsLineSegment2D( QgsPointXY( 2, 1 ), QgsPointXY( 2, -1 ) ), intersect ) );
QCOMPARE( intersect.x(), 2.0 );
QCOMPARE( intersect.y(), 0.0 );
QVERIFY( ray.intersects( QgsLineSegment2D( QgsPointXY( 2, 0 ), QgsPointXY( 3, 0 ) ), intersect ) );
QCOMPARE( intersect.x(), 2.0 );
QCOMPARE( intersect.y(), 0.0 );
QVERIFY( ray.intersects( QgsLineSegment2D( QgsPointXY( 3, 0 ), QgsPointXY( 2, 0 ) ), intersect ) );
QCOMPARE( intersect.x(), 2.0 );
QCOMPARE( intersect.y(), 0.0 );
QVERIFY( ray.intersects( QgsLineSegment2D( QgsPointXY( 1, 0 ), QgsPointXY( 1, -1 ) ), intersect ) );
QCOMPARE( intersect.x(), 1.0 );
QCOMPARE( intersect.y(), 0.0 );
}

void TestQgsInternalGeometryEngine::lineSegmentDistanceComparer()
void TestQgsInternalGeometryEngine::testLineSegmentDistanceComparer_data()
{
QTest::addColumn<QgsPointXY>( "origin" );
QTest::addColumn<QgsPointXY>( "a" );
QTest::addColumn<QgsPointXY>( "b" );
QTest::addColumn<QgsPointXY>( "c" );
QTest::addColumn<QgsPointXY>( "d" );

QTest::newRow( "a" ) << QgsPointXY( 3, 5 ) << QgsPointXY( 1, 2 ) << QgsPointXY( 3, 4 ) << QgsPointXY( 11, 2 ) << QgsPointXY( 13, 4 );
QTest::newRow( "b" ) << QgsPointXY( 0, 0 ) << QgsPointXY( 1, 1 ) << QgsPointXY( 1, -1 ) << QgsPointXY( 2, 1 ) << QgsPointXY( 2, -1 );
QTest::newRow( "b" ) << QgsPointXY( 0, 0 ) << QgsPointXY( 1, 1 ) << QgsPointXY( 1, -1 ) << QgsPointXY( 2, 2 ) << QgsPointXY( 2, 3 );
QTest::newRow( "b" ) << QgsPointXY( 0, 0 ) << QgsPointXY( 2, 0 ) << QgsPointXY( 1, 1 ) << QgsPointXY( 2, 1 ) << QgsPointXY( 2, 0 );
QTest::newRow( "b" ) << QgsPointXY( 0, 0 ) << QgsPointXY( 2, 1 ) << QgsPointXY( 2, 0 ) << QgsPointXY( 2, 0 ) << QgsPointXY( 3, 1 );
}

void TestQgsInternalGeometryEngine::testLineSegmentDistanceComparer()
{
QFETCH( QgsPointXY, origin );
QFETCH( QgsPointXY, a );
QFETCH( QgsPointXY, b );
QFETCH( QgsPointXY, c );
QFETCH( QgsPointXY, d );

QgsLineSegmentDistanceComparer cmp( origin );
QVERIFY( cmp( QgsLineSegment2D( a, b ), QgsLineSegment2D( c, d ) ) );
QVERIFY( cmp( QgsLineSegment2D( b, a ), QgsLineSegment2D( c, d ) ) );
QVERIFY( cmp( QgsLineSegment2D( a, b ), QgsLineSegment2D( d, c ) ) );
QVERIFY( cmp( QgsLineSegment2D( b, a ), QgsLineSegment2D( d, c ) ) );

QVERIFY( !cmp( QgsLineSegment2D( c, d ), QgsLineSegment2D( a, b ) ) );
QVERIFY( !cmp( QgsLineSegment2D( d, c ), QgsLineSegment2D( a, b ) ) );
QVERIFY( !cmp( QgsLineSegment2D( c, d ), QgsLineSegment2D( b, a ) ) );
QVERIFY( !cmp( QgsLineSegment2D( d, c ), QgsLineSegment2D( b, a ) ) );

QgsLineSegmentDistanceComparer comp( QgsPointXY( 3, 5 ) );

QVERIFY( comp( QgsLineSegment2D( QgsPointXY( 1, 2 ), QgsPointXY( 3, 4 ) ),
QgsLineSegment2D( QgsPointXY( 11, 2 ), QgsPointXY( 13, 4 ) ) ) );
QVERIFY( comp( QgsLineSegment2D( QgsPointXY( 1, 2 ), QgsPointXY( 3, 4 ) ),
QgsLineSegment2D( QgsPointXY( 13, 4 ), QgsPointXY( 11, 2 ) ) ) );
QVERIFY( comp( QgsLineSegment2D( QgsPointXY( 1, 2 ), QgsPointXY( 3, 4 ) ),
QgsLineSegment2D( QgsPointXY( -13, 4 ), QgsPointXY( -11, 2 ) ) ) );
QVERIFY( comp( QgsLineSegment2D( QgsPointXY( 1, 2 ), QgsPointXY( 3, 4 ) ),
QgsLineSegment2D( QgsPointXY( -13, -4 ), QgsPointXY( -11, 2 ) ) ) );
QVERIFY( comp( QgsLineSegment2D( QgsPointXY( 1, 2 ), QgsPointXY( 3, 4 ) ),
QgsLineSegment2D( QgsPointXY( 11, 2 ), QgsPointXY( 13, 4 ) ) ) );
QVERIFY( !comp( QgsLineSegment2D( QgsPointXY( 11, 2 ), QgsPointXY( 13, 4 ) ),
QgsLineSegment2D( QgsPointXY( 1, 2 ), QgsPointXY( 3, 4 ) ) ) );
QVERIFY( !comp( QgsLineSegment2D( QgsPointXY( 1, 2 ), QgsPointXY( 3, 4 ) ),
QgsLineSegment2D( QgsPointXY( 5, 6 ), QgsPointXY( 8, 9 ) ) ) );
QVERIFY( comp( QgsLineSegment2D( QgsPointXY( 5, 6 ), QgsPointXY( 8, 9 ) ),
Expand All @@ -124,5 +171,27 @@ void TestQgsInternalGeometryEngine::lineSegmentDistanceComparer()
QgsLineSegment2D( QgsPointXY( 8, 9 ), QgsPointXY( 15, 16 ) ) ) );
}

void TestQgsInternalGeometryEngine::clockwiseAngleComparer()
{
QgsClockwiseAngleComparer cmp( QgsPointXY( 0, 0 ) );
QVERIFY( cmp( QgsPointXY( 0, 1 ), QgsPointXY( 1, 1 ) ) );
QVERIFY( !cmp( QgsPointXY( 1, 1 ), QgsPointXY( 0, 1 ) ) );

QVERIFY( cmp( QgsPointXY( 1, 1 ), QgsPointXY( 1, -1 ) ) );
QVERIFY( !cmp( QgsPointXY( 1, -1 ), QgsPointXY( 1, 1 ) ) );

QVERIFY( cmp( QgsPointXY( 1, 0 ), QgsPointXY( -1, -1 ) ) );
QVERIFY( !cmp( QgsPointXY( -1, -1 ), QgsPointXY( 1, 0 ) ) );

QVERIFY( cmp( QgsPointXY( 0, 1 ), QgsPointXY( 0, -1 ) ) );
QVERIFY( !cmp( QgsPointXY( 0, -1 ), QgsPointXY( 0, 1 ) ) );

QVERIFY( cmp( QgsPointXY( 1, 0 ), QgsPointXY( 2, 0 ) ) );
QVERIFY( !cmp( QgsPointXY( 2, 0 ), QgsPointXY( 1, 0 ) ) );

QVERIFY( !cmp( QgsPointXY( 1, 0 ), QgsPointXY( 1, 0 ) ) );
QVERIFY( !cmp( QgsPointXY( 0, 0 ), QgsPointXY( 0, 0 ) ) );
}

QGSTEST_MAIN( TestQgsInternalGeometryEngine )
#include "testqgsinternalgeometryengine.moc"

0 comments on commit cd3b976

Please sign in to comment.