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}