AbstractPreparedPolygonContains.java

/*
 * Copyright (c) 2016 Vivid Solutions.
 *
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License 2.0
 * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
 * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
 * and the Eclipse Distribution License is available at
 *
 * http://www.eclipse.org/org/documents/edl-v10.php.
 */
package org.locationtech.jts.geom.prep;

import java.util.List;

import org.locationtech.jts.geom.Geometry;
import org.locationtech.jts.geom.Polygon;
import org.locationtech.jts.geom.Polygonal;
import org.locationtech.jts.noding.SegmentIntersectionDetector;
import org.locationtech.jts.noding.SegmentStringUtil;



/**
 * A base class containing the logic for computes the <tt>contains</tt>
 * and <tt>covers</tt> spatial relationship predicates
 * for a {@link PreparedPolygon} relative to all other {@link Geometry} classes.
 * Uses short-circuit tests and indexing to improve performance. 
 * <p>
 * Contains and covers are very similar, and differ only in how certain
 * cases along the boundary are handled.  These cases require 
 * full topological evaluation to handle, so all the code in 
 * this class is common to both predicates.
 * <p>
 * It is not possible to short-circuit in all cases, in particular
 * in the case where line segments of the test geometry touches the polygon linework.
 * In this case full topology must be computed.
 * (However, if the test geometry consists of only points, this 
 * <i>can</i> be evaluated in an optimized fashion.
 * 
 * @author Martin Davis
 *
 */
abstract class AbstractPreparedPolygonContains 
	extends PreparedPolygonPredicate
{
	/**
	 * This flag controls a difference between contains and covers.
	 * 
	 * For contains the value is true.
	 * For covers the value is false.
	 */
	protected boolean requireSomePointInInterior = true; 
	
	// information about geometric situation
	private boolean hasSegmentIntersection = false;
  private boolean hasProperIntersection = false;
  private boolean hasNonProperIntersection = false;
	
  /**
   * Creates an instance of this operation.
   * 
   * @param prepPoly the PreparedPolygon to evaluate
   */
	public AbstractPreparedPolygonContains(PreparedPolygon prepPoly)
	{
		super(prepPoly);
	}
	
	/**
	 * Evaluate the <tt>contains</tt> or <tt>covers</tt> relationship
	 * for the given geometry.
	 * 
	 * @param geom the test geometry
	 * @return true if the test geometry is contained
	 */
	protected boolean eval(Geometry geom)
	{
	  if (geom.getDimension() == 0) {
	    return evalPoints(geom);
	  }

		/**
		 * Do point-in-poly tests first, since they are cheaper and may result
		 * in a quick negative result.
		 * 
		 * If a point of any test components does not lie in target, result is false
		 */
		boolean isAllInTargetArea = isAllTestComponentsInTarget(geom);
		if (! isAllInTargetArea) return false;
		
		/**
		 * Check if there is any intersection between the line segments
		 * in target and test.
		 * In some important cases, finding a proper intersection implies that the
		 * test geometry is NOT contained.
		 * These cases are:
		 * <ul>
		 * <li>If the test geometry is polygonal
		 * <li>If the target geometry is a single polygon with no holes
		 * <ul>
		 * In both of these cases, a proper intersection implies that there
		 * is some portion of the interior of the test geometry lying outside
		 * the target, which means that the test is not contained.
		 */
		boolean properIntersectionImpliesNotContained = isProperIntersectionImpliesNotContainedSituation(geom);
		// MD - testing only
//		properIntersectionImpliesNotContained = true;
		
    // find all intersection types which exist
    findAndClassifyIntersections(geom);
		
		if (properIntersectionImpliesNotContained && hasProperIntersection)
			return false;
		
    /**
     * If all intersections are proper 
     * (i.e. no non-proper intersections occur)
     * we can conclude that the test geometry is not contained in the target area,
     * by the Epsilon-Neighbourhood Exterior Intersection condition.
     * In real-world data this is likely to be by far the most common situation, 
     * since natural data is unlikely to have many exact vertex segment intersections.
     * Thus this check is very worthwhile, since it avoid having to perform
     * a full topological check.
     * 
     * (If non-proper (vertex) intersections ARE found, this may indicate
     * a situation where two shells touch at a single vertex, which admits
     * the case where a line could cross between the shells and still be wholely contained in them.
     */
		if (hasSegmentIntersection && ! hasNonProperIntersection)
      return false;
    
		/**
		 * If there is a segment intersection and the situation is not one
		 * of the ones above, the only choice is to compute the full topological
		 * relationship.  This is because contains/covers is very sensitive 
		 * to the situation along the boundary of the target.
		 */
		if (hasSegmentIntersection) {
			return fullTopologicalPredicate(geom);
//			System.out.println(geom);
		}
				
		/**
		 * This tests for the case where a ring of the target lies inside
		 * a test polygon - which implies the exterior of the Target
		 * intersects the interior of the Test, and hence the result is false
		 */
		if (geom instanceof Polygonal) {
			// TODO: generalize this to handle GeometryCollections
			boolean isTargetInTestArea = isAnyTargetComponentInAreaTest(geom, prepPoly.getRepresentativePoints());
			if (isTargetInTestArea) return false;
		}
		return true;
	}
	
	/**
	 * Evaluation optimized for Point geometries.
	 * This provides about a 2x performance increase, and less memory usage.
	 * 
	 * @param geom a Point or MultiPoint geometry
	 * @return the value of the predicate being evaluated
	 */
	private boolean evalPoints(Geometry geom) {
    /**
     * Do point-in-poly tests first, since they are cheaper and may result
     * in a quick negative result.
     * 
     * If a point of any test components does not lie in target, result is false
     */
    boolean isAllInTargetArea = isAllTestPointsInTarget(geom);
    if (! isAllInTargetArea) return false;
    
    /**
     * If the test geometry consists of only Points, 
     * then it is now sufficient to test if any of those
     * points lie in the interior of the target geometry.
     * If so, the test is contained.
     * If not, all points are on the boundary of the area,
     * which implies not contained.
     */
    if (requireSomePointInInterior) {
      boolean isAnyInTargetInterior = isAnyTestPointInTargetInterior(geom);
      return isAnyInTargetInterior;
    }
    return true;
  }

  private boolean isProperIntersectionImpliesNotContainedSituation(Geometry testGeom)
	{
    /**
     * If the test geometry is polygonal we have the A/A situation.
     * In this case, a proper intersection indicates that 
     * the Epsilon-Neighbourhood Exterior Intersection condition exists.
     * This condition means that in some small
     * area around the intersection point, there must exist a situation
     * where the interior of the test intersects the exterior of the target.
     * This implies the test is NOT contained in the target. 
     */
		if (testGeom instanceof Polygonal) return true;
    /**
     * A single shell with no holes allows concluding that 
     * a proper intersection implies not contained 
     * (due to the Epsilon-Neighbourhood Exterior Intersection condition) 
     */
		if (isSingleShell(prepPoly.getGeometry())) return true;
		return false;
	}
	
  /**
   * Tests whether a geometry consists of a single polygon with no holes.
   *  
   * @return true if the geometry is a single polygon with no holes
   */
	private boolean isSingleShell(Geometry geom)
	{
    // handles single-element MultiPolygons, as well as Polygons
		if (geom.getNumGeometries() != 1) return false;
		
		Polygon poly = (Polygon) geom.getGeometryN(0);
		int numHoles = poly.getNumInteriorRing();
		if (numHoles == 0) return true;
		return false;
	}
	
	private void findAndClassifyIntersections(Geometry geom)
	{
    List lineSegStr = SegmentStringUtil.extractSegmentStrings(geom);
    
		SegmentIntersectionDetector intDetector = new SegmentIntersectionDetector();
		intDetector.setFindAllIntersectionTypes(true);
		prepPoly.getIntersectionFinder().intersects(lineSegStr, intDetector);
			
		hasSegmentIntersection = intDetector.hasIntersection();
    hasProperIntersection = intDetector.hasProperIntersection();
    hasNonProperIntersection = intDetector.hasNonProperIntersection();
	}
			
	/**
	 * Computes the full topological predicate.
	 * Used when short-circuit tests are not conclusive.
	 * 
	 * @param geom the test geometry
	 * @return true if this prepared polygon has the relationship with the test geometry
	 */
	protected abstract boolean fullTopologicalPredicate(Geometry geom);
	
}