Add QgsRay2D class representing an infinite ray from a point in a dir…

…ection
qgis · Apr 23, 2018 · 6e6ddbb · 6e6ddbb
1 parent 8f1d1a3
commit 6e6ddbb
Show file tree

Hide file tree

Showing 4 changed files with 188 additions and 1 deletion.
diff --git a/src/core/geometry/qgsinternalgeometryengine.cpp b/src/core/geometry/qgsinternalgeometryengine.cpp
@@ -22,7 +22,7 @@
 #include "qgsmulticurve.h"
 #include "qgsgeometry.h"
 #include "qgsgeometryutils.h"
-
+#include "qgslinesegment.h"
 
 #include <QTransform>
 #include <memory>
@@ -710,3 +710,53 @@ QgsGeometry QgsInternalGeometryEngine::densifyByDistance( double distance ) cons
     return QgsGeometry( densifyGeometry( mGeometry, -1, distance ) );
   }
 }
+
+bool QgsRay2D::intersects( const QgsLineSegment2D &segment, QgsPointXY &intersectPoint ) const
+{
+  const QgsVector ao = origin - segment.start();
+  const QgsVector ab = segment.end() - segment.start();
+  const double det = ab.crossProduct( direction );
+  if ( qgsDoubleNear( det, 0.0 ) )
+  {
+    const int abo = segment.pointLeftOfLine( origin );
+    if ( abo != 0 )
+    {
+      return false;
+    }
+    else
+    {
+      const double distA = ao * direction;
+      const double distB = ( origin - segment.end() ) * direction;
+
+      if ( distA > 0 && distB > 0 )
+      {
+        return false;
+      }
+      else
+      {
+        if ( ( distA > 0 ) != ( distB > 0 ) )
+          intersectPoint = origin;
+        else if ( distA > distB ) // at this point, both distances are negative
+          intersectPoint = segment.start(); // hence the nearest point is A
+        else
+          intersectPoint = segment.end();
+        return true;
+      }
+    }
+  }
+  else
+  {
+    const double u = ao.crossProduct( direction ) / det;
+    if ( u < 0.0 || 1.0 < u )
+    {
+      return false;
+    }
+    else
+    {
+      const double t = -ab.crossProduct( ao ) / det;
+      intersectPoint = origin + direction * t;
+      return qgsDoubleNear( t, 0.0 ) || t > 0;
+    }
+  }
+}
+
diff --git a/src/core/geometry/qgsinternalgeometryengine.h b/src/core/geometry/qgsinternalgeometryengine.h
@@ -18,8 +18,12 @@
 
 #define SIP_NO_FILE
 
+#include "qgspointxy.h"
+
 class QgsGeometry;
 class QgsAbstractGeometry;
+class QgsLineString;
+class QgsLineSegment2D;
 
 /**
  * \ingroup core
@@ -102,4 +106,37 @@ class QgsInternalGeometryEngine
     const QgsAbstractGeometry *mGeometry = nullptr;
 };
 
+/**
+ * A 2D ray which extends from an origin point to an infinite distance in a given direction.
+ * \ingroup core
+ * \since QGIS 3.2
+ */
+class CORE_EXPORT QgsRay2D
+{
+  public:
+
+    /**
+     * Constructor for a ray starting at the given \a origin and extending an infinite distance
+     * in the specified \a direction.
+     */
+    QgsRay2D( const QgsPointXY &origin, QgsVector direction )
+      : origin( origin )
+      , direction( direction )
+    {}
+
+    /**
+     * Finds the closest intersection point of the ray and a line \a segment.
+     *
+     * If found, the intersection point will be stored in \a intersectPoint.
+     *
+     * Returns true if the ray intersects the line segment.
+     */
+    bool intersects( const QgsLineSegment2D &segment, QgsPointXY &intersectPoint ) const;
+
+  private:
+
+    QgsPointXY origin;
+    QgsVector direction;
+};
+
 #endif // QGSINTERNALGEOMETRYENGINE_H
diff --git a/tests/src/core/CMakeLists.txt b/tests/src/core/CMakeLists.txt
@@ -107,6 +107,7 @@ SET(TESTS
  testqgsgraduatedsymbolrenderer.cpp
  testqgshistogram.cpp
  testqgsimageoperation.cpp
+ testqgsinternalgeometryengine.cpp
  testqgsinvertedpolygonrenderer.cpp
  testqgsjsonutils.cpp
  testqgslabelingengine.cpp

diff --git a/tests/src/core/testqgsinternalgeometryengine.cpp b/tests/src/core/testqgsinternalgeometryengine.cpp
@@ -0,0 +1,99 @@
+/***************************************************************************
+     testqgsinternalgeometryengine.cpp
+     --------------------------------------
+    Date                 : April 2018
+    Copyright            : (C) 2018 by Nyall Dawson
+    Email                : nyall dot dawson at gmail dot com
+ ***************************************************************************
+ *                                                                         *
+ *   This program is free software; you can redistribute it and/or modify  *
+ *   it under the terms of the GNU General Public License as published by  *
+ *   the Free Software Foundation; either version 2 of the License, or     *
+ *   (at your option) any later version.                                   *
+ *                                                                         *
+ ***************************************************************************/
+#include "qgstest.h"
+
+//qgis includes...
+#include "qgsinternalgeometryengine.h"
+#include "qgslinesegment.h"
+
+class TestQgsInternalGeometryEngine : public QObject
+{
+    Q_OBJECT
+
+  public:
+
+  private slots:
+    void initTestCase();// will be called before the first testfunction is executed.
+    void cleanupTestCase();// will be called after the last testfunction was executed.
+    void init();// will be called before each testfunction is executed.
+    void cleanup();// will be called after every testfunction.
+    void ray();
+
+};
+
+void TestQgsInternalGeometryEngine::initTestCase()
+{
+  // Runs once before any tests are run
+  // init QGIS's paths - true means that all path will be inited from prefix
+  QgsApplication::init();
+  QgsApplication::initQgis();
+}
+
+
+void TestQgsInternalGeometryEngine::cleanupTestCase()
+{
+  QgsApplication::exitQgis();
+}
+
+void TestQgsInternalGeometryEngine::init()
+{
+}
+
+void TestQgsInternalGeometryEngine::cleanup()
+{
+}
+
+void TestQgsInternalGeometryEngine::ray()
+{
+  QgsRay2D ray( QgsPointXY( 3, 5 ), QgsVector( -1, 1 ) );
+  QgsPointXY intersect;
+  QVERIFY( !ray.intersects( QgsLineSegment2D( QgsPointXY( 4, -1 ), QgsPointXY( 5, 15 ) ), intersect ) );
+  QVERIFY( !ray.intersects( QgsLineSegment2D( QgsPointXY( 5, 15 ), QgsPointXY( 4, -1 ) ), intersect ) );
+
+  QVERIFY( ray.intersects( QgsLineSegment2D( QgsPointXY( 5, 15 ), QgsPointXY( 3, 5 ) ), intersect ) );
+  QCOMPARE( intersect.x(), 3.0 );
+  QCOMPARE( intersect.y(), 5.0 );
+  QVERIFY( ray.intersects( QgsLineSegment2D( QgsPointXY( 3, 5 ), QgsPointXY( 5, 15 ) ), intersect ) );
+  QCOMPARE( intersect.x(), 3.0 );
+  QCOMPARE( intersect.y(), 5.0 );
+  QVERIFY( ray.intersects( QgsLineSegment2D( QgsPointXY( 3, 1 ), QgsPointXY( 3, 6 ) ), intersect ) );
+  QCOMPARE( intersect.x(), 3.0 );
+  QCOMPARE( intersect.y(), 5.0 );
+  QVERIFY( !ray.intersects( QgsLineSegment2D( QgsPointXY( 4, 1 ), QgsPointXY( 4, 6 ) ), intersect ) );
+  QVERIFY( ray.intersects( QgsLineSegment2D( QgsPointXY( 2, 1 ), QgsPointXY( 2, 6 ) ), intersect ) );
+  QCOMPARE( intersect.x(), 2.0 );
+  QCOMPARE( intersect.y(), 6.0 );
+  QVERIFY( ray.intersects( QgsLineSegment2D( QgsPointXY( 2, 1 ), QgsPointXY( 2, 16 ) ), intersect ) );
+  QCOMPARE( intersect.x(), 2.0 );
+  QCOMPARE( intersect.y(), 6.0 );
+  QVERIFY( !ray.intersects( QgsLineSegment2D( QgsPointXY( 1, 1 ), QgsPointXY( 1, 6 ) ), intersect ) );
+  QVERIFY( ray.intersects( QgsLineSegment2D( QgsPointXY( 1, 1 ), QgsPointXY( 1, 26 ) ), intersect ) );
+  QCOMPARE( intersect.x(), 1.0 );
+  QCOMPARE( intersect.y(), 7.0 );
+  QVERIFY( ray.intersects( QgsLineSegment2D( QgsPointXY( 4, 4 ), QgsPointXY( 2, 6 ) ), intersect ) );
+  QCOMPARE( intersect.x(), 3.0 );
+  QCOMPARE( intersect.y(), 5.0 );
+  QVERIFY( !ray.intersects( QgsLineSegment2D( QgsPointXY( 14, 14 ), QgsPointXY( 12, 16 ) ), intersect ) );
+  QVERIFY( ray.intersects( QgsLineSegment2D( QgsPointXY( 2, 6 ), QgsPointXY( 1, 7 ) ), intersect ) );
+  QCOMPARE( intersect.x(), 2.0 );
+  QCOMPARE( intersect.y(), 6.0 );
+  QVERIFY( ray.intersects( QgsLineSegment2D( QgsPointXY( 1, 7 ), QgsPointXY( 2, 6 ) ), intersect ) );
+  QCOMPARE( intersect.x(), 2.0 );
+  QCOMPARE( intersect.y(), 6.0 );
+
+}
+
+QGSTEST_MAIN( TestQgsInternalGeometryEngine )
+#include "testqgsinternalgeometryengine.moc"