src/geom/prep/AbstractPreparedPolygonContains.cpp

   1 /**********************************************************************
   2  *
   3  * GEOS - Geometry Engine Open Source
   4  * http://geos.osgeo.org
   5  *
   6  * Copyright (C) 2001-2002 Vivid Solutions Inc.
   7  *
   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.
  12  *
  13  **********************************************************************
  14  *
  15  * Last port: geom/prep/AbstractPreparedPolygonContains.java r388 (JTS-1.12)
  16  *
  17  **********************************************************************/
  18
  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>
  29 // std
  30 #include <cstddef>
  31
  32 namespace geos {
  33 namespace geom { // geos::geom
  34 namespace prep { // geos::geom::prep
  35 //
  36 // private:
  37 //
  38 bool
  39 AbstractPreparedPolygonContains::isProperIntersectionImpliesNotContainedSituation( const geom::Geometry * testGeom)
  40 {
  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 )
  50                 return true;
  51
  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()) )
  56                 return true;
  57
  58         return false;
  59 }
  60
  61
  62 bool
  63 AbstractPreparedPolygonContains::isSingleShell(const geom::Geometry& geom)
  64 {
  65         // handles single-element MultiPolygons, as well as Polygons
  66         if (geom.getNumGeometries() != 1)
  67     {
  68                 return false;
  69     }
  70
  71   const geom::Geometry* g = geom.getGeometryN(0);
  72   const geom::Polygon* poly = dynamic_cast<const Polygon*>(g);
  73   assert(poly);
  74
  75   std::size_t numHoles = poly->getNumInteriorRing();
  76   return (0 == numHoles);
  77 }
  78
  79
  80 void
  81 AbstractPreparedPolygonContains::findAndClassifyIntersections(const geom::Geometry* geom)
  82 {
  83         noding::SegmentString::ConstVect lineSegStr;
  84         noding::SegmentStringUtil::extractSegmentStrings(geom, lineSegStr);
  85
  86         algorithm::LineIntersector li;
  87
  88         noding::SegmentIntersectionDetector intDetector(&li);
  89
  90         intDetector.setFindAllIntersectionTypes(true);
  91         prepPoly->getIntersectionFinder()->intersects(&lineSegStr, &intDetector);
  92
  93         hasSegmentIntersection = intDetector.hasIntersection();
  94         hasProperIntersection = intDetector.hasProperIntersection();
  95         hasNonProperIntersection = intDetector.hasNonProperIntersection();
  96
  97         for (std::size_t i = 0, ni = lineSegStr.size(); i < ni; i++ )
  98         {
  99                 delete lineSegStr[i];
 100         }
 101 }
 102
 103
 104 //
 105 // protected:
 106 //
 107 bool
 108 AbstractPreparedPolygonContains::eval( const geom::Geometry * geom)
 109 {
 110         // Do point-in-poly tests first, since they are cheaper and may result
 111         // in a quick negative result.
 112         //
 113         // If a point of any test components does not lie in target,
 114         // result is false
 115         bool isAllInTargetArea = isAllTestComponentsInTarget( geom);
 116         if ( !isAllInTargetArea )
 117                 return false;
 118
 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 )
 126         {
 127                 bool isAnyInTargetInterior = isAnyTestComponentInTargetInterior( geom);
 128                 return isAnyInTargetInterior;
 129         }
 130
 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.
 135         // These cases are:
 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);
 142
 143     // find all intersection types which exist
 144     findAndClassifyIntersections( geom);
 145
 146         if ( properIntersectionImpliesNotContained && hasProperIntersection )
 147                 return false;
 148
 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.
 157         //
 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 )
 162                 return false;
 163
 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);
 170
 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 )
 176         {
 177                 // TODO: generalize this to handle GeometryCollections
 178                 bool isTargetInTestArea = isAnyTargetComponentInAreaTest( geom, prepPoly->getRepresentativePoints());
 179
 180                 if ( isTargetInTestArea )
 181                         return false;
 182         }
 183
 184         return true;
 185 }
 186
 187 //
 188 // public:
 189 //
 190
 191 } // geos::geom::prep
 192 } // geos::geom
 193 } // geos
 194
 195 /**********************************************************************
 196  * $Log$
 197  *
 198  **********************************************************************/