polybase.java

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

/* -*- tab-width: 4 -*-
 *
 * Electric(tm) VLSI Design System
 *
 * File: PolyBase.java
 *
 * Copyright (c) 2003 Sun Microsystems and Static Free Software
 *
 * Electric(tm) is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * Electric(tm) is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Electric(tm); see the file COPYING.  If not, write to
 * the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
 * Boston, Mass 02111-1307, USA.
 */
package com.sun.electric.database.geometry;

import com.sun.electric.database.hierarchy.Export;
import com.sun.electric.database.prototype.PortOriginal;
import com.sun.electric.database.prototype.PortProto;
import com.sun.electric.database.topology.NodeInst;
import com.sun.electric.database.topology.PortInst;
import com.sun.electric.database.variable.EditWindow0;
import com.sun.electric.database.variable.ElectricObject;
import com.sun.electric.technology.Layer;
import com.sun.electric.tool.Job;

import java.awt.Rectangle;
import java.awt.Shape;
import java.awt.font.GlyphVector;
import java.awt.geom.AffineTransform;
import java.awt.geom.Area;
import java.awt.geom.PathIterator;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.util.*;

/**
 * The Poly class describes an extended set of points
 * that can be outlines, filled shapes, curves, text, and more.
 * The Poly also contains a Layer and some connectivity information.
 */
public class PolyBase implements Shape, PolyNodeMerge
{

	/** the style (outline, text, lines, etc.) */			private Poly.Type style;
	/** the points */										protected Point2D points[];
	/** the layer (used for graphics) */					private Layer layer;
	/** the bounds of the points */							protected Rectangle2D bounds;
	/** the PortProto (if from a node or TEXT) */			private PortProto pp;
    /** the bit saying if the polygon is perfect rectangle */  private char bitRectangle = 2;  /** 2 not calculated, 0 not a rectangle, 1 a rectangle */

    /** represents X axis */                                public static final int X = 0;
    /** represents Y axis */                                public static final int Y = 1;
    /** represents Z axis */                                public static final int Z = 2;

	/**
	 * The constructor creates a new Poly given an array of points.
	 * @param points the array of coordinates.
	 */
	public PolyBase(Point2D [] points)
	{
		initialize(points);
	}

	/**
	 * The constructor creates a new Poly that describes a rectangle.
	 * @param cX the center X coordinate of the rectangle.
	 * @param cY the center Y coordinate of the rectangle.
	 * @param width the width of the rectangle.
	 * @param height the height of the rectangle.
	 */
	public PolyBase(double cX, double cY, double width, double height)
	{
		double halfWidth = width / 2;
		double halfHeight = height / 2;
		initialize(makePoints(cX-halfWidth, cX+halfWidth,cY-halfHeight , cY+halfHeight));
	}

	/**
	 * The constructor creates a new Poly that describes a rectangle.
	 * @param rect the Rectangle2D of the rectangle.
	 */
	public PolyBase(Rectangle2D rect)
	{
		initialize(makePoints(rect));
	}

	/**
	 * Method to create an array of Points that describes a Rectangle.
	 * @param lX the low X coordinate of the rectangle.
	 * @param hX the high X coordinate of the rectangle.
	 * @param lY the low Y coordinate of the rectangle.
	 * @param hY the high Y coordinate of the rectangle.
	 * @return an array of 4 Points that describes the Rectangle.
	 */
	public static Point2D [] makePoints(double lX, double hX, double lY, double hY)
	{
		return  new Point2D.Double[] {
			new Point2D.Double(lX, lY),
			new Point2D.Double(hX, lY),
			new Point2D.Double(hX, hY),
			new Point2D.Double(lX, hY)};
	}

	/**
	 * Method to create an array of Points that describes a Rectangle.
	 * @param rect the Rectangle.
	 * @return an array of 4 Points that describes the Rectangle.
	 */
	public static Point2D [] makePoints(Rectangle2D rect)
	{
		double lX = rect.getMinX();
		double hX = rect.getMaxX();
		double lY = rect.getMinY();
		double hY = rect.getMaxY();
		return new Point2D.Double[] {
			new Point2D.Double(lX, lY),
			new Point2D.Double(hX, lY),
			new Point2D.Double(hX, hY),
			new Point2D.Double(lX, hY)};
	}

	/**
	 * Method to help initialize this Poly.
	 */
	private void initialize(Point2D [] points)
	{
		this.style = Poly.Type.CLOSED;
		this.points = points;
		this.layer = null;
		this.bounds = null;
		this.pp = null;
	}

	/**
	 * Method to return the style associated with this Poly.
	 * The style controls how the points are interpreted (FILLED, CIRCLE, etc.)
	 * @return the style associated with this Poly.
	 */
	public Poly.Type getStyle() { return style; }

	/**
	 * Method to set the style associated with this Poly.
	 * The style controls how the points are interpreted (FILLED, CIRCLE, etc.)
	 * @param style the style associated with this Poly.
	 */
	public void setStyle(Poly.Type style) { this.style = style; }

	/**
	 * Method to return the points associated with this Poly.
	 * @return the points associated with this Poly.
	 */
	public Point2D [] getPoints() { return points; }

	/**
	 * Method to return the layer associated with this Poly.
	 * @return the layer associated with this Poly.
	 */
	public Layer getLayer() { return layer != null ? layer.getNonPseudoLayer() : layer; }

	/**
	 * Method to return the layer or pseudo-layer associated with this Poly.
	 * @return the layer or pseudo-layer associated with this Poly.
	 */
	public Layer getLayerOrPseudoLayer() { return layer; }

	/**
	 * Method to set the layer associated with this Poly.
	 * @param layer the layer associated with this Poly.
	 */
	public void setLayer(Layer layer) { this.layer = layer; }

	/**
	 * Method to tell if the layer associated with this Poly is a pseudo-layer.
	 * @return true if the layer associated with this Poly is a pseudo-layer.
	 */
	public boolean isPseudoLayer() { return layer != null && layer.isPseudoLayer(); }

	/**
	 * Method to return the PortProto associated with this Poly.
	 * This applies to ports on Nodes and Exports on Cells.
	 * @return the PortProto associated with this Poly.
	 */
	public PortProto getPort() { return pp; }

	/**
	 * Method to set the PortProto associated with this Poly.
	 * This applies to ports on Nodes and Exports on Cells.
	 * @param pp the PortProto associated with this Poly.
	 */
	public void setPort(PortProto pp) { this.pp = pp; }

	/**
	 * Method to transformed the points in this Poly.
	 * @param af transformation to apply.
	 */
	public void transform(AffineTransform af)
	{
		// Nothing to do
		if (af.getType() == AffineTransform.TYPE_IDENTITY) return;

		// special case for Poly type CIRCLEARC and THICKCIRCLEARC: if transposing, reverse points
		if (style == Poly.Type.CIRCLEARC || style == Poly.Type.THICKCIRCLEARC)
		{
			double det = af.getDeterminant();
			if (det < 0) for(int i=0; i<points.length; i += 3)
			{
				double x = points[i+1].getX();
				double y = points[i+1].getY();
				points[i+1].setLocation(points[i+2].getX(), points[i+2].getY());
				points[i+2].setLocation(x, y);
			}
		}
		af.transform(points, 0, points, 0, points.length);
		bounds = null;
	}

	/**
	 * Method to convert points from lambda units to grid units.
	 */
    public void lambdaToGrid() {
        for (Point2D p: points)
            p.setLocation(DBMath.lambdaToGrid(p.getX()), DBMath.lambdaToGrid(p.getY()));
        bounds = null;
    }
    
	/**
	 * Method to convert points from grid units to lambda units.
	 */
    public void gridToLambda() {
        for (Point2D p: points)
            p.setLocation(DBMath.gridToLambda(p.getX()), DBMath.gridToLambda(p.getY()));
        bounds = null;
    }
    
	/**
	 * Method to return a Rectangle that describes the orthogonal box in this Poly.
	 * @return the Rectangle that describes this Poly.
	 * If the Poly is not an orthogonal box, returns null.
	 * IT IS NOT PERMITTED TO MODIFY THE RETURNED RECTANGLE
	 * (because it is taken from the internal bounds of the Poly).
	 */
	public Rectangle2D getBox()
	{
        if (bitRectangle == 1)
            return getBounds2D();
        else if (bitRectangle == 0)
            return null;

        bitRectangle = 0;
        if (points.length == 4)
		{
			// only closed polygons and text can be boxes
			if (style != Poly.Type.FILLED && style != Poly.Type.CLOSED && style != Poly.Type.TEXTBOX && style != Poly.Type.CROSSED) return null;
		} else if (points.length == 5)
		{
			if (style != Poly.Type.FILLED && style != Poly.Type.CLOSED &&
				style != Poly.Type.OPENED && style != Poly.Type.OPENEDT1 &&
				style != Poly.Type.OPENEDT2 && style != Poly.Type.OPENEDT3) return null;
			if (points[0].getX() != points[4].getX() || points[0].getY() != points[4].getY()) return null;
		} else return null;

        // make sure the polygon is rectangular and orthogonal
		if (points[0].getX() == points[1].getX() && points[2].getX() == points[3].getX() &&
			points[0].getY() == points[3].getY() && points[1].getY() == points[2].getY())
		{
            bitRectangle = 1;
            return getBounds2D();
		}
		if (points[0].getX() == points[3].getX() && points[1].getX() == points[2].getX() &&
			points[0].getY() == points[1].getY() && points[2].getY() == points[3].getY())
		{
            bitRectangle = 1;
            return getBounds2D();
		}
		return null;
	}

	/**
	 * Method to compute the minimum size of this Polygon.
	 * Only works with manhattan geometry.
	 * @return the minimum dimension.
	 */
	public double getMinSize()
	{
		Rectangle2D box = getBox();
		if (box == null) return 0;
		return Math.min(box.getWidth(), box.getHeight());
	}

	/**
	 * Method to compute the maximum size of this Polygon.
	 * Only works with manhattan geometry.
	 */
	public double getMaxSize()
	{
		Rectangle2D box = getBox();
		if (box == null) return 0;
		return Math.max(box.getWidth(), box.getHeight());
	}

	/**
	 * Method to compare this Poly to another.
	 * @param polyOther the other Poly to compare.
	 * @return true if the Polys are the same.
	 */
	public boolean polySame(PolyBase polyOther)
	{
		// polygons must have the same number of points
		Point2D [] points = getPoints();
		Point2D [] pointsO = polyOther.getPoints();
		if (points.length != pointsO.length) return false;

		// if both are boxes, compare their extents
		Rectangle2D box = getBox();
		Rectangle2D boxO = polyOther.getBox();
		if (box != null && boxO != null)
		{
			// compare box extents
			return box.equals(boxO);
		}
		if (box != null || boxO != null) return false;

		// compare these boxes the hard way
		for(int i=0; i<points.length; i++)
			if (!points[i].equals(pointsO[i])) return false;
		return true;
	}

	/**
	 * Method to tell whether a coordinate is inside of this Poly.
     * The algorith relies on the Java class Area. Very slow.
	 * @param pt the point in question.
	 * @return true if the point is inside of this Poly.
	 */
//    public boolean isPointInsideArea(Point2D pt)
//    {
//        Area area = new Area(this);
//        return area.contains(pt.getX(), pt.getY());
//    }

    /**
     * Method to determine if a point is inside a polygon. The method is based on counting
     * how many time an imaginary line cuts the polygon in one direction.
     * @param pt
     * @return
     */
    private boolean isPointInsideCutAlgorithm(Point2D pt)
    {
        // general polygon containment by counting reference line intersections
        Point2D lastPoint = points[points.length-1];
        //if (pt.equals(lastPoint)) return true;
        if (DBMath.areEquals(pt, lastPoint))
        {
            return true;
        }
        Rectangle2D box = getBounds2D();

        // The point is outside the bounding box of the polygon
        if (!DBMath.pointInsideRect(pt, box))
            return false;

        int count = 0;

        for (Point2D thisPoint : points)
        {
            if (DBMath.areEquals(pt, thisPoint))
            {
                return true;
            }

            // Checking if point is along polygon edge
            if (DBMath.isOnLine(thisPoint, lastPoint, pt))
            {
                return true;
            }

            double ptY = pt.getY();
            double lastY = lastPoint.getY();
            double thisY = thisPoint.getY();

            // not counting if the horizontal line passes through the point
            boolean skip = DBMath.areEquals(ptY, thisY) && DBMath.areEquals(ptY, lastY);