polygon.java

来自「纯java操作系统jnode,安装简单和操作简单的个人使用的Java操作系统」· Java 代码 · 共 752 行 · 第 1/2 页

    boolean inside = false;
    int limit = condensed[0];
    int curx = condensed[(limit << 1) - 1];
    int cury = condensed[limit << 1];
    for (int i = 1; i <= limit; i++)
      {
        int priorx = curx;
        int priory = cury;
        curx = condensed[(i << 1) - 1];
        cury = condensed[i << 1];
        if ((priorx > x && curx > x) // Left of segment, or NaN.
            || (priory > y && cury > y) // Below segment, or NaN.
            || (priory < y && cury < y)) // Above segment.
          continue;
        if (priory == cury) // Horizontal segment, y == cury == priory
          {
            if (priorx < x && curx < x) // Right of segment.
              {
                inside = ! inside;
                continue;
              }
            // Did we approach this segment from above or below?
            // This mess is necessary to obey rules of Shape.
            priory = condensed[((limit + i - 2) % limit) << 1];
            boolean above = priory > cury;
            if ((curx == x && (curx > priorx || above))
                || (priorx == x && (curx < priorx || ! above))
                || (curx > priorx && ! above) || above)
              inside = ! inside;
            continue;
          }
        if (priorx == x && priory == y) // On prior vertex.
          continue;
        if (priorx == curx // Vertical segment.
            || (priorx < x && curx < x)) // Right of segment.
          {
            inside = ! inside;
            continue;
          }
        // The point is inside the segment's bounding box, compare slopes.
        double leftx = curx > priorx ? priorx : curx;
        double lefty = curx > priorx ? priory : cury;
        double slopeseg = (double) (cury - priory) / (curx - priorx);
        double slopepoint = (double) (y - lefty) / (x - leftx);
        if ((slopeseg > 0 && slopeseg > slopepoint)
            || slopeseg < slopepoint)
          inside = ! inside;
      }
    return inside;
  }

  /**
   * Tests whether or not the specified point is inside this polygon.
   *
   * @param p the point to test
   * @return true if the point is inside this polygon
   * @throws NullPointerException if p is null
   * @see #contains(double, double)
   * @since 1.2
   */
  public boolean contains(Point2D p)
  {
    return contains(p.getX(), p.getY());
  }

  /**
   * Test if a high-precision rectangle intersects the shape. This is true
   * if any point in the rectangle is in the shape. This implementation is
   * precise.
   *
   * @param x the x coordinate of the rectangle
   * @param y the y coordinate of the rectangle
   * @param w the width of the rectangle, treated as point if negative
   * @param h the height of the rectangle, treated as point if negative
   * @return true if the rectangle intersects this shape
   * @since 1.2
   */
  public boolean intersects(double x, double y, double w, double h)
  {
    // First, the obvious bounds checks.
    if (w <= 0 || h <= 0 || npoints == 0 ||
        ! getBounds().intersects(x, y, w, h))
      return false; // Disjoint bounds.
    if ((x <= bounds.x && x + w >= bounds.x + bounds.width
         && y <= bounds.y && y + h >= bounds.y + bounds.height)
        || contains(x, y))
      return true; // Rectangle contains the polygon, or one point matches.
    // If any vertex is in the rectangle, the two might intersect.
    int curx = 0;
    int cury = 0;
    for (int i = 0; i < npoints; i++)
      {
        curx = xpoints[i];
        cury = ypoints[i];
        if (curx >= x && curx < x + w && cury >= y && cury < y + h
            && contains(curx, cury)) // Boundary check necessary.
          return true;
      }
    // Finally, if at least one of the four bounding lines intersect any
    // segment of the polygon, return true. Be careful of the semantics of
    // Shape; coinciding lines do not necessarily return true.
    for (int i = 0; i < npoints; i++)
      {
        int priorx = curx;
        int priory = cury;
        curx = xpoints[i];
        cury = ypoints[i];
        if (priorx == curx) // Vertical segment.
          {
            if (curx < x || curx >= x + w) // Outside rectangle.
              continue;
            if ((cury >= y + h && priory <= y)
                || (cury <= y && priory >= y + h))
              return true; // Bisects rectangle.
            continue;
          }
        if (priory == cury) // Horizontal segment.
          {
            if (cury < y || cury >= y + h) // Outside rectangle.
              continue;
            if ((curx >= x + w && priorx <= x)
                || (curx <= x && priorx >= x + w))
              return true; // Bisects rectangle.
            continue;
          }
        // Slanted segment.
        double slope = (double) (cury - priory) / (curx - priorx);
        double intersect = slope * (x - curx) + cury;
        if (intersect > y && intersect < y + h) // Intersects left edge.
          return true;
        intersect = slope * (x + w - curx) + cury;
        if (intersect > y && intersect < y + h) // Intersects right edge.
          return true;
        intersect = (y - cury) / slope + curx;
        if (intersect > x && intersect < x + w) // Intersects bottom edge.
          return true;
        intersect = (y + h - cury) / slope + cury;
        if (intersect > x && intersect < x + w) // Intersects top edge.
          return true;
      }
    return false;
  }

  /**
   * Test if a high-precision rectangle intersects the shape. This is true
   * if any point in the rectangle is in the shape. This implementation is
   * precise.
   *
   * @param r the rectangle
   * @return true if the rectangle intersects this shape
   * @throws NullPointerException if r is null
   * @see #intersects(double, double, double, double)
   * @since 1.2
   */
  public boolean intersects(Rectangle2D r)
  {
    return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight());
  }

  /**
   * Test if a high-precision rectangle lies completely in the shape. This is
   * true if all points in the rectangle are in the shape. This implementation
   * is precise.
   *
   * @param x the x coordinate of the rectangle
   * @param y the y coordinate of the rectangle
   * @param w the width of the rectangle, treated as point if negative
   * @param h the height of the rectangle, treated as point if negative
   * @return true if the rectangle is contained in this shape
   * @since 1.2
   */
  public boolean contains(double x, double y, double w, double h)
  {
    // First, the obvious bounds checks.
    if (w <= 0 || h <= 0 || ! contains(x, y)
        || ! bounds.contains(x, y, w, h))
      return false;
    // Now, if any of the four bounding lines intersects a polygon segment,
    // return false. The previous check had the side effect of setting
    // the condensed array, which we use. Be careful of the semantics of
    // Shape; coinciding lines do not necessarily return false.
    int limit = condensed[0];
    int curx = condensed[(limit << 1) - 1];
    int cury = condensed[limit << 1];
    for (int i = 1; i <= limit; i++)
      {
        int priorx = curx;
        int priory = cury;
        curx = condensed[(i << 1) - 1];
        cury = condensed[i << 1];
        if (curx > x && curx < x + w && cury > y && cury < y + h)
          return false; // Vertex is in rectangle.
        if (priorx == curx) // Vertical segment.
          {
            if (curx < x || curx > x + w) // Outside rectangle.
              continue;
            if ((cury >= y + h && priory <= y)
                || (cury <= y && priory >= y + h))
              return false; // Bisects rectangle.
            continue;
          }
        if (priory == cury) // Horizontal segment.
          {
            if (cury < y || cury > y + h) // Outside rectangle.
              continue;
            if ((curx >= x + w && priorx <= x)
                || (curx <= x && priorx >= x + w))
              return false; // Bisects rectangle.
            continue;
          }
        // Slanted segment.
        double slope = (double) (cury - priory) / (curx - priorx);
        double intersect = slope * (x - curx) + cury;
        if (intersect > y && intersect < y + h) // Intersects left edge.
          return false;
        intersect = slope * (x + w - curx) + cury;
        if (intersect > y && intersect < y + h) // Intersects right edge.
          return false;
        intersect = (y - cury) / slope + curx;
        if (intersect > x && intersect < x + w) // Intersects bottom edge.
          return false;
        intersect = (y + h - cury) / slope + cury;
        if (intersect > x && intersect < x + w) // Intersects top edge.
          return false;
      }
    return true;
  }

  /**
   * Test if a high-precision rectangle lies completely in the shape. This is
   * true if all points in the rectangle are in the shape. This implementation
   * is precise.
   *
   * @param r the rectangle
   * @return true if the rectangle is contained in this shape
   * @throws NullPointerException if r is null
   * @see #contains(double, double, double, double)
   * @since 1.2
   */
  public boolean contains(Rectangle2D r)
  {
    return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight());
  }

  /**
   * Return an iterator along the shape boundary. If the optional transform
   * is provided, the iterator is transformed accordingly. Each call returns
   * a new object, independent from others in use. This class is not
   * threadsafe to begin with, so the path iterator is not either.
   *
   * @param transform an optional transform to apply to the iterator
   * @return a new iterator over the boundary
   * @since 1.2
   */
  public PathIterator getPathIterator(final AffineTransform transform)
  {
    return new PathIterator()
    {
      /** The current vertex of iteration. */
      private int vertex;

      public int getWindingRule()
      {
        return WIND_EVEN_ODD;
      }

      public boolean isDone()
      {
        return vertex > npoints;
      }

      public void next()
      {
        vertex++;
      }

      public int currentSegment(float[] coords)
      {
        if (vertex >= npoints)
          return SEG_CLOSE;
        coords[0] = xpoints[vertex];
        coords[1] = ypoints[vertex];
        if (transform != null)
          transform.transform(coords, 0, coords, 0, 1);
        return vertex == 0 ? SEG_MOVETO : SEG_LINETO;
      }

      public int currentSegment(double[] coords)
      {
        if (vertex >= npoints)
          return SEG_CLOSE;
        coords[0] = xpoints[vertex];
        coords[1] = ypoints[vertex];
        if (transform != null)
          transform.transform(coords, 0, coords, 0, 1);
        return vertex == 0 ? SEG_MOVETO : SEG_LINETO;
      }
    };
  }

  /**
   * Return an iterator along the flattened version of the shape boundary.
   * Since polygons are already flat, the flatness parameter is ignored, and
   * the resulting iterator only has SEG_MOVETO, SEG_LINETO and SEG_CLOSE
   * points. If the optional transform is provided, the iterator is
   * transformed accordingly. Each call returns a new object, independent
   * from others in use. This class is not threadsafe to begin with, so the
   * path iterator is not either.
   *
   * @param transform an optional transform to apply to the iterator
   * @param double the maximum distance for deviation from the real boundary
   * @return a new iterator over the boundary
   * @since 1.2
   */
  public PathIterator getPathIterator(AffineTransform transform,
                                      double flatness)
  {
    return getPathIterator(transform);
  }

  /**
   * Helper for contains, which caches a condensed version of the polygon.
   * This condenses all colinear points, so that consecutive segments in
   * the condensed version always have different slope.
   *
   * @return true if the condensed polygon has area
   * @see #condensed
   * @see #contains(double, double)
   */
  private boolean condense()
  {
    if (npoints <= 2)
      return false;
    if (condensed != null)
      return condensed[0] > 2;
    condensed = new int[npoints * 2 + 1];
    int curx = xpoints[npoints - 1];
    int cury = ypoints[npoints - 1];
    double curslope = Double.NaN;
    int count = 0;
  outer:
    for (int i = 0; i < npoints; i++)
      {
        int priorx = curx;
        int priory = cury;
        double priorslope = curslope;
        curx = xpoints[i];
        cury = ypoints[i];
        while (curx == priorx && cury == priory)
          {
            if (++i == npoints)
              break outer;
            curx = xpoints[i];
            cury = ypoints[i];
          }
        curslope = (curx == priorx ? Double.POSITIVE_INFINITY
                    : (double) (cury - priory) / (curx - priorx));
        if (priorslope == curslope)
          {
            if (count > 1 && condensed[(count << 1) - 3] == curx
                && condensed[(count << 1) - 2] == cury)
              {
                count--;
                continue;
              }
          }
        else
          count++;
        condensed[(count << 1) - 1] = curx;
        condensed[count << 1] = cury;
      }
    condensed[0] = count;
    return count > 2;
  }
} // class Polygon