给大家几个关于几何的方法，希望有用O(∩_∩)O~

Question

网上找来的
判断一个点是否在一个矩形内：
  /**
   * Check if a specified point is inside a specified rectangle.
   * 
   * @param x0, y0, x1, y1  Upper left and lower right corner of rectangle
   *                        (inclusive)
   * @param x,y             Point to check.
   * @return                True if the point is inside the rectangle,
   *                        false otherwise.
   */
  public static boolean isPointInsideRectangle (int x0, int y0, int x1, int y1,
                                                int x, int y)
  {
    return x >= x0 && x < x1 && y >= y0 && y < y1;
  }
判断一个点是否在一个复杂的多边形内：
  /**
   * Check if a given point is inside a given (complex) polygon.
   * 
   * @param x, y            Polygon.
   * @param pointX, pointY  Point to check.
   * @return  True if the given point is inside the polygon, false otherwise.
   */
  public static boolean isPointInsidePolygon (double[] x, double[] y,
                                              double pointX, double pointY)
  {
    boolean  isInside = false;
    int nPoints = x.length;
    
    int j = 0;
    for (int i = 0; i < nPoints; i++) {
      j++;
      if (j == nPoints) j = 0;
      
      if (y[i] < pointY && y[j] >= pointY || y[j] < pointY && y[i] >= pointY) {
        if (x[i] + (pointY - y[i]) / (y[j] - y[i]) * (x[j] - x[i]) < pointX) {
          isInside = !isInside;
        }
      }
    }
    
    return isInside;
  }
判断两条直线是否相交：
  /**
   * Check if two line segments intersects. Integer domain.
   * 
   * @param x0, y0, x1, y1  End points of first line to check.
   * @param x2, yy, x3, y3  End points of second line to check.
   * @return                True if the two lines intersects.
   */
  public static boolean isLineIntersectingLine (int x0, int y0, int x1, int y1,
                                                int x2, int y2, int x3, int y3)
  {
    int s1 = Geometry.sameSide (x0, y0, x1, y1, x2, y2, x3, y3);
    int s2 = Geometry.sameSide (x2, y2, x3, y3, x0, y0, x1, y1);
    
    return s1 <= 0 && s2 <= 0;
  }
判断一条直线是否与一个矩形相交：
/**
   * Check if a specified line intersects a specified rectangle.
   * Integer domain.
   * 
   * @param lx0, ly0        1st end point of line
   * @param ly1, ly1        2nd end point of line
   * @param x0, y0, x1, y1  Upper left and lower right corner of rectangle
   *                        (inclusive).
   * @return                True if the line intersects the rectangle,
   *                        false otherwise.
   */
  public static boolean isLineIntersectingRectangle (int lx0, int ly0,
                                                     int lx1, int ly1,
                                                     int x0, int y0,
                                                     int x1, int y1)
  {
    // Is one of the line endpoints inside the rectangle
    if (Geometry.isPointInsideRectangle (x0, y0, x1, y1, lx0, ly0) ||
        Geometry.isPointInsideRectangle (x0, y0, x1, y1, lx1, ly1))
      return true;    // If it intersects it goes through. Need to check three sides only.    // Check against top rectangle line
    if (Geometry.isLineIntersectingLine (lx0, ly0, lx1, ly1,
                                         x0, y0, x1, y0))
      return true;    // Check against left rectangle line
    if (Geometry.isLineIntersectingLine (lx0, ly0, lx1, ly1,
                                         x0, y0, x0, y1))
      return true;    // Check against bottom rectangle line
    if (Geometry.isLineIntersectingLine (lx0, ly0, lx1, ly1,
                                         x0, y1, x1, y1))
      return true;    return false;
  }
判断一个多边形是否与一个矩形相交：
/**
   * Check if a specified polygon intersects a specified rectangle.
   * Integer domain.
   * 
   * @param x   X coordinates of polyline.
   * @param y   Y coordinates of polyline.   
   * @param x0  X of upper left corner of rectangle.
   * @param y0  Y of upper left corner of rectangle.   
   * @param x1  X of lower right corner of rectangle.
   * @param y1  Y of lower right corner of rectangle.   
   * @return    True if the polyline intersects the rectangle, false otherwise.
   */
  public static boolean isPolygonIntersectingRectangle (int[] x, int[] y,
                                                        int x0, int y0,
                                                        int x1, int y1)
  {
    int n = x.length;
    
    if (n == 0)
      return false;
    
    if (n == 1)
      return Geometry.isPointInsideRectangle (x0, y0, x1, y1, x[0], y[0]);
    
    //
    // If the polyline constituting the polygon intersects the rectangle
    // the polygon does too.
    //
    if (Geometry.isPolylineIntersectingRectangle (x, y, x0, y0, x1, y1))
      return true;
  
    // Check last leg as well
    if (Geometry.isLineIntersectingRectangle (x[n-2], y[n-2], x[n-1], y[n-1],
                                              x0, y0, x1, y1))
      return true;    //
    // The rectangle and polygon are now completely including each other
    // or separate.
    //
    if (Geometry.isPointInsidePolygon (x, y, x0, y0) ||
        Geometry.isPointInsideRectangle (x0, y0, x1, y1, x[0], y[0]))
      return true;
  
    // Separate
    return false;
  }

Answer 1

上述方法都在一个Geometry类里面

Answer 2

判断两个点是否在一条直线一边
/**
   * Check if two points are on the same side of a given line.
   * Algorithm from Sedgewick page 350.
   * 
   * @param x0, y0, x1, y1  The line.
   * @param px0, py0        First point.
   * @param px1, py1        Second point.
   * @return                <0 if points on opposite sides.
   *                        =0 if one of the points is exactly on the line
   *                        >0 if points on same side.
   */
  private static int sameSide (double x0, double y0, double x1, double y1,
                              double px0, double py0, double px1, double py1)
  {
    int  sameSide = 0;
    
    double dx  = x1  - x0;
    double dy  = y1  - y0;
    double dx1 = px0 - x0;
    double dy1 = py0 - y0;
    double dx2 = px1 - x1;
    double dy2 = py1 - y1;    // Cross product of the vector from the endpoint of the line to the point
    double c1 = dx * dy1 - dy * dx1;
    double c2 = dx * dy2 - dy * dx2;    if (c1 != 0 && c2 != 0)
      sameSide = c1 < 0 != c2 < 0 ? -1 : 1;
    else if (dx == 0 && dx1 == 0 && dx2 == 0)
      sameSide = !isBetween (y0, y1, py0) && !isBetween (y0, y1, py1) ? 1 : 0;
    else if (dy == 0 && dy1 == 0 && dy2 == 0)
      sameSide = !isBetween (x0, x1, px0) && !isBetween (x0, x1, px1) ? 1 : 0;    return sameSide;
  }
    
  /**
   * Check if two points are on the same side of a given line. Integer domain.
   * 
   * @param x0, y0, x1, y1  The line.
   * @param px0, py0        First point.
   * @param px1, py1        Second point.
   * @return                <0 if points on opposite sides.
   *                        =0 if one of the points is exactly on the line
   *                        >0 if points on same side.
   */
  private static int sameSide (int x0, int y0, int x1, int y1,
                               int px0, int py0, int px1, int py1)
  {
    return sameSide ((double) x0, (double) y0, (double) x1, (double) y1,
                     (double) px0, (double) py0, (double) px1, (double) py1);
  }