| IntersectionCalculators.java |
1 /****************************************************************************
2 * This demo file is part of yFiles for Java 2.14.
3 * Copyright (c) 2000-2017 by yWorks GmbH, Vor dem Kreuzberg 28,
4 * 72070 Tuebingen, Germany. All rights reserved.
5 *
6 * yFiles demo files exhibit yFiles for Java functionalities. Any redistribution
7 * of demo files in source code or binary form, with or without
8 * modification, is not permitted.
9 *
10 * Owners of a valid software license for a yFiles for Java version that this
11 * demo is shipped with are allowed to use the demo source code as basis
12 * for their own yFiles for Java powered applications. Use of such programs is
13 * governed by the rights and conditions as set out in the yFiles for Java
14 * license agreement.
15 *
16 * THIS SOFTWARE IS PROVIDED ''AS IS'' AND ANY EXPRESS OR IMPLIED
17 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
18 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
19 * NO EVENT SHALL yWorks BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
20 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
21 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
22 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
23 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
24 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 *
27 ***************************************************************************/
28 package demo.layout.withoutview;
29
30 import y.base.DataProvider;
31 import y.base.Edge;
32 import y.base.Node;
33 import y.geom.YPoint;
34 import y.layout.IntersectionCalculator;
35 import y.layout.LayoutGraph;
36 import y.layout.NodeLayout;
37 import y.util.DataProviderAdapter;
38
39 import java.util.ArrayList;
40 import java.util.Iterator;
41
42 /**
43 * Provides utilities for calculating intersection points of edges at nodes.
44 */
45 public class IntersectionCalculators {
46 /**
47 * Data provider key to register a data provider that may be queried for a
48 * node's shape type.
49 * This data provider is necessary to be able to determine a node's shape
50 * when visualizing a graph in
51 * {@link IntersectionCalculatorDemo.MyLayoutPreviewPanel}.
52 */
53 static final Object SHAPE_DPKEY = "demo.layout.withoutview.IntersectionCalculator.SHAPE_DPKEY";
54
55 /**
56 * Shape type specifier for nodes that should be considered rectangular.
57 */
58 public static final int SHAPE_RECTANGLE = 0;
59 /**
60 * Shape type specifier for nodes that should be considered elliptical.
61 */
62 public static final int SHAPE_ELLIPSE = 1;
63 /**
64 * Shape type specifier for nodes that should be considered diamond shaped.
65 */
66 public static final int SHAPE_DIAMOND = 2;
67
68 private IntersectionCalculators() {
69 }
70
71 /**
72 * Registers a data provider that returns intersection calculators for
73 * nodes based on the node shape type returned by the given shape data
74 * provider.
75 * @param graph the graph on which the data provider is registered.
76 * @param shapeDp the data provider that is queried for the nodes' shapes.
77 * @param source <code>true</code> if intersection calculators for source
78 * nodes of edges are needed and <code>false</code> if intersection
79 * calculators for target nodes of edges are needed.
80 */
81 public static void addIntersectionCalculator(
82 final LayoutGraph graph, final DataProvider shapeDp, final boolean source
83 ) {
84 if (source) {
85 final Object key = IntersectionCalculator.SOURCE_INTERSECTION_CALCULATOR_DPKEY;
86 graph.addDataProvider(key, new IntersectionCalculatorProvider(shapeDp, true));
87 } else {
88 final Object key = IntersectionCalculator.TARGET_INTERSECTION_CALCULATOR_DPKEY;
89 graph.addDataProvider(key, new IntersectionCalculatorProvider(shapeDp, false));
90 }
91 }
92
93 /**
94 * Data provider that returns {@link IntersectionCalculator}s for endpoints
95 * of edges depending on node shape.
96 */
97 private static class IntersectionCalculatorProvider extends DataProviderAdapter {
98 private final DataProvider shapeDp;
99 private final boolean source;
100 private final DiamondCalculator diamondCalculator;
101 private final EllipseCalculator ellipseCalculator;
102
103 /**
104 * Initializes a new <code>IntersectionCalculatorProvider</code>.
105 * @param shapeDp a data provider that can be queried for a node's shape.
106 * @param source <code>true</code> if intersection calculators for
107 * source nodes should be returned or <code>false</code> if intersection
108 * calculators for target nodes should be returned.
109 */
110 IntersectionCalculatorProvider(
111 final DataProvider shapeDp,
112 final boolean source
113 ) {
114 this.shapeDp = shapeDp;
115 this.source = source;
116 diamondCalculator = new DiamondCalculator();
117 ellipseCalculator = new EllipseCalculator();
118 }
119
120 /**
121 * Returns an intersection calculator for the given edge's source or target
122 * node.
123 * @param dataHolder the edge for which source or target intersection has
124 * to be calculated.
125 * @return an intersection calculator suitable for the given edge's source
126 * or target node or <code>null</code> if the node should be handled
127 * as a rectangle.
128 */
129 public Object get( final Object dataHolder ) {
130 final Edge edge = (Edge) dataHolder;
131 switch (getShape(source ? edge.source() : edge.target())) {
132 case SHAPE_DIAMOND:
133 return diamondCalculator;
134 case SHAPE_ELLIPSE:
135 return ellipseCalculator;
136 default:
137 return null;
138 }
139 }
140
141 /**
142 * Returns the shape type for the specified node.
143 * @return one of <ul>
144 * <li>{@link IntersectionCalculators#SHAPE_RECTANGLE},</li>
145 * <li>{@link IntersectionCalculators#SHAPE_ELLIPSE}, and</li>
146 * <li>{@link IntersectionCalculators#SHAPE_DIAMOND}.</li>
147 * </ul>
148 */
149 private int getShape( final Node node ) {
150 return shapeDp == null ? SHAPE_RECTANGLE : shapeDp.getInt(node);
151 }
152 }
153
154 /**
155 * Intersection calculator for diamond shaped nodes whose symmetry axes
156 * are paraxial (i.e. the tips of the diamond are assumed to be horizontally
157 * or vertically centered in the node's bounding box).
158 */
159 private static final class DiamondCalculator implements IntersectionCalculator {
160 private static final double EPS = 1e-10;
161
162 /**
163 * Calculates the intersection point by intersecting the affine line that
164 * is given by the specified offset and direction with each of the four
165 * sides of a diamond.
166 */
167 public YPoint calculateIntersectionPoint(
168 final NodeLayout nl,
169 final double xOffset, final double yOffset,
170 final double dx, final double dy
171 ) {
172 final double w = nl.getWidth();
173 final double w2 = w * 0.5;
174 final double minX = nl.getX();
175 final double maxX = minX + w;
176 final double cx = minX + w2;
177
178 final double h = nl.getHeight();
179 final double h2 = h * 0.5;
180 final double minY = nl.getY();
181 final double maxY = minY + h;
182 final double cy = minY + h2;
183
184 // one point on the line that is test for intersection with the diamond's
185 // sides
186 final double qx = cx + xOffset;
187 final double qy = cy + yOffset;
188
189 // another point on the line that is test for intersection with the
190 // diamond's sides
191 // this second point is constructed such that it lies outside the given
192 // node's bounding box
193 double px = qx - dx;
194 double py = qy - dy;
195 if (dx > 0) {
196 if (qx > minX) {
197 px = minX - 10;
198 py = qy + (px - qx)/dx * dy;
199 }
200 } else if (dx < 0) {
201 if (qx < maxX) {
202 px = maxX + 10;
203 py = qy + (px - qx)/dx * dy;
204 }
205 } else {
206 if (dy > 0) {
207 if (qy > minY) {
208 px = qx;
209 py = minY - 10;
210 }
211 } else if (dy < 0) {
212 if (qy < maxY) {
213 px = qx;
214 py = maxY + 10;
215 }
216 } else {
217 // dx == 0 and dy == 0 means q + t*d == q for all t
218 // in other words, there is no intersection point because the
219 // given data does not define an affine line but a single point
220 return null;
221 }
222 }
223
224 final ArrayList intersections = new ArrayList();
225
226 final double inf = -EPS;
227 final double sup = w2 + EPS;
228
229 // check if the given line intersects the diamond's upper left side
230 final YPoint p1 = calcIntersection(px, py, qx, qy, cx, minY, minX, cy);
231 if (p1 != null) {
232 // check if the intersection lies on the line segment that makes up
233 // the diamond's upper left side
234 final double tmp = p1.getX() - minX;
235 // fuzzy check to compensate double rounding errors
236 if (inf < tmp && tmp < sup) {
237 intersections.add(p1);
238 }
239 }
240
241 // check if the given line intersects the diamond's lower left side
242 final YPoint p2 = calcIntersection(px, py, qx, qy, minX, cy, cx, maxY);
243 if (p2 != null) {
244 // check if the intersection lies on the line segment that makes up
245 // the diamond's lower left side
246 final double tmp = p2.getX() - minX;
247 // fuzzy check to compensate double rounding errors
248 if (inf < tmp && tmp < sup) {
249 intersections.add(p2);
250 }
251 }
252
253 // check if the given line intersects the diamond's lower right side
254 final YPoint p3 = calcIntersection(px, py, qx, qy, cx, maxY, maxX, cy);
255 if (p3 != null) {
256 // check if the intersection lies on the line segment that makes up
257 // the diamond's lower right side
258 final double tmp = maxX - p3.getX();
259 // fuzzy check to compensate double rounding errors
260 if (inf < tmp && tmp < sup) {
261 intersections.add(p3);
262 }
263 }
264
265 // check if the given line intersects the diamond's upper right side
266 final YPoint p4 = calcIntersection(px, py, qx, qy, maxX, cy, cx, minY);
267 if (p4 != null) {
268 // check if the intersection lies on the line segment that makes up
269 // the diamond's upper right side
270 final double tmp = maxX - p4.getX();
271 // fuzzy check to compensate double rounding errors
272 if (inf < tmp && tmp < sup) {
273 intersections.add(p4);
274 }
275 }
276
277 if (intersections.isEmpty()) {
278 return null;
279 } else if (intersections.size() == 1) {
280 final YPoint p = (YPoint) intersections.get(0);
281 // transform the intersection point into a point relative
282 // to the node's center
283 return new YPoint(p.getX() - cx, p.getY() - cy);
284 } else {
285 // since p lies outside the node's bounding box by construction
286 // the correct intersection point can be chosen as the intersection
287 // point closest to p
288 Iterator it = intersections.iterator();
289
290 YPoint result = (YPoint) it.next();
291 double distX = result.getX() - px;
292 double distY = result.getY() - py;
293 double distSqr = distX * distX + distY * distY;
294 while (it.hasNext()) {
295 final YPoint next = (YPoint) it.next();
296 distX = next.getX() - px;
297 distY = next.getY() - py;
298 final double tmp = distX * distX + distY * distY;
299 if (distSqr > tmp) {
300 distSqr = tmp;
301 result = next;
302 }
303 }
304
305 // transform the chosen intersection point into a point relative
306 // to the node's center
307 return new YPoint(result.getX() - cx, result.getY() - cy);
308 }
309 }
310
311 private static YPoint calcIntersection(
312 final double x1, final double y1,
313 final double x2, final double y2,
314 final double x3, final double y3,
315 final double x4, final double y4
316 ) {
317 final double a1 = y2 - y1;
318 final double b1 = x1 - x2;
319
320 final double a2 = y4 - y3;
321 final double b2 = x3 - x4;
322
323 final double det = a1 * b2 - a2 * b1;
324 if (det == 0) {
325 return null;
326 } else {
327 final double c1 = a1 * x1 + b1 * y1;
328 final double c2 = a2 * x3 + b2 * y3;
329 final double x = (b2 * c1 - b1 * c2) / det;
330 final double y = (a1 * c2 - a2 * c1) / det;
331 return new YPoint(x, y);
332 }
333 }
334 }
335
336 /**
337 * Intersection calculator for elliptical nodes.
338 */
339 private static final class EllipseCalculator implements IntersectionCalculator {
340 /**
341 * Calculates the intersection point by intersecting the affine line that
342 * is given by the specified offset and direction with the ellipse
343 * <code>[(x - c_x)/r_x]^2 + [(y - c_y)/r_y]^2 = 1</code> with
344 * <code>(r_x, r_y) = (c_x, c_y) - (x, y)</code>, <code>(c_x, c_y)</code>
345 * the center, and <code>(x, y)</code> the upper left corner of the given
346 * node layout.
347 */
348 public YPoint calculateIntersectionPoint(
349 final NodeLayout nl,
350 final double xOffset, final double yOffset,
351 final double dx, final double dy
352 ) {
353 final double rx = nl.getWidth() * 0.5;
354 final double ry = nl.getHeight() * 0.5;
355
356 final double v1x = dx / rx;
357 final double v1y = dy / ry;
358 final double v2x = xOffset / rx;
359 final double v2y = yOffset / ry;
360
361 final double a = v1x*v1x + v1y*v1y;
362 final double b = 2 * v1x * v2x + 2 * v1y * v2y;
363 final double c = v2x*v2x + v2y*v2y - 1;
364
365 final double det = b * b - 4 * a * c;
366 if (det < 0) {
367 return null;
368 } else if (det > 0) {
369 final double sqrt = Math.sqrt(det);
370 final double m = (-b - sqrt) / (2 * a);
371 return new YPoint(xOffset + m * dx, yOffset + m * dy);
372 } else {
373 final double m = -b / (2 * a);
374 return new YPoint(xOffset + m * dx, yOffset + m * dy);
375 }
376 }
377 }
378 }
379