segmentss_touch_2D((a,b), (c,d)) is equivalent to segments_colinear((a,b), (c,d)) |
    numpy.isfinite(segment_intersection_2D((a,b), (c,d))[0])
557688
def segments_touch_2D(ab, cd):
    '''
    
    '''
    return segments_colinear(ab, cd) | np.isfinite(segment_intersection_2D(ab, cd)[0])
1283758
public static boolean touches(Geometry geometry, Coordinate coordinate) {
		if (geometry instanceof MultiPolygon) {
			for (int i = 0; i < geometry.getNumGeometries(); i++) {
				if (touches(geometry.getGeometryN(i), coordinate)) {
					return true;
				}
			}
			return false;
		} else if (geometry instanceof Polygon) {
			Polygon polygon = (Polygon) geometry;
			if (touchesLineString(polygon.getExteriorRing(), coordinate)) {
				return true;
			}
			for (int n = 0; n < polygon.getNumInteriorRing(); n++) {
				if (touchesLineString(polygon.getInteriorRingN(n), coordinate)) {
					return true;
				}
			}
			return false;
		} else if (geometry instanceof MultiLineString) {
			for (int i = 0; i < geometry.getNumGeometries(); i++) {
				if (touchesLineString((LineString) geometry.getGeometryN(i), coordinate)) {
					return true;
				}
			}
			return false;
		} else if (geometry instanceof LineString) {
			return touchesLineString((LineString) geometry, coordinate);
		} else if (geometry instanceof Point) {
			Coordinate c = geometry.getCoordinates()[0];
			Vector2D v1 = new Vector2D(c.getX(), c.getY());
			Vector2D v2 = new Vector2D(coordinate.getX(), coordinate.getY());
			return (v1.distance(v2) < ZERO);
		}
		return false;
	}
233607
function getIntersectionRect (rect1, rect2) {
  const intersectRect = {
    topLeft: {},
    bottomRight: {}
  };

  if (!doesIntersect(rect1, rect2)) {
    return;
  }

  const rect1Points = rectToPoints(rect1);
  const rect2Points = rectToPoints(rect2);

  if (rect1.width >= 0) {
    if (rect2.width >= 0) {
      intersectRect.topLeft.x = Math.max(rect1Points.topLeft.x, rect2Points.topLeft.x);
      intersectRect.bottomRight.x = Math.min(rect1Points.bottomRight.x, rect2Points.bottomRight.x);
    } else {
      intersectRect.topLeft.x = Math.max(rect1Points.topLeft.x, rect2Points.bottomRight.x);
      intersectRect.bottomRight.x = Math.min(rect1Points.bottomRight.x, rect2Points.topLeft.x);
    }
  } else if (rect2.width >= 0) {
    intersectRect.topLeft.x = Math.min(rect1Points.topLeft.x, rect2Points.bottomRight.x);
    intersectRect.bottomRight.x = Math.max(rect1Points.bottomRight.x, rect2Points.topLeft.x);
  } else {
    intersectRect.topLeft.x = Math.min(rect1Points.topLeft.x, rect2Points.topLeft.x);
    intersectRect.bottomRight.x = Math.max(rect1Points.bottomRight.x, rect2Points.bottomRight.x);
  }

  if (rect1.height >= 0) {
    if (rect2.height >= 0) {
      intersectRect.topLeft.y = Math.max(rect1Points.topLeft.y, rect2Points.topLeft.y);
      intersectRect.bottomRight.y = Math.min(rect1Points.bottomRight.y, rect2Points.bottomRight.y);
    } else {
      intersectRect.topLeft.y = Math.max(rect1Points.topLeft.y, rect2Points.bottomRight.y);
      intersectRect.bottomRight.y = Math.min(rect1Points.bottomRight.y, rect2Points.topLeft.y);
    }
  } else if (rect2.height >= 0) {
    intersectRect.topLeft.y = Math.min(rect1Points.topLeft.y, rect2Points.bottomRight.y);
    intersectRect.bottomRight.y = Math.max(rect1Points.bottomRight.y, rect2Points.topLeft.y);
  } else {
    intersectRect.topLeft.y = Math.min(rect1Points.topLeft.y, rect2Points.topLeft.y);
    intersectRect.bottomRight.y = Math.max(rect1Points.bottomRight.y, rect2Points.bottomRight.y);
  }

  // Returns top-left and bottom-right points of intersected rectangle
  return intersectRect;

}
691648
def interval_intersection_width(a, b, c, d):
    """"""
    return max(0, min(b, d) - max(a, c))
465143
function pointRectangleSimple(p, a1, a2) {
    if (!(a1.x > p.x ||
        a2.x < p.x ||
        a1.y > p.y ||
        a2.y < p.y))
        return {result: collision.INSIDE};
    return {result: collision.OUTSIDE};
}
1154546
def intersect(self, other_seg, tol=1e-12):
        """"""
        if isinstance(other_seg, Line):
            return bezier_by_line_intersections(self, other_seg)
        elif (isinstance(other_seg, QuadraticBezier) or
              isinstance(other_seg, CubicBezier)):
            assert self != other_seg
            longer_length = max(self.length(), other_seg.length())
            return bezier_intersections(self, other_seg,
                                        longer_length=longer_length,
                                        tol=tol, tol_deC=tol)
        elif isinstance(other_seg, Arc):
            t2t1s = other_seg.intersect(self)
            return [(t1, t2) for t2, t1 in t2t1s]
        elif isinstance(other_seg, Path):
            raise TypeError(
                "other_seg must be a path segment, not a Path object, use "
                "Path.intersect().")
        else:
            raise TypeError("other_seg must be a path segment.")
503639
private static boolean polylineTouchesPolyline_(Polyline polyline_a,
			Polyline polyline_b, double tolerance,
			ProgressTracker progress_tracker) {
		// Quick rasterize test to see whether the the geometries are disjoint.
		if (tryRasterizedContainsOrDisjoint_(polyline_a, polyline_b, tolerance,
				false) == Relation.disjoint)
			return false;

		AttributeStreamOfDbl intersections = new AttributeStreamOfDbl(0);

		int dim = linearPathIntersectsLinearPathMaxDim_(polyline_a, polyline_b,
				tolerance, intersections);

		if (dim != 0)
			return false;

		MultiPoint intersection = new MultiPoint();

		for (int i = 0; i < intersections.size(); i += 2) {
			double x = intersections.read(i);
			double y = intersections.read(i + 1);
			intersection.add(x, y);
		}

		MultiPoint boundary_a_b = (MultiPoint) (polyline_a.getBoundary());
		MultiPoint boundary_b = (MultiPoint) (polyline_b.getBoundary());

		boundary_a_b.add(boundary_b, 0, boundary_b.getPointCount());

		return multiPointContainsMultiPointBrute_(boundary_a_b, intersection,
				tolerance);
	}
449886
private void intersectionMatrix(int[][] res, ArrayList<int[]> partsx, ArrayList<int[]> partsy, int gridsize) {
    for(int x = 0; x < gridsize; x++) {
      final int[] px = partsx.get(x);
      final int[] rowx = res[x];
      for(int y = 0; y < gridsize; y++) {
        int[] py = partsy.get(y);
        rowx[y] = intersectionSize(px, py);
      }
    }
  }
1009556
private boolean intersection(
            final long pX0, final long pY0, final long pX1, final long pY1,
            final long pX2, final long pY2, final long pX3, final long pY3
    ) {
        return SegmentIntersection.intersection(
                pX0, pY0, pX1, pY1,
                pX2, pY2, pX3, pY3, mOptimIntersection);
    }
1025622
def intersects(self, e):
    
    if self.chrom != e.chrom:
      return False

    if e.start >= self.start and e.start < self.end:
      return True
    if e.end > self.start and e.end <= self.end:
      return True
    if e.start < self.start and e.end > self.end:
      return True
    return False
994043
private static boolean polygonTouchesMultiPoint_(Polygon polygon_a,
			MultiPoint multipoint_b, double tolerance,
			ProgressTracker progress_tracker) {
		// Quick rasterize test to see whether the the geometries are disjoint,
		// or if one is contained in the other.
		int relation = tryRasterizedContainsOrDisjoint_(polygon_a,
				multipoint_b, tolerance, false);

		if (relation == Relation.disjoint || relation == Relation.contains)
			return false;

        Envelope2D env_a_inflated = new Envelope2D();
        polygon_a.queryEnvelope2D(env_a_inflated);
        env_a_inflated.inflate(tolerance, tolerance);

        Point2D ptB;
        boolean b_boundary = false;

        MultiPathImpl polygon_a_impl = (MultiPathImpl)polygon_a._getImpl();

        Polygon pa = null;
        Polygon p_polygon_a = polygon_a;

        boolean b_checked_polygon_a_quad_tree = false;

        for (int i = 0; i < multipoint_b.getPointCount(); i++)
        {
            ptB = multipoint_b.getXY(i);

            if (env_a_inflated.contains(ptB)) {

                PolygonUtils.PiPResult result = PolygonUtils.isPointInPolygon2D(p_polygon_a, ptB, tolerance);

                if (result == PolygonUtils.PiPResult.PiPBoundary)
                    b_boundary = true;
                else if (result == PolygonUtils.PiPResult.PiPInside)
                    return false;
            }

            if (!b_checked_polygon_a_quad_tree) {
                if (PointInPolygonHelper.quadTreeWillHelp(polygon_a, multipoint_b.getPointCount() - 1) && (polygon_a_impl._getAccelerators() == null || polygon_a_impl._getAccelerators().getQuadTree() == null)) {
                    pa = new Polygon();
                    polygon_a.copyTo(pa);
                    ((MultiPathImpl) pa._getImpl())._buildQuadTreeAccelerator(Geometry.GeometryAccelerationDegree.enumMedium);
                    p_polygon_a = pa;
                } else {
                    p_polygon_a = polygon_a;
                }

                b_checked_polygon_a_quad_tree = true;
            }
        }

        if (b_boundary)
            return true;

        return false;
	}
1050484
function polygonIsSimple(polygon){
    var path = polygon, i;
    // Check
    for(i=0; i<path.length-1; i++){
        for(var j=0; j<i-1; j++){
            if(lineSegmentsIntersect(path[i], path[i+1], path[j], path[j+1] )){
                return false;
            }
        }
    }

    // Check the segment between the last and the first point to all others
    for(i=1; i<path.length-2; i++){
        if(lineSegmentsIntersect(path[0], path[path.length-1], path[i], path[i+1] )){
            return false;
        }
    }

    return true;
}
934030
int filterClosePoints(double tolerance, boolean b_remove_last_vertices, boolean only_polygons) {
		int res = 0;
		for (int geometry = getFirstGeometry(); geometry != -1; geometry = getNextGeometry(geometry)) {
			int gt = getGeometryType(geometry);
			if (!Geometry.isMultiPath(gt))
				continue;
			if (only_polygons && gt != GeometryType.Polygon)
				continue;

			boolean b_polygon = getGeometryType(geometry) == Geometry.GeometryType.Polygon;

			for (int path = getFirstPath(geometry); path != -1;) {
				// We go from the start to the half of the path first, then we
				// go from the end to the half of the path.
				int vertex_counter = 0;
				for (int vertex = getFirstVertex(path); vertex_counter < getPathSize(path) / 2;) {
					int next = getNextVertex(vertex);
					if (next == -1)
						break;
					int vindex = getVertexIndex(vertex);
					Segment seg = getSegmentFromIndex_(vindex);
					double length = 0;
					if (seg != null) {
						length = seg.calculateLength2D();
					} else {
						int vindex_next = getVertexIndex(next);
						length = m_vertices._getShortestDistance(vindex,
								vindex_next);
					}

					if (length <= tolerance) {
						if (length == 0) {
							if (res == 0)
								res = -1;
						} else
							res = 1;

						if (next != getLastVertex(path)) {
							transferAllDataToTheVertex(next, vertex);
							removeVertex(next, true);
						}
					} else {
						vertex = getNextVertex(vertex);
					}
					vertex_counter++;
				}

				int first_vertex = getFirstVertex(path);
				for (int vertex = isClosedPath(path) ? first_vertex
						: getLastVertex(path); getPathSize(path) > 0;) {
					int prev = getPrevVertex(vertex);
					if (prev != -1) {
						int vindex_prev = getVertexIndex(prev);
						Segment seg = getSegmentFromIndex_(vindex_prev);
						double length = 0;
						if (seg != null) {
							length = seg.calculateLength2D();
						} else {
							int vindex = getVertexIndex(vertex);
							length = m_vertices._getShortestDistance(vindex,
									vindex_prev);
						}

						if (length <= tolerance) {
							if (length == 0) {
								if (res == 0)
									res = -1;
							} else
								res = 1;

							transferAllDataToTheVertex(prev, vertex);
							removeVertex(prev, false);
							if (first_vertex == prev)
								first_vertex = getFirstVertex(path);
						} else {
							vertex = getPrevVertex(vertex);
							if (vertex == first_vertex)
								break;
						}
					} else {
						removeVertex(vertex, true);// remove the last vertex in
													// the path
						if (res == 0)
							res = -1;
						break;
					}
				}

				int path_size = getPathSize(path);
				if (b_remove_last_vertices
						&& (b_polygon ? path_size < 3 : path_size < 2)) {
					path = removePath(path);
					res = path_size > 0 ? 1 : (res == 0 ? -1 : res);
				} else
					path = getNextPath(path);
			}
		}

		return res;
	}
1103363
static boolean linearPathIntersectsPoint_(MultiPath multipathA,
			Point2D ptB, double tolerance) {
		Point2D closest = new Point2D();
		double toleranceSq = tolerance * tolerance;
		SegmentIteratorImpl segIterA = ((MultiPathImpl) multipathA._getImpl())
				.querySegmentIterator();

		GeometryAccelerators accel = ((MultiPathImpl) multipathA._getImpl())
				._getAccelerators();

		if (accel != null) {
			QuadTreeImpl quadTreeA = accel.getQuadTree();
			if (quadTreeA != null) {
				Envelope2D env_b = new Envelope2D();
				env_b.setCoords(ptB);

				QuadTreeImpl.QuadTreeIteratorImpl qt_iter = quadTreeA
						.getIterator(env_b, tolerance);

				for (int e = qt_iter.next(); e != -1; e = qt_iter.next()) {
					segIterA.resetToVertex(quadTreeA.getElement(e));

					if (segIterA.hasNextSegment()) {
						Segment segmentA = segIterA.nextSegment();

						double t = segmentA.getClosestCoordinate(ptB, false);
						segmentA.getCoord2D(t, closest);

						if (Point2D.sqrDistance(ptB, closest) <= toleranceSq) {
							return true;
						}
					}
				}

				return false;
			}
		}
		Envelope2D env_a = new Envelope2D();

		while (segIterA.nextPath()) {
			while (segIterA.hasNextSegment()) {
				Segment segmentA = segIterA.nextSegment();
				segmentA.queryEnvelope2D(env_a);
				env_a.inflate(tolerance, tolerance);

				if (!env_a.contains(ptB)) {
					continue;
				}

				double t = segmentA.getClosestCoordinate(ptB, false);
				segmentA.getCoord2D(t, closest);

				if (Point2D.sqrDistance(ptB, closest) <= toleranceSq) {
					return true;
				}
			}
		}

		return false;
	}
526104
def intersects_segment(self, seg):
		
		return any(value.intersects_segment(seg) for value in self.itervalues())
847740
def intersects_segment(self, other):
		
		i = _bisect_left(self, other)
		return ((i != 0) and (other[0] < self[i-1][1])) or ((i != len(self)) and (other[1] > self[i][0]))
279999
function ifIsectAddToOutput(ring0, edge0, ring1, edge1) {
    var start0 = coord[ring0][edge0];
    var end0 = coord[ring0][edge0+1];
    var start1 = coord[ring1][edge1];
    var end1 = coord[ring1][edge1+1];

    var isect = intersect(start0, end0, start1, end1);

    if (isect == null) return; // discard parallels and coincidence
    frac0, frac1;
    if (end0[0] != start0[0]) {
      var frac0 = (isect[0]-start0[0])/(end0[0]-start0[0]);
    } else {
      var frac0 = (isect[1]-start0[1])/(end0[1]-start0[1]);
    };
    if (end1[0] != start1[0]) {
      var frac1 = (isect[0]-start1[0])/(end1[0]-start1[0]);
    } else {
      var frac1 = (isect[1]-start1[1])/(end1[1]-start1[1]);
    };

    // There are roughly three cases we need to deal with.
    // 1. If at least one of the fracs lies outside [0,1], there is no intersection.
    if (isOutside(frac0) || isOutside(frac1)) {
      return; // require segment intersection
    }

    // 2. If both are either exactly 0 or exactly 1, this is not an intersection but just
    // two edge segments sharing a common vertex.
    if (isBoundaryCase(frac0) && isBoundaryCase(frac1)){
      if(! options.reportVertexOnVertex) return;
    }

    // 3. If only one of the fractions is exactly 0 or 1, this is
    // a vertex-on-edge situation.
    if (isBoundaryCase(frac0) || isBoundaryCase(frac1)){
      if(! options.reportVertexOnEdge) return;
    }

    var key = isect;
    var unique = !seen[key];
    if (unique) {
      seen[key] = true;
    }

    if (filterFn) {
      output.push(filterFn(isect, ring0, edge0, start0, end0, frac0, ring1, edge1, start1, end1, frac1, unique));
    } else {
      output.push(isect);
    }
  }