polyqtree.java

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

		 * Returns a printable version of this PolyNode.
		 * @return a printable version of this PolyNode.
		 */
		public String toString()
		{
			return ("PolyNode " + getBounds());
		}

		/**
		 * Overwriting original for Area to consider touching polygons
		 */
		public boolean intersects (Area a)
		{
			if (a.isRectangular())
			{
				boolean inter = intersects(a.getBounds2D());
				if (inter) return (inter);

				// detecting if they touch each other...
				inter = doesTouch(a.getBounds2D().getPathIterator(null));

				return (inter);
			}
			else if (isRectangular())
			{
				return (a.intersects(getBounds2D()));
			}
			// @TODO: GVG Missing part. Doesn't detect if elements are touching
			// @TODO: GVG very expensive?
			Area area = (Area)this.clone();
			area.intersect(a);
			boolean inter = !area.isEmpty();

			return (inter);
		}
		private boolean isOriginal()
		{
			return ((original >> 0 & 1) == 0);
		}
		private void setNotOriginal()
		{
			original |= 1 << 0;
		}
		private Collection<PolyNode> getSimpleObjects(boolean simple)
		{
			Set<PolyNode> set = new HashSet<PolyNode>();
            // Possible not connected loops
            double [] coords = new double[6];
            List<Point2D> pointList = new ArrayList<Point2D>();
            PathIterator pi = getPathIterator(null);
            List<GeneralPath> polyList = new ArrayList<GeneralPath>();
            boolean isSingular = isSingular();
            List<GeneralPath> toDelete = new ArrayList<GeneralPath>();

            while (!pi.isDone()) {
                switch (pi.currentSegment(coords)) {
                    case PathIterator.SEG_CLOSE:
                        {
                            Object [] points = pointList.toArray();
                            GeneralPath simplepath = new GeneralPath();
                            for (int i = 0; i < pointList.size(); i++)
                            {
                                int j = (i + 1)% pointList.size();
                                Line2D line = new Line2D.Double(((Point2D)points[i]), (Point2D)points[j]);
                                simplepath.append(line, true);
                            }
                            toDelete.clear();
                            //PolyNode node = new PolyNode(simplepath);
                            // Search possible inner loops
                            if (!simple && !isSingular)
                            {
                                Iterator<GeneralPath> it = polyList.iterator();
                                while (it.hasNext())
                                {
                                    GeneralPath pn = it.next();
                                    if (pn.contains(pointList.get(0)))
                                    {
                                        pn.append(simplepath.getPathIterator(null), true);
                                        simplepath = null;
                                        break;
                                    }
                                    else if (simplepath.contains(pn.getCurrentPoint()))
                                    {
                                        // Checking if inner loop is pn
                                        simplepath.append(pn.getPathIterator(null), true);
                                        toDelete.add(pn);
                                        //break;  // @TODO might not work with double loops!!
                                    }
                                }
                            }
                            //set.add(node);
                            if (simplepath != null)
                                polyList.add(simplepath);
                            polyList.removeAll(toDelete);
                            pointList.clear();
                        }
                        break;
                    default:
                        Point2D pt = new Point2D.Double(coords[0], coords[1]);
                        pointList.add(pt);
                }
                pi.next();
            }
            for (Iterator<GeneralPath> it = polyList.iterator(); it.hasNext();)
            {
                GeneralPath pn = it.next();
                PolyNode node = new PolyNode(pn);
                set.add(node);
            }
			return set;
		}

        /**
         * Sort list of objects based on area
         */
		public List getSortedLoops()
		{
			Collection<PolyNode> set = getSimpleObjects(true);
			List<PolyNode> list = new ArrayList<PolyNode>(set);
			Collections.sort(list);
			return (list);
		}
	}
	private static class PolyQNode
    {
		private Set<PolyNode> nodes; // If Set, no need to check whether they are duplicated or not. Java will do it for you
		private PolyQNode[] children;

		/**
		 *
		 */
		private PolyQNode () { ; }

		private int getQuadrants(double centerX, double centerY, Rectangle2D box)
		{
		   	int loc = 0;

			if (box.getMinY() < centerY)
			{
				// either 0 or 1 quadtrees
				if (box.getMinX() < centerX)
					loc |= 1 << 0;
				if (box.getMaxX() > centerX)
					loc |= 1 << 1;
			}
			if (box.getMaxY() > centerY)
			{
				// the other quadtrees
				if (box.getMinX() < centerX)
					loc |= 1 << 2;
				if (box.getMaxX() > centerX)
					loc |= 1 << 3;
			}
			return loc;
		}

		/**
		 * Calculates the bounding box of a child depending on the location. Parameters are passed to avoid
		 * extra calculation
		 * @param x Parent x value
		 * @param y Parent y value
		 * @param w Child width (1/4 of parent if qtree)
		 * @param h Child height (1/2 of parent if qtree)
		 * @param centerX Parent center x value
		 * @param centerY Parent center y value
		 * @param loc Location in qtree
		 */
		private Rectangle2D getBox(double x, double y, double w, double h, double centerX, double centerY, int loc)
		{
			if ((loc >> 0 & 1) == 1)
			{
				x = centerX;
			}
			if ((loc >> 1 & 1) == 1)
			{
				y = centerY;
			}
			return (new Rectangle2D.Double(x, y, w, h));
		}

		/**
		 * Collects recursive leaf elements in a list. Uses set to avoid
		 * duplicate elements (qtree could sort same element in all quadrants
		 * @param modified True if no original elements should be considered
		 * @param simple True if simple elements should be retrieved
		 */
		protected void getLeafObjects(Set<PolyNode> set, boolean modified, boolean simple)
		{
			if (nodes != null)
			{
				// Not sure how efficient this is
				for (Iterator<PolyNode> it = nodes.iterator(); it.hasNext();)
				{
					PolyNode node = it.next();
					if (!modified || (modified && !node.isOriginal()))
					{
						//if (node.isOriginal() || !simple)
							set.add(node);
						//else
							//set.addAll(node.getSimpleObjects(false));
					}
				}
			}
			if (children == null) return;
			for (int i = 0; i < PolyQTree.MAX_NUM_CHILDREN; i++)
			{
				if (children[i] != null) children[i].getLeafObjects(set, modified, simple);
			}
		}

		/**
		 *   print function for debugging purposes
		 */
		protected void print()
		{
			if (nodes == null) return;
			for (Iterator<PolyNode> it = nodes.iterator(); it.hasNext();)
				System.out.println("Area " + it.next());
			if (children == null) return;
			for (int i = 0; i < PolyQTree.MAX_NUM_CHILDREN; i++)
			{
				if (children[i] != null) children[i].print();
			}
		}

		/**
		 * To compact nodes if child elements have been removed
		 * @return true if node can be removed
		 */
		private boolean compact()
		{
			//@TODO GVG Compact tree
			if (children != null)
			{
				for (int i = 0; i < PolyQTree.MAX_NUM_CHILDREN; i++)
					if (children[i] != null)
					{
						//System.out.println("To implement") ;
						return (false);
					}
			}
			return (nodes == null || nodes.isEmpty());
		}

//		/**
//		 * Original Rectangle2D:intersects doesn't detect when two elements are touching
//		 */
//		private static boolean intersects(Rectangle2D a, Rectangle2D b)
//		{
//			double x = b.getX();
//			double y = b.getY();
//			double w = b.getWidth();
//			double h = b.getHeight();
//
//			if (a.isEmpty() || w <= 0 || h <= 0) {
//	            return false;
//			}
//			double x0 = a.getX();
//			double y0 = a.getY();
//			return ((x + w) >= x0 &&
//				(y + h) >= y0 &&
//				x <= (x0 + a.getWidth()) &&
//				y <= (y0 + a.getHeight()));
//		}

		/**
		 * Removes from tree all objects overlapping with obj. Returns the overlapping region.
		 */
		protected boolean findAndRemoveObjects(Rectangle2D box, PolyNode obj, Rectangle2D areaBB,
		                                       boolean fasterAlgorithm, Set<PolyNode> removedElems)
		{
			double centerX = box.getCenterX();
            double centerY = box.getCenterY();

            // Node has been split
			if (children != null)
			{
				int loc = getQuadrants(centerX, centerY, areaBB);
				double w = box.getWidth()/2;
				double h = box.getHeight()/2;
				double x = box.getX();
				double y = box.getY();

				for (int i = 0; i < PolyQTree.MAX_NUM_CHILDREN; i++)
				{
					if (((loc >> i) & 1) == 1)
					{
						Rectangle2D bb = getBox(x, y, w, h, centerX, centerY, i);

						// if identical element was found, no need of re-insertion
						// No need of reviewing other quadrants?
						if (children[i] == null) continue;

						if (children[i].findAndRemoveObjects(bb, obj, areaBB, fasterAlgorithm, removedElems))
							return (true);

						if (children[i].compact())
							children[i] = null;
					}
				}
			}
			else if (nodes != null)
			{
				Set<PolyNode> deleteSet = new HashSet<PolyNode>();

				for (Iterator<PolyNode> it = nodes.iterator(); it.hasNext();)
				{
					PolyNode node = it.next();

					if (node.equals((Object)obj))
					{
						if (removedElems.size() != 0)
							System.out.println("I will have problems here!!");
						return (true);           // I will have problems here!!!
					}

					// @TODO this should be reviewed!!
					if (!fasterAlgorithm || (fasterAlgorithm && node.intersects(obj)))
					{
						//obj.add(node);  // It might removed immeadiately in other quadrants
						removedElems.add(node);
						obj.setNotOriginal();
						deleteSet.add(node);
					}
				}
				nodes.removeAll(deleteSet);
				if (nodes.size() == 0)
				{
					// not sure yet
					nodes.clear();
					nodes = null;
				}
			}
			// No identical element found
			return (false);
		}

		/**
		 * To make sure new element is inserted in all childres
		 * @param box Bounding box of current node
		 * @param centerX To avoid calculation inside function from object box
		 * @param centerY To avoid calculation inside function from object box
		 * @param obj Object to insert
		 * @param areaBB Bounding box of the object to insert
		 * @return True if element was inserted
		 */
		protected boolean insertInAllChildren(Rectangle2D box, double centerX, double centerY, PolyNode obj,
		                                      Rectangle2D areaBB, Set removedElems)
		{
			int loc = getQuadrants(centerX, centerY, areaBB);
			boolean inserted = false;
			double w = box.getWidth()/2;
			double h = box.getHeight()/2;
			double x = box.getX();
			double y = box.getY();

			for (int i = 0; i < PolyQTree.MAX_NUM_CHILDREN; i++)
			{
				if (((loc >> i) & 1) == 1)
				{
					Rectangle2D bb = getBox(x, y, w, h, centerX, centerY, i);

					if (children[i] == null) children[i] = new PolyQNode();

					boolean done = children[i].insert(bb, obj, areaBB, removedElems);

					inserted = (inserted) ? inserted : done;
				}
			}
			return (inserted);
		}

		/**
		 * Method.
		 * @param box Bounding box of the current PolyQNode
		 * @param obj Object to insert
		 * @param areaBB Bounding box of object to insert
		 * @param removedElems list of old nodes that might need to be replaced
		 * @return if node was really inserted
		 */
		protected boolean insert(Rectangle2D box, PolyNode obj, Rectangle2D areaBB, Set removedElems)
		{
			if (!box.intersects(areaBB))
			{
				// new element is outside of bounding box. Might need flag to avoid
				// double checking if obj is coming from findAndRemove
				return (false);
			}

			double centerX = box.getCenterX();
            double centerY = box.getCenterY();

			// Node has been split
			if (children != null)
			{
				return (insertInAllChildren(box, centerX, centerY, obj, areaBB, removedElems));
			}
			if (nodes == null)
			{
				nodes = new HashSet<PolyNode>();
			}
			boolean inserted = false;

			if (nodes.size() < PolyQTree.MAX_NUM_NODES)
			{
				inserted = nodes.add(obj);
				// still might have references to previous nodes that were merged.
				if(removedElems != null)
					nodes.removeAll(removedElems);
				//  nodes.add(obj.clone());
			}
			else
			{
				// subdivides into PolyQTree.MAX_NUM_CHILDREN. Might work only for 2^n
				children = new PolyQNode[PolyQTree.MAX_NUM_CHILDREN];
				double w = box.getWidth()/2;
				double h = box.getHeight()/2;
				double x = box.getX();
				double y = box.getY();

				// Redistributing existing elements in children
				for (int i = 0; i < PolyQTree.MAX_NUM_CHILDREN; i++)
				{
					children[i] = new PolyQNode();
					Rectangle2D bb = getBox(x, y, w, h, centerX, centerY, i);

					for (Iterator<PolyNode> it = nodes.iterator(); it.hasNext();)
					{
						PolyNode node = it.next();

						children[i].insert(bb, node, node.getBounds2D(), removedElems);
					}
				}
				nodes.clear(); // not sure about this clear yet
				nodes = null;
				inserted = insertInAllChildren(box, centerX, centerY, obj, areaBB, null);
			}
			return (inserted);
		}
	}
}