Checks if one of the lines in the polyline intersects
with a given rectangle.
@see java.awt.Shape#intersects(double, double, double, double)
322962
public boolean intersects(double x, double y, double w, double h) {
		return intersects(new Rectangle2D.Double(x, y, w, h));
	}
928220
public void intersect (Area area) {
        if (area == null) {
            return;
        } else if (isEmpty() || area.isEmpty()) {
            reset();
            return;
        }

        if (isPolygonal() && area.isPolygonal()) {
            intersectPolygon(area);
        } else {
            intersectCurvePolygon(area);
        }

        if (areaBoundsSquare() < GeometryUtil.EPSILON) {
            reset();
        }
    }
410728
private boolean isCrossed(Point2d beg1, Point2d end1, Point2d beg2, Point2d end2) {
        return Line2D.linesIntersect(beg1.x, beg1.y, end1.x, end1.y, beg2.x, beg2.y, end2.x, end2.y);
    }
620659
public boolean isValid() {
		if (!isEmpty()) {
			for (int i = 0; i < polygons.length; i++) {
				if (!polygons[i].isValid()) {
					return false;
				}
				for (int j = i + 1; j < polygons.length; j++) {
					if (polygons[i].intersects(polygons[j])) {
						return false;
					}
				}
			}
		}
		return true;
	}
518162
public boolean intersects(Rectangle2D r) {
		if(np==0)return false;
		Line2D line = new Line2D.Double(x[0],y[0],x[0],y[0]);
		for (int i = 1; i < np; i++) {
			line.setLine(x[i-1], y[i-1], x[i], y[i]);
			if(line.intersects(r))return true;
		}
		return false;
	}
1159687
public static int intersectLine (double x1, double y1, double x2, double y2, double rx1,
                                     double ry1, double rx2, double ry2) {
        // LEFT/RIGHT/UP
        if ((rx2 < x1 && rx2 < x2) || (rx1 > x1 && rx1 > x2) || (ry1 > y1 && ry1 > y2)) {
            return 0;
        }

        // DOWN
        if (ry2 < y1 && ry2 < y2) {

        } else {
            // INSIDE
            if (x1 == x2) {
                return CROSSING;
            }

            // Build bound
            double bx1, bx2;
            if (x1 < x2) {
                bx1 = x1 < rx1 ? rx1 : x1;
                bx2 = x2 < rx2 ? x2 : rx2;
            } else {
                bx1 = x2 < rx1 ? rx1 : x2;
                bx2 = x1 < rx2 ? x1 : rx2;
            }
            double k = (y2 - y1) / (x2 - x1);
            double by1 = k * (bx1 - x1) + y1;
            double by2 = k * (bx2 - x1) + y1;

            // BOUND-UP
            if (by1 < ry1 && by2 < ry1) {
                return 0;
            }

            // BOUND-DOWN
            if (by1 > ry2 && by2 > ry2) {
            } else {
                return CROSSING;
            }
        }

        // EMPTY
        if (x1 == x2) {
            return 0;
        }

        // CURVE-START
        if (rx1 == x1) {
            return x1 < x2 ? 0 : -1;
        }

        // CURVE-END
        if (rx1 == x2) {
            return x1 < x2 ? 1 : 0;
        }

        if (x1 < x2) {
            return x1 < rx1 && rx1 < x2 ? 1 : 0;
        }
        return x2 < rx1 && rx1 < x1 ? -1 : 0;
    }
395592
public boolean intersects(GeoBounds other)
    {
        boolean rv = false;
        for (Rectangle2D r1 : rects)
        {
            for (Rectangle2D r2 : other.rects)
            {
                rv = r1.intersects(r2);
                if (rv)
                {
                    break;
                }
            }
            if (rv)
            {
                break;
            }

        }
        return rv;
    }
372811
public boolean contains(Shape other) {
    	if (other.intersects(this)) {
    		return false;
    	}
    	
    	for (int i=0;i<other.getPointCount();i++) {
    		float[] pt = other.getPoint(i);
    		if (!contains(pt[0], pt[1])) {
    			return false;
    		}
    	}
    	
    	return true;
    }
1335040
private static boolean intersectsPoint(Geometry point, Geometry geometry) {
		if (geometry.getGeometries() != null) {
			for (Geometry child : geometry.getGeometries()) {
				if (intersectsPoint(point, child)) {
					return true;
				}
			}
		}
		if (geometry.getCoordinates() != null) {
			Coordinate coordinate = point.getCoordinates()[0];
			if (geometry.getCoordinates().length == 1) {
				return coordinate.equals(geometry.getCoordinates()[0]);
			} else {
				for (int i = 0; i < geometry.getCoordinates().length - 1; i++) {
					double distance = MathService.distance(geometry.getCoordinates()[i],
							geometry.getCoordinates()[i + 1], coordinate);
					if (distance < DEFAULT_DOUBLE_DELTA) {
						return true;
					}
				}
			}
		}
		return false;
	}
932961
private static Point getShapeIntersection(Shape shape,
                                              Line2D.Double line) {
        PathIterator it = shape.getPathIterator(null);
        double[] coords = new double[6];
        double[] pos = new double[2];
        Line2D.Double l = new Line2D.Double();
        while (!it.isDone()) {
            int type = it.currentSegment(coords);
            switch (type) {
                case PathIterator.SEG_MOVETO:
                    pos[0] = coords[0];
                    pos[1] = coords[1];
                    break;
                case PathIterator.SEG_LINETO:
                    l = new Line2D.Double(pos[0],
                                          pos[1],
                                          coords[0],
                                          coords[1]);
                    if (line.intersectsLine(l)) {
                        return getLinesIntersection(line,
                                                    l);
                    }
                    pos[0] = coords[0];
                    pos[1] = coords[1];
                    break;
                case PathIterator.SEG_CLOSE:
                    break;
                default:
                    // whatever
            }
            it.next();
        }
        return null;
    }
536815
public HitResult intersect(Shape shape, Line line) {
		float distance = Float.MAX_VALUE;
		HitResult hit = null;
		
		for (int i=0;i<shape.getPointCount();i++) {
			int next = rationalPoint(shape, i+1);
			Line local = getLine(shape, i, next);
		
			Vector2f pt = line.intersect(local, true);
			if (pt != null) {
				float newDis = pt.distance(line.getStart());
				if ((newDis < distance) && (newDis > EPSILON)) {
					hit = new HitResult();
					hit.pt = pt;
					hit.line = local;
					hit.p1 = i;
					hit.p2 = next;
					distance = newDis;
				}
			}
		}
		
		return hit;
	}
1218003
private static boolean polylineDisjointPoint_(Polyline polyline_a,
			Point point_b, double tolerance, ProgressTracker progress_tracker) {
		// Quick rasterize test to see whether the the geometries are disjoint.
		if (tryRasterizedContainsOrDisjoint_(polyline_a, point_b, tolerance,
				false) == Relation.disjoint)
			return true;

		Point2D pt_b = point_b.getXY();
		return !linearPathIntersectsPoint_(polyline_a, pt_b, tolerance);
	}
122132
public static boolean intersects(Bbox one, Bbox two) {
		if (two.getX() > one.getMaxX()) {
			return false;
		}
		if (two.getY() > one.getMaxY()) {
			return false;
		}
		if (two.getMaxX() < one.getX()) {
			return false;
		}
		if (two.getMaxY() < one.getY()) {
			return false;
		}
		return true;
	}
110160
public static boolean intersects(Coordinate p, Triangle t) {
        Vector2D v0 = new Vector2D(t.p0.x - t.p2.x, t.p0.y - t.p2.y);
        Vector2D v1 = new Vector2D(t.p1.x - t.p2.x, t.p1.y - t.p2.y);
        Vector2D v2 = new Vector2D(p.x - t.p2.x, p.y - t.p2.y);

        // Compute dot products
        double dot00 = v0.dot(v0);
        double dot01 = v0.dot(v1);
        double dot02 = v0.dot(v2);
        double dot11 = v1.dot(v1);
        double dot12 = v1.dot(v2);

        // Compute barycentric coordinates
        double invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
        double u = (dot11 * dot02 - dot01 * dot12) * invDenom;
        double v = (dot00 * dot12 - dot01 * dot02) * invDenom;

        // Check if point is in triangle
        return (u > (0. - epsilon)) && (v > (0. - epsilon))
                && (u + v < (1. + epsilon));

}
1089903
public boolean intersect(Line other, boolean limit, Vector2f result) {
		float dx1 = end.getX() - start.getX();
		float dx2 = other.end.getX() - other.start.getX();
		float dy1 = end.getY() - start.getY();
		float dy2 = other.end.getY() - other.start.getY();
		float denom = (dy2 * dx1) - (dx2 * dy1);

		if (denom == 0) {
			return false;
		}

		float ua = (dx2 * (start.getY() - other.start.getY()))
				- (dy2 * (start.getX() - other.start.getX()));
		ua /= denom;
		float ub = (dx1 * (start.getY() - other.start.getY()))
				- (dy1 * (start.getX() - other.start.getX()));
		ub /= denom;

		if ((limit) && ((ua < 0) || (ua > 1) || (ub < 0) || (ub > 1))) {
			return false;
		}

		float u = ua;

		float ix = start.getX() + (u * (end.getX() - start.getX()));
		float iy = start.getY() + (u * (end.getY() - start.getY()));

		result.set(ix, iy);
		return true;
	}
430874
@Override
    public boolean collide(final Collidable collidable, final Collidable collidable2) {
        // check if bounding boxes intersect
        if (!RECTANGLE_COLLISION_CHECKER.collide(collidable, collidable2)) {
            return false;
        }

        final Point position = collidable.getPosition();
        final Point position2 = collidable2.getPosition();
        final CollisionRaster collisionRaster = collidable.getCollisionRaster();
        final CollisionRaster collisionRaster2 = collidable2.getCollisionRaster();

        // get the overlapping box
        final int startX = Math.max(position.x, position2.x);
        final int endX = Math.min(position.x + collidable.getDimension().width,
                                  position2.x + collidable2.getDimension().width);

        final int startY = Math.max(position.y, position2.y);
        final int endY = Math.min(position.y + collidable.getDimension().height,
                                  position2.y + collidable2.getDimension().height);

        final int endX1 = endX - position.x;
        final int endX2 = endX - position2.x;

        final int stop1 = position.x + -1;
        final int stop2 = position2.x + -1;
        
        // this is the fast path of finding collisions: we expect the none transparent
        // pixel to be around the center, using padding will increase this effect.
        final int stepSize = ((endY - startY) / 3) + 1;
        
        for (int i = stepSize - 1; i >= 0; i--) {
            for (int y = startY + i; y < endY; y += stepSize) {
                final int yOfPosition = y - position.y;
                int absolute1 = position.x + collisionRaster.nextNotTransparentPixel(
                        startX - position.x, endX1, yOfPosition
                );

                if (absolute1 == stop1) {
                    continue;
                }

                final int yOfPosition2 = y - position2.y;
                int absolute2 = position2.x + collisionRaster2.nextNotTransparentPixel(
                        startX - position2.x, endX2, yOfPosition2
                );

                if (absolute2 == stop2) {
                    continue;
                }
                
                while (true) {
                    if (absolute1 > absolute2) {
                        absolute2 = position2.x + collisionRaster2.nextNotTransparentPixel(
                                absolute1 - position2.x, endX2, yOfPosition2
                        );
                        
                        if (absolute2 == stop2) {
                            break;
                        } 
                    } else if (absolute1 < absolute2) {
                        absolute1 = position.x + collisionRaster.nextNotTransparentPixel(
                                absolute2 - position.x, endX1, yOfPosition
                        );
                        
                        if (absolute1 == stop1) {
                            break;
                        } 
                    } else {
                        return true;
                    }
                }
            }
        }
        return false;
    }
134369
def intersects(self, other_grid_coordinates):
        
        ogc = other_grid_coordinates  # alias
        # for explanation: http://stackoverflow.com/questions/306316/determine-if-two-rectangles-overlap-each-other
        # Note the flipped y-coord in this coord system.
        ax1, ay1, ax2, ay2 = self.ULC.lon, self.ULC.lat, self.LRC.lon, self.LRC.lat
        bx1, by1, bx2, by2 = ogc.ULC.lon, ogc.ULC.lat, ogc.LRC.lon, ogc.LRC.lat
        if ((ax1 <= bx2) and (ax2 >= bx1) and (ay1 >= by2) and (ay2 <= by1)):
            return True
        else:
            return False