X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;ds=sidebyside;f=bundles%2Forg.simantics.scenegraph%2Fsrc%2Fcom%2Finfomatiq%2Fjsi%2Frtree%2FNode.java;h=2ce34c71ec87de03a26e60ff886b05f23704886f;hb=9f207b4d5d34917ca528684bd3268a0cf4eff331;hp=9c03bbbd9e098d9a60e64bfb7a89c1c10dfb370c;hpb=969bd23cab98a79ca9101af33334000879fb60c5;p=simantics%2Fplatform.git diff --git a/bundles/org.simantics.scenegraph/src/com/infomatiq/jsi/rtree/Node.java b/bundles/org.simantics.scenegraph/src/com/infomatiq/jsi/rtree/Node.java index 9c03bbbd9..2ce34c71e 100644 --- a/bundles/org.simantics.scenegraph/src/com/infomatiq/jsi/rtree/Node.java +++ b/bundles/org.simantics.scenegraph/src/com/infomatiq/jsi/rtree/Node.java @@ -1,162 +1,162 @@ -// Node.java -// Java Spatial Index Library -// Copyright (C) 2002-2005 Infomatiq Limited -// Copyright (C) 2008-2010 aled@sourceforge.net -// -// This library is free software; you can redistribute it and/or -// modify it under the terms of the GNU Lesser General Public -// License as published by the Free Software Foundation; either -// version 2.1 of the License, or (at your option) any later version. -// -// This library 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 -// Lesser General Public License for more details. -// -// You should have received a copy of the GNU Lesser General Public -// License along with this library; if not, write to the Free Software -// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - -package com.infomatiq.jsi.rtree; - -/** - *
Used by RTree. There are no public methods in this class.
- * - * @author aled.morris@infomatiq.co.uk - * @version 1.0b8 - */ -public class Node { - int nodeId = 0; - float mbrMinX = Float.MAX_VALUE; - float mbrMinY = Float.MAX_VALUE; - float mbrMaxX = -Float.MAX_VALUE; - float mbrMaxY = -Float.MAX_VALUE; - - float[] entriesMinX = null; - float[] entriesMinY = null; - float[] entriesMaxX = null; - float[] entriesMaxY = null; - - int[] ids = null; - int level; - int entryCount; - - Node(int nodeId, int level, int maxNodeEntries) { - this.nodeId = nodeId; - this.level = level; - entriesMinX = new float[maxNodeEntries]; - entriesMinY = new float[maxNodeEntries]; - entriesMaxX = new float[maxNodeEntries]; - entriesMaxY = new float[maxNodeEntries]; - ids = new int[maxNodeEntries]; - } - - void addEntry(float minX, float minY, float maxX, float maxY, int id) { - ids[entryCount] = id; - entriesMinX[entryCount] = minX; - entriesMinY[entryCount] = minY; - entriesMaxX[entryCount] = maxX; - entriesMaxY[entryCount] = maxY; - - if (minX < mbrMinX) mbrMinX = minX; - if (minY < mbrMinY) mbrMinY = minY; - if (maxX > mbrMaxX) mbrMaxX = maxX; - if (maxY > mbrMaxY) mbrMaxY = maxY; - - entryCount++; - } - - // Return the index of the found entry, or -1 if not found - int findEntry(float minX, float minY, float maxX, float maxY, int id) { - for (int i = 0; i < entryCount; i++) { - if (id == ids[i] && - entriesMinX[i] == minX && entriesMinY[i] == minY && - entriesMaxX[i] == maxX && entriesMaxY[i] == maxY) { - return i; - } - } - return -1; - } - - // delete entry. This is done by setting it to null and copying the last entry into its space. - void deleteEntry(int i) { - int lastIndex = entryCount - 1; - float deletedMinX = entriesMinX[i]; - float deletedMinY = entriesMinY[i]; - float deletedMaxX = entriesMaxX[i]; - float deletedMaxY = entriesMaxY[i]; - - if (i != lastIndex) { - entriesMinX[i] = entriesMinX[lastIndex]; - entriesMinY[i] = entriesMinY[lastIndex]; - entriesMaxX[i] = entriesMaxX[lastIndex]; - entriesMaxY[i] = entriesMaxY[lastIndex]; - ids[i] = ids[lastIndex]; - } - entryCount--; - - // adjust the MBR - recalculateMBRIfInfluencedBy(deletedMinX, deletedMinY, deletedMaxX, deletedMaxY); - } - - // deletedMin/MaxX/Y is a rectangle that has just been deleted or made smaller. - // Thus, the MBR is only recalculated if the deleted rectangle influenced the old MBR - void recalculateMBRIfInfluencedBy(float deletedMinX, float deletedMinY, float deletedMaxX, float deletedMaxY) { - if (mbrMinX == deletedMinX || mbrMinY == deletedMinY || mbrMaxX == deletedMaxX || mbrMaxY == deletedMaxY) { - recalculateMBR(); - } - } - - void recalculateMBR() { - mbrMinX = entriesMinX[0]; - mbrMinY = entriesMinY[0]; - mbrMaxX = entriesMaxX[0]; - mbrMaxY = entriesMaxY[0]; - - for (int i = 1; i < entryCount; i++) { - if (entriesMinX[i] < mbrMinX) mbrMinX = entriesMinX[i]; - if (entriesMinY[i] < mbrMinY) mbrMinY = entriesMinY[i]; - if (entriesMaxX[i] > mbrMaxX) mbrMaxX = entriesMaxX[i]; - if (entriesMaxY[i] > mbrMaxY) mbrMaxY = entriesMaxY[i]; - } - } - - /** - * eliminate null entries, move all entries to the start of the source node - */ - void reorganize(RTree rtree) { - int countdownIndex = rtree.maxNodeEntries - 1; - for (int index = 0; index < entryCount; index++) { - if (ids[index] == -1) { - while (ids[countdownIndex] == -1 && countdownIndex > index) { - countdownIndex--; - } - entriesMinX[index] = entriesMinX[countdownIndex]; - entriesMinY[index] = entriesMinY[countdownIndex]; - entriesMaxX[index] = entriesMaxX[countdownIndex]; - entriesMaxY[index] = entriesMaxY[countdownIndex]; - ids[index] = ids[countdownIndex]; - ids[countdownIndex] = -1; - } - } - } - - public int getEntryCount() { - return entryCount; - } - - public int getId(int index) { - if (index < entryCount) { - return ids[index]; - } - return -1; - } - - boolean isLeaf() { - return (level == 1); - } - - public int getLevel() { - return level; - } -} +// Node.java +// Java Spatial Index Library +// Copyright (C) 2002-2005 Infomatiq Limited +// Copyright (C) 2008-2010 aled@sourceforge.net +// +// This library is free software; you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public +// License as published by the Free Software Foundation; either +// version 2.1 of the License, or (at your option) any later version. +// +// This library 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 +// Lesser General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public +// License along with this library; if not, write to the Free Software +// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +package com.infomatiq.jsi.rtree; + +/** + *Used by RTree. There are no public methods in this class.
+ * + * @author aled.morris@infomatiq.co.uk + * @version 1.0b8 + */ +public class Node { + int nodeId = 0; + float mbrMinX = Float.MAX_VALUE; + float mbrMinY = Float.MAX_VALUE; + float mbrMaxX = -Float.MAX_VALUE; + float mbrMaxY = -Float.MAX_VALUE; + + float[] entriesMinX = null; + float[] entriesMinY = null; + float[] entriesMaxX = null; + float[] entriesMaxY = null; + + int[] ids = null; + int level; + int entryCount; + + Node(int nodeId, int level, int maxNodeEntries) { + this.nodeId = nodeId; + this.level = level; + entriesMinX = new float[maxNodeEntries]; + entriesMinY = new float[maxNodeEntries]; + entriesMaxX = new float[maxNodeEntries]; + entriesMaxY = new float[maxNodeEntries]; + ids = new int[maxNodeEntries]; + } + + void addEntry(float minX, float minY, float maxX, float maxY, int id) { + ids[entryCount] = id; + entriesMinX[entryCount] = minX; + entriesMinY[entryCount] = minY; + entriesMaxX[entryCount] = maxX; + entriesMaxY[entryCount] = maxY; + + if (minX < mbrMinX) mbrMinX = minX; + if (minY < mbrMinY) mbrMinY = minY; + if (maxX > mbrMaxX) mbrMaxX = maxX; + if (maxY > mbrMaxY) mbrMaxY = maxY; + + entryCount++; + } + + // Return the index of the found entry, or -1 if not found + int findEntry(float minX, float minY, float maxX, float maxY, int id) { + for (int i = 0; i < entryCount; i++) { + if (id == ids[i] && + entriesMinX[i] == minX && entriesMinY[i] == minY && + entriesMaxX[i] == maxX && entriesMaxY[i] == maxY) { + return i; + } + } + return -1; + } + + // delete entry. This is done by setting it to null and copying the last entry into its space. + void deleteEntry(int i) { + int lastIndex = entryCount - 1; + float deletedMinX = entriesMinX[i]; + float deletedMinY = entriesMinY[i]; + float deletedMaxX = entriesMaxX[i]; + float deletedMaxY = entriesMaxY[i]; + + if (i != lastIndex) { + entriesMinX[i] = entriesMinX[lastIndex]; + entriesMinY[i] = entriesMinY[lastIndex]; + entriesMaxX[i] = entriesMaxX[lastIndex]; + entriesMaxY[i] = entriesMaxY[lastIndex]; + ids[i] = ids[lastIndex]; + } + entryCount--; + + // adjust the MBR + recalculateMBRIfInfluencedBy(deletedMinX, deletedMinY, deletedMaxX, deletedMaxY); + } + + // deletedMin/MaxX/Y is a rectangle that has just been deleted or made smaller. + // Thus, the MBR is only recalculated if the deleted rectangle influenced the old MBR + void recalculateMBRIfInfluencedBy(float deletedMinX, float deletedMinY, float deletedMaxX, float deletedMaxY) { + if (mbrMinX == deletedMinX || mbrMinY == deletedMinY || mbrMaxX == deletedMaxX || mbrMaxY == deletedMaxY) { + recalculateMBR(); + } + } + + void recalculateMBR() { + mbrMinX = entriesMinX[0]; + mbrMinY = entriesMinY[0]; + mbrMaxX = entriesMaxX[0]; + mbrMaxY = entriesMaxY[0]; + + for (int i = 1; i < entryCount; i++) { + if (entriesMinX[i] < mbrMinX) mbrMinX = entriesMinX[i]; + if (entriesMinY[i] < mbrMinY) mbrMinY = entriesMinY[i]; + if (entriesMaxX[i] > mbrMaxX) mbrMaxX = entriesMaxX[i]; + if (entriesMaxY[i] > mbrMaxY) mbrMaxY = entriesMaxY[i]; + } + } + + /** + * eliminate null entries, move all entries to the start of the source node + */ + void reorganize(RTree rtree) { + int countdownIndex = rtree.maxNodeEntries - 1; + for (int index = 0; index < entryCount; index++) { + if (ids[index] == -1) { + while (ids[countdownIndex] == -1 && countdownIndex > index) { + countdownIndex--; + } + entriesMinX[index] = entriesMinX[countdownIndex]; + entriesMinY[index] = entriesMinY[countdownIndex]; + entriesMaxX[index] = entriesMaxX[countdownIndex]; + entriesMaxY[index] = entriesMaxY[countdownIndex]; + ids[index] = ids[countdownIndex]; + ids[countdownIndex] = -1; + } + } + } + + public int getEntryCount() { + return entryCount; + } + + public int getId(int index) { + if (index < entryCount) { + return ids[index]; + } + return -1; + } + + boolean isLeaf() { + return (level == 1); + } + + public int getLevel() { + return level; + } +}