Add method to determine closest side of rectangle to a point

qgis · Mar 19, 2021 · 425f271 · 425f271
1 parent ba6d967
commit 425f271
Show file tree

Hide file tree

Showing 4 changed files with 162 additions and 0 deletions.
diff --git a/python/core/auto_generated/geometry/qgsgeometryutils.sip.in b/python/core/auto_generated/geometry/qgsgeometryutils.sip.in
@@ -498,6 +498,32 @@ Averages two angles, correctly handling negative angles and ensuring the result
 
 
 
+    static int closestSideOfRectangle( double right, double bottom, double left, double top, double x, double y );
+%Docstring
+Returns a number representing the closest side of a rectangle defined by /a right,
+``bottom``, ``left``, ``top`` to the point at (``x``, ``y``), where
+the point may be in ther interior of the rectangle or outside it.
+
+The returned value may be:
+
+1. Point is closest to top side of rectangle
+2. Point is located on the top-right diagonal of rectangle, equally close to the top and right sides
+3. Point is closest to right side of rectangle
+4. Point is located on the bottom-right diagonal of rectangle, equally close to the bottom and right sides
+5. Point is closest to bottom side of rectangle
+6. Point is located on the bottom-left diagonal of rectangle, equally close to the bottom and left sides
+7. Point is closest to left side of rectangle
+8. Point is located on the top-left diagonal of rectangle, equally close to the top and left sides
+
+.. note::
+
+   This method effectively partitions the space outside of the rectangle into Voronoi cells, so a point
+   to the top left of the rectangle may be assigned to the left or top sides based on its position relative
+   to the diagonal line extended from the rectangle's top-left corner.
+
+.. versionadded:: 3.20
+%End
+
     static QgsPoint midpoint( const QgsPoint &pt1, const QgsPoint &pt2 ) /HoldGIL/;
 %Docstring
 Returns a middle point between points pt1 and pt2.

diff --git a/src/core/geometry/qgsgeometryutils.cpp b/src/core/geometry/qgsgeometryutils.cpp
@@ -1402,6 +1402,83 @@ QStringList QgsGeometryUtils::wktGetChildBlocks( const QString &wkt, const QStri
   return blocks;
 }
 
+int QgsGeometryUtils::closestSideOfRectangle( double right, double bottom, double left, double top, double x, double y )
+{
+  // point outside rectangle
+  if ( x <= left && y <= bottom )
+  {
+    const double dx = left - x;
+    const double dy = bottom - y;
+    if ( qgsDoubleNear( dx, dy ) )
+      return 6;
+    else if ( dx < dy )
+      return 5;
+    else
+      return 7;
+  }
+  else if ( x >= right && y >= top )
+  {
+    const double dx = x - right;
+    const double dy = y - top;
+    if ( qgsDoubleNear( dx, dy ) )
+      return 2;
+    else if ( dx < dy )
+      return 1;
+    else
+      return 3;
+  }
+  else if ( x >= right && y <= bottom )
+  {
+    const double dx = x - right;
+    const double dy = bottom - y;
+    if ( qgsDoubleNear( dx, dy ) )
+      return 4;
+    else if ( dx < dy )
+      return 5;
+    else
+      return 3;
+  }
+  else if ( x <= left && y >= top )
+  {
+    const double dx = left - x;
+    const double dy = y - top;
+    if ( qgsDoubleNear( dx, dy ) )
+      return 8;
+    else if ( dx < dy )
+      return 1;
+    else
+      return 7;
+  }
+  else if ( x <= left )
+    return 7;
+  else if ( x >= right )
+    return 3;
+  else if ( y <= bottom )
+    return 5;
+  else if ( y >= top )
+    return 1;
+
+  // point is inside rectangle
+  const double smallestX = std::min( right - x, x - left );
+  const double smallestY = std::min( top - y, y - bottom );
+  if ( smallestX < smallestY )
+  {
+    // closer to left/right side
+    if ( right - x < x - left )
+      return 3; // closest to right side
+    else
+      return 7;
+  }
+  else
+  {
+    // closer to top/bottom side
+    if ( top - y < y - bottom )
+      return 1; // closest to top side
+    else
+      return 5;
+  }
+}
+
 QgsPoint QgsGeometryUtils::midpoint( const QgsPoint &pt1, const QgsPoint &pt2 )
 {
   QgsWkbTypes::Type pType( QgsWkbTypes::Point );

diff --git a/src/core/geometry/qgsgeometryutils.h b/src/core/geometry/qgsgeometryutils.h
@@ -547,6 +547,30 @@ class CORE_EXPORT QgsGeometryUtils
      */
     static QStringList wktGetChildBlocks( const QString &wkt, const QString &defaultType = QString() ) SIP_SKIP;
 
+    /**
+     * Returns a number representing the closest side of a rectangle defined by /a right,
+     * \a bottom, \a left, \a top to the point at (\a x, \a y), where
+     * the point may be in ther interior of the rectangle or outside it.
+     *
+     * The returned value may be:
+     *
+     * 1. Point is closest to top side of rectangle
+     * 2. Point is located on the top-right diagonal of rectangle, equally close to the top and right sides
+     * 3. Point is closest to right side of rectangle
+     * 4. Point is located on the bottom-right diagonal of rectangle, equally close to the bottom and right sides
+     * 5. Point is closest to bottom side of rectangle
+     * 6. Point is located on the bottom-left diagonal of rectangle, equally close to the bottom and left sides
+     * 7. Point is closest to left side of rectangle
+     * 8. Point is located on the top-left diagonal of rectangle, equally close to the top and left sides
+     *
+     * \note This method effectively partitions the space outside of the rectangle into Voronoi cells, so a point
+     * to the top left of the rectangle may be assigned to the left or top sides based on its position relative
+     * to the diagonal line extended from the rectangle's top-left corner.
+     *
+     * \since QGIS 3.20
+     */
+    static int closestSideOfRectangle( double right, double bottom, double left, double top, double x, double y );
+
     /**
      * Returns a middle point between points pt1 and pt2.
      * Z value is computed if one of this point have Z.

diff --git a/tests/src/core/testqgsgeometryutils.cpp b/tests/src/core/testqgsgeometryutils.cpp
@@ -84,6 +84,7 @@ class TestQgsGeometryUtils: public QObject
     void testBisector();
     void testAngleBisector();
     void testPerpendicularOffsetPoint();
+    void testClosestSideOfRectangle();
 };
 
 
@@ -1567,5 +1568,39 @@ void TestQgsGeometryUtils::testPerpendicularOffsetPoint()
   QGSCOMPARENEAR( y, 6.0, 10e-3 );
 }
 
+void TestQgsGeometryUtils::testClosestSideOfRectangle()
+{
+  // outside rect
+  QCOMPARE( QgsGeometryUtils::closestSideOfRectangle( 16, -20, 10, -18, 1, -19 ), 7 );
+
+  QCOMPARE( QgsGeometryUtils::closestSideOfRectangle( 16, -20, 10, -18, 1, -17 ), 7 );
+  QCOMPARE( QgsGeometryUtils::closestSideOfRectangle( 16, -20, 10, -18, 9, -17 ), 8 );
+  QCOMPARE( QgsGeometryUtils::closestSideOfRectangle( 16, -20, 10, -18, 9, -1 ), 1 );
+
+  QCOMPARE( QgsGeometryUtils::closestSideOfRectangle( 16, -20, 10, -18, 1, -21 ), 7 );
+  QCOMPARE( QgsGeometryUtils::closestSideOfRectangle( 16, -20, 10, -18, 9, -21 ), 6 );
+  QCOMPARE( QgsGeometryUtils::closestSideOfRectangle( 16, -20, 10, -18, 9, -22 ), 5 );
+
+  QCOMPARE( QgsGeometryUtils::closestSideOfRectangle( 16, -20, 10, -18, 14, -1 ), 1 );
+
+  QCOMPARE( QgsGeometryUtils::closestSideOfRectangle( 16, -20, 10, -18, 18, -1 ), 1 );
+  QCOMPARE( QgsGeometryUtils::closestSideOfRectangle( 16, -20, 10, -18, 17, -17 ), 2 );
+  QCOMPARE( QgsGeometryUtils::closestSideOfRectangle( 16, -20, 10, -18, 20, -17 ), 3 );
+
+  QCOMPARE( QgsGeometryUtils::closestSideOfRectangle( 16, -20, 10, -18, 18, -19 ), 3 );
+
+  QCOMPARE( QgsGeometryUtils::closestSideOfRectangle( 16, -20, 10, -18, 18, -21 ), 3 );
+  QCOMPARE( QgsGeometryUtils::closestSideOfRectangle( 16, -20, 10, -18, 17, -21 ), 4 );
+  QCOMPARE( QgsGeometryUtils::closestSideOfRectangle( 16, -20, 10, -18, 17, -25 ), 5 );
+
+  QCOMPARE( QgsGeometryUtils::closestSideOfRectangle( 16, -20, 10, -18, 14, -21 ), 5 );
+
+  // inside rect
+  QCOMPARE( QgsGeometryUtils::closestSideOfRectangle( 16, -20, 10, -18, 10.5, -19 ), 7 );
+  QCOMPARE( QgsGeometryUtils::closestSideOfRectangle( 16, -20, 10, -18, 16.5, -19 ), 3 );
+  QCOMPARE( QgsGeometryUtils::closestSideOfRectangle( 16, -20, 10, -18, 14, -18.5 ), 1 );
+  QCOMPARE( QgsGeometryUtils::closestSideOfRectangle( 16, -20, 10, -18, 14, -19.5 ), 5 );
+}
+
 QGSTEST_MAIN( TestQgsGeometryUtils )
 #include "testqgsgeometryutils.moc"