1 | /*
|
2 | * Copyright (C) 1998-2021 by Northwoods Software Corporation. All Rights Reserved.
|
3 | */
|
4 | /*
|
5 | * This is an extension and not part of the main GoJS library.
|
6 | * Note that the API for this class may change with any version, even point releases.
|
7 | * If you intend to use an extension in production, you should copy the code to your own source directory.
|
8 | * Extensions can be found in the GoJS kit under the extensions or extensionsTS folders.
|
9 | * See the Extensions intro page (https://gojs.net/latest/intro/extensions.html) for more information.
|
10 | */
|
11 | import * as go from '../release/go-module.js';
|
12 | import { Quadtree } from './Quadtree.js';
|
13 | /**
|
14 | * @hidden @internal
|
15 | * Used to represent the perimeter of the currently packed
|
16 | * shape when packing rectangles. Segments are always assumed
|
17 | * to be either horizontal or vertical, and store whether or
|
18 | * not their first point is concave (this makes sense in the
|
19 | * context of representing a perimeter, as the next segment
|
20 | * will always be connected to the last).
|
21 | */
|
22 | class Segment {
|
23 | /**
|
24 | * @hidden @internal
|
25 | * Constructs a new Segment. Segments are assumed to be either
|
26 | * horizontal or vertical, and the given coordinates should
|
27 | * reflect that.
|
28 | * @param x1 the x coordinate of the first point
|
29 | * @param y1 the y coordinate of the first point
|
30 | * @param x2 the x coordinate of the second point
|
31 | * @param y2 the y coordinate of the second point
|
32 | * @param p1Concave whether or not the first point is concave
|
33 | */
|
34 | constructor(x1, y1, x2, y2, p1Concave) {
|
35 | this.x1 = x1;
|
36 | this.y1 = y1;
|
37 | this.x2 = x2;
|
38 | this.y2 = y2;
|
39 | this.bounds = Segment.rectFromSegment(this);
|
40 | this.p1Concave = p1Concave;
|
41 | this.isHorizontal = Math.abs(y2 - y1) < 1e-7;
|
42 | }
|
43 | /**
|
44 | * @hidden @internal
|
45 | * Gets a rectangle representing the bounds of a given segment.
|
46 | * Used to supply bounds of segments to the quadtree.
|
47 | * @this {VirtualizedPackedLayout}
|
48 | * @param segment the segment to get a rectangle for
|
49 | */
|
50 | static rectFromSegment(segment) {
|
51 | if (Math.abs(segment.x1 - segment.x2) < 1e-7) {
|
52 | return new go.Rect(segment.x1, Math.min(segment.y1, segment.y2), 0, Math.abs(segment.y1 - segment.y2));
|
53 | }
|
54 | return new go.Rect(Math.min(segment.x1, segment.x2), segment.y1, Math.abs(segment.x1 - segment.x2), 0);
|
55 | }
|
56 | }
|
57 | /**
|
58 | * @hidden @internal
|
59 | * Defines the possible orientations that two adjacent
|
60 | * horizontal/vertical segments can form.
|
61 | */
|
62 | var Orientation;
|
63 | (function (Orientation) {
|
64 | Orientation[Orientation["NE"] = 0] = "NE";
|
65 | Orientation[Orientation["NW"] = 1] = "NW";
|
66 | Orientation[Orientation["SW"] = 2] = "SW";
|
67 | Orientation[Orientation["SE"] = 3] = "SE";
|
68 | })(Orientation || (Orientation = {}));
|
69 | /**
|
70 | * @hidden @internal
|
71 | * Structure for storing possible placements when packing
|
72 | * rectangles. Fits have a cost associated with them (lower
|
73 | * cost placements are preferred), and can be placed relative
|
74 | * to either one or two segments. If the fit is only placed
|
75 | * relative to one segment, s2 will be undefined. Fits placed
|
76 | * relative to multiple segments will hereafter be referred to
|
77 | * as "skip fits".
|
78 | */
|
79 | class Fit {
|
80 | /**
|
81 | * @hidden @internal
|
82 | * Constructs a new Fit.
|
83 | * @param bounds the boundaries of the placement, including defined x and y coordinates
|
84 | * @param cost the cost of the placement, lower cost fits will be preferred
|
85 | * @param s1 the segment that the placement was made relative to
|
86 | * @param s2 the second segment that the placement was made relative to, if the fit is a skip fit
|
87 | */
|
88 | constructor(bounds, cost, s1, s2) {
|
89 | this.bounds = bounds;
|
90 | this.cost = cost;
|
91 | this.s1 = s1;
|
92 | this.s2 = s2;
|
93 | }
|
94 | }
|
95 | ;
|
96 | /**
|
97 | * A Custom Layout that attempts to pack nodes as close together as possible
|
98 | * without overlap. Each node is assumed to be either rectangular or
|
99 | * circular (dictated by the {@link #hasCircularNodes} property). This layout
|
100 | * supports packing nodes into either a rectangle or an ellipse, with the
|
101 | * shape determined by the packShape property and the aspect ratio determined
|
102 | * by either the aspectRatio property or the specified width and height
|
103 | * (depending on the packMode).
|
104 | *
|
105 | * Nodes with 0 width or height cannot be packed, so they are treated by this
|
106 | * layout as having a width or height of 0.1 instead.
|
107 | *
|
108 | * Unlike other "Virtualized..." layouts, this does not inherit from {@link PackedLayout}
|
109 | * because there were a lot of internal changes that needed to be made. That may
|
110 | * change in the future if PackedLayout's implementation is generalized.
|
111 | * @category Layout Extension
|
112 | */
|
113 | export class VirtualizedPackedLayout extends go.Layout {
|
114 | constructor() {
|
115 | super(...arguments);
|
116 | // configuration defaults
|
117 | /** @hidden @internal */ this._packShape = VirtualizedPackedLayout.Elliptical;
|
118 | /** @hidden @internal */ this._packMode = VirtualizedPackedLayout.AspectOnly;
|
119 | /** @hidden @internal */ this._sortMode = VirtualizedPackedLayout.None;
|
120 | /** @hidden @internal */ this._sortOrder = VirtualizedPackedLayout.Descending;
|
121 | /** @hidden @internal */ this._comparer = undefined;
|
122 | /** @hidden @internal */ this._aspectRatio = 1;
|
123 | /** @hidden @internal */ this._size = new go.Size(500, 500);
|
124 | /** @hidden @internal */ this._defaultSize = this._size.copy();
|
125 | /** @hidden @internal */ this._fillViewport = false; // true if size is (NaN, NaN)
|
126 | /** @hidden @internal */ this._spacing = 0;
|
127 | /** @hidden @internal */ this._hasCircularNodes = false;
|
128 | /** @hidden @internal */ this._arrangesToOrigin = true;
|
129 | /**
|
130 | * @hidden @internal
|
131 | * The forced spacing value applied in the {@link VirtualizedPackedLayout.Fit}
|
132 | * and {@link VirtualizedPackedLayout.ExpandToFit} modes.
|
133 | */
|
134 | this._fixedSizeModeSpacing = 0;
|
135 | /**
|
136 | * @hidden @internal
|
137 | * The actual target aspect ratio, set from either {@link #aspectRatio}
|
138 | * or from the {@link #size}, depending on the {@link #packMode}.
|
139 | */
|
140 | this._eAspectRatio = this._aspectRatio;
|
141 | // layout state
|
142 | /** @hidden @internal */ this._center = new go.Point();
|
143 | /** @hidden @internal */ this._bounds = new go.Rect();
|
144 | /** @hidden @internal */ this._actualBounds = new go.Rect();
|
145 | /** @hidden @internal */ this._enclosingCircle = null;
|
146 | /** @hidden @internal */ this._minXSegment = null;
|
147 | /** @hidden @internal */ this._minYSegment = null;
|
148 | /** @hidden @internal */ this._maxXSegment = null;
|
149 | /** @hidden @internal */ this._maxYSegment = null;
|
150 | /** @hidden @internal */ this._tree = new Quadtree();
|
151 | // saved node bounds and segment list to use to calculate enclosing circle in the enclosingCircle getter
|
152 | /** @hidden @internal */ this._nodeBounds = [];
|
153 | /** @hidden @internal */ this._segments = new CircularDoublyLinkedList();
|
154 | }
|
155 | /**
|
156 | * Gets or sets the shape that nodes will be packed into. Valid values are
|
157 | * {@link VirtualizedPackedLayout.Elliptical}, {@link VirtualizedPackedLayout.Rectangular}, and
|
158 | * {@link VirtualizedPackedLayout.Spiral}.
|
159 | *
|
160 | * In {@link VirtualizedPackedLayout.Spiral} mode, nodes are not packed into a particular
|
161 | * shape, but rather packed consecutively one after another in a spiral fashion.
|
162 | * The {@link #aspectRatio} property is ignored in this mode, and
|
163 | * the {@link #size} property (if provided) is expected to be square.
|
164 | * If it is not square, the largest dimension given will be used. This mode
|
165 | * currently only works with circular nodes, so setting it cause the assume that
|
166 | * layout to assume that {@link #hasCircularNodes} is true.
|
167 | *
|
168 | * Note that this property sets only the shape, not the aspect ratio. The aspect
|
169 | * ratio of this shape is determined by either {@link #aspectRatio}
|
170 | * or {@link #size}, depending on the {@link #packMode}.
|
171 | *
|
172 | * When the {@link #packMode} is {@link VirtualizedPackedLayout.Fit} or
|
173 | * {@link VirtualizedPackedLayout.ExpandToFit} and this property is set to true, the
|
174 | * layout will attempt to make the diameter of the enclosing circle of the
|
175 | * layout approximately equal to the greater dimension of the given
|
176 | * {@link #size} property.
|
177 | *
|
178 | * The default value is {@link VirtualizedPackedLayout.Elliptical}.
|
179 | */
|
180 | get packShape() { return this._packShape; }
|
181 | set packShape(value) {
|
182 | if (this._packShape !== value && (value === VirtualizedPackedLayout.Elliptical || value === VirtualizedPackedLayout.Rectangular || value === VirtualizedPackedLayout.Spiral)) {
|
183 | this._packShape = value;
|
184 | this.invalidateLayout();
|
185 | }
|
186 | }
|
187 | /**
|
188 | * Gets or sets the mode that the layout will use to determine its size. Valid values
|
189 | * are {@link VirtualizedPackedLayout.AspectOnly}, {@link VirtualizedPackedLayout.Fit}, and {@link VirtualizedPackedLayout.ExpandToFit}.
|
190 | *
|
191 | * The default value is {@link VirtualizedPackedLayout.AspectOnly}. In this mode, the layout will simply
|
192 | * grow as needed, attempting to keep the aspect ratio defined by {@link #aspectRatio}.
|
193 | */
|
194 | get packMode() { return this._packMode; }
|
195 | set packMode(value) {
|
196 | if (value === VirtualizedPackedLayout.AspectOnly || value === VirtualizedPackedLayout.Fit || value === VirtualizedPackedLayout.ExpandToFit) {
|
197 | this._packMode = value;
|
198 | this.invalidateLayout();
|
199 | }
|
200 | }
|
201 | /**
|
202 | * Gets or sets the method by which nodes will be sorted before being packed. To change
|
203 | * the order, see {@link #sortOrder}.
|
204 | *
|
205 | * The default value is {@link VirtualizedPackedLayout.None}, in which nodes will not be sorted at all.
|
206 | */
|
207 | get sortMode() { return this._sortMode; }
|
208 | set sortMode(value) {
|
209 | if (value === VirtualizedPackedLayout.None || value === VirtualizedPackedLayout.MaxSide || value === VirtualizedPackedLayout.Area) {
|
210 | this._sortMode = value;
|
211 | this.invalidateLayout();
|
212 | }
|
213 | }
|
214 | /**
|
215 | * Gets or sets the order that nodes will be sorted in before being packed. To change
|
216 | * the sort method, see {@link #sortMode}.
|
217 | *
|
218 | * The default value is {@link VirtualizedPackedLayout.Descending}
|
219 | */
|
220 | get sortOrder() { return this._sortOrder; }
|
221 | set sortOrder(value) {
|
222 | if (value === VirtualizedPackedLayout.Descending || value === VirtualizedPackedLayout.Ascending) {
|
223 | this._sortOrder = value;
|
224 | this.invalidateLayout();
|
225 | }
|
226 | }
|
227 | /**
|
228 | * Gets or sets the comparison function used for sorting nodes.
|
229 | *
|
230 | * By default, the comparison function is set according to the values of {@link #sortMode}
|
231 | * and {@link #sortOrder}.
|
232 | *
|
233 | * Whether this comparison function is used is determined by the value of {@link #sortMode}.
|
234 | * Any value except {@link VirtualizedPackedLayout.None} will result in the comparison function being used.
|
235 | * ```js
|
236 | * $(VirtualizedPackedLayout,
|
237 | * {
|
238 | * sortMode: VirtualizedPackedLayout.Area,
|
239 | * comparer: function(na, nb) {
|
240 | * var na = na.data;
|
241 | * var nb = nb.data;
|
242 | * if (da.someProperty < db.someProperty) return -1;
|
243 | * if (da.someProperty > db.someProperty) return 1;
|
244 | * return 0;
|
245 | * }
|
246 | * }
|
247 | * )
|
248 | * ```
|
249 | */
|
250 | get comparer() { return this._comparer; }
|
251 | set comparer(value) {
|
252 | if (typeof value === 'function') {
|
253 | this._comparer = value;
|
254 | }
|
255 | }
|
256 | /**
|
257 | * Gets or sets the aspect ratio for the shape that nodes will be packed into.
|
258 | * The provided aspect ratio should be a nonzero postive number.
|
259 | *
|
260 | * Note that this only applies if the {@link #packMode} is
|
261 | * {@link VirtualizedPackedLayout.AspectOnly}. Otherwise, the {@link #size}
|
262 | * will determine the aspect ratio of the packed shape.
|
263 | *
|
264 | * The default value is 1.
|
265 | */
|
266 | get aspectRatio() { return this._aspectRatio; }
|
267 | set aspectRatio(value) {
|
268 | if (this.isNumeric(value) && isFinite(value) && value > 0) {
|
269 | this._aspectRatio = value;
|
270 | this.invalidateLayout();
|
271 | }
|
272 | }
|
273 | /**
|
274 | * Gets or sets the size for the shape that nodes will be packed into.
|
275 | * To fill the viewport, set a size with a width and height of NaN. Size
|
276 | * values of 0 are considered for layout purposes to instead be 1.
|
277 | *
|
278 | * If the width and height are set to NaN (to fill the viewport), but this
|
279 | * layout has no diagram associated with it, the default value of size will
|
280 | * be used instead.
|
281 | *
|
282 | * Note that this only applies if the {@link #packMode} is
|
283 | * {@link VirtualizedPackedLayout.Fit} or {@link VirtualizedPackedLayout.ExpandToFit}.
|
284 | *
|
285 | * The default value is 500x500.
|
286 | */
|
287 | get size() { return this._size; }
|
288 | set size(value) {
|
289 | // check if both width and height are NaN, as per https://stackoverflow.com/a/16988441
|
290 | if (value.width !== value.width && value.height !== value.height) {
|
291 | this._size = value;
|
292 | this._fillViewport = true;
|
293 | this.invalidateLayout();
|
294 | }
|
295 | else if (this.isNumeric(value.width) && isFinite(value.width) && value.width >= 0
|
296 | && this.isNumeric(value.height) && isFinite(value.height) && value.height >= 0) {
|
297 | this._size = value;
|
298 | this.invalidateLayout();
|
299 | }
|
300 | }
|
301 | /**
|
302 | * Gets or sets the spacing between nodes. This value can be set to any
|
303 | * real number (a negative spacing will compress nodes together, and a
|
304 | * positive spacing will leave space between them).
|
305 | *
|
306 | * Note that the spacing value is only respected in the {@link VirtualizedPackedLayout.Fit}
|
307 | * {@link #packMode} if it does not cause the layout to grow outside
|
308 | * of the specified bounds. In the {@link VirtualizedPackedLayout.ExpandToFit}
|
309 | * {@link #packMode}, this property does not do anything.
|
310 | *
|
311 | * The default value is 0.
|
312 | */
|
313 | get spacing() { return this._spacing; }
|
314 | set spacing(value) {
|
315 | if (this.isNumeric(value) && isFinite(value)) {
|
316 | this._spacing = value;
|
317 | this.invalidateLayout();
|
318 | }
|
319 | }
|
320 | /**
|
321 | * Gets or sets whether or not to assume that nodes are circular. This changes
|
322 | * the packing algorithm to one that is much more efficient for circular nodes.
|
323 | *
|
324 | * As this algorithm expects circles, it is assumed that if this property is set
|
325 | * to true that the given nodes will all have the same height and width. All
|
326 | * calculations are done using the width of the given nodes, so unexpected results
|
327 | * may occur if the height differs from the width.
|
328 | *
|
329 | * The default value is false.
|
330 | */
|
331 | get hasCircularNodes() { return this._hasCircularNodes; }
|
332 | set hasCircularNodes(value) {
|
333 | if (typeof (value) === typeof (true) && value !== this._hasCircularNodes) {
|
334 | this._hasCircularNodes = value;
|
335 | this.invalidateLayout();
|
336 | }
|
337 | }
|
338 | /**
|
339 | * This read-only property is the effective spacing calculated after {@link VirtualizedPackedLayout#doLayout}.
|
340 | *
|
341 | * If the {@link #packMode} is {@link VirtualizedPackedLayout.AspectOnly}, this will simply be the
|
342 | * {@link #spacing} property. However, in the {@link VirtualizedPackedLayout.Fit} and
|
343 | * {@link VirtualizedPackedLayout.ExpandToFit} modes, this property will include the forced spacing added by
|
344 | * the modes themselves.
|
345 | *
|
346 | * Note that this property will only return a valid value after a layout has been performed. Before
|
347 | * then, its behavior is undefined.
|
348 | */
|
349 | get actualSpacing() { return this.spacing + this._fixedSizeModeSpacing; }
|
350 | /**
|
351 | * This read-only property returns the actual rectangular bounds occupied by the packed nodes.
|
352 | * This property does not take into account any kind of spacing around the packed nodes.
|
353 | *
|
354 | * Note that this property will only return a valid value after a layout has been performed. Before
|
355 | * then, its behavior is undefined.
|
356 | */
|
357 | get actualBounds() { return this._actualBounds; }
|
358 | /**
|
359 | * This read-only property returns the smallest enclosing circle around the packed nodes. It makes
|
360 | * use of the {@link #hasCircularNodes} property to determine whether or not to make
|
361 | * enclosing circle calculations for rectangles or for circles. This property does not take into
|
362 | * account any kind of spacing around the packed nodes. The enclosing circle calculation is
|
363 | * performed the first time this property is retrieved, and then cached to prevent slow accesses
|
364 | * in the future.
|
365 | *
|
366 | * Note that this property will only return a valid value after a layout has been performed. Before
|
367 | * then, its behavior is undefined.
|
368 | *
|
369 | * This property is included as it may be useful for some data visualizations.
|
370 | */
|
371 | get enclosingCircle() {
|
372 | if (this._enclosingCircle === null) {
|
373 | if (this.hasCircularNodes || this.packShape === VirtualizedPackedLayout.Spiral) { // remember, spiral mode assumes hasCircularNodes
|
374 | const circles = new Array(this._nodeBounds.length);
|
375 | for (let i = 0; i < circles.length; i++) {
|
376 | const bounds = this._nodeBounds[i];
|
377 | const r = bounds.width / 2;
|
378 | circles[i] = new Circle(bounds.x + r, bounds.y + r, r);
|
379 | }
|
380 | this._enclosingCircle = enclose(circles);
|
381 | }
|
382 | else {
|
383 | const points = new Array(); // TODO: make this work with segments, not the whole nodeboudns list
|
384 | let segment = this._segments.start;
|
385 | if (segment !== null) {
|
386 | do {
|
387 | points.push(new go.Point(segment.data.x1, segment.data.y1));
|
388 | segment = segment.next;
|
389 | } while (segment !== this._segments.start);
|
390 | }
|
391 | this._enclosingCircle = enclose(points);
|
392 | }
|
393 | }
|
394 | return this._enclosingCircle;
|
395 | }
|
396 | /**
|
397 | * Gets or sets whether or not to use the {@link Layout#arrangementOrigin}
|
398 | * property when placing nodes.
|
399 | *
|
400 | * The default value is true.
|
401 | */
|
402 | get arrangesToOrigin() { return this._arrangesToOrigin; }
|
403 | set arrangesToOrigin(value) {
|
404 | if (typeof (value) === typeof (true) && value !== this._arrangesToOrigin) {
|
405 | this._arrangesToOrigin = value;
|
406 | this.invalidateLayout();
|
407 | }
|
408 | }
|
409 | /**
|
410 | * Performs the VirtualizedPackedLayout.
|
411 | * @this {VirtualizedPackedLayout}
|
412 | * @param {Diagram|Group|Iterable.<Part>} coll A {@link Diagram} or a {@link Group} or a collection of {@link Part}s.
|
413 | */
|
414 | performLayout(nodes) {
|
415 | const diagram = this.diagram;
|
416 | if (diagram !== null)
|
417 | diagram.startTransaction('Layout');
|
418 | this._bounds = new go.Rect();
|
419 | this._enclosingCircle = null;
|
420 | // push all nodes in parts iterator to an array for easy sorting
|
421 | let averageSize = 0;
|
422 | let maxSize = 0;
|
423 | nodes.forEach(function (node) {
|
424 | averageSize += node.bounds.width + node.bounds.height;
|
425 | if (node.bounds.width > maxSize) {
|
426 | maxSize = node.bounds.width;
|
427 | }
|
428 | else if (node.bounds.height > maxSize) {
|
429 | maxSize = node.bounds.height;
|
430 | }
|
431 | });
|
432 | averageSize = averageSize / (nodes.length * 2);
|
433 | if (averageSize < 1) {
|
434 | averageSize = 1;
|
435 | }
|
436 | if (this.sortMode !== VirtualizedPackedLayout.None) {
|
437 | if (!this.comparer) {
|
438 | const sortOrder = this.sortOrder;
|
439 | const sortMode = this.sortMode;
|
440 | this.comparer = (a, b) => {
|
441 | const sortVal = sortOrder === VirtualizedPackedLayout.Ascending ? 1 : -1;
|
442 | if (sortMode === VirtualizedPackedLayout.MaxSide) {
|
443 | const aMax = Math.max(a.bounds.width, a.bounds.height);
|
444 | const bMax = Math.max(b.bounds.width, b.bounds.height);
|
445 | if (aMax > bMax) {
|
446 | return sortVal;
|
447 | }
|
448 | else if (bMax > aMax) {
|
449 | return -sortVal;
|
450 | }
|
451 | return 0;
|
452 | }
|
453 | else if (sortMode === VirtualizedPackedLayout.Area) {
|
454 | const area1 = a.bounds.width * a.bounds.height;
|
455 | const area2 = b.bounds.width * b.bounds.height;
|
456 | if (area1 > area2) {
|
457 | return sortVal;
|
458 | }
|
459 | else if (area2 > area1) {
|
460 | return -sortVal;
|
461 | }
|
462 | return 0;
|
463 | }
|
464 | return 0;
|
465 | };
|
466 | }
|
467 | nodes.sort(this.comparer);
|
468 | }
|
469 | let targetWidth = this.size.width !== 0 ? this.size.width : 1;
|
470 | let targetHeight = this.size.height !== 0 ? this.size.height : 1;
|
471 | if (this._fillViewport && this.diagram !== null) {
|
472 | targetWidth = this.diagram.viewportBounds.width !== 0 ? this.diagram.viewportBounds.width : 1;
|
473 | targetHeight = this.diagram.viewportBounds.height !== 0 ? this.diagram.viewportBounds.height : 1;
|
474 | }
|
475 | else if (this._fillViewport) {
|
476 | targetWidth = this._defaultSize.width !== 0 ? this._defaultSize.width : 1;
|
477 | targetHeight = this._defaultSize.height !== 0 ? this._defaultSize.height : 1;
|
478 | }
|
479 | // set the target aspect ratio using the given bounds if necessary
|
480 | if (this.packMode === VirtualizedPackedLayout.Fit || this.packMode === VirtualizedPackedLayout.ExpandToFit) {
|
481 | this._eAspectRatio = targetWidth / targetHeight;
|
482 | }
|
483 | else {
|
484 | this._eAspectRatio = this.aspectRatio;
|
485 | }
|
486 | let fits = this.hasCircularNodes || this.packShape === VirtualizedPackedLayout.Spiral ? this.fitCircles(nodes) : this.fitRects(nodes);
|
487 | // in the Fit and ExpandToFit modes, we need to run the packing another time to figure out what the correct
|
488 | // _fixedModeSpacing should be. Then the layout is run a final time with the correct spacing.
|
489 | if (this.packMode === VirtualizedPackedLayout.Fit || this.packMode === VirtualizedPackedLayout.ExpandToFit) {
|
490 | const bounds0 = this._bounds.copy();
|
491 | this._bounds = new go.Rect();
|
492 | this._fixedSizeModeSpacing = Math.floor(averageSize);
|
493 | fits = this.hasCircularNodes || this.packShape === VirtualizedPackedLayout.Spiral ? this.fitCircles(nodes) : this.fitRects(nodes);
|
494 | if ((this.hasCircularNodes || this.packShape === VirtualizedPackedLayout.Spiral) && this.packShape === VirtualizedPackedLayout.Spiral) {
|
495 | const targetDiameter = Math.max(targetWidth, targetHeight);
|
496 | const oldDiameter = targetDiameter === targetWidth ? bounds0.width : bounds0.height;
|
497 | const newDiameter = targetDiameter === targetWidth ? this._bounds.width : this._bounds.height;
|
498 | const diff = (newDiameter - oldDiameter) / this._fixedSizeModeSpacing;
|
499 | this._fixedSizeModeSpacing = (targetDiameter - oldDiameter) / diff;
|
500 | }
|
501 | else {
|
502 | const dx = (this._bounds.width - bounds0.width) / this._fixedSizeModeSpacing;
|
503 | const dy = (this._bounds.height - bounds0.height) / this._fixedSizeModeSpacing;
|
504 | const paddingX = (targetWidth - bounds0.width) / dx;
|
505 | const paddingY = (targetHeight - bounds0.height) / dy;
|
506 | this._fixedSizeModeSpacing = Math.abs(paddingX) > Math.abs(paddingY) ? paddingX : paddingY;
|
507 | }
|
508 | if (this.packMode === VirtualizedPackedLayout.Fit) {
|
509 | // make sure that the spacing is not positive in this mode
|
510 | this._fixedSizeModeSpacing = Math.min(this._fixedSizeModeSpacing, 0);
|
511 | }
|
512 | if (this._fixedSizeModeSpacing === Infinity) {
|
513 | this._fixedSizeModeSpacing = -maxSize;
|
514 | }
|
515 | this._bounds = new go.Rect();
|
516 | fits = this.hasCircularNodes || this.packShape === VirtualizedPackedLayout.Spiral ? this.fitCircles(nodes) : this.fitRects(nodes);
|
517 | }
|
518 | // move the nodes and calculate the actualBounds property
|
519 | if (this.arrangesToOrigin) {
|
520 | this._actualBounds = new go.Rect(this.arrangementOrigin.x, this.arrangementOrigin.y, 0, 0);
|
521 | }
|
522 | const nodeBounds = new Array(nodes.length);
|
523 | for (let i = 0; i < nodes.length; i++) {
|
524 | const fit = fits[i];
|
525 | const node = nodes[i];
|
526 | if (this.arrangesToOrigin) {
|
527 | // translate coordinates to respect this.arrangementOrigin
|
528 | // this.arrangementOrigin should be the top left corner of the bounding box around the layout
|
529 | fit.x = fit.x - this._bounds.x + this.arrangementOrigin.x;
|
530 | fit.y = fit.y - this._bounds.y + this.arrangementOrigin.y;
|
531 | }
|
532 | this.moveNode(node, fit.x, fit.y);
|
533 | nodeBounds[i] = node.bounds;
|
534 | this._actualBounds.unionRect(node.bounds);
|
535 | }
|
536 | this._nodeBounds = nodeBounds; // save node bounds in case we want to calculate the smallest enclosing circle later
|
537 | // can be overriden to change layout behavior, doesn't do anything by default
|
538 | this.commitLayout();
|
539 | if (diagram !== null)
|
540 | diagram.commitTransaction('Layout');
|
541 | this.isValidLayout = true;
|
542 | }
|
543 | /**
|
544 | * Cause the vertex to be moved so that its position is at (nx,ny).
|
545 | * The default implementation assumes the node.bounds is a Rect that may be modified.
|
546 | * @expose
|
547 | * @param node
|
548 | * @param nx
|
549 | * @param ny
|
550 | */
|
551 | moveNode(node, nx, ny) {
|
552 | node.bounds.x = nx;
|
553 | node.bounds.y = ny;
|
554 | }
|
555 | /**
|
556 | * This method is called at the end of {@link #doLayout}, but
|
557 | * before the layout transaction is committed. It can be overriden and
|
558 | * used to customize layout behavior. By default, the method does nothing.
|
559 | * @expose
|
560 | * @this {VirtualizedPackedLayout}
|
561 | */
|
562 | commitLayout() { }
|
563 | /**
|
564 | * @hidden @internal
|
565 | * Runs a circle packing algorithm on the given array of nodes. The
|
566 | * algorithm used is a slightly modified version of the one proposed
|
567 | * by Wang et al. in "Visualization of large hierarchical data by
|
568 | * circle packing", 2006.
|
569 | * @this {VirtualizedPackedLayout}
|
570 | * @param nodes the array of Nodes to pack
|
571 | * @return {Array<Rect>} an array of positioned rectangles corresponding to the nodes argument
|
572 | */
|
573 | fitCircles(nodes) {
|
574 | function place(a, b, c) {
|
575 | const ax = a.centerX;
|
576 | const ay = a.centerY;
|
577 | let da = (b.width + c.width) / 2;
|
578 | let db = (a.width + c.width) / 2;
|
579 | const dx = b.centerX - ax;
|
580 | const dy = b.centerY - ay;
|
581 | const dc = dx * dx + dy * dy;
|
582 | if (dc) {
|
583 | const x = 0.5 + ((db *= db) - (da *= da)) / (2 * dc);
|
584 | const y = Math.sqrt(Math.max(0, 2 * da * (db + dc) - (db -= dc) * db - da * da)) / (2 * dc);
|
585 | c.x = (ax + x * dx + y * dy) - (c.width / 2);
|
586 | c.y = (ay + x * dy - y * dx) - (c.height / 2);
|
587 | }
|
588 | else {
|
589 | c.x = ax + db;
|
590 | c.y = ay;
|
591 | }
|
592 | return c;
|
593 | }
|
594 | function intersects(a, b) {
|
595 | const ar = a.height / 2;
|
596 | const br = b.height / 2;
|
597 | const dist = Math.sqrt(a.center.distanceSquaredPoint(b.center));
|
598 | const difference = dist - (ar + br);
|
599 | return difference < -0.0000001;
|
600 | }
|
601 | const aspect = this._eAspectRatio;
|
602 | const shape = this.packShape;
|
603 | const placementCost = this.placementCost;
|
604 | function score(n) {
|
605 | const a = n.data;
|
606 | const b = n.next.data;
|
607 | const ar = a.width / 2;
|
608 | const br = b.width / 2;
|
609 | const ab = ar + br;
|
610 | const dx = (a.centerX * br + b.centerX * ar) / ab;
|
611 | const dy = (a.centerY * br + b.centerY * ar) / ab * aspect;
|
612 | return shape === VirtualizedPackedLayout.Elliptical ? dx * dx + dy * dy : Math.max(dx * dx, dy * dy);
|
613 | }
|
614 | const sideSpacing = (this.spacing + this._fixedSizeModeSpacing) / 2;
|
615 | const fits = [];
|
616 | const frontChain = new CircularDoublyLinkedList();
|
617 | if (!nodes.length)
|
618 | return fits;
|
619 | let r1 = nodes[0].bounds.copy().inflate(sideSpacing, sideSpacing);
|
620 | r1.setTo(0, 0, r1.width === 0 ? 0.1 : r1.width, r1.height === 0 ? 0.1 : r1.height);
|
621 | fits.push(r1.setTo(0, 0, r1.width, r1.height));
|
622 | this._bounds.unionRect(r1);
|
623 | if (nodes.length < 2)
|
624 | return fits;
|
625 | let r2 = nodes[1].bounds.copy().inflate(sideSpacing, sideSpacing);
|
626 | r2.setTo(0, 0, r2.width === 0 ? 0.1 : r2.width, r2.height === 0 ? 0.1 : r2.height);
|
627 | fits.push(r2.setTo(-r2.width, r1.centerY - r2.width / 2, r2.width, r2.height));
|
628 | this._bounds.unionRect(r2);
|
629 | if (nodes.length < 3)
|
630 | return fits;
|
631 | let r3 = nodes[2].bounds.copy().inflate(sideSpacing, sideSpacing);
|
632 | r3.setTo(0, 0, r3.width === 0 ? 0.1 : r3.width, r3.height === 0 ? 0.1 : r3.height);
|
633 | fits.push(place(r2, r1, r3));
|
634 | this._bounds.unionRect(r3);
|
635 | let n2 = frontChain.push(r2);
|
636 | let n3 = frontChain.push(r3);
|
637 | let n1 = frontChain.push(r1);
|
638 | pack: for (let i = 3; i < nodes.length; i++) {
|
639 | r3 = nodes[i].bounds.copy().inflate(sideSpacing, sideSpacing);
|
640 | r3.setTo(0, 0, r3.width === 0 ? 0.1 : r3.width, r3.height === 0 ? 0.1 : r3.height);
|
641 | place(n1.data, n2.data, r3);
|
642 | let j = n2.next;
|
643 | let k = n1.prev;
|
644 | let sj = n2.data.width / 2;
|
645 | let sk = n1.data.width / 2;
|
646 | do {
|
647 | if (sj <= sk) {
|
648 | if (intersects(j.data, r3)) {
|
649 | n2 = frontChain.removeBetween(n1, j), i--;
|
650 | continue pack;
|
651 | }
|
652 | sj += j.data.width / 2, j = j.next;
|
653 | }
|
654 | else {
|
655 | if (intersects(k.data, r3)) {
|
656 | frontChain.removeBetween(k, n2);
|
657 | n1 = k, i--;
|
658 | continue pack;
|
659 | }
|
660 | sk += k.data.width / 2, k = k.prev;
|
661 | }
|
662 | } while (j !== k.next);
|
663 | fits.push(r3);
|
664 | this._bounds.unionRect(r3);
|
665 | n2 = n3 = frontChain.insertAfter(r3, n1);
|
666 | if (this.packShape !== VirtualizedPackedLayout.Spiral) {
|
667 | let aa = score(n1);
|
668 | while ((n3 = n3.next) !== n2) {
|
669 | const ca = score(n3);
|
670 | if (ca < aa) {
|
671 | n1 = n3, aa = ca;
|
672 | }
|
673 | }
|
674 | n2 = n1.next;
|
675 | }
|
676 | }
|
677 | return fits;
|
678 | }
|
679 | /**
|
680 | * @hidden @internal
|
681 | * Runs a rectangle packing algorithm on the given array of nodes.
|
682 | * The algorithm presented is original, and operates by maintaining
|
683 | * a representation (with segments) of the perimeter of the already
|
684 | * packed shape. The perimeter of segments is stored in both a linked
|
685 | * list (for ordered iteration) and a quadtree (for fast intersection
|
686 | * detection). Similar to the circle packing algorithm presented
|
687 | * above, this is a greedy algorithm.
|
688 | *
|
689 | * For each node, a large list of possible placements is created,
|
690 | * each one relative to a segment on the perimeter. These placements
|
691 | * are sorted according to a cost function, and then the lowest cost
|
692 | * placement with no intersections is picked. The perimeter
|
693 | * representation is then updated according to the new placement.
|
694 | *
|
695 | * However, in addition to placements made relative to a single segment
|
696 | * on the perimeter, the algorithm also attempts to make placements
|
697 | * between two nonsequential segments ("skip fits"), closing gaps in the
|
698 | * packed shape. If a placement made in this way has no intersections
|
699 | * and a lower cost than any of the original placements, it is picked
|
700 | * instead. This step occurs simultaneously to checking intersections on
|
701 | * the original placement list.
|
702 | *
|
703 | * Intersections for new placements are checked only against the current
|
704 | * perimeter of segments, rather than the entire packed shape.
|
705 | * Additionally, before the quadtree is queried at all, a few closely
|
706 | * surrounding segments to the placement are checked in case an
|
707 | * intersection can be found more quickly. The combination of these two
|
708 | * strategies enables intersection checking to take place extremely
|
709 | * quickly, when it would normally be the slowest part of the entire
|
710 | * algorithm.
|
711 | *
|
712 | * @this {VirtualizedPackedLayout}
|
713 | * @param nodes the array of Nodes to pack
|
714 | * @return {Array<Rect>} an array of positioned rectangles corresponding to the nodes argument
|
715 | */
|
716 | fitRects(nodes) {
|
717 | const sideSpacing = (this.spacing + this._fixedSizeModeSpacing) / 2;
|
718 | const fits = [];
|
719 | const segments = new CircularDoublyLinkedList();
|
720 | // reset layout state
|
721 | this._tree.clear();
|
722 | this._minXSegment = null;
|
723 | this._maxXSegment = null;
|
724 | this._minYSegment = null;
|
725 | this._maxYSegment = null;
|
726 | if (nodes.length < 1) {
|
727 | return fits;
|
728 | }
|
729 | // place first node at 0, 0
|
730 | const bounds0 = nodes[0].bounds;
|
731 | fits.push(new go.Rect(sideSpacing, sideSpacing, bounds0.width, bounds0.height));
|
732 | fits[0].inflate(sideSpacing, sideSpacing);
|
733 | fits[0].setTo(0, 0, fits[0].width === 0 ? 0.1 : fits[0].width, fits[0].height === 0 ? 0.1 : fits[0].height);
|
734 | this._bounds.unionRect(fits[0]);
|
735 | this._center = fits[0].center;
|
736 | const s1 = new Segment(0, 0, fits[0].width, 0, false);
|
737 | const s2 = new Segment(fits[0].width, 0, fits[0].width, fits[0].height, false);
|
738 | const s3 = new Segment(fits[0].width, fits[0].height, 0, fits[0].height, false);
|
739 | const s4 = new Segment(0, fits[0].height, 0, 0, false);
|
740 | this._tree.add(s1);
|
741 | this._tree.add(s2);
|
742 | this._tree.add(s3);
|
743 | this._tree.add(s4);
|
744 | segments.push(s1, s2, s3, s4);
|
745 | this.fixMissingMinMaxSegments(true);
|
746 | for (let i = 1; i < nodes.length; i++) {
|
747 | const node = nodes[i];
|
748 | const bounds = node.bounds.copy().inflate(sideSpacing, sideSpacing);
|
749 | bounds.setTo(0, 0, bounds.width === 0 ? 0.1 : bounds.width, bounds.height === 0 ? 0.1 : bounds.height);
|
750 | const possibleFits = new Array(segments.length);
|
751 | let j = 0;
|
752 | let s = segments.start;
|
753 | do {
|
754 | // make sure segment is perfectly straight (fixing some floating point error)
|
755 | const sdata = s.data;
|
756 | sdata.x1 = s.prev.data.x2;
|
757 | sdata.y1 = s.prev.data.y2;
|
758 | if (sdata.isHorizontal) {
|
759 | sdata.y2 = sdata.y1;
|
760 | }
|
761 | else {
|
762 | sdata.x2 = sdata.x1;
|
763 | }
|
764 | const fitBounds = this.getBestFitRect(s, bounds.width, bounds.height);
|
765 | const cost = this.placementCost(fitBounds);
|
766 | possibleFits[j] = new Fit(fitBounds, cost, s);
|
767 | s = s.next;
|
768 | j++;
|
769 | } while (s !== segments.start);
|
770 | possibleFits.sort((a, b) => {
|
771 | return a.cost - b.cost;
|
772 | });
|
773 | /* scales the cost of skip fits. a number below
|
774 | * one makes skip fits more likely to appear,
|
775 | * which is preferable because they are more
|
776 | * aesthetically pleasing and reduce the total
|
777 | * number of segments.
|
778 | */
|
779 | const skipFitScaleFactor = 0.98;
|
780 | let bestFit = null;
|
781 | let onlyCheckSkipFits = false;
|
782 | for (const fit of possibleFits) {
|
783 | if (bestFit && bestFit.cost <= fit.cost) {
|
784 | onlyCheckSkipFits = true;
|
785 | }
|
786 | let hasIntersections = true; // set initially to true to make skip fit checking work when onlyCheckSkipFits = true
|
787 | if (!onlyCheckSkipFits) {
|
788 | hasIntersections = this.fastFitHasIntersections(fit) || this.fitHasIntersections(fit);
|
789 | if (!hasIntersections) {
|
790 | bestFit = fit;
|
791 | continue;
|
792 | }
|
793 | }
|
794 | // check skip fits
|
795 | if (hasIntersections && !fit.s1.data.p1Concave && (fit.s1.next.data.p1Concave || fit.s1.next.next.data.p1Concave)) {
|
796 | let [nextSegment, usePreviousSegment] = this.findNextOrientedSegment(fit, fit.s1.next);
|
797 | let nextSegmentTouchesFit = false;
|
798 | while (hasIntersections && nextSegment !== null) {
|
799 | fit.bounds = this.rectAgainstMultiSegment(fit.s1, nextSegment, bounds.width, bounds.height);
|
800 | hasIntersections = this.fastFitHasIntersections(fit) || this.fitHasIntersections(fit);
|
801 | nextSegmentTouchesFit = this.segmentIsOnFitPerimeter(nextSegment.data, fit.bounds);
|
802 | if (hasIntersections || !nextSegmentTouchesFit) {
|
803 | [nextSegment, usePreviousSegment] = this.findNextOrientedSegment(fit, nextSegment);
|
804 | }
|
805 | }
|
806 | if (!hasIntersections && nextSegment !== null && nextSegmentTouchesFit) {
|
807 | fit.cost = this.placementCost(fit.bounds) * skipFitScaleFactor;
|
808 | if (bestFit === null || fit.cost <= bestFit.cost) {
|
809 | bestFit = fit;
|
810 | bestFit.s2 = nextSegment;
|
811 | if (usePreviousSegment) {
|
812 | bestFit.s1 = bestFit.s1.prev;
|
813 | }
|
814 | }
|
815 | }
|
816 | }
|
817 | }
|
818 | if (bestFit !== null) {
|
819 | this.updateSegments(bestFit, segments);
|
820 | fits.push(bestFit.bounds);
|
821 | this._bounds.unionRect(bestFit.bounds);
|
822 | }
|
823 | }
|
824 | // save segments in case we want to calculate the enclosing circle later
|
825 | this._segments = segments;
|
826 | return fits;
|
827 | }
|
828 | /**
|
829 | * @hidden @internal
|
830 | * Attempts to find a segment which can be used to create a new skip fit
|
831 | * between fit.s1 and the found segment. A number of conditions are checked
|
832 | * before returning a segment, ensuring that if the skip fit *does* intersect
|
833 | * with the already packed shape, it will do so along the perimeter (so that it
|
834 | * can be detected with only knowledge about the perimeter). Multiple oriented
|
835 | * segments can be found for a given fit, so this function starts searching at
|
836 | * the segment after the given lastSegment parameter.
|
837 | *
|
838 | * Oriented segments can be oriented with either fit.s1, or fit.s1.prev. The
|
839 | * second return value (usePreviousSegment) indicates which the found segment is.
|
840 | *
|
841 | * @this {VirtualizedPackedLayout}
|
842 | * @param fit the fit to search for a new segment for
|
843 | * @param lastSegment the last segment found.
|
844 | */
|
845 | findNextOrientedSegment(fit, lastSegment) {
|
846 | lastSegment = lastSegment.next;
|
847 | const orientation = this.segmentOrientation(fit.s1.prev.data, fit.s1.data);
|
848 | const targetOrientation = (orientation + 1) % 4;
|
849 | while (!this.segmentIsMinOrMax(lastSegment.data)) {
|
850 | const usePreviousSegment = lastSegment.data.isHorizontal === fit.s1.data.isHorizontal;
|
851 | let lastOrientation;
|
852 | if (usePreviousSegment) {
|
853 | lastOrientation = this.segmentOrientation(lastSegment.data, lastSegment.next.data);
|
854 | if (lastSegment.next.data.p1Concave) {
|
855 | lastOrientation = (lastOrientation + 1) % 4;
|
856 | }
|
857 | }
|
858 | else {
|
859 | lastOrientation = this.segmentOrientation(lastSegment.prev.data, lastSegment.data);
|
860 | if (lastSegment.data.p1Concave) {
|
861 | lastOrientation = (lastOrientation + 1) % 4;
|
862 | }
|
863 | }
|
864 | const validLastOrientation = lastOrientation === targetOrientation;
|
865 | const exceededPrimaryDimension = fit.s1.data.isHorizontal ?
|
866 | Math.abs(lastSegment.data.y1 - fit.s1.data.y1) + 1e-7 > fit.bounds.height :
|
867 | Math.abs(lastSegment.data.x1 - fit.s1.data.x1) + 1e-7 > fit.bounds.width;
|
868 | let validCornerPlacement;
|
869 | let exceededSecondaryDimension;
|
870 | switch (orientation) {
|
871 | case Orientation.NE:
|
872 | validCornerPlacement = fit.s1.data.x1 < lastSegment.data.x1;
|
873 | exceededSecondaryDimension = usePreviousSegment ? fit.s1.data.y1 - fit.bounds.height >= lastSegment.data.y1 : fit.s1.data.y2 + fit.bounds.height <= lastSegment.data.y1;
|
874 | break;
|
875 | case Orientation.NW:
|
876 | validCornerPlacement = fit.s1.data.y1 > lastSegment.data.y1;
|
877 | exceededSecondaryDimension = usePreviousSegment ? fit.s1.data.x1 - fit.bounds.width >= lastSegment.data.x1 : fit.s1.data.x2 + fit.bounds.width <= lastSegment.data.x1;
|
878 | break;
|
879 | case Orientation.SW:
|
880 | validCornerPlacement = fit.s1.data.x1 > lastSegment.data.x1;
|
881 | exceededSecondaryDimension = usePreviousSegment ? fit.s1.data.y1 + fit.bounds.height <= lastSegment.data.y1 : fit.s1.data.y2 - fit.bounds.height >= lastSegment.data.y1;
|
882 | break;
|
883 | case Orientation.SE:
|
884 | validCornerPlacement = fit.s1.data.y1 < lastSegment.data.y1;
|
885 | exceededSecondaryDimension = usePreviousSegment ? fit.s1.data.x1 + fit.bounds.width <= lastSegment.data.x1 : fit.s1.data.x2 - fit.bounds.width >= lastSegment.data.x1;
|
886 | break;
|
887 | default:
|
888 | throw new Error('Unknown orientation ' + orientation);
|
889 | }
|
890 | if (!exceededPrimaryDimension && !exceededSecondaryDimension && validCornerPlacement && validLastOrientation) {
|
891 | return [lastSegment, usePreviousSegment];
|
892 | }
|
893 | lastSegment = lastSegment.next;
|
894 | }
|
895 | return [null, false];
|
896 | }
|
897 | /**
|
898 | * @hidden @internal
|
899 | * Returns the orientation of two adjacent segments. s2
|
900 | * is assumed to start at the end of s1.
|
901 | * @this {VirtualizedPackedLayout}
|
902 | * @param s1 the first segment
|
903 | * @param s2 the second segment
|
904 | */
|
905 | segmentOrientation(s1, s2) {
|
906 | if (s1.isHorizontal) {
|
907 | if (s1.x1 < s2.x1) {
|
908 | return s2.p1Concave ? Orientation.SE : Orientation.NE;
|
909 | }
|
910 | else {
|
911 | return s2.p1Concave ? Orientation.NW : Orientation.SW;
|
912 | }
|
913 | }
|
914 | else {
|
915 | if (s1.y1 < s2.y1) {
|
916 | return s2.p1Concave ? Orientation.SW : Orientation.SE;
|
917 | }
|
918 | else {
|
919 | return s2.p1Concave ? Orientation.NE : Orientation.NW;
|
920 | }
|
921 | }
|
922 | }
|
923 | /**
|
924 | * @hidden @internal
|
925 | * Fits a rectangle between two segments (used for skip fits). This is an operation
|
926 | * related more to corners than segments, so fit.s1 should always be supplied for
|
927 | * segment a (even if usePreviousSegment was true in the return value for
|
928 | * {@link #findNextOrientedSegment}).
|
929 | *
|
930 | * @this {VirtualizedPackedLayout}
|
931 | * @param a the first segment to fit between, should always be fit.s1
|
932 | * @param b the second segment to fit between, found with {@link #findNextOrientedSegment}
|
933 | * @param width the width of the rectangle, should be fit.width
|
934 | * @param height the height of the rectangle, should be fit.height
|
935 | */
|
936 | rectAgainstMultiSegment(a, b, width, height) {
|
937 | switch (this.segmentOrientation(a.prev.data, a.data)) {
|
938 | case Orientation.NE:
|
939 | if (a.data.y1 > b.data.y2) {
|
940 | return new go.Rect(b.data.x1 - width, a.data.y1 - height, width, height);
|
941 | }
|
942 | else {
|
943 | return new go.Rect(a.data.x1, b.data.y1 - height, width, height);
|
944 | }
|
945 | case Orientation.NW:
|
946 | if (a.data.x1 > b.data.x2) {
|
947 | return new go.Rect(a.data.x1 - width, b.data.y1, width, height);
|
948 | }
|
949 | else {
|
950 | return new go.Rect(b.data.x1 - width, a.data.y1 - height, width, height);
|
951 | }
|
952 | case Orientation.SW:
|
953 | if (a.data.y1 < b.data.y2) {
|
954 | return new go.Rect(b.data.x1, a.data.y1, width, height);
|
955 | }
|
956 | else {
|
957 | return new go.Rect(a.data.x1 - width, b.data.y1, width, height);
|
958 | }
|
959 | case Orientation.SE:
|
960 | if (a.data.x1 < b.data.x2) {
|
961 | return new go.Rect(a.data.x1, b.data.y1 - height, width, height);
|
962 | }
|
963 | else {
|
964 | return new go.Rect(b.data.x1, a.data.y1, width, height);
|
965 | }
|
966 | }
|
967 | }
|
968 | /**
|
969 | * @hidden @internal
|
970 | * Gets the rectangle placed against the given segment with the lowest
|
971 | * placement cost. Rectangles can be placed against a segment either at
|
972 | * the top/left side, the bottom/right side, or at the center coordinate
|
973 | * of the entire packed shape (if the segment goes through either the x
|
974 | * or y coordinate of the center).
|
975 | * @this {VirtualizedPackedLayout}
|
976 | * @param s the segment to place against
|
977 | * @param width the width of the fit, fit.width
|
978 | * @param height the height of the fit, fit.height
|
979 | */
|
980 | getBestFitRect(s, width, height) {
|
981 | let x1 = s.data.x1;
|
982 | let y1 = s.data.y1;
|
983 | let x2 = s.data.x2;
|
984 | let y2 = s.data.y2;
|
985 | let dir = this.segmentOrientation(s.prev.data, s.data);
|
986 | if (s.data.p1Concave) {
|
987 | dir = (dir + 3) % 4;
|
988 | }
|
989 | const coordIsX = dir === Orientation.NW || dir === Orientation.SE;
|
990 | if (dir === Orientation.NE) {
|
991 | y2 -= height;
|
992 | }
|
993 | else if (dir === Orientation.SE) {
|
994 | x1 -= width;
|
995 | }
|
996 | else if (dir === Orientation.SW) {
|
997 | x1 -= width;
|
998 | y1 -= height;
|
999 | x2 -= width;
|
1000 | }
|
1001 | else if (dir === Orientation.NW) {
|
1002 | y1 -= height;
|
1003 | x2 -= width;
|
1004 | y2 -= height;
|
1005 | }
|
1006 | const r = new go.Rect(x1, y1, width, height);
|
1007 | const cost1 = this.placementCost(r);
|
1008 | const cost2 = this.placementCost(r.setTo(x2, y2, width, height));
|
1009 | let cost3 = Infinity;
|
1010 | if (coordIsX && (this._center.x - (x1 + width / 2)) * (this._center.x - (x2 + width / 2)) < 0) {
|
1011 | cost3 = this.placementCost(r.setTo(this._center.x - width / 2, y1, width, height));
|
1012 | }
|
1013 | else if (!coordIsX && (this._center.y - (y1 + height / 2)) * (this._center.y - (y2 + height / 2)) < 0) {
|
1014 | cost3 = this.placementCost(r.setTo(x1, this._center.y - height / 2, width, height));
|
1015 | }
|
1016 | return cost3 < cost2 && cost3 < cost1 ? r
|
1017 | : (cost2 < cost1 ? r.setTo(x2, y2, width, height)
|
1018 | : r.setTo(x1, y1, width, height));
|
1019 | }
|
1020 | /**
|
1021 | * @hidden @internal
|
1022 | * Checks if a segment is on the perimeter of the given fit bounds.
|
1023 | * Also returns true if the segment is within the rect, but that
|
1024 | * shouldn't matter for any of the cases where this function is used.
|
1025 | * @this {VirtualizedPackedLayout}
|
1026 | * @param s the segment to test
|
1027 | * @param bounds the fit bounds
|
1028 | */
|
1029 | segmentIsOnFitPerimeter(s, bounds) {
|
1030 | const xCoordinatesTogether = this.numberIsBetween(s.x1, bounds.left, bounds.right)
|
1031 | || this.numberIsBetween(s.x2, bounds.left, bounds.right)
|
1032 | || this.numberIsBetween(bounds.left, s.x1, s.x2)
|
1033 | || this.numberIsBetween(bounds.right, s.x1, s.x2);
|
1034 | const yCoordinatesTogether = this.numberIsBetween(s.y1, bounds.top, bounds.bottom)
|
1035 | || this.numberIsBetween(s.y2, bounds.top, bounds.bottom)
|
1036 | || this.numberIsBetween(bounds.top, s.y1, s.y2)
|
1037 | || this.numberIsBetween(bounds.bottom, s.y1, s.y2);
|
1038 | return (s.isHorizontal && (this.approxEqual(s.y1, bounds.top) || this.approxEqual(s.y1, bounds.bottom)) && xCoordinatesTogether)
|
1039 | || (!s.isHorizontal && (this.approxEqual(s.x1, bounds.left) || this.approxEqual(s.x1, bounds.right)) && yCoordinatesTogether);
|
1040 | }
|
1041 | /**
|
1042 | * @hidden @internal
|
1043 | * Checks if a point is on the perimeter of the given fit bounds.
|
1044 | * Also returns true if the point is within the rect, but that
|
1045 | * shouldn't matter for any of the cases where this function is used.
|
1046 | * @this {VirtualizedPackedLayout}
|
1047 | * @param x the x coordinate of the point to test
|
1048 | * @param y the y coordinate of the point to test
|
1049 | * @param bounds the fit bounds
|
1050 | */
|
1051 | pointIsOnFitPerimeter(x, y, bounds) {
|
1052 | return (x >= bounds.left - 1e-7 && x <= bounds.right + 1e-7 && y >= bounds.top - 1e-7 && y <= bounds.bottom + 1e-7);
|
1053 | }
|
1054 | /**
|
1055 | * @hidden @internal
|
1056 | * Checks if a point is on the corner of the given fit bounds.
|
1057 | * @this {VirtualizedPackedLayout}
|
1058 | * @param x the x coordinate of the point to test
|
1059 | * @param y the y coordinate of the point to test
|
1060 | * @param bounds the fit bounds
|
1061 | */
|
1062 | pointIsFitCorner(x, y, bounds) {
|
1063 | return (this.approxEqual(x, bounds.left) && this.approxEqual(y, bounds.top)) ||
|
1064 | (this.approxEqual(x, bounds.right) && this.approxEqual(y, bounds.top)) ||
|
1065 | (this.approxEqual(x, bounds.left) && this.approxEqual(y, bounds.bottom)) ||
|
1066 | (this.approxEqual(x, bounds.right) && this.approxEqual(y, bounds.bottom));
|
1067 | }
|
1068 | /**
|
1069 | * @hidden @internal
|
1070 | * Updates the representation of the perimeter of segments after
|
1071 | * a new placement is made. This modifies the given segments list,
|
1072 | * as well as the quadtree class variable {@link #_tree}.
|
1073 | * Also updates the minimum/maximum segments if they have changed as
|
1074 | * a result of the new placement.
|
1075 | * @this {VirtualizedPackedLayout}
|
1076 | * @param fit the fit to add
|
1077 | * @param segments the list of segments to update
|
1078 | */
|
1079 | updateSegments(fit, segments) {
|
1080 | let s0 = fit.s1;
|
1081 | while (this.pointIsOnFitPerimeter(s0.data.x1, s0.data.y1, fit.bounds)) {
|
1082 | s0 = s0.prev;
|
1083 | }
|
1084 | if (!this.segmentIsMinOrMax(s0.data) || !this.segmentIsMinOrMax(s0.prev.data)) {
|
1085 | let sTest = s0.prev.prev; // test for conflicting segments
|
1086 | let sFound = null;
|
1087 | let minMaxCount = 0;
|
1088 | while (minMaxCount < 2) {
|
1089 | if (this.segmentIsOnFitPerimeter(sTest.data, fit.bounds)) {
|
1090 | sFound = sTest;
|
1091 | }
|
1092 | sTest = sTest.prev;
|
1093 | if (this.segmentIsMinOrMax(sTest.next.data)) {
|
1094 | minMaxCount++;
|
1095 | }
|
1096 | }
|
1097 | if (sFound !== null) {
|
1098 | while (this.pointIsOnFitPerimeter(sFound.data.x1, sFound.data.y1, fit.bounds)) {
|
1099 | sFound = sFound.prev;
|
1100 | }
|
1101 | this.removeBetween(segments, sFound, s0);
|
1102 | s0 = sFound;
|
1103 | }
|
1104 | }
|
1105 | let nextConvexCornerOrientation;
|
1106 | let lastConvexCornerOrientation;
|
1107 | let testOrientation = this.segmentOrientation(s0.prev.data, s0.data);
|
1108 | if (s0.data.p1Concave) {
|
1109 | testOrientation = (testOrientation + 3) % 4;
|
1110 | }
|
1111 | let [cornerX, cornerY] = this.cornerFromRect(testOrientation, fit.bounds);
|
1112 | const extended0 = this.approxEqual(cornerX, s0.data.x2) && this.approxEqual(cornerY, s0.data.y2);
|
1113 | let shortened0Precond;
|
1114 | let [cornerX2, cornerY2] = this.cornerFromRect((testOrientation + 1) % 4, fit.bounds);
|
1115 | if (s0.data.isHorizontal) {
|
1116 | shortened0Precond = this.numberIsBetween(cornerX2, s0.data.x1, s0.data.x2) && this.approxEqual(cornerY2, s0.data.y1);
|
1117 | }
|
1118 | else {
|
1119 | shortened0Precond = this.numberIsBetween(cornerY2, s0.data.y1, s0.data.y2) && this.approxEqual(cornerX2, s0.data.x1);
|
1120 | }
|
1121 | const shortened0 = !extended0 && this.pointIsFitCorner(s0.data.x2, s0.data.y2, fit.bounds)
|
1122 | || !this.pointIsOnFitPerimeter(s0.data.x2, s0.data.y2, fit.bounds)
|
1123 | || (this.pointIsOnFitPerimeter(s0.data.x2, s0.data.y2, fit.bounds)
|
1124 | && !this.pointIsOnFitPerimeter(s0.data.x1, s0.data.y1, fit.bounds)
|
1125 | && shortened0Precond);
|
1126 | if (extended0) {
|
1127 | // extend s0
|
1128 | [s0.data.x2, s0.data.y2] = this.cornerFromRect((testOrientation + 3) % 4, fit.bounds);
|
1129 | this._tree.setTo(s0.data, Segment.rectFromSegment(s0.data));
|
1130 | nextConvexCornerOrientation = (testOrientation + 3) % 4;
|
1131 | this.updateMinMaxSegments(s0.data);
|
1132 | }
|
1133 | else {
|
1134 | if (shortened0) {
|
1135 | [s0.data.x2, s0.data.y2] = this.cornerFromRect((testOrientation + 1) % 4, fit.bounds);
|
1136 | this._tree.setTo(s0.data, Segment.rectFromSegment(s0.data));
|
1137 | }
|
1138 | const newSegment = new Segment(s0.data.x2, s0.data.y2, cornerX, cornerY, true);
|
1139 | s0 = segments.insertAfter(newSegment, s0);
|
1140 | this._tree.add(newSegment);
|
1141 | nextConvexCornerOrientation = testOrientation;
|
1142 | this.updateMinMaxSegments(newSegment);
|
1143 | }
|
1144 | let sNext = fit.s2 ? fit.s2 : s0;
|
1145 | while (this.pointIsOnFitPerimeter(sNext.data.x2, sNext.data.y2, fit.bounds)) {
|
1146 | sNext = sNext.next;
|
1147 | }
|
1148 | if (!this.segmentIsMinOrMax(sNext.data) || !this.segmentIsMinOrMax(sNext.next.data)) {
|
1149 | let sTest = sNext.next.next; // test for conflicting segments
|
1150 | let sFound = null;
|
1151 | let minMaxCount = 0;
|
1152 | while (minMaxCount < 2) {
|
1153 | if (this.segmentIsOnFitPerimeter(sTest.data, fit.bounds)) {
|
1154 | sFound = sTest;
|
1155 | }
|
1156 | sTest = sTest.next;
|
1157 | if (this.segmentIsMinOrMax(sTest.prev.data)) {
|
1158 | minMaxCount++;
|
1159 | }
|
1160 | }
|
1161 | if (sFound !== null) {
|
1162 | sNext = sFound;
|
1163 | while (this.pointIsOnFitPerimeter(sNext.data.x2, sNext.data.y2, fit.bounds)) {
|
1164 | sNext = sNext.next;
|
1165 | }
|
1166 | }
|
1167 | }
|
1168 | testOrientation = this.segmentOrientation(sNext.data, sNext.next.data);
|
1169 | if (sNext.data.p1Concave) {
|
1170 | testOrientation = (testOrientation + 2) % 4;
|
1171 | }
|
1172 | if (sNext.next.data.p1Concave) {
|
1173 | testOrientation = (testOrientation + 1) % 4;
|
1174 | }
|
1175 | [cornerX2, cornerY2] = this.cornerFromRect((testOrientation + 3) % 4, fit.bounds);
|
1176 | if (sNext.data.isHorizontal && this.numberIsBetween(cornerX2, sNext.data.x1, sNext.data.x2) && this.approxEqual(cornerY2, sNext.data.y1)
|
1177 | || (!sNext.data.isHorizontal && this.numberIsBetween(cornerY2, sNext.data.y1, sNext.data.y2) && this.approxEqual(cornerX2, sNext.data.x1))
|
1178 | || (sNext.data.isHorizontal && this.numberIsBetween(fit.bounds.left, sNext.data.x1, sNext.data.x2) && this.numberIsBetween(fit.bounds.right, sNext.data.x1, sNext.data.x2)
|
1179 | && (this.approxEqual(fit.bounds.top, sNext.data.y1) || this.approxEqual(fit.bounds.bottom, sNext.data.y1)))
|
1180 | || (!sNext.data.isHorizontal && this.numberIsBetween(fit.bounds.top, sNext.data.y1, sNext.data.y2) && this.numberIsBetween(fit.bounds.bottom, sNext.data.y1, sNext.data.y2)
|
1181 | && (this.approxEqual(fit.bounds.left, sNext.data.x1) || this.approxEqual(fit.bounds.right, sNext.data.x1)))) {
|
1182 | sNext = sNext.next;
|
1183 | testOrientation = this.segmentOrientation(sNext.data, sNext.next.data);
|
1184 | if (sNext.data.p1Concave) {
|
1185 | testOrientation = (testOrientation + 2) % 4;
|
1186 | }
|
1187 | if (sNext.next.data.p1Concave) {
|
1188 | testOrientation = (testOrientation + 1) % 4;
|
1189 | }
|
1190 | }
|
1191 | this.removeBetween(segments, s0, sNext);
|
1192 | [cornerX, cornerY] = this.cornerFromRect(testOrientation, fit.bounds);
|
1193 | if (this.approxEqual(cornerX, sNext.data.x1) && this.approxEqual(cornerY, sNext.data.y1)) {
|
1194 | // extend sNext
|
1195 | if (s0.data.isHorizontal === sNext.data.isHorizontal && (s0.data.isHorizontal ? this.approxEqual(s0.data.y1, sNext.data.y1) : this.approxEqual(s0.data.x1, sNext.data.x1))) {
|
1196 | s0.data.x2 = sNext.data.x2;
|
1197 | s0.data.y2 = sNext.data.y2;
|
1198 | this.removeSegmentFromLayoutState(sNext);
|
1199 | segments.remove(sNext);
|
1200 | this._tree.setTo(s0.data, Segment.rectFromSegment(s0.data));
|
1201 | lastConvexCornerOrientation = nextConvexCornerOrientation; // no additional segments need to be added
|
1202 | this.updateMinMaxSegments(s0.data);
|
1203 | }
|
1204 | else {
|
1205 | [sNext.data.x1, sNext.data.y1] = this.cornerFromRect((testOrientation + 1) % 4, fit.bounds);
|
1206 | this._tree.setTo(sNext.data, Segment.rectFromSegment(sNext.data));
|
1207 | lastConvexCornerOrientation = (testOrientation + 1) % 4;
|
1208 | this.updateMinMaxSegments(sNext.data);
|
1209 | }
|
1210 | }
|
1211 | else if (extended0 && (s0.data.isHorizontal ?
|
1212 | this.approxEqual(s0.data.y1, sNext.data.y1) && this.numberIsBetween(sNext.data.x1, s0.data.x1, s0.data.x2) :
|
1213 | this.approxEqual(s0.data.x1, sNext.data.x1) && this.numberIsBetween(sNext.data.y1, s0.data.y1, s0.data.y2))) {
|
1214 | if (s0.data.isHorizontal) {
|
1215 | s0.data.x2 = sNext.data.x1;
|
1216 | }
|
1217 | else {
|
1218 | s0.data.y2 = sNext.data.y1;
|
1219 | }
|
1220 | this._tree.setTo(s0.data, Segment.rectFromSegment(s0.data));
|
1221 | lastConvexCornerOrientation = nextConvexCornerOrientation;
|
1222 | sNext.data.p1Concave = true;
|
1223 | this.updateMinMaxSegments(s0.data);
|
1224 | }
|
1225 | else if (!this.pointIsFitCorner(sNext.data.x1, sNext.data.y1, fit.bounds)) {
|
1226 | // add concave segment
|
1227 | const newSegment = new Segment(cornerX, cornerY, sNext.data.x1, sNext.data.y1, false);
|
1228 | if (this.pointIsOnFitPerimeter(sNext.data.x1, sNext.data.y1, fit.bounds)) {
|
1229 | sNext.data.p1Concave = true;
|
1230 | }
|
1231 | else {
|
1232 | newSegment.p1Concave = true;
|
1233 | }
|
1234 | if (this.approxEqual(sNext.prev.data.x1, cornerX) && this.approxEqual(sNext.prev.data.y1, cornerY) && newSegment.isHorizontal === sNext.prev.data.isHorizontal) {
|
1235 | sNext.prev.data.x2 = sNext.data.x1;
|
1236 | sNext.prev.data.y2 = sNext.data.y1;
|
1237 | this._tree.setTo(sNext.prev.data, Segment.rectFromSegment(sNext.prev.data));
|
1238 | lastConvexCornerOrientation = nextConvexCornerOrientation;
|
1239 | }
|
1240 | else {
|
1241 | segments.insertAfter(newSegment, sNext.prev);
|
1242 | this._tree.add(newSegment);
|
1243 | lastConvexCornerOrientation = testOrientation;
|
1244 | this.updateMinMaxSegments(newSegment);
|
1245 | }
|
1246 | }
|
1247 | else { // if (this.pointIsOnFitPerimeter(sNext.data.x1, sNext.data.y1, fit.bounds))
|
1248 | // shorten existing segment
|
1249 | [sNext.data.x1, sNext.data.y1] = this.cornerFromRect((testOrientation + 3) % 4, fit.bounds);
|
1250 | sNext.data.p1Concave = true;
|
1251 | this._tree.setTo(sNext.data, Segment.rectFromSegment(sNext.data));
|
1252 | lastConvexCornerOrientation = (testOrientation + 3) % 4;
|
1253 | }
|
1254 | while (nextConvexCornerOrientation !== lastConvexCornerOrientation) {
|
1255 | [cornerX, cornerY] = this.cornerFromRect((nextConvexCornerOrientation + 3) % 4, fit.bounds);
|
1256 | const newSegment = new Segment(s0.data.x2, s0.data.y2, cornerX, cornerY, false);
|
1257 | s0 = segments.insertAfter(newSegment, s0);
|
1258 | this._tree.add(newSegment);
|
1259 | nextConvexCornerOrientation = (nextConvexCornerOrientation + 3) % 4;
|
1260 | this.updateMinMaxSegments(newSegment);
|
1261 | }
|
1262 | this.fixMissingMinMaxSegments();
|
1263 | }
|
1264 | /**
|
1265 | * @hidden @internal
|
1266 | * Finds the new minimum and maximum segments in the packed shape if
|
1267 | * any of them have been deleted. To do this quickly, the quadtree
|
1268 | * is used.
|
1269 | * @this{VirtualizedPackedLayout}
|
1270 | * @param force whether or not to force an update based on the quadtree even if none of the segments were deleted
|
1271 | */
|
1272 | fixMissingMinMaxSegments(force = false) {
|
1273 | if (!this._minXSegment || !this._maxXSegment || !this._minYSegment || !this._maxYSegment || force) {
|
1274 | [this._minXSegment, this._maxXSegment, this._minYSegment, this._maxYSegment] = this._tree.findExtremeObjects();
|
1275 | }
|
1276 | }
|
1277 | /**
|
1278 | * @hidden @internal
|
1279 | * Updates the minimum or maximum segments with a new segment if that
|
1280 | * segment is a new minimum or maximum.
|
1281 | * @this {VirtualizedPackedLayout}
|
1282 | * @param s the new segment to test
|
1283 | */
|
1284 | updateMinMaxSegments(s) {
|
1285 | const centerX = (s.x1 + s.x2) / 2;
|
1286 | const centerY = (s.y1 + s.y2) / 2;
|
1287 | if (this._minXSegment && centerX < (this._minXSegment.x1 + this._minXSegment.x2) / 2) {
|
1288 | this._minXSegment = s;
|
1289 | }
|
1290 | if (this._minYSegment && centerY < (this._minYSegment.y1 + this._minYSegment.y2) / 2) {
|
1291 | this._minYSegment = s;
|
1292 | }
|
1293 | if (this._maxXSegment && centerX > (this._maxXSegment.x1 + this._maxXSegment.x2) / 2) {
|
1294 | this._maxXSegment = s;
|
1295 | }
|
1296 | if (this._maxYSegment && centerY > (this._maxYSegment.y1 + this._maxYSegment.y2) / 2) {
|
1297 | this._maxYSegment = s;
|
1298 | }
|
1299 | }
|
1300 | /**
|
1301 | * @hidden @internal
|
1302 | * Gets the x and y coordinates of a corner of a given rectangle.
|
1303 | * @this {VirtualizedPackedLayout}
|
1304 | * @param orientation the orientation of the corner to get
|
1305 | * @param bounds the bounds of the rectangle to get the corner from
|
1306 | */
|
1307 | cornerFromRect(orientation, bounds) {
|
1308 | let x = bounds.x;
|
1309 | let y = bounds.y;
|
1310 | if (orientation === Orientation.NE || orientation === Orientation.SE) {
|
1311 | x = bounds.right;
|
1312 | }
|
1313 | if (orientation === Orientation.SW || orientation === Orientation.SE) {
|
1314 | y = bounds.bottom;
|
1315 | }
|
1316 | return [x, y];
|
1317 | }
|
1318 | /**
|
1319 | * @hidden @internal
|
1320 | * Tests if a number is in between two other numbers, with included
|
1321 | * allowance for some floating point error with the supplied values.
|
1322 | * The order of the given boundaries does not matter.
|
1323 | * @this {VirtualizedPackedLayout}
|
1324 | * @param n the number to test
|
1325 | * @param b1 the first boundary
|
1326 | * @param b2 the second boundary
|
1327 | */
|
1328 | numberIsBetween(n, b1, b2) {
|
1329 | const tmp = b1;
|
1330 | b1 = Math.min(b1, b2);
|
1331 | b2 = Math.max(tmp, b2);
|
1332 | return n + 1e-7 >= b1 && n - 1e-7 <= b2;
|
1333 | }
|
1334 | /**
|
1335 | * @hidden @internal
|
1336 | * Tests whether or not a given segment is a minimum or maximum segment.
|
1337 | * @this {VirtualizedPackedLayout}
|
1338 | * @param s the segment to test
|
1339 | */
|
1340 | segmentIsMinOrMax(s) {
|
1341 | return s === this._minXSegment || s === this._minYSegment || s === this._maxXSegment || s === this._maxYSegment;
|
1342 | }
|
1343 | /**
|
1344 | * @hidden @internal
|
1345 | * Removes a segment from the layout state. This includes removing it
|
1346 | * from the quadtree, as well as setting the corresponding minimum or
|
1347 | * maximum segment to null if the given segment is a minimum or
|
1348 | * maximum.
|
1349 | * @this {VirtualizedPackedLayout}
|
1350 | * @param s the segment to remove
|
1351 | */
|
1352 | removeSegmentFromLayoutState(s) {
|
1353 | if (s.data === this._minXSegment) {
|
1354 | this._minXSegment = null;
|
1355 | }
|
1356 | if (s.data === this._maxXSegment) {
|
1357 | this._maxXSegment = null;
|
1358 | }
|
1359 | if (s.data === this._minYSegment) {
|
1360 | this._minYSegment = null;
|
1361 | }
|
1362 | if (s.data === this._maxYSegment) {
|
1363 | this._maxYSegment = null;
|
1364 | }
|
1365 | this._tree.remove(s.data);
|
1366 | }
|
1367 | /**
|
1368 | * @hidden @internal
|
1369 | * Removes all segments between the two given segments (exclusive).
|
1370 | * This includes removing them from the layout state, as well as
|
1371 | * the given segment list.
|
1372 | * @this {VirtualizedPackedLayout}
|
1373 | * @param segments the full list of segments
|
1374 | * @param s1 the first segment
|
1375 | * @param s2 the second segment
|
1376 | */
|
1377 | removeBetween(segments, s1, s2) {
|
1378 | if (s1 === s2)
|
1379 | return;
|
1380 | let last = s1.next;
|
1381 | let count = 0;
|
1382 | while (last !== s2) {
|
1383 | if (last === segments.start) {
|
1384 | segments.start = s2;
|
1385 | }
|
1386 | this.removeSegmentFromLayoutState(last);
|
1387 | count++;
|
1388 | last = last.next;
|
1389 | }
|
1390 | s1.next = s2;
|
1391 | s2.prev = s1;
|
1392 | segments.length -= count;
|
1393 | }
|
1394 | /**
|
1395 | * @hidden @internal
|
1396 | * Calculates the cost of a given fit placement, depending on the
|
1397 | * {@link #packShape} and {@link #_eAspectRatio}.
|
1398 | * @this {VirtualizedPackedLayout}
|
1399 | * @param fit the fit to calculate the cost of
|
1400 | */
|
1401 | placementCost(fit) {
|
1402 | if (this.packShape === VirtualizedPackedLayout.Rectangular) {
|
1403 | if (this._bounds.containsRect(fit)) {
|
1404 | return 0;
|
1405 | }
|
1406 | return Math.max(Math.abs(this._center.x - fit.center.x), Math.abs(this._center.y - fit.center.y) * this._eAspectRatio);
|
1407 | }
|
1408 | else { // if (this.packShape === VirtualizedPackedLayout.Elliptical)
|
1409 | return Math.pow((fit.center.x - this._center.x) / this._eAspectRatio, 2) + Math.pow(fit.center.y - this._center.y, 2);
|
1410 | }
|
1411 | }
|
1412 | /**
|
1413 | * @hidden @internal
|
1414 | * Uses the quadtree to determine if the given fit has any
|
1415 | * intersections anywhere along the perimeter.
|
1416 | * @this {VirtualizedPackedLayout}
|
1417 | * @param fit the fit to check
|
1418 | */
|
1419 | fitHasIntersections(fit) {
|
1420 | return this._tree.intersecting(fit.bounds).length > 0;
|
1421 | }
|
1422 | /**
|
1423 | * @hidden @internal
|
1424 | * Checks if a few nearby segments intersect with the given fit,
|
1425 | * producing faster interesection detection than a complete check
|
1426 | * with the quadtree in many cases. However, since it doesn't check
|
1427 | * the entire perimeter, this function is susceptible to false
|
1428 | * negatives and should only be used with a more comprehensive check.
|
1429 | * @this {VirtualizedPackedLayout}
|
1430 | * @param fit the fit to check
|
1431 | */
|
1432 | fastFitHasIntersections(fit) {
|
1433 | let sNext = fit.s1.next;
|
1434 | let sPrev = fit.s1.prev;
|
1435 | for (let i = 0; i < 2; i++) {
|
1436 | if (this.segmentIntersectsRect(sNext.data, fit.bounds)) {
|
1437 | return true;
|
1438 | }
|
1439 | if (this.segmentIntersectsRect(sPrev.data, fit.bounds)) {
|
1440 | return true;
|
1441 | }
|
1442 | sNext = sNext.next;
|
1443 | sPrev = sPrev.prev;
|
1444 | }
|
1445 | return false;
|
1446 | }
|
1447 | /**
|
1448 | * @hidden @internal
|
1449 | * Checks whether or not a segment intersects with a given rect.
|
1450 | * Used for {@link #fastFitHasIntersections}.
|
1451 | * @this {VirtualizedPackedLayout}
|
1452 | * @param s the segment to test
|
1453 | * @param r the rectangle to test
|
1454 | */
|
1455 | segmentIntersectsRect(s, r) {
|
1456 | const left = Math.min(s.x1, s.x2);
|
1457 | const right = Math.max(s.x1, s.x2);
|
1458 | const top = Math.min(s.y1, s.y2);
|
1459 | const bottom = Math.min(s.y1, s.y2);
|
1460 | return !(left + 1e-7 >= r.right || right - 1e-7 <= r.left || top + 1e-7 >= r.bottom || bottom - 1e-7 <= r.top);
|
1461 | }
|
1462 | /**
|
1463 | * @hidden @internal
|
1464 | * Checks if two numbers are approximately equal, used for
|
1465 | * eliminating mistakes caused by floating point error.
|
1466 | * @this {VirtualizedPackedLayout}
|
1467 | * @param x the first number
|
1468 | * @param y the second number
|
1469 | */
|
1470 | approxEqual(x, y) {
|
1471 | return Math.abs(x - y) < 1e-7;
|
1472 | }
|
1473 | /**
|
1474 | * @hidden @internal
|
1475 | * Checks if a value is a number, used for parameter validation
|
1476 | * @this {VirtualizedPackedLayout}
|
1477 | * @param value the value to check
|
1478 | */
|
1479 | isNumeric(value) {
|
1480 | return !isNaN(Number(value.toString()));
|
1481 | }
|
1482 | /**
|
1483 | * @hidden @internal
|
1484 | * Copies properties to a cloned Layout.
|
1485 | * @this {VirtualizedPackedLayout}
|
1486 | * @param {?} copy
|
1487 | */
|
1488 | cloneProtected(copy) {
|
1489 | copy._packShape = this._packShape;
|
1490 | copy._packMode = this._packMode;
|
1491 | copy._sortMode = this._sortMode;
|
1492 | copy._sortOrder = this._sortOrder;
|
1493 | copy._comparer = this._comparer;
|
1494 | copy._aspectRatio = this._aspectRatio;
|
1495 | copy._size = this._size;
|
1496 | copy._spacing = this._spacing;
|
1497 | copy._hasCircularNodes = this._hasCircularNodes;
|
1498 | copy._arrangesToOrigin = this._arrangesToOrigin;
|
1499 | }
|
1500 | }
|
1501 | /********************** Configuration constants **********************/
|
1502 | // These values determine the shape of the final layout
|
1503 | /**
|
1504 | * This value for {@link #packShape} causes nodes to be packed
|
1505 | * into an ellipse.
|
1506 | *
|
1507 | * The aspect ratio of this ellipse is determined by either
|
1508 | * {@link #aspectRatio} or {@link #size}.
|
1509 | * @constant
|
1510 | */
|
1511 | VirtualizedPackedLayout.Elliptical = 0;
|
1512 | /**
|
1513 | * Causes nodes to be packed into a rectangle; this value is used for
|
1514 | * {@link #packShape}.
|
1515 | *
|
1516 | * The aspect ratio of this rectangle is determined by either
|
1517 | * {@link #aspectRatio} or {@link #size}.
|
1518 | * @constant
|
1519 | */
|
1520 | VirtualizedPackedLayout.Rectangular = 1;
|
1521 | /**
|
1522 | * Causes nodes to be packed into a spiral shape; this value is used
|
1523 | * for {@link #packShape}.
|
1524 | *
|
1525 | * The {@link #aspectRatio} property is ignored in this mode, the
|
1526 | * {@link #size} is expected to be square, and {@link #hasCircularNodes}
|
1527 | * will be assumed 'true'. Please see {@link #packShape} for more details.
|
1528 | */
|
1529 | VirtualizedPackedLayout.Spiral = 2;
|
1530 | // These values determine the size of the layout
|
1531 | /**
|
1532 | * Nodes will be packed using the {@link #aspectRatio} property, with
|
1533 | * no size considerations; this value is used for {@link #packMode}.
|
1534 | *
|
1535 | * The {@link #spacing} property will be respected in this mode.
|
1536 | * @constant
|
1537 | */
|
1538 | VirtualizedPackedLayout.AspectOnly = 10;
|
1539 | /**
|
1540 | * Nodes will be compressed if necessary (using negative spacing) to fit the given
|
1541 | * {@link #size}. However, if the {@link #size} is bigger
|
1542 | * than the packed shape (with 0 spacing), it will not expand to fit it. This value
|
1543 | * is used for {@link #packMode}.
|
1544 | *
|
1545 | * The {@link #spacing} property will be respected in this mode, but only
|
1546 | * if it does not cause the layout to grow larger than the {@link #size}.
|
1547 | * @constant
|
1548 | */
|
1549 | VirtualizedPackedLayout.Fit = 11;
|
1550 | /**
|
1551 | * Nodes will be either compressed or spaced evenly to fit the given
|
1552 | * {@link #size}; this value is used for {@link #packMode}.
|
1553 | *
|
1554 | * The {@link #spacing} property will not be respected in this mode, and
|
1555 | * will not do anything if set.
|
1556 | * @constant
|
1557 | */
|
1558 | VirtualizedPackedLayout.ExpandToFit = 12;
|
1559 | // These values specify an optional method by which to sort nodes before packing
|
1560 | /**
|
1561 | * Nodes will not be sorted before packing; this value is used for {@link #sortMode}.
|
1562 | * @constant
|
1563 | */
|
1564 | VirtualizedPackedLayout.None = 20;
|
1565 | /**
|
1566 | * Nodes will be sorted by their maximum side length before packing; this value is
|
1567 | * used for {@link #sortMode}.
|
1568 | * @constant
|
1569 | */
|
1570 | VirtualizedPackedLayout.MaxSide = 21;
|
1571 | /**
|
1572 | * Nodes will be sorted by their area; this value is used for {@link #sortMode}.
|
1573 | * @constant
|
1574 | */
|
1575 | VirtualizedPackedLayout.Area = 22;
|
1576 | // These values specify the order that nodes will be sorted, if applicable
|
1577 | /**
|
1578 | * Nodes will be sorted in descending order; this value is used for {@link #sortOrder}.
|
1579 | *
|
1580 | * Does nothing if {@link #sortMode} is set to {@link VirtualizedPackedLayout.None}.
|
1581 | * @constant
|
1582 | */
|
1583 | VirtualizedPackedLayout.Descending = 30;
|
1584 | /**
|
1585 | * Nodes will be sorted in ascending order; this value is used for {@link #sortOrder}.
|
1586 | *
|
1587 | * Does nothing if {@link #sortMode} is set to {@link VirtualizedPackedLayout.None}.
|
1588 | * @constant
|
1589 | */
|
1590 | VirtualizedPackedLayout.Ascending = 31;
|
1591 | /**
|
1592 | * @hidden @internal
|
1593 | * Class for a node in a {{@link CircularDoublyLinkedList}.
|
1594 | * Stores a pointer to the previous and next node.
|
1595 | */
|
1596 | class ListNode {
|
1597 | constructor(data, prev, next) {
|
1598 | this.data = data;
|
1599 | this.prev = prev !== undefined ? prev : this;
|
1600 | this.next = next !== undefined ? next : this;
|
1601 | }
|
1602 | }
|
1603 | /**
|
1604 | * @hidden @internal
|
1605 | * A Circular doubly linked list, used by {@link VirtualizedPackedLayout} to
|
1606 | * efficiently store {@link Segment}s with fast insertion and
|
1607 | * deletion time.
|
1608 | */
|
1609 | class CircularDoublyLinkedList {
|
1610 | /**
|
1611 | * Constructs a new list with an optional list of values
|
1612 | * @param vals values to create the list with
|
1613 | */
|
1614 | constructor(...vals) {
|
1615 | /**
|
1616 | * The start of the list, null when the list is empty.
|
1617 | */
|
1618 | this.start = null;
|
1619 | /**
|
1620 | * The length of the list.
|
1621 | */
|
1622 | this.length = 0;
|
1623 | if (vals.length > 0) {
|
1624 | this.push(...vals);
|
1625 | }
|
1626 | }
|
1627 | /**
|
1628 | * Inserts the given value directly after the given node
|
1629 | * @this {CircularDoublyLinkedList}
|
1630 | * @param val the value to insert
|
1631 | * @param node the node to insert after
|
1632 | * @return {ListNode<T>} the new node
|
1633 | */
|
1634 | insertAfter(val, node) {
|
1635 | if (node === null) {
|
1636 | const newnode = new ListNode(val);
|
1637 | newnode.prev = newnode;
|
1638 | newnode.next = newnode;
|
1639 | this.length = 1;
|
1640 | return this.start = newnode;
|
1641 | }
|
1642 | const tmp = node.next;
|
1643 | node.next = new ListNode(val, node, tmp);
|
1644 | tmp.prev = node.next;
|
1645 | this.length++;
|
1646 | return node.next;
|
1647 | }
|
1648 | /**
|
1649 | * Inserts the given value or values at the end of the list
|
1650 | * @this {CircularDoublyLinkedList}
|
1651 | * @param vals the value(s) to insert
|
1652 | * @return {ListNode<T>} the node for the last value inserted (a list of values is inserted sequentially)
|
1653 | */
|
1654 | push(...vals) {
|
1655 | if (vals.length === 0) {
|
1656 | throw new Error('You must push at least one element!');
|
1657 | }
|
1658 | const sp = this.start !== null ? this.start.prev : null;
|
1659 | let last = this.insertAfter(vals[0], sp);
|
1660 | for (let i = 1; i < vals.length; i++) {
|
1661 | last = this.insertAfter(vals[i], last);
|
1662 | }
|
1663 | return last;
|
1664 | }
|
1665 | /**
|
1666 | * Removes the given node from the list
|
1667 | * @this {CircularDoublyLinkedList}
|
1668 | * @param node the node to remove
|
1669 | */
|
1670 | remove(node) {
|
1671 | this.length--;
|
1672 | if (this.length) {
|
1673 | node.prev.next = node.next;
|
1674 | node.next.prev = node.prev;
|
1675 | if (node === this.start) {
|
1676 | this.start = node.next;
|
1677 | }
|
1678 | }
|
1679 | else {
|
1680 | this.start = null;
|
1681 | }
|
1682 | }
|
1683 | /**
|
1684 | * Removes all nodes between the given start and end point (exclusive).
|
1685 | * Returns the given end node.
|
1686 | * @this {CircularDoublyLinkedList}
|
1687 | * @param start node to start removing after
|
1688 | * @param end node to stop removing at
|
1689 | * @return {ListNode<T>} the end node
|
1690 | */
|
1691 | removeBetween(start, end) {
|
1692 | if (start !== end) {
|
1693 | let last = start.next;
|
1694 | let count = 0;
|
1695 | while (last !== end) {
|
1696 | if (last === this.start) {
|
1697 | this.start = end;
|
1698 | }
|
1699 | count++;
|
1700 | last = last.next;
|
1701 | }
|
1702 | start.next = end;
|
1703 | end.prev = start;
|
1704 | this.length -= count;
|
1705 | return end;
|
1706 | }
|
1707 | return start;
|
1708 | }
|
1709 | }
|
1710 | /**
|
1711 | * The following is a BSD-licensed implementation of the
|
1712 | * Matousek-Sharir-Welzl algorithm for finding the smallest
|
1713 | * enclosing circle around a given set of circles. The
|
1714 | * original algorithm was adapted to support enclosing points
|
1715 | * by assuming that the radius of a point is 0.
|
1716 | */
|
1717 | /**
|
1718 | * Copyright 2010-2016 Mike Bostock
|
1719 | * All rights reserved.
|
1720 | *
|
1721 | * Redistribution and use in source and binary forms, with or without modification,
|
1722 | * are permitted provided that the following conditions are met:
|
1723 | *
|
1724 | * * Redistributions of source code must retain the above copyright notice, this
|
1725 | * list of conditions and the following disclaimer.
|
1726 | *
|
1727 | * * Redistributions in binary form must reproduce the above copyright notice,
|
1728 | * this list of conditions and the following disclaimer in the documentation
|
1729 | * and/or other materials provided with the distribution.
|
1730 | *
|
1731 | * * Neither the name of the author nor the names of contributors may be used to
|
1732 | * endorse or promote products derived from this software without specific prior
|
1733 | * written permission.
|
1734 | *
|
1735 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
|
1736 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
|
1737 | * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
|
1738 | * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
|
1739 | * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
|
1740 | * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
|
1741 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
|
1742 | * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
|
1743 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
|
1744 | * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
1745 | */
|
1746 | /**
|
1747 | * @hidden @internal
|
1748 | * Represents a circle for the purposes of the smallest-enclosing
|
1749 | * circle algorithm. The x and y values represent the center of
|
1750 | * the circle.
|
1751 | */
|
1752 | class Circle extends go.Point {
|
1753 | constructor(x, y, r) {
|
1754 | super(x, y);
|
1755 | this.r = r;
|
1756 | }
|
1757 | }
|
1758 | /**
|
1759 | * @hidden @internal
|
1760 | * @param circles array of circles of points to find the enclosing circle for
|
1761 | */
|
1762 | function enclose(circles) {
|
1763 | let i = 0;
|
1764 | const n = (circles = shuffle(circles.slice())).length;
|
1765 | let B = new Array();
|
1766 | let p;
|
1767 | let e = null;
|
1768 | while (i < n) {
|
1769 | p = circles[i];
|
1770 | if (e !== null && enclosesWeak(e, p))
|
1771 | ++i;
|
1772 | else
|
1773 | e = encloseBasis(B = extendBasis(B, p)), i = 0;
|
1774 | }
|
1775 | if (e !== null) {
|
1776 | return circleToRect(e);
|
1777 | }
|
1778 | else { // this will never happen, but needs to be here for strict TypeScript compilation
|
1779 | throw new Error('Assertion error');
|
1780 | }
|
1781 | }
|
1782 | /**
|
1783 | * @hidden @internal
|
1784 | * Converts a Circle to a go.Rect object
|
1785 | * @param c the Circle to convert
|
1786 | */
|
1787 | function circleToRect(c) {
|
1788 | return new go.Rect(c.x - c.r, c.y - c.r, c.r * 2, c.r * 2);
|
1789 | }
|
1790 | /**
|
1791 | * @hidden @internal
|
1792 | */
|
1793 | function extendBasis(B, p) {
|
1794 | if (enclosesWeakAll(p, B))
|
1795 | return [p];
|
1796 | // If we get here then B must have at least one element.
|
1797 | for (let i = 0; i < B.length; ++i) {
|
1798 | if (enclosesNot(p, B[i])
|
1799 | && enclosesWeakAll(encloseBasis2(B[i], p), B)) {
|
1800 | return [B[i], p];
|
1801 | }
|
1802 | }
|
1803 | // If we get here then B must have at least two elements.
|
1804 | for (let i = 0; i < B.length - 1; ++i) {
|
1805 | for (let j = i + 1; j < B.length; ++j) {
|
1806 | if (enclosesNot(encloseBasis2(B[i], B[j]), p)
|
1807 | && enclosesNot(encloseBasis2(B[i], p), B[j])
|
1808 | && enclosesNot(encloseBasis2(B[j], p), B[i])
|
1809 | && enclosesWeakAll(encloseBasis3(B[i], B[j], p), B)) {
|
1810 | return [B[i], B[j], p];
|
1811 | }
|
1812 | }
|
1813 | }
|
1814 | // If we get here then something is very wrong.
|
1815 | throw new Error('Assertion error');
|
1816 | }
|
1817 | /**
|
1818 | * @hidden @internal
|
1819 | */
|
1820 | function enclosesNot(a, b) {
|
1821 | const ar = a instanceof Circle ? a.r : 0;
|
1822 | const br = b instanceof Circle ? b.r : 0;
|
1823 | const dr = ar - br;
|
1824 | const dx = b.x - a.x;
|
1825 | const dy = b.y - a.y;
|
1826 | return dr < 0 || dr * dr < dx * dx + dy * dy;
|
1827 | }
|
1828 | /**
|
1829 | * @hidden @internal
|
1830 | */
|
1831 | function enclosesWeak(a, b) {
|
1832 | const ar = a instanceof Circle ? a.r : 0;
|
1833 | const br = b instanceof Circle ? b.r : 0;
|
1834 | const dr = ar - br + 1e-6;
|
1835 | const dx = b.x - a.x;
|
1836 | const dy = b.y - a.y;
|
1837 | return dr > 0 && dr * dr > dx * dx + dy * dy;
|
1838 | }
|
1839 | /**
|
1840 | * @hidden @internal
|
1841 | */
|
1842 | function enclosesWeakAll(a, B) {
|
1843 | for (let i = 0; i < B.length; ++i) {
|
1844 | if (!enclosesWeak(a, B[i])) {
|
1845 | return false;
|
1846 | }
|
1847 | }
|
1848 | return true;
|
1849 | }
|
1850 | /**
|
1851 | * @hidden @internal
|
1852 | */
|
1853 | function encloseBasis(B) {
|
1854 | switch (B.length) {
|
1855 | case 2: return encloseBasis2(B[0], B[1]);
|
1856 | case 3: return encloseBasis3(B[0], B[1], B[2]);
|
1857 | default: return encloseBasis1(B[0]); // case 1
|
1858 | }
|
1859 | }
|
1860 | /**
|
1861 | * @hidden @internal
|
1862 | */
|
1863 | function encloseBasis1(a) {
|
1864 | const ar = a instanceof Circle ? a.r : 0;
|
1865 | return new Circle(a.x, a.y, ar);
|
1866 | }
|
1867 | /**
|
1868 | * @hidden @internal
|
1869 | */
|
1870 | function encloseBasis2(a, b) {
|
1871 | const ar = a instanceof Circle ? a.r : 0;
|
1872 | const br = b instanceof Circle ? b.r : 0;
|
1873 | const x1 = a.x;
|
1874 | const y1 = a.y;
|
1875 | const r1 = ar;
|
1876 | const x2 = b.x;
|
1877 | const y2 = b.y;
|
1878 | const r2 = br;
|
1879 | const x21 = x2 - x1;
|
1880 | const y21 = y2 - y1;
|
1881 | const r21 = r2 - r1;
|
1882 | const l = Math.sqrt(x21 * x21 + y21 * y21);
|
1883 | return new Circle((x1 + x2 + x21 / l * r21) / 2, (y1 + y2 + y21 / l * r21) / 2, (l + r1 + r2) / 2);
|
1884 | }
|
1885 | /**
|
1886 | * @hidden @internal
|
1887 | */
|
1888 | function encloseBasis3(a, b, c) {
|
1889 | const ar = a instanceof Circle ? a.r : 0;
|
1890 | const br = b instanceof Circle ? b.r : 0;
|
1891 | const cr = c instanceof Circle ? c.r : 0;
|
1892 | const x1 = a.x;
|
1893 | const y1 = a.y;
|
1894 | const r1 = ar;
|
1895 | const x2 = b.x;
|
1896 | const y2 = b.y;
|
1897 | const r2 = br;
|
1898 | const x3 = c.x;
|
1899 | const y3 = c.y;
|
1900 | const r3 = cr;
|
1901 | const a2 = x1 - x2;
|
1902 | const a3 = x1 - x3;
|
1903 | const b2 = y1 - y2;
|
1904 | const b3 = y1 - y3;
|
1905 | const c2 = r2 - r1;
|
1906 | const c3 = r3 - r1;
|
1907 | const d1 = x1 * x1 + y1 * y1 - r1 * r1;
|
1908 | const d2 = d1 - x2 * x2 - y2 * y2 + r2 * r2;
|
1909 | const d3 = d1 - x3 * x3 - y3 * y3 + r3 * r3;
|
1910 | const ab = a3 * b2 - a2 * b3;
|
1911 | const xa = (b2 * d3 - b3 * d2) / (ab * 2) - x1;
|
1912 | const xb = (b3 * c2 - b2 * c3) / ab;
|
1913 | const ya = (a3 * d2 - a2 * d3) / (ab * 2) - y1;
|
1914 | const yb = (a2 * c3 - a3 * c2) / ab;
|
1915 | const A = xb * xb + yb * yb - 1;
|
1916 | const B = 2 * (r1 + xa * xb + ya * yb);
|
1917 | const C = xa * xa + ya * ya - r1 * r1;
|
1918 | const r = -(A ? (B + Math.sqrt(B * B - 4 * A * C)) / (2 * A) : C / B);
|
1919 | return new Circle(x1 + xa + xb * r, y1 + ya + yb * r, r);
|
1920 | }
|
1921 | /**
|
1922 | * @hidden @internal
|
1923 | * Shuffles array in place.
|
1924 | * @param {Array} a items An array containing the items.
|
1925 | */
|
1926 | function shuffle(a) {
|
1927 | let j;
|
1928 | let x;
|
1929 | let i;
|
1930 | for (i = a.length - 1; i > 0; i--) {
|
1931 | j = Math.floor(Math.random() * (i + 1));
|
1932 | x = a[i];
|
1933 | a[i] = a[j];
|
1934 | a[j] = x;
|
1935 | }
|
1936 | return a;
|
1937 | }
|