1 /**********************************************************************
3 * GEOS - Geometry Engine Open Source
4 * http://geos.osgeo.org
6 * Copyright (C) 2001-2002 Vivid Solutions Inc.
8 * This is free software; you can redistribute and/or modify it under
9 * the terms of the GNU Lesser General Public Licence as published
10 * by the Free Software Foundation.
11 * See the COPYING file for more information.
13 **********************************************************************
15 * Last port: geom/prep/AbstractPreparedPolygonContains.java r388 (JTS-1.12)
17 **********************************************************************/
19 #include <geos/geom/prep/AbstractPreparedPolygonContains.h>
20 #include <geos/geom/prep/PreparedPolygon.h>
21 #include <geos/geom/Geometry.h>
22 #include <geos/geom/Polygon.h>
23 #include <geos/geom/MultiPolygon.h>
24 #include <geos/noding/SegmentString.h>
25 #include <geos/noding/SegmentStringUtil.h>
26 #include <geos/noding/SegmentIntersectionDetector.h>
27 #include <geos/noding/FastSegmentSetIntersectionFinder.h>
28 #include <geos/algorithm/LineIntersector.h>
33 namespace geom
{ // geos::geom
34 namespace prep
{ // geos::geom::prep
39 AbstractPreparedPolygonContains::isProperIntersectionImpliesNotContainedSituation( const geom::Geometry
* testGeom
)
41 // If the test geometry is polygonal we have the A/A situation.
42 // In this case, a proper intersection indicates that
43 // the Epsilon-Neighbourhood Exterior Intersection condition exists.
44 // This condition means that in some small
45 // area around the intersection point, there must exist a situation
46 // where the interior of the test intersects the exterior of the target.
47 // This implies the test is NOT contained in the target.
48 if ( testGeom
->getGeometryTypeId() == geos::geom::GEOS_MULTIPOLYGON
49 || testGeom
->getGeometryTypeId() == geos::geom::GEOS_POLYGON
)
52 // A single shell with no holes allows concluding that
53 // a proper intersection implies not contained
54 // (due to the Epsilon-Neighbourhood Exterior Intersection condition)
55 if ( isSingleShell( prepPoly
->getGeometry()) )
63 AbstractPreparedPolygonContains::isSingleShell(const geom::Geometry
& geom
)
65 // handles single-element MultiPolygons, as well as Polygons
66 if (geom
.getNumGeometries() != 1)
71 const geom::Geometry
* g
= geom
.getGeometryN(0);
72 const geom::Polygon
* poly
= dynamic_cast<const Polygon
*>(g
);
75 std::size_t numHoles
= poly
->getNumInteriorRing();
76 return (0 == numHoles
);
81 AbstractPreparedPolygonContains::findAndClassifyIntersections(const geom::Geometry
* geom
)
83 noding::SegmentString::ConstVect lineSegStr
;
84 noding::SegmentStringUtil::extractSegmentStrings(geom
, lineSegStr
);
86 algorithm::LineIntersector li
;
88 noding::SegmentIntersectionDetector
intDetector(&li
);
90 intDetector
.setFindAllIntersectionTypes(true);
91 prepPoly
->getIntersectionFinder()->intersects(&lineSegStr
, &intDetector
);
93 hasSegmentIntersection
= intDetector
.hasIntersection();
94 hasProperIntersection
= intDetector
.hasProperIntersection();
95 hasNonProperIntersection
= intDetector
.hasNonProperIntersection();
97 for (std::size_t i
= 0, ni
= lineSegStr
.size(); i
< ni
; i
++ )
108 AbstractPreparedPolygonContains::eval( const geom::Geometry
* geom
)
110 // Do point-in-poly tests first, since they are cheaper and may result
111 // in a quick negative result.
113 // If a point of any test components does not lie in target,
115 bool isAllInTargetArea
= isAllTestComponentsInTarget( geom
);
116 if ( !isAllInTargetArea
)
119 // If the test geometry consists of only Points,
120 // then it is now sufficient to test if any of those
121 // points lie in the interior of the target geometry.
122 // If so, the test is contained.
123 // If not, all points are on the boundary of the area,
124 // which implies not contained.
125 if ( requireSomePointInInterior
&& geom
->getDimension() == 0 )
127 bool isAnyInTargetInterior
= isAnyTestComponentInTargetInterior( geom
);
128 return isAnyInTargetInterior
;
131 // Check if there is any intersection between the line segments
132 // in target and test.
133 // In some important cases, finding a proper interesection implies that the
134 // test geometry is NOT contained.
136 // - If the test geometry is polygonal
137 // - If the target geometry is a single polygon with no holes
138 // In both of these cases, a proper intersection implies that there
139 // is some portion of the interior of the test geometry lying outside
140 // the target, which means that the test is not contained.
141 bool properIntersectionImpliesNotContained
= isProperIntersectionImpliesNotContainedSituation( geom
);
143 // find all intersection types which exist
144 findAndClassifyIntersections( geom
);
146 if ( properIntersectionImpliesNotContained
&& hasProperIntersection
)
149 // If all intersections are proper
150 // (i.e. no non-proper intersections occur)
151 // we can conclude that the test geometry is not contained in the target area,
152 // by the Epsilon-Neighbourhood Exterior Intersection condition.
153 // In real-world data this is likely to be by far the most common situation,
154 // since natural data is unlikely to have many exact vertex segment intersections.
155 // Thus this check is very worthwhile, since it avoid having to perform
156 // a full topological check.
158 // (If non-proper (vertex) intersections ARE found, this may indicate
159 // a situation where two shells touch at a single vertex, which admits
160 // the case where a line could cross between the shells and still be wholely contained in them.
161 if ( hasSegmentIntersection
&& !hasNonProperIntersection
)
164 // If there is a segment intersection and the situation is not one
165 // of the ones above, the only choice is to compute the full topological
166 // relationship. This is because contains/covers is very sensitive
167 // to the situation along the boundary of the target.
168 if ( hasSegmentIntersection
)
169 return fullTopologicalPredicate( geom
);
171 // This tests for the case where a ring of the target lies inside
172 // a test polygon - which implies the exterior of the Target
173 // intersects the interior of the Test, and hence the result is false
174 if ( geom
->getGeometryTypeId() == geos::geom::GEOS_MULTIPOLYGON
175 || geom
->getGeometryTypeId() == geos::geom::GEOS_POLYGON
)
177 // TODO: generalize this to handle GeometryCollections
178 bool isTargetInTestArea
= isAnyTargetComponentInAreaTest( geom
, prepPoly
->getRepresentativePoints());
180 if ( isTargetInTestArea
)
191 } // geos::geom::prep