Skip to content

Commit 9c4375b

Browse files
committedApr 23, 2021
Add QgsGeometry::isAxisParallelRectangle for checking whether
a geometry is a axis-parallel rectangle Credit to @stefanuhrig
1 parent 6470771 commit 9c4375b

File tree

6 files changed

+226
-0
lines changed

6 files changed

+226
-0
lines changed
 

‎python/core/auto_generated/geometry/qgsgeometry.sip.in

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -353,6 +353,21 @@ Uses GEOS library for the test.
353353
for checking anomalies in polygon geometries one can use :py:func:`~QgsGeometry.isGeosValid`.
354354

355355
.. versionadded:: 3.0
356+
%End
357+
358+
bool isAxisParallelRectangle( double maximumDeviation, bool simpleRectanglesOnly = false ) const;
359+
%Docstring
360+
Returns ``True`` if the geometry is a polygon that is almost an axis-parallel rectangle.
361+
362+
The ``maximumDeviation`` argument specifes the maximum angle (in degrees) that the polygon edges
363+
are allowed to deviate from axis parallel lines.
364+
365+
By default the check will permit polygons with more than 4 edges, so long as the overall shape of
366+
the polygon is an axis-parallel rectangle (i.e. it is tolerant to rectangles with additional vertices
367+
added along the rectangle sides). If ``simpleRectanglesOnly`` is set to ``True`` then the method will
368+
only return ``True`` if the geometry is a simple rectangle consisting of 4 edges.
369+
370+
.. versionadded:: 3.20
356371
%End
357372

358373
double area() const;

‎src/core/geometry/qgsgeometry.cpp

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2737,6 +2737,15 @@ bool QgsGeometry::isSimple() const
27372737
return geos.isSimple( &mLastError );
27382738
}
27392739

2740+
bool QgsGeometry::isAxisParallelRectangle( double maximumDeviation, bool simpleRectanglesOnly ) const
2741+
{
2742+
if ( !d->geometry )
2743+
return false;
2744+
2745+
QgsInternalGeometryEngine engine( *this );
2746+
return engine.isAxisParallelRectangle( maximumDeviation, simpleRectanglesOnly );
2747+
}
2748+
27402749
bool QgsGeometry::isGeosEqual( const QgsGeometry &g ) const
27412750
{
27422751
if ( !d->geometry || !g.d->geometry )

‎src/core/geometry/qgsgeometry.h

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -389,6 +389,21 @@ class CORE_EXPORT QgsGeometry
389389
*/
390390
bool isSimple() const;
391391

392+
/**
393+
* Returns TRUE if the geometry is a polygon that is almost an axis-parallel rectangle.
394+
*
395+
* The \a maximumDeviation argument specifes the maximum angle (in degrees) that the polygon edges
396+
* are allowed to deviate from axis parallel lines.
397+
*
398+
* By default the check will permit polygons with more than 4 edges, so long as the overall shape of
399+
* the polygon is an axis-parallel rectangle (i.e. it is tolerant to rectangles with additional vertices
400+
* added along the rectangle sides). If \a simpleRectanglesOnly is set to TRUE then the method will
401+
* only return TRUE if the geometry is a simple rectangle consisting of 4 edges.
402+
*
403+
* \since QGIS 3.20
404+
*/
405+
bool isAxisParallelRectangle( double maximumDeviation, bool simpleRectanglesOnly = false ) const;
406+
392407
/**
393408
* Returns the planar, 2-dimensional area of the geometry.
394409
*

‎src/core/geometry/qgsinternalgeometryengine.cpp

Lines changed: 133 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -46,6 +46,139 @@ QString QgsInternalGeometryEngine::lastError() const
4646
return mLastError;
4747
}
4848

49+
50+
enum class Direction
51+
{
52+
Up,
53+
Right,
54+
Down,
55+
Left,
56+
None
57+
};
58+
59+
/**
60+
* Determines the direction of an edge from p1 to p2. maxDev is the tangent of
61+
* the maximum allowed edge deviation angle. If the edge deviates more than
62+
* the allowed angle, Direction::None will be returned.
63+
*/
64+
Direction getEdgeDirection( const QgsPoint &p1, const QgsPoint &p2, double maxDev )
65+
{
66+
double dx = p2.x() - p1.x();
67+
double dy = p2.y() - p1.y();
68+
if ( ( dx == 0.0 ) && ( dy == 0.0 ) )
69+
return Direction::None;
70+
if ( fabs( dx ) >= fabs( dy ) )
71+
{
72+
double dev = fabs( dy ) / fabs( dx );
73+
if ( dev > maxDev )
74+
return Direction::None;
75+
return dx > 0.0 ? Direction::Right : Direction::Left;
76+
}
77+
else
78+
{
79+
double dev = fabs( dx ) / fabs( dy );
80+
if ( dev > maxDev )
81+
return Direction::None;
82+
return dy > 0.0 ? Direction::Up : Direction::Down;
83+
}
84+
}
85+
86+
/**
87+
* Checks whether the polygon consists of four nearly axis-parallel sides. All
88+
* consecutive edges having the same direction are considered to belong to the
89+
* same side.
90+
*/
91+
std::pair<bool, std::array<Direction, 4>> getEdgeDirections( const QgsPolygon *g, double maxDev )
92+
{
93+
std::pair<bool, std::array<Direction, 4>> ret = { false, { Direction::None, Direction::None, Direction::None, Direction::None } };
94+
// The polygon might start in the middle of a side. Hence, we need a fifth
95+
// direction to record the beginning of the side when we went around the
96+
// polygon.
97+
std::array<Direction, 5> dirs;
98+
99+
int idx = 0;
100+
QgsAbstractGeometry::vertex_iterator previous = g->vertices_begin();
101+
QgsAbstractGeometry::vertex_iterator current = previous;
102+
++current;
103+
QgsAbstractGeometry::vertex_iterator end = g->vertices_end();
104+
while ( current != end )
105+
{
106+
Direction dir = getEdgeDirection( *previous, *current, maxDev );
107+
if ( dir == Direction::None )
108+
return ret;
109+
if ( idx == 0 )
110+
{
111+
dirs[0] = dir;
112+
++idx;
113+
}
114+
else if ( dir != dirs[idx - 1] )
115+
{
116+
if ( idx == 5 )
117+
return ret;
118+
dirs[idx] = dir;
119+
++idx;
120+
}
121+
previous = current;
122+
++current;
123+
}
124+
ret.first = ( idx == 5 ) ? ( dirs[0] == dirs[4] ) : ( idx == 4 );
125+
std::copy( dirs.begin(), dirs.begin() + 4, ret.second.begin() );
126+
return ret;
127+
}
128+
129+
bool matchesOrientation( std::array<Direction, 4> dirs, std::array<Direction, 4> oriented )
130+
{
131+
int idx = std::find( oriented.begin(), oriented.end(), dirs[0] ) - oriented.begin();
132+
for ( int i = 1; i < 4; ++i )
133+
{
134+
if ( dirs[i] != oriented[( idx + i ) % 4] )
135+
return false;
136+
}
137+
return true;
138+
}
139+
140+
/**
141+
* Checks whether the 4 directions in dirs make up a clockwise rectangle.
142+
*/
143+
bool isClockwise( std::array<Direction, 4> dirs )
144+
{
145+
const std::array<Direction, 4> cwdirs = { Direction::Up, Direction::Right, Direction::Down, Direction::Left };
146+
return matchesOrientation( dirs, cwdirs );
147+
}
148+
149+
/**
150+
* Checks whether the 4 directions in dirs make up a counter-clockwise
151+
* rectangle.
152+
*/
153+
bool isCounterClockwise( std::array<Direction, 4> dirs )
154+
{
155+
const std::array<Direction, 4> ccwdirs = { Direction::Right, Direction::Up, Direction::Left, Direction::Down };
156+
return matchesOrientation( dirs, ccwdirs );
157+
}
158+
159+
160+
bool QgsInternalGeometryEngine::isAxisParallelRectangle( double maximumDeviation, bool simpleRectanglesOnly ) const
161+
{
162+
if ( QgsWkbTypes::flatType( mGeometry->wkbType() ) != QgsWkbTypes::Polygon )
163+
return false;
164+
165+
const QgsPolygon *polygon = qgsgeometry_cast< const QgsPolygon * >( mGeometry );
166+
if ( !polygon->exteriorRing() || polygon->numInteriorRings() > 0 )
167+
return false;
168+
169+
const int vertexCount = polygon->exteriorRing()->numPoints();
170+
if ( vertexCount < 4 )
171+
return false;
172+
else if ( simpleRectanglesOnly && ( vertexCount != 5 || !polygon->exteriorRing()->isClosed() ) )
173+
return false;
174+
175+
bool found4Dirs;
176+
std::array<Direction, 4> dirs;
177+
std::tie( found4Dirs, dirs ) = getEdgeDirections( polygon, std::tan( maximumDeviation * M_PI / 180 ) );
178+
179+
return found4Dirs && ( isCounterClockwise( dirs ) || isClockwise( dirs ) );
180+
}
181+
49182
/***************************************************************************
50183
* This class is considered CRITICAL and any change MUST be accompanied with
51184
* full unit tests.

‎src/core/geometry/qgsinternalgeometryengine.h

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -56,6 +56,21 @@ class QgsInternalGeometryEngine
5656
*/
5757
QString lastError() const;
5858

59+
/**
60+
* Returns TRUE if the geometry is a polygon that is almost an axis-parallel rectangle.
61+
*
62+
* The \a maximumDeviation argument specifes the maximum angle (in degrees) that the polygon edges
63+
* are allowed to deviate from axis parallel lines.
64+
*
65+
* By default the check will permit polygons with more than 4 edges, so long as the overall shape of
66+
* the polygon is an axis-parallel rectangle (i.e. it is tolerant to rectangles with additional vertices
67+
* added along the rectangle sides). If \a simpleRectanglesOnly is set to TRUE then the method will
68+
* only return TRUE if the geometry is a simple rectangle consisting of 4 edges.
69+
*
70+
* \since QGIS 3.20
71+
*/
72+
bool isAxisParallelRectangle( double maximumDeviation, bool simpleRectanglesOnly = false ) const;
73+
5974
/**
6075
* Will extrude a line or (segmentized) curve by a given offset and return a polygon
6176
* representation of it.

‎tests/src/python/test_qgsgeometry.py

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -6011,6 +6011,45 @@ def testGeosCrash(self):
60116011
# test we don't crash when geos returns a point geometry with no points
60126012
QgsGeometry.fromWkt('Polygon ((0 0, 1 1, 1 0, 0 0))').intersection(QgsGeometry.fromWkt('Point (42 0)')).isNull()
60136013

6014+
def testIsRectangle(self):
6015+
"""
6016+
Test checking if geometries are rectangles
6017+
"""
6018+
# non polygons
6019+
self.assertFalse(QgsGeometry().isAxisParallelRectangle(0))
6020+
self.assertFalse(QgsGeometry.fromWkt('Point(0 1)').isAxisParallelRectangle(0))
6021+
self.assertFalse(QgsGeometry.fromWkt('LineString(0 1, 1 2)').isAxisParallelRectangle(0))
6022+
6023+
self.assertFalse(QgsGeometry.fromWkt('Polygon((0 0, 0 1, 1 1, 0 0))').isAxisParallelRectangle(0))
6024+
self.assertFalse(QgsGeometry.fromWkt('Polygon((0 0, 0 1, 1 1, 0 0))').isAxisParallelRectangle(0, True))
6025+
self.assertFalse(QgsGeometry.fromWkt('Polygon((0 0, 0 1, 1 1, 0 1))').isAxisParallelRectangle(0))
6026+
self.assertFalse(QgsGeometry.fromWkt('Polygon((0 0, 0 1, 1 1, 0 1))').isAxisParallelRectangle(0, True))
6027+
self.assertFalse(QgsGeometry.fromWkt('Polygon(())').isAxisParallelRectangle(0))
6028+
6029+
self.assertTrue(QgsGeometry.fromWkt('Polygon((0 0, 1 0, 1 1, 0 1, 0 0))').isAxisParallelRectangle(0))
6030+
self.assertTrue(QgsGeometry.fromWkt('Polygon((0 0, 1 0, 1 1, 0 1, 0 0))').isAxisParallelRectangle(0, True))
6031+
self.assertTrue(QgsGeometry.fromWkt('Polygon((0 0, 0 1, 1 1, 1 0, 0 0))').isAxisParallelRectangle(0))
6032+
self.assertTrue(QgsGeometry.fromWkt('Polygon((0 0, 0 1, 1 1, 1 0, 0 0))').isAxisParallelRectangle(0, True))
6033+
# with rings
6034+
self.assertFalse(QgsGeometry.fromWkt('Polygon((0 0, 1 0, 1 1, 0 1, 0 0), (0.1 0.1, 0.2 0.1, 0.2 0.2, 0.1 0.2, 0.1 0.1))').isAxisParallelRectangle(0))
6035+
# densified
6036+
self.assertTrue(QgsGeometry.fromWkt('Polygon((0 0, 0.5 0.0, 1 0, 1 1, 0 1, 0 0))').densifyByCount(5).isAxisParallelRectangle(0))
6037+
# not a simple rectangle
6038+
self.assertFalse(QgsGeometry.fromWkt('Polygon((0 0, 0.5 0.0, 1 0, 1 1, 0 1, 0 0))').densifyByCount(5).isAxisParallelRectangle(0, True))
6039+
6040+
# starting mid way through a side
6041+
self.assertTrue(QgsGeometry.fromWkt('Polygon((0.5 0, 1 0, 1 1, 0 1, 0 0, 0.5 0))').densifyByCount(
6042+
5).isAxisParallelRectangle(0))
6043+
self.assertFalse(QgsGeometry.fromWkt('Polygon((0.5 0, 1 0, 1 1, 0 1, 0 0, 0.5 0))').densifyByCount(
6044+
5).isAxisParallelRectangle(0, True))
6045+
6046+
# with tolerance
6047+
self.assertFalse(QgsGeometry.fromWkt('Polygon((0 0, 1 0.001, 1 1, 0 1, 0 0))').isAxisParallelRectangle(0))
6048+
self.assertTrue(QgsGeometry.fromWkt('Polygon((0 0, 1 0.001, 1 1, 0 1, 0 0))').isAxisParallelRectangle(1))
6049+
self.assertFalse(QgsGeometry.fromWkt('Polygon((0 0, 1 0.1, 1 1, 0 1, 0 0))').isAxisParallelRectangle(1))
6050+
self.assertTrue(QgsGeometry.fromWkt('Polygon((0 0, 1 0.1, 1 1, 0 1, 0 0))').isAxisParallelRectangle(10))
6051+
self.assertTrue(QgsGeometry.fromWkt('Polygon((0 0, 1 0.1, 1 1, 0 1, 0 0))').densifyByCount(5).isAxisParallelRectangle(10))
6052+
60146053
def testTransformWithClass(self):
60156054
"""
60166055
Test transforming using a python based class (most of the tests for this are in c++, this is just

0 commit comments

Comments
 (0)
Please sign in to comment.