mev-4.0.01/source/org/tigr/microarray/mev/cluster/algorithm/impl/terrain/QuadTreeT.java

Code
Comments
Other
Rev Date Author Line
2 26 Feb 07 jari 1 /*
2 26 Feb 07 jari 2 Copyright @ 1999-2003, The Institute for Genomic Research (TIGR).
2 26 Feb 07 jari 3 All rights reserved.
2 26 Feb 07 jari 4 */
2 26 Feb 07 jari 5 /*
2 26 Feb 07 jari 6  * $RCSfile: QuadTreeT.java,v $
2 26 Feb 07 jari 7  * $Revision: 1.4 $
2 26 Feb 07 jari 8  * $Date: 2006/02/23 20:59:46 $
2 26 Feb 07 jari 9  * $Author: caliente $
2 26 Feb 07 jari 10  * $State: Exp $
2 26 Feb 07 jari 11  */
2 26 Feb 07 jari 12 package org.tigr.microarray.mev.cluster.algorithm.impl.terrain;
2 26 Feb 07 jari 13
2 26 Feb 07 jari 14 import javax.vecmath.Vector2f;
2 26 Feb 07 jari 15
2 26 Feb 07 jari 16 import org.tigr.microarray.mev.cluster.algorithm.impl.util.IntArray;
2 26 Feb 07 jari 17
2 26 Feb 07 jari 18 public class QuadTreeT {
2 26 Feb 07 jari 19
2 26 Feb 07 jari 20     public SNode[] m_arrNodes;
2 26 Feb 07 jari 21     private InterfaceToObjects m_rInterface;
2 26 Feb 07 jari 22
2 26 Feb 07 jari 23     private final static int c_iMaxQuadTreeTDepth = 15;
2 26 Feb 07 jari 24     // helper methods
2 26 Feb 07 jari 25     private int GetLinearSize(int iDepth) {
2 26 Feb 07 jari 26         return(int)((Math.pow(4,iDepth)-1.0)/3.0+0.5);
2 26 Feb 07 jari 27     }
2 26 Feb 07 jari 28
2 26 Feb 07 jari 29     private void Clear() {
2 26 Feb 07 jari 30         int n=m_arrNodes.length;
2 26 Feb 07 jari 31         for (int i=0; i<n; i++)
2 26 Feb 07 jari 32             m_arrNodes[i].Destroy();
2 26 Feb 07 jari 33     }
2 26 Feb 07 jari 34
2 26 Feb 07 jari 35     private void SetNode(int iInd, int[] rArrIds) {
2 26 Feb 07 jari 36         //ASSERT(iInd>=0 && UINT(iInd)<m_arrNodes.size());
2 26 Feb 07 jari 37         if (rArrIds.length<=0)
2 26 Feb 07 jari 38             return;
2 26 Feb 07 jari 39         // calculate midpt, averagept, rectBounding
2 26 Feb 07 jari 40         int nSize=rArrIds.length;
2 26 Feb 07 jari 41         Vector2f ptSum = new Vector2f(), ptAvg = new Vector2f();
2 26 Feb 07 jari 42         Vector2f ptCur = new Vector2f();
2 26 Feb 07 jari 43         Vector2f ptTmp = new Vector2f();
2 26 Feb 07 jari 44         RectDT rectBounding = new RectDT();
2 26 Feb 07 jari 45         rectBounding.MakeEmpty();
2 26 Feb 07 jari 46         for (int i=0; i<nSize; i++) {
2 26 Feb 07 jari 47             m_rInterface.GetObjectGeom(rArrIds[i], ptTmp);
2 26 Feb 07 jari 48             ptCur.x=ptTmp.x;
2 26 Feb 07 jari 49             ptCur.y=ptTmp.y;
2 26 Feb 07 jari 50             rectBounding.IncludePoint(ptCur);
2 26 Feb 07 jari 51             ptSum.add(ptCur);
2 26 Feb 07 jari 52         }
2 26 Feb 07 jari 53         ptAvg.set(ptSum);
2 26 Feb 07 jari 54         ptAvg.scale(1f/(float)nSize); // ptAvg is average point now
2 26 Feb 07 jari 55         Vector2f midPoint = new Vector2f((rectBounding.m_Right+rectBounding.m_Left)/2, (rectBounding.m_Bottom+rectBounding.m_Top)/2);
2 26 Feb 07 jari 56
2 26 Feb 07 jari 57         // instantiate current node
2 26 Feb 07 jari 58         m_arrNodes[iInd].m_ptMid.set(ptAvg);     //middle point(the point to divide the rect)
2 26 Feb 07 jari 59         m_arrNodes[iInd].m_ptAvg.set(ptAvg);         //average(center of mass) point... TODO: change midpoint to average point
2 26 Feb 07 jari 60         m_arrNodes[iInd].m_Rect.set(rectBounding);   // bounding of the objects
2 26 Feb 07 jari 61         m_arrNodes[iInd].m_iPointNumBehind=nSize;// the number of objects inside the rectangle(belonging to bounding rectangle)
2 26 Feb 07 jari 62
2 26 Feb 07 jari 63         int iChildInd=GetChild(iInd, LEFT_UP);
2 26 Feb 07 jari 64         if (iChildInd<0||nSize==1) {  // if this is leaf by structure of QuadTreeT
2 26 Feb 07 jari 65             m_arrNodes[iInd].SetLeaf(); //invalidate middle point
2 26 Feb 07 jari 66             m_arrNodes[iInd].m_arrPointsIds=rArrIds;
2 26 Feb 07 jari 67             return;
2 26 Feb 07 jari 68         }
2 26 Feb 07 jari 69
2 26 Feb 07 jari 70         //divide the set of nodes to the four subsets for each quadrant(around midPoint)
2 26 Feb 07 jari 71         IntArray arrLeftUpIds = new IntArray(), arrRightUpIds = new IntArray();
2 26 Feb 07 jari 72         IntArray arrLeftDownIds = new IntArray(), arrRightDownIds = new IntArray();
2 26 Feb 07 jari 73         for (int i=0; i<nSize; i++) {
2 26 Feb 07 jari 74             m_rInterface.GetObjectGeom(rArrIds[i], ptTmp);
2 26 Feb 07 jari 75             ptCur.set(ptTmp);
2 26 Feb 07 jari 76             
2 26 Feb 07 jari 77             if (ptCur.x<=midPoint.x) {                // On the left
2 26 Feb 07 jari 78                 if (ptCur.y<=midPoint.y)
2 26 Feb 07 jari 79                     arrLeftUpIds.add(rArrIds[i]);           // Left-upper corner
2 26 Feb 07 jari 80                 else
2 26 Feb 07 jari 81                     arrLeftDownIds.add(rArrIds[i]);     // Left-down corner
2 26 Feb 07 jari 82             } else {                                            // On the right
2 26 Feb 07 jari 83                 if (ptCur.y<=midPoint.y)
2 26 Feb 07 jari 84                     arrRightUpIds.add(rArrIds[i]);      // Right-upper corner
2 26 Feb 07 jari 85                 else
2 26 Feb 07 jari 86                     arrRightDownIds.add(rArrIds[i]);        // Right-down corner
2 26 Feb 07 jari 87             }
2 26 Feb 07 jari 88         }
2 26 Feb 07 jari 89
2 26 Feb 07 jari 90         // call SetNode(int iInd, const vector<Vector2D>& rArrIn, const vector<int>& rArrIds) recursively for each quadrant
2 26 Feb 07 jari 91         //ASSERT(iChildInd>iInd && UINT(iChildInd)<m_arrNodes.size());
2 26 Feb 07 jari 92         SetNode(iChildInd, arrLeftUpIds.toArray());
2 26 Feb 07 jari 93         arrLeftUpIds = null;
2 26 Feb 07 jari 94
2 26 Feb 07 jari 95         iChildInd=GetChild(iInd, RIGHT_UP);
2 26 Feb 07 jari 96         //ASSERT(iChildInd>iInd && UINT(iChildInd)<m_arrNodes.size());
2 26 Feb 07 jari 97         SetNode(iChildInd, arrRightUpIds.toArray());
2 26 Feb 07 jari 98         arrRightUpIds = null;
2 26 Feb 07 jari 99
2 26 Feb 07 jari 100         iChildInd=GetChild(iInd, LEFT_DOWN);
2 26 Feb 07 jari 101         //ASSERT(iChildInd>iInd && UINT(iChildInd)<m_arrNodes.size());
2 26 Feb 07 jari 102         SetNode(iChildInd, arrLeftDownIds.toArray());
2 26 Feb 07 jari 103         arrLeftDownIds = null;
2 26 Feb 07 jari 104
2 26 Feb 07 jari 105         iChildInd=GetChild(iInd, RIGHT_DOWN);
2 26 Feb 07 jari 106         //ASSERT(iChildInd>iInd && UINT(iChildInd)<m_arrNodes.size());
2 26 Feb 07 jari 107         SetNode(iChildInd, arrRightDownIds.toArray());
2 26 Feb 07 jari 108         arrRightDownIds = null;
2 26 Feb 07 jari 109     }
2 26 Feb 07 jari 110
2 26 Feb 07 jari 111     public static class SNode {
2 26 Feb 07 jari 112         // properties
2 26 Feb 07 jari 113         Vector2f m_ptMid = new Vector2f();   // 'middle' point
2 26 Feb 07 jari 114         Vector2f m_ptAvg = new Vector2f();   // average point
2 26 Feb 07 jari 115         public RectDT m_Rect = new RectDT();      // m_ptMid==f(m_Rect)
2 26 Feb 07 jari 116         int m_iPointNumBehind;
2 26 Feb 07 jari 117         int[] m_arrPointsIds;
2 26 Feb 07 jari 118
2 26 Feb 07 jari 119         // methods
2 26 Feb 07 jari 120         public SNode() {
2 26 Feb 07 jari 121             Destroy();
2 26 Feb 07 jari 122         }
2 26 Feb 07 jari 123
2 26 Feb 07 jari 124         public void Destroy() {
2 26 Feb 07 jari 125             m_arrPointsIds = null; 
2 26 Feb 07 jari 126             m_ptMid.set(Float.MAX_VALUE, Float.MAX_VALUE);
2 26 Feb 07 jari 127             m_iPointNumBehind = 0;
2 26 Feb 07 jari 128         }
2 26 Feb 07 jari 129         public void Init(Vector2f rIn) {
2 26 Feb 07 jari 130             Destroy(); m_ptMid.set(rIn);
2 26 Feb 07 jari 131         }
2 26 Feb 07 jari 132         public void Init(int[] rIn) {
2 26 Feb 07 jari 133             Destroy(); m_arrPointsIds=rIn;
2 26 Feb 07 jari 134         }
2 26 Feb 07 jari 135
2 26 Feb 07 jari 136         public boolean IsLeaf() {
2 26 Feb 07 jari 137             return m_ptMid.x == Float.MAX_VALUE && m_ptMid.y == Float.MAX_VALUE;
2 26 Feb 07 jari 138         }
2 26 Feb 07 jari 139         public void SetLeaf() {
2 26 Feb 07 jari 140             m_ptMid.set(Float.MAX_VALUE, Float.MAX_VALUE);
2 26 Feb 07 jari 141         }
2 26 Feb 07 jari 142     }
2 26 Feb 07 jari 143
2 26 Feb 07 jari 144
2 26 Feb 07 jari 145     // Construction
2 26 Feb 07 jari 146     QuadTreeT(int iDepth, InterfaceToObjects rInterface) {
2 26 Feb 07 jari 147         if (iDepth > c_iMaxQuadTreeTDepth)
2 26 Feb 07 jari 148             throw new IllegalArgumentException("The tree depth can't be more than "+c_iMaxQuadTreeTDepth);
2 26 Feb 07 jari 149         m_rInterface = rInterface;
2 26 Feb 07 jari 150         int iSize=GetLinearSize(iDepth);
2 26 Feb 07 jari 151         m_arrNodes = new SNode[iSize];
2 26 Feb 07 jari 152         for (int i=0; i<m_arrNodes.length; i++)
2 26 Feb 07 jari 153             m_arrNodes[i] = new SNode();
2 26 Feb 07 jari 154     }
2 26 Feb 07 jari 155
2 26 Feb 07 jari 156     // Initialization
2 26 Feb 07 jari 157     void Initialize() {
2 26 Feb 07 jari 158         Clear();
2 26 Feb 07 jari 159         int[] arrObjIds = m_rInterface.GetAllObjectsIds();  //retrieve all obj ids from the interface to the objects
2 26 Feb 07 jari 160         SetNode(0, arrObjIds);
2 26 Feb 07 jari 161     }
2 26 Feb 07 jari 162
2 26 Feb 07 jari 163     // Quad Tree navigation methods
2 26 Feb 07 jari 164     int GetParent(int iChild) {             // get the index of iChild's parent node in quad tree, or -1 if no any
2 26 Feb 07 jari 165         return(iChild>0)?((iChild >> 2 )):0;   //just divide to 4
2 26 Feb 07 jari 166     }
2 26 Feb 07 jari 167     int GetChild(int iChild, int eDir) {    // go down to appropriate direction from iChild node to eDir... returns -1 if such operation is not available
2 26 Feb 07 jari 168         int iNewInd=(iChild<<2)+eDir;
2 26 Feb 07 jari 169         if (iNewInd<0 || iNewInd>=m_arrNodes.length)
2 26 Feb 07 jari 170             iNewInd=-1;
2 26 Feb 07 jari 171         return iNewInd;
2 26 Feb 07 jari 172     }
2 26 Feb 07 jari 173
2 26 Feb 07 jari 174     public static final int LEFT_UP=1, RIGHT_UP=2, LEFT_DOWN=3, RIGHT_DOWN=4;
2 26 Feb 07 jari 175 }

Generated on Thu Jul 20 09:25:24 2023 (UTC) by svndigest 0.11.2pre (dev build 1672)