genmath.java

The ElectricTM VLSI Design System is an open-source Electronic Design Automation (EDA) system that c

    	d = hx*a + ly*b;   if (d < low1) low1 = d;   if (d > high1) high1 = d;
    	d = hx*a + hy*b;   if (d < low1) low1 = d;   if (d > high1) high1 = d;
    	d = lx*a + hy*b;   if (d < low1) low1 = d;   if (d > high1) high1 = d;

    	// get the range of distances from the line to port 2
    	lx = lx2;   hx = hx2;   ly = ly2;   hy = hy2;
    	d = lx*a + ly*b;   double low2 = d;   double high2 = d;
    	d = hx*a + ly*b;   if (d < low2) low2 = d;   if (d > high2) high2 = d;
    	d = hx*a + hy*b;   if (d < low2) low2 = d;   if (d > high2) high2 = d;
    	d = lx*a + hy*b;   if (d < low2) low2 = d;   if (d > high2) high2 = d;

    	// if the ranges do not overlap, a line cannot be drawn
    	if (low1 > high2 || low2 > high1) return null;

    	// the line can be drawn: determine equation (aX + bY = d)
    	d = ((low1 > low2 ? low1 : low2) + (high1 < high2 ? high1 : high2)) / 2.0f;

    	// determine intersection with polygon 1
    	points[0] = db_findconnectionpoint(lx1, hx1, ly1, hy1, a, b, d);
    	points[0] = db_findconnectionpoint(lx2, hx2, ly2, hy2, a, b, d);
    	return points;
    }

    /**
     * Method to find a point inside the rectangle bounded by (lx<=X<=hx, ly<=Y<=hy)
     * that satisfies the equation aX + bY = d.  Returns the point in (x,y).
     */
    private static Point2D db_findconnectionpoint(double lx, double hx, double ly, double hy, double a, double b, double d)
    {
     	if (a != 0.0)
    	{
    		double out = (d - b * ly) / a;
    		if (out >= lx && out <= hx) return new Point2D.Double(out, ly);
    		out = (d - b * hy) / a;
    		if (out >= lx && out <= hx) return new Point2D.Double(out, hy);
    	}
    	if (b != 0.0)
    	{
    		double out = (d - b * lx) / a;
    		if (out >= ly && out <= hy) return new Point2D.Double(lx, out);
    		out = (d - b * hx) / a;
    		if (out >= ly && out <= hy) return new Point2D.Double(hx, out);
    	}

    	// not the right solution, but nothing else works
    	return new Point2D.Double((lx+hx) / 2, (ly+hy) / 2);
    }

    /**
     * Method to calcute Euclidean distance between two points.
     * @param p1 the first point.
     * @param p2 the second point.
     * @return the distance between the points.
     */
    public static double distBetweenPoints(Point2D p1, Point2D p2)
    {
        double deltaX = p1.getX() - p2.getX();
        double deltaY = p1.getY() - p2.getY();
        return (Math.hypot(deltaX, deltaY));
    }

    /**
     * Method to compute the distance between point (x,y) and the line that runs
     * from (x1,y1) to (x2,y2).
     */
    public static double distToLine(Point2D l1, Point2D l2, Point2D pt)
    {
        // get point on line from (x1,y1) to (x2,y2) close to (x,y)
        double x1 = l1.getX();   double y1 = l1.getY();
        double x2 = l2.getX();   double y2 = l2.getY();
        if (doublesEqual(x1, x2) && doublesEqual(y1, y2))
        {
            return pt.distance(l1);
        }
        int ang = figureAngle(l1, l2);
        Point2D iPt = intersect(l1, ang, pt, ang+900);
        double iX = iPt.getX();
        double iY = iPt.getY();
        if (doublesEqual(x1, x2)) iX = x1;
        if (doublesEqual(y1, y2)) iY = y1;

        // make sure (ix,iy) is on the segment from (x1,y1) to (x2,y2)
        if (iX < Math.min(x1,x2) || iX > Math.max(x1,x2) ||
                iY < Math.min(y1,y2) || iY > Math.max(y1,y2))
        {
            if (Math.abs(iX-x1) + Math.abs(iY-y1) < Math.abs(iX-x2) + Math.abs(iY-y2))
            {
                iX = x1;   iY = y1;
            } else
            {
                iX = x2;   iY = y2;
            }
        }
        iPt.setLocation(iX, iY);
        return iPt.distance(pt);
    }

	/**
	 * Method used by "ioedifo.c" and "routmaze.c".
	 */
	public static Point2D computeArcCenter(Point2D c, Point2D p1, Point2D p2)
	{
		// reconstruct angles to p1 and p2
		double radius = p1.distance(c);
		double a1 = calculateAngle(radius, p1.getX() - c.getX(), p1.getY() - c.getY());
		double a2 = calculateAngle(radius, p2.getX() - c.getX(), p1.getY() - c.getY());
		if (a1 < a2) a1 += 3600;
		double a = (a1 + a2) / 2;
		double theta = a * Math.PI / 1800.0;	/* in radians */
		return new Point2D.Double(c.getX() + radius * Math.cos(theta), c.getY() + radius * Math.sin(theta));
	}

	private static double calculateAngle(double r, double dx, double dy)
	{
		double ratio, a1, a2;

		ratio = 1800.0 / Math.PI;
		a1 = Math.acos(dx/r) * ratio;
		a2 = Math.asin(dy/r) * ratio;
		if (a2 < 0.0) return 3600.0 - a1;
		return a1;
	}

    /**
     * Method to find the two possible centers for a circle given a radius and two edge points.
     * @param r the radius of the circle.
     * @param p1 one point on the edge of the circle.
     * @param p2 the other point on the edge of the circle.
     * @return an array of two Point2Ds, either of which could be the center.
     * Returns null if there are no possible centers.
     * This code was written by John Mohammed of Schlumberger.
     */
    public static Point2D [] findCenters(double r, Point2D p1, Point2D p2)
    {
        // quit now if the circles concentric
        if (p1.getX() == p2.getX() && p1.getY() == p2.getY()) return null;

        // find the intersections, if any
        double d = p1.distance(p2);
        double r2 = r * r;
        double delta_1 = -d / 2.0;
        double delta_12 = delta_1 * delta_1;

        // quit if there are no intersections
        if (r2 < delta_12) return null;

        // compute the intersection points
        double delta_2 = Math.sqrt(r2 - delta_12);
        double x1 = p2.getX() + ((delta_1 * (p2.getX() - p1.getX())) + (delta_2 * (p2.getY() - p1.getY()))) / d;
        double y1 = p2.getY() + ((delta_1 * (p2.getY() - p1.getY())) + (delta_2 * (p1.getX() - p2.getX()))) / d;
        double x2 = p2.getX() + ((delta_1 * (p2.getX() - p1.getX())) + (delta_2 * (p1.getY() - p2.getY()))) / d;
        double y2 = p2.getY() + ((delta_1 * (p2.getY() - p1.getY())) + (delta_2 * (p2.getX() - p1.getX()))) / d;
        Point2D [] retArray = new Point2D[2];
        retArray[0] = new Point2D.Double(x1, y1);
        retArray[1] = new Point2D.Double(x2, y2);
        return retArray;
    }

    /**
     * Method to determine the intersection of two lines and return that point.
     * @param p1 a point on the first line.
     * @param ang1 the angle of the first line (in tenth degrees).
     * @param p2 a point on the second line.
     * @param ang2 the angle of the second line (in tenth degrees).
     * @return a point that is the intersection of the lines.
     * Returns null if there is no intersection point.
     */
    public static Point2D intersect(Point2D p1, int ang1, Point2D p2, int ang2)
    {
        // cannot handle lines if they are at the same angle
        while (ang1 < 0) ang1 += 3600;
        if (ang1 >= 3600) ang1 %= 3600;
        while (ang2 < 0) ang2 += 3600;
        if (ang2 >= 3600) ang2 %= 3600;
        if (ang1 == ang2) return null;

        // also cannot handle lines that are off by 180 degrees
        int amin = ang2, amax = ang1;
        if (ang1 < ang2)
        {
            amin = ang1;   amax = ang2;
        }
        if (amin + 1800 == amax) return null;

        double fa1 = sin(ang1);
        double fb1 = -cos(ang1);
        double fc1 = -fa1 * p1.getX() - fb1 * p1.getY();
        double fa2 = sin(ang2);
        double fb2 = -cos(ang2);
        double fc2 = -fa2 * p2.getX() - fb2 * p2.getY();
        if (Math.abs(fa1) < Math.abs(fa2))
        {
            double fswap = fa1;   fa1 = fa2;   fa2 = fswap;
            fswap = fb1;   fb1 = fb2;   fb2 = fswap;
            fswap = fc1;   fc1 = fc2;   fc2 = fswap;
        }
        double fy = (fa2 * fc1 / fa1 - fc2) / (fb2 - fa2*fb1/fa1);
        return new Point2D.Double((-fb1 * fy - fc1) / fa1, fy);
    }

    /**
     * Method to determine the intersection of two lines and return that point.
     * @param p1 a point on the first line.
     * @param ang1 the angle of the first line (in radians).
     * @param p2 a point on the second line.
     * @param ang2 the angle of the second line (in radians).
     * @return a point that is the intersection of the lines.
     * Returns null if there is no intersection point.
     */
    public static Point2D intersectRadians(Point2D p1, double ang1, Point2D p2, double ang2)
    {
        // cannot handle lines if they are at the same angle
    	while (ang1 > Math.PI) ang1 -= Math.PI;
    	while (ang1 < 0) ang1 += Math.PI;
    	while (ang2 > Math.PI) ang2 -= Math.PI;
    	while (ang2 < 0) ang2 += Math.PI;
        if (doublesClose(ang1, ang2)) return null;

        // also at the same angle if off by 180 degrees
        double fMin = ang2, fMax = ang2;
        if (ang1 < ang2) { fMin = ang1; fMax = ang2; }
        if (doublesClose(fMin + Math.PI, fMax)) return null;

        double fa1 = Math.sin(ang1);
        double fb1 = -Math.cos(ang1);
        double fc1 = -fa1 * p1.getX() - fb1 * p1.getY();
        double fa2 = Math.sin(ang2);
        double fb2 = -Math.cos(ang2);
        double fc2 = -fa2 * p2.getX() - fb2 * p2.getY();
        if (Math.abs(fa1) < Math.abs(fa2))
        {
            double fswap = fa1;   fa1 = fa2;   fa2 = fswap;
            fswap = fb1;   fb1 = fb2;   fb2 = fswap;
            fswap = fc1;   fc1 = fc2;   fc2 = fswap;
        }
        double fy = (fa2 * fc1 / fa1 - fc2) / (fb2 - fa2*fb1/fa1);
        return new Point2D.Double((-fb1 * fy - fc1) / fa1, fy);
    }

	/**
	 * Method to compute the bounding box of the arc that runs clockwise from
	 * "s" to "e" and is centered at "c".  The bounding box is returned.
	 */
	public static Rectangle2D arcBBox(Point2D s, Point2D e, Point2D c)
	{
		// determine radius and compute bounds of full circle
		double radius = c.distance(s);
		double lx = c.getX() - radius;
		double ly = c.getY() - radius;
		double hx = c.getX() + radius;
		double hy = c.getY() + radius;

		// compute quadrant of two endpoints
		double x1 = s.getX() - c.getX();    double x2 = e.getX() - c.getX();
		double y1 = s.getY() - c.getY();    double y2 = e.getY() - c.getY();
		int q1 = db_quadrant(x1, y1);
		int q2 = db_quadrant(x2, y2);

		// see if the two endpoints are in the same quadrant
		if (q1 == q2)
		{
			// if the arc runs a full circle, use the MBR of the circle
			if (q1 == 1 || q1 == 2)
			{
				if (x1 > x2) return new Rectangle2D.Double(lx, ly, hx-lx, hy-ly);;
			} else
			{
				if (x1 < x2) return new Rectangle2D.Double(lx, ly, hx-lx, hy-ly);;
			}

			// use the MBR of the two arc points
			lx = Math.min(s.getX(), e.getX());
			hx = Math.max(s.getX(), e.getX());
			ly = Math.min(s.getY(), e.getY());
			hy = Math.max(s.getY(), e.getY());
			return new Rectangle2D.Double(lx, ly, hx-lx, hy-ly);
		}

		switch (q1)
		{
			case 1: switch (q2)
			{
				case 2:	// 3 quadrants clockwise from Q1 to Q2
				hy = Math.max(y1,y2) + c.getY();
				break;

				case 3:	// 2 quadrants clockwise from Q1 to Q3
				lx = x2 + c.getX();
				hy = y1 + c.getY();
				break;

				case 4:	// 1 quadrant clockwise from Q1 to Q4
				lx = Math.min(x1,x2) + c.getX();
				ly = y2 + c.getY();
				hy = y1 + c.getY();
				break;
			}
			break;

			case 2: switch (q2)
			{
				case 1:	// 1 quadrant clockwise from Q2 to Q1
				lx = x1 + c.getX();
				ly = Math.min(y1,y2) + c.getY();
				hx = x2 + c.getX();
				break;

				case 3:	// 3 quadrants clockwise from Q2 to Q3
				lx = Math.min(x1,x2) + c.getX();
				break;

				case 4:	// 2 quadrants clockwise from Q2 to Q4
				lx = x1 + c.getX();
				ly = y2 + c.getY();
				break;
			}
			break;

			case 3: switch (q2)
			{
				case 1:	// 2 quadrants clockwise from Q3 to Q1
				ly = y1 + c.getY();
				hx = x2 + c.getX();
				break;

				case 2:	// 1 quadrant clockwise from Q3 to Q2
				ly = y1 + c.getY();
				hx = Math.max(x1,x2) + c.getX();
				hy = y2 + c.getY();
				break;

				case 4:	// 3 quadrants clockwise from Q3 to Q4
				ly = Math.min(y1,y2) + c.getY();
				break;
			}