import math.geom2d.Point2D; //导入依赖的package包/类
/**
 * Gets the distance of the StraightObject2d to the given point. This method
 * is not designed to be used directly, because AbstractLine2D is an
 * abstract class, but it can be used by subclasses to help computations.
 * 
 * @param x x-coordinate of the point
 * @param y y-coordinate of the point
 * @return distance between this object and the point (x,y)
 */
public double getDistance(double x, double y) {
	// first project on the line
    Point2D proj = getProjectedPoint(x, y);
    
    // if the line contains the projection, returns the distance
    if (contains(proj))
        return proj.distance(x, y);
    
    // otherwise, returns the distance to the closest singular point
    double dist = Double.POSITIVE_INFINITY;
    if(!Double.isInfinite(getT0()))
    	dist = getFirstPoint().getDistance(x, y);
    if(!Double.isInfinite(getT1()))
    	dist = Math.min(dist, getLastPoint().getDistance(x, y));
   	return dist;
}
 

import math.geom2d.Point2D; //导入依赖的package包/类
/**
 * Gets border point of the mesh for the path between specified points.
 *
 * @param start Start of the path.
 * @param end End of the path.
 * @return Border point in the direction of the path.
 */
public BorderPoint getBorderPoint(Location start, Location end) {
	
    // compute the direction from start to end
	Vector2D direction = new Vector2D( new Point2D( start.x, start.y ), new Point2D( end.x, end.y ) );

	ClearanceLimit clearanceLimit = clearanceComputer.findEdge(start, direction, direction.getNorm(), NavMeshDropGrounder.DEFAULT_GROUND_DISTANCE);

	if ( clearanceLimit == null ) {
		return new BorderPoint(end, null); // no edge found, use start
	} else if ( clearanceLimit.getLocation() == start ) {
		return new BorderPoint(start, null); // failed to ground start
	} else {
		return new BorderPoint( clearanceLimit.getLocation().addZ( NavMeshConstants.liftPolygonLocation ), null);  
	}
}
 

import math.geom2d.Point2D; //导入依赖的package包/类
/** Get parametric representation of intersection with another linear shape
 * 
 * @param other the other linear shape
 * @return parametric representation of the intersection or NaN if doesn't exist (parallel lines, etc)
 */
public double getIntersectionParametric(LinearShape2D line) {
    Vector2D vect = line.getVector();
    double dx2 = vect.getX();
    double dy2 = vect.getY();

    // test if two lines are parallel
    if (Math.abs(dx*dy2-dy*dx2)<Shape2D.ACCURACY)
        return Double.NaN;

    // compute position on the line
    Point2D origin = line.getOrigin();
    double x2 = origin.getX();
    double y2 = origin.getY();
    double t = ((y0-y2)*dx2-(x0-x2)*dy2)/(dx*dy2-dy*dx2);
    
	if ( !containsParametric( t ) ) {
		return Double.NaN;
	}
	
	if ( !line.contains( getPoint(t) ) ) {
		return Double.NaN;
	}
	
	return t;
}
 

import math.geom2d.Point2D; //导入依赖的package包/类
/**
 * Return all intersection points between the 2 polylines.
 * @param poly1 a polyline
 * @param poly2 a polyline
 * @return the set of intersection points
 */
public final static Collection<Point2D> intersect(
        Polyline2D poly1, Polyline2D poly2) {
    ArrayList<Point2D> points = new ArrayList<Point2D>();
    
    Point2D point;
    for(LineSegment2D edge1 : poly1.getEdges()){
        for(LineSegment2D edge2 : poly2.getEdges()){
            point = edge1.getIntersection(edge2);
            if(point!=null)
                points.add(point);
        }
    }

    return points;
}
 

import math.geom2d.Point2D; //导入依赖的package包/类
/**
 * Transforms the parabola by an affine transform. The transformed parabola
 * is direct if this parabola and the affine transform are both either
 * direct or indirect.
 */
public Parabola2D transform(AffineTransform2D trans) {
	//TODO: check if transform work also for non-motion transforms...
    Point2D vertex = this.getVertex().transform(trans);
    Point2D focus = this.getFocus().transform(trans);
    double a = 1/(4.0*Point2D.getDistance(vertex, focus));
    double theta = Angle2D.getHorizontalAngle(vertex, focus)-Math.PI/2;

    // check orientation of resulting parabola
    if (this.a<0^trans.isDirect())
        // normal case
        return new Parabola2D(vertex, a, theta);
    else
        // inverted case
        return new Parabola2D(vertex, -a, theta+Math.PI);
}
 

import math.geom2d.Point2D; //导入依赖的package包/类
public PointSet2D getVertices(Box2D box) {
    double x, y; // iterations
    double xmin, ymin, xmax, ymax; // limits
    double xi, yi; // first point in the box

    // extract bounds of the box
    xmin = box.getMinX();
    ymin = box.getMinY();
    xmax = box.getMaxX();
    ymax = box.getMaxY();

    // coordinates of first vertex in the box
    xi = Math.ceil((xmin-x0)/sx)*sx+x0;
    yi = Math.ceil((ymin-y0)/sy)*sy+y0;

    ArrayList<Point2D> array = new ArrayList<Point2D>();

    // iterate on lines in each direction
    for (y = yi; y-ymax<Shape2D.ACCURACY; y += sy)
        for (x = xi; x-xmax<Shape2D.ACCURACY; x += sx)
            array.add(new Point2D(x, y));

    // return the set of lines
    return new PointArray2D(array);
}
 

import math.geom2d.Point2D; //导入依赖的package包/类
public java.awt.geom.GeneralPath appendPath(java.awt.geom.GeneralPath path) {
	// Check curve is bounded
    if (!this.isBounded())
        throw new UnboundedShapeException(this);

    // Compute position and tangent at extremities
    Point2D p1 = this.getFirstPoint();
    Point2D p2 = this.getLastPoint();
    Vector2D v1 = this.getTangent(this.getT0());
    Vector2D v2 = this.getTangent(this.getT1());
    
    // Compute tangent lines at extremities
    StraightLine2D line1 = new StraightLine2D(p1, v1);
    StraightLine2D line2 = new StraightLine2D(p2, v2);
    
    // Compute intersection point of tangent lines
    Point2D pc = line1.getIntersection(line2);
    
    // Use quadratic curve to represent (exactly) the parabola arc
    path.quadTo(pc.getX(), pc.getY(), p2.getX(), p2.getY());
    return path;
}
 

import math.geom2d.Point2D; //导入依赖的package包/类
private boolean contains(Point2D point, Node node, int depth){
    if(node==null) return false;
    
    // select direction
    int dir = depth%2;
    
    // sort points according to i-th dimension
    int res;
    if(dir==0){
        // Compare points based on their x-coordinate
        res = xComparator.compare(point, node.point);
    }else{
        // Compare points based on their x-coordinate
        res = yComparator.compare(point, node.point);
    }
    
    if(res<0)
        return contains(point, node.left, depth+1);
    if(res>0)
        return contains(point, node.right, depth+1);
    
    return true;
}
 

import math.geom2d.Point2D; //导入依赖的package包/类
private Point2D findNextPoint(Point2D basePoint, double startAngle,
        Collection<? extends Point2D> points) {
    Point2D minPoint = null;
    double minAngle = Double.MAX_VALUE;
    double angle;

    for (Point2D point : points) {
        // Avoid to test same point
        if (basePoint.equals(point))
            continue;

        // Compute angle between current direction and next point
        angle = Angle2D.getHorizontalAngle(basePoint, point);
        angle = Angle2D.formatAngle(angle-startAngle);

        // Keep current point if angle is minimal
        if (angle<minAngle) {
            minAngle = angle;
            minPoint = point;
        }
    }

    return minPoint;
}
 

import math.geom2d.Point2D; //导入依赖的package包/类
/**
 * Creates a series a cubic bezier curves, by grouping consecutive couples
 * of points and vectors. A polycurve composed of N Bezier curves requires
 * N+1 points and N+1 vectors. 
 */
public final static PolyCubicBezierCurve2D create(
		Point2D[] points, Vector2D[] vectors){
	// number of points
	int np = Math.min(points.length, vectors.length);
	
	// compute number of curves
	int nc = (np-1)/2;
	
	// create array of curves
	PolyCubicBezierCurve2D polyBezier = new PolyCubicBezierCurve2D(nc);
	
	// build each curve
	for(int i=0; i<nc; i++)
		polyBezier.addCurve(new CubicBezierCurve2D(
				points[i*2], vectors[i*2], points[i*2+1], vectors[i*2+1]));
	
	// return the curve
	return polyBezier;
}
 

import math.geom2d.Point2D; //导入依赖的package包/类
/**
 * Computes the approximate projection position of the point on the ellipse.
 * The ellipse is first converted to a unit circle, then the angular
 * position of the point is computed in the transformed basis.
 */
public double project(java.awt.geom.Point2D point) {
    double xp = point.getX();
    double yp = point.getY();

    // translate
    xp = xp-this.xc;
    yp = yp-this.yc;

    // rotate
    double xp1 = xp*Math.cos(theta)+yp*Math.sin(theta);
    double yp1 = -xp*Math.sin(theta)+yp*Math.cos(theta);
    xp = xp1;
    yp = yp1;

    // scale
    xp = xp/this.r1;
    yp = yp/this.r2;

    // compute angle
    double angle = Angle2D.getHorizontalAngle(xp, yp);

    return angle;
}
 

import math.geom2d.Point2D; //导入依赖的package包/类
@Override
public double getSignedDistance(double x, double y) {
    double dist = getDistance(x, y);
    Point2D point = new Point2D(x, y);

    boolean direct = angleExtent>0;
    // boolean inCircle = Point2D.getDistance(x, y, xc, yc)<=r;
    boolean inCircle = circle.isInside(point);
    if (inCircle)
        return angleExtent>0 ? -dist : dist;

    Point2D p1 = circle.getPoint(startAngle);
    Point2D p2 = circle.getPoint(startAngle+angleExtent);
    boolean onLeft = (new StraightLine2D(p1, p2)).isInside(point);

    if (direct&&!onLeft)
        return dist;
    if (!direct&&onLeft)
        return -dist;

    boolean left1 = (new Ray2D(p1, circle.getTangent(startAngle)))
            .isInside(point);
    if (direct&&!left1)
        return dist;
    if (!direct&&left1)
        return -dist;

    boolean left2 = (new Ray2D(p2, circle
            .getTangent(startAngle+angleExtent))).isInside(point);
    if (direct&&!left2)
        return dist;
    if (!direct&&left2)
        return -dist;

    if (direct)
        return -dist;
    else
        return dist;
}
 

import math.geom2d.Point2D; //导入依赖的package包/类
/**
 * @see math.geom2d.domain.OrientedCurve2D#getSignedDistance(java.awt.geom.Point2D)
 */
public double getSignedDistance(double x, double y) {
    if (isInside(new Point2D(x, y)))
        return -getDistance(x, y);
    else
        return getDistance(x, y);
}
 

import math.geom2d.Point2D; //导入依赖的package包/类
@Override
public Point2D getPoint(double t) {
       if (curves.size()==0)
           return null;
       if (t<getT0())
           return this.getFirstCurve().getFirstPoint();
       if (t>getT1())
           return this.getLastCurve().getLastPoint();

       // curve index
       int nc = (int) Math.floor(t);

       // check index if even-> corresponds to a curve
       int indc = (int) Math.floor(nc/2);
       if (indc*2==nc) {
           Curve2D curve = curves.get(indc);
           double pos = Curve2DUtils.fromUnitSegment(t-nc, 
           		curve.getT0(), curve.getT1());
           return curve.getPoint(pos);
       } else {
           // return either last point of preceding curve,
           // or first point of next curve
           if (t-nc<.5)
               return curves.get(indc).getLastPoint();
           else
               return curves.get(indc+1).getFirstPoint();
       }
   }
 

import math.geom2d.Point2D; //导入依赖的package包/类
public CirculinearElement2D transform(CircleInversion2D inv) {
	// Extract inversion parameters
       Point2D center 	= inv.getCenter();
       double r 		= inv.getRadius();
       
       // compute distance of line to inversion center
       Point2D po 	= new StraightLine2D(this).getProjectedPoint(center);
       double d 	= this.getDistance(po);
       
       // Degenerate case of a line passing through the center.
       // returns the line itself.
       if (Math.abs(d)<Shape2D.ACCURACY){
       	Point2D p1 = this.getFirstPoint().transform(inv);
       	Point2D p2 = this.getLastPoint().transform(inv);
       	return new LineSegment2D(p1, p2);
       }
       
       // angle from center to line
       double angle = Angle2D.getHorizontalAngle(center, po);

       // center of transformed circle
       double r2 	= r*r/d/2;
       Point2D c2 	= Point2D.createPolar(center, r2, angle);

       // choose direction of circle arc
       boolean direct = !this.isInside(center);
       
       // compute angle between center of transformed circle and end points
       double theta1 = Angle2D.getHorizontalAngle(c2, p1);
       double theta2 = Angle2D.getHorizontalAngle(c2, p2);
       
       // create the new circle arc
       return new CircleArc2D(c2, r2, theta1, theta2, direct);
}
 

import math.geom2d.Point2D; //导入依赖的package包/类
/**
 * return the first point, as this is the same as the last point.
 */
@Override
public Point2D getLastPoint() {
    if (points.size()==0)
        return null;
    return points.get(0);
}
 

import math.geom2d.Point2D; //导入依赖的package包/类
/**
 * Computes the signed area of the polyline. Algorithm is taken from page:
 * <a href="http://local.wasp.uwa.edu.au/~pbourke/geometry/polyarea/">
 * http://local.wasp.uwa.edu.au/~pbourke/geometry/polyarea/</a>. Signed are
 * is positive if polyline is oriented counter-clockwise, and negative
 * otherwise. Result is wrong if polyline is self-intersecting.
 * 
 * @return the signed area of the polyline.
 */
public double getSignedArea() {
    double area = 0;
    Point2D prev = this.points.get(this.points.size()-1);
    Point2D point;
    for (int i = 0; i<points.size(); i++) {
        point = this.points.get(i);
        area += prev.getX()*point.getY()-prev.getY()*point.getX();
        prev = point;
    }
    return area /= 2;
}
 

import math.geom2d.Point2D; //导入依赖的package包/类
private static CircleArc2D createCircularCap(Point2D p1, Point2D p2){
	Point2D center = Point2D.midPoint(p1, p2);
	double radius = p1.getDistance(p2)/2;
	double angle1 = Angle2D.getHorizontalAngle(center, p1);
	double angle2 = Angle2D.getHorizontalAngle(center, p2);
	return CircleArc2D.create(center, radius, angle1, angle2, true);
}
 

import math.geom2d.Point2D; //导入依赖的package包/类
public boolean contains(double x, double y) {
    // Check on parent parabola
    if (!parabola.contains(x, y))
        return false;
    
    // Check if position of point is inside of bounds
    double t = parabola.getPosition(new Point2D(x, y));
    if (t<this.t0)
        return false;
    if (t>this.t1)
        return false;

    return true;
}
 

import math.geom2d.Point2D; //导入依赖的package包/类
@Override
public ConicTwoLines2D transform(AffineTransform2D trans) {
    Point2D center = new Point2D(xc, yc).transform(trans);
    StraightLine2D line = this.getFirstCurve().transform(trans);

    return new ConicTwoLines2D(center, line.getDistance(center), line
            .getHorizontalAngle());
}