001/* 002 * Copyright 2006 - 2013 003 * Stefan Balev <stefan.balev@graphstream-project.org> 004 * Julien Baudry <julien.baudry@graphstream-project.org> 005 * Antoine Dutot <antoine.dutot@graphstream-project.org> 006 * Yoann Pigné <yoann.pigne@graphstream-project.org> 007 * Guilhelm Savin <guilhelm.savin@graphstream-project.org> 008 * 009 * This file is part of GraphStream <http://graphstream-project.org>. 010 * 011 * GraphStream is a library whose purpose is to handle static or dynamic 012 * graph, create them from scratch, file or any source and display them. 013 * 014 * This program is free software distributed under the terms of two licenses, the 015 * CeCILL-C license that fits European law, and the GNU Lesser General Public 016 * License. You can use, modify and/ or redistribute the software under the terms 017 * of the CeCILL-C license as circulated by CEA, CNRS and INRIA at the following 018 * URL <http://www.cecill.info> or under the terms of the GNU LGPL as published by 019 * the Free Software Foundation, either version 3 of the License, or (at your 020 * option) any later version. 021 * 022 * This program is distributed in the hope that it will be useful, but WITHOUT ANY 023 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A 024 * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. 025 * 026 * You should have received a copy of the GNU Lesser General Public License 027 * along with this program. If not, see <http://www.gnu.org/licenses/>. 028 * 029 * The fact that you are presently reading this means that you have had 030 * knowledge of the CeCILL-C and LGPL licenses and that you accept their terms. 031 */ 032package org.graphstream.ui.layout.springbox.implementations; 033 034import java.util.Iterator; 035 036import org.graphstream.ui.geom.Vector3; 037import org.graphstream.ui.layout.springbox.EdgeSpring; 038import org.graphstream.ui.layout.springbox.Energies; 039import org.graphstream.ui.layout.springbox.GraphCellData; 040import org.graphstream.ui.layout.springbox.NodeParticle; 041import org.miv.pherd.Particle; 042import org.miv.pherd.ParticleBox; 043import org.miv.pherd.geom.Point3; 044import org.miv.pherd.ntree.Anchor; 045import org.miv.pherd.ntree.Cell; 046 047public class SpringBoxNodeParticle extends NodeParticle { 048 /** 049 * New node. 050 * 051 * The node is placed at random in the space of the simulation. 052 * 053 * @param box 054 * The spring box. 055 * @param id 056 * The node identifier. 057 */ 058 public SpringBoxNodeParticle(SpringBox box, String id) { 059 //this(box, id, box.getCenterPoint().x, box.getCenterPoint().y, box.is3D() ? box.getCenterPoint().z : 0); 060 this(box, id, box.randomXInsideBounds(), box.randomYInsideBounds(), box.is3D() ? box.randomZInsideBounds() : 0); 061 //this(box, id, (box.getRandom().nextDouble() * 2 * box.k) - box.k, (box.getRandom().nextDouble() * 2 * box.k) - box.k, box.is3D() ? (box.getRandom().nextDouble() * 2 * box.k) - box.k : 0); 062 063 this.box = box; 064 } 065 066 /** 067 * New node at a given position. 068 * 069 * @param box 070 * The spring box. 071 * @param id 072 * The node identifier. 073 * @param x 074 * The abscissa. 075 * @param y 076 * The ordinate. 077 * @param z 078 * The depth. 079 */ 080 public SpringBoxNodeParticle(SpringBox box, String id, double x, double y, 081 double z) { 082 super(box, id, x, y, z); 083 } 084 085 @Override 086 protected void repulsionN2(Vector3 delta) { 087 SpringBox box = (SpringBox) this.box; 088 boolean is3D = box.is3D(); 089 ParticleBox nodes = box.getSpatialIndex(); 090 Energies energies = box.getEnergies(); 091 Iterator<Object> i = nodes.getParticleIdIterator(); 092 093 while (i.hasNext()) { 094 SpringBoxNodeParticle node = (SpringBoxNodeParticle) nodes 095 .getParticle(i.next()); 096 097 if (node != this) { 098 delta.set(node.pos.x - pos.x, node.pos.y - pos.y, 099 is3D ? node.pos.z - pos.z : 0); 100 101 double len = delta.normalize(); 102 103 if(len > 0) { 104 if (len < box.k) 105 len = box.k; // XXX NEW To prevent infinite 106 // repulsion. 107 108 double factor = len != 0 ? ((box.K2 / (len * len)) * node.weight) 109 : 0.00001; 110 111 energies.accumulateEnergy(factor); // TODO check this 112 delta.scalarMult(-factor); 113 disp.add(delta); 114 } 115 } 116 } 117 } 118 119 @Override 120 protected void repulsionNLogN(Vector3 delta) { 121 // Explore the n-tree from the root cell and consider the contents 122 // of one cell only if it does intersect an area around the current 123 // node. Else take its (weighted) barycenter into account. 124 125 recurseRepulsion(box.getSpatialIndex().getNTree().getRootCell(), delta); 126 } 127 128 protected void recurseRepulsion(Cell cell, Vector3 delta) { 129 SpringBox box = (SpringBox) this.box; 130 boolean is3D = box.is3D(); 131 Energies energies = box.getEnergies(); 132 133 if (intersection(cell)) { 134 if (cell.isLeaf()) { 135 Iterator<? extends Particle> i = cell.getParticles(); 136 137 while (i.hasNext()) { 138 SpringBoxNodeParticle node = (SpringBoxNodeParticle) i.next(); 139 140 if (node != this) { 141 delta.set(node.pos.x - pos.x, node.pos.y - pos.y, is3D ? node.pos.z 142 - pos.z : 0); 143 144 double len = delta.normalize(); 145 146 if (len > 0)// && len < ( box.k * box.viewZone ) ) 147 { 148 if (len < box.k) 149 len = box.k; // XXX NEW To prevent infinite 150 // repulsion. 151 double factor = len != 0 ? ((box.K2 / (len * len)) * node 152 .weight) : 0.00001; 153 energies.accumulateEnergy(factor); // TODO check 154 // this 155 repE += factor; 156 delta.scalarMult(-factor); 157 disp.add(delta); 158 } 159 } 160 } 161 } else { 162 int div = cell.getSpace().getDivisions(); 163 164 for (int i = 0; i < div; i++) 165 recurseRepulsion(cell.getSub(i), delta); 166 } 167 } else { 168 if (cell != this.cell) { 169 GraphCellData bary = (GraphCellData) cell.getData(); 170 171 double dist = bary.distanceFrom(pos); 172 double size = cell.getSpace().getSize(); 173 174 if ((!cell.isLeaf()) 175 && ((size / dist) > box.getBarnesHutTheta())) { 176 int div = cell.getSpace().getDivisions(); 177 178 for (int i = 0; i < div; i++) 179 recurseRepulsion(cell.getSub(i), delta); 180 } else { 181 if (bary.weight != 0) { 182 delta.set(bary.center.x - pos.x, bary.center.y - pos.y, 183 is3D ? bary.center.z - pos.z : 0); 184 185 double len = delta.normalize(); 186 187 if (len > 0) { 188 if (len < box.k) 189 len = box.k; // XXX NEW To prevent infinite 190 // repulsion. 191 double factor = len != 0 ? ((box.K2 / (len * len)) * (bary.weight)) 192 : 0.00001f; 193 energies.accumulateEnergy(factor); 194 delta.scalarMult(-factor); 195 repE += factor; 196 197 disp.add(delta); 198 } 199 } 200 } 201 } 202 } 203 } 204 205 @Override 206 protected void attraction(Vector3 delta) { 207 SpringBox box = (SpringBox) this.box; 208 boolean is3D = box.is3D(); 209 Energies energies = box.getEnergies(); 210 int neighbourCount = neighbours.size(); 211 212 for (EdgeSpring edge : neighbours) { 213 if (!edge.ignored) { 214 NodeParticle other = edge.getOpposite(this); 215 Point3 opos = other.getPosition(); 216 217 delta.set(opos.x - pos.x, opos.y - pos.y, is3D ? opos.z - pos.z 218 : 0); 219 220 double len = delta.normalize(); 221 double k = box.k * edge.weight; 222 double factor = box.K1 * (len - k); 223 224 // delta.scalarMult( factor ); 225 delta.scalarMult(factor * (1f / (neighbourCount * 0.1f))); 226 // ^^^ XXX NEW inertia based on the node degree. This is one 227 // of the amelioration of the Spring-Box algorithm. Compare 228 // it to the Force-Atlas algorithm that does this on 229 // **repulsion**. 230 231 disp.add(delta); 232 attE += factor; 233 energies.accumulateEnergy(factor); 234 } 235 } 236 } 237 238 protected void gravity(Vector3 delta) { 239 SpringBox box = (SpringBox) this.box; 240 boolean is3D = box.is3D(); 241 //org.graphstream.ui.geom.Point3 center = box.getCenterPoint(); 242 //delta.set(center.x - pos.x, center.y - pos.y, is3D ? center.z - pos.z : 0); 243 delta.set(-pos.x, -pos.y, is3D ? -pos.z : 0);// Use (0,0,0) instead of the layout center. 244 delta.normalize(); 245 delta.scalarMult(box.getGravityFactor()); 246 disp.add(delta); 247 } 248 249 protected boolean intersection(Cell cell) { 250 SpringBox box = (SpringBox) this.box; 251 252 double k = box.k; 253 double vz = box.getViewZone(); 254 255 Anchor lo = cell.getSpace().getLoAnchor(); 256 Anchor hi = cell.getSpace().getHiAnchor(); 257 258 double x1 = lo.x; 259 double x2 = hi.x; 260 double X1 = pos.x - (k * vz); 261 double X2 = pos.x + (k * vz); 262 263 if (X2 < x1 || X1 > x2) 264 return false; 265 266 double y1 = lo.y; 267 double y2 = hi.y; 268 double Y1 = pos.y - (k * vz); 269 double Y2 = pos.y + (k * vz); 270 271 if (Y2 < y1 || Y1 > y2) 272 return false; 273 274 double z1 = lo.z; 275 double z2 = hi.z; 276 double Z1 = pos.z - (k * vz); 277 double Z2 = pos.z + (k * vz); 278 279 if (Z2 < z1 || Z1 > z2) 280 return false; 281 282 return true; 283 } 284}