1 |
|
2 |
|
3 |
|
4 |
|
5 |
|
6 |
|
7 |
|
8 |
|
9 |
|
10 |
|
11 |
|
12 |
|
13 | import * as go from '../release/go-module.js';
|
14 | import { Quadtree } from './Quadtree.js';
|
15 |
|
16 |
|
17 |
|
18 |
|
19 |
|
20 |
|
21 |
|
22 |
|
23 |
|
24 |
|
25 | class Segment {
|
26 | public x1: number;
|
27 | public y1: number;
|
28 | public x2: number;
|
29 | public y2: number;
|
30 | public p1Concave: boolean;
|
31 | public isHorizontal: boolean;
|
32 |
|
33 | |
34 |
|
35 |
|
36 |
|
37 |
|
38 |
|
39 |
|
40 |
|
41 |
|
42 |
|
43 |
|
44 | constructor(x1: number, y1: number, x2: number, y2: number, p1Concave: boolean) {
|
45 | this.x1 = x1;
|
46 | this.y1 = y1;
|
47 | this.x2 = x2;
|
48 | this.y2 = y2;
|
49 | this.p1Concave = p1Concave;
|
50 | this.isHorizontal = Math.abs(y2 - y1) < 1e-7;
|
51 | }
|
52 | }
|
53 |
|
54 |
|
55 |
|
56 |
|
57 |
|
58 |
|
59 | enum Orientation {
|
60 | NE,
|
61 | NW,
|
62 | SW,
|
63 | SE
|
64 | }
|
65 |
|
66 |
|
67 |
|
68 |
|
69 |
|
70 |
|
71 |
|
72 |
|
73 |
|
74 |
|
75 |
|
76 | class Fit {
|
77 | public bounds: go.Rect;
|
78 | public cost: number;
|
79 | public s1: ListNode<Segment>;
|
80 | public s2: ListNode<Segment> | undefined;
|
81 |
|
82 | |
83 |
|
84 |
|
85 |
|
86 |
|
87 |
|
88 |
|
89 |
|
90 | constructor(bounds: go.Rect, cost: number, s1: ListNode<Segment>, s2?: ListNode<Segment>) {
|
91 | this.bounds = bounds;
|
92 | this.cost = cost;
|
93 | this.s1 = s1;
|
94 | this.s2 = s2;
|
95 | }
|
96 | }
|
97 |
|
98 |
|
99 |
|
100 |
|
101 |
|
102 |
|
103 |
|
104 |
|
105 |
|
106 |
|
107 |
|
108 |
|
109 |
|
110 |
|
111 |
|
112 | export class PackedLayout extends go.Layout {
|
113 | |
114 |
|
115 |
|
116 |
|
117 |
|
118 |
|
119 |
|
120 |
|
121 |
|
122 |
|
123 |
|
124 |
|
125 |
|
126 |
|
127 |
|
128 |
|
129 |
|
130 |
|
131 |
|
132 |
|
133 |
|
134 |
|
135 |
|
136 |
|
137 |
|
138 | get packShape(): number { return this._packShape; }
|
139 | set packShape(value: number) {
|
140 | if (this._packShape !== value && (value === PackedLayout.Elliptical || value === PackedLayout.Rectangular || value === PackedLayout.Spiral)) {
|
141 | this._packShape = value;
|
142 | this.invalidateLayout();
|
143 | }
|
144 | }
|
145 |
|
146 | |
147 |
|
148 |
|
149 |
|
150 |
|
151 |
|
152 |
|
153 | get packMode(): number { return this._packMode; }
|
154 | set packMode(value: number) {
|
155 | if (value === PackedLayout.AspectOnly || value === PackedLayout.Fit || value === PackedLayout.ExpandToFit) {
|
156 | this._packMode = value;
|
157 | this.invalidateLayout();
|
158 | }
|
159 | }
|
160 |
|
161 | |
162 |
|
163 |
|
164 |
|
165 |
|
166 |
|
167 | get sortMode(): number { return this._sortMode; }
|
168 | set sortMode(value: number) {
|
169 | if (value === PackedLayout.None || value === PackedLayout.MaxSide || value === PackedLayout.Area) {
|
170 | this._sortMode = value;
|
171 | this.invalidateLayout();
|
172 | }
|
173 | }
|
174 |
|
175 | |
176 |
|
177 |
|
178 |
|
179 |
|
180 |
|
181 | get sortOrder(): number { return this._sortOrder; }
|
182 | set sortOrder(value: number) {
|
183 | if (value === PackedLayout.Descending || value === PackedLayout.Ascending) {
|
184 | this._sortOrder = value;
|
185 | this.invalidateLayout();
|
186 | }
|
187 | }
|
188 |
|
189 | |
190 |
|
191 |
|
192 |
|
193 |
|
194 |
|
195 |
|
196 |
|
197 |
|
198 |
|
199 |
|
200 |
|
201 |
|
202 |
|
203 |
|
204 |
|
205 |
|
206 |
|
207 |
|
208 |
|
209 |
|
210 |
|
211 |
|
212 | get comparer(): ((a: go.Node, b: go.Node) => number) | undefined { return this._comparer; }
|
213 | set comparer(value: ((a: go.Node, b: go.Node) => number) | undefined) {
|
214 | if (typeof value === 'function') {
|
215 | this._comparer = value;
|
216 | }
|
217 | }
|
218 |
|
219 | /**
|
220 | * Gets or sets the aspect ratio for the shape that nodes will be packed into.
|
221 | * The provided aspect ratio should be a nonzero postive number.
|
222 | *
|
223 | * Note that this only applies if the {@link #packMode} is
|
224 | * {@link PackedLayout.AspectOnly}. Otherwise, the {@link #size}
|
225 | * will determine the aspect ratio of the packed shape.
|
226 | *
|
227 | * The default value is 1.
|
228 | */
|
229 | get aspectRatio(): number { return this._aspectRatio; }
|
230 | set aspectRatio(value: number) {
|
231 | if (this.isNumeric(value) && isFinite(value) && value > 0) {
|
232 | this._aspectRatio = value;
|
233 | this.invalidateLayout();
|
234 | }
|
235 | }
|
236 |
|
237 | /**
|
238 | * Gets or sets the size for the shape that nodes will be packed into.
|
239 | * To fill the viewport, set a size with a width and height of NaN. Size
|
240 | * values of 0 are considered for layout purposes to instead be 1.
|
241 | *
|
242 | * If the width and height are set to NaN (to fill the viewport), but this
|
243 | * layout has no diagram associated with it, the default value of size will
|
244 | * be used instead.
|
245 | *
|
246 | * Note that this only applies if the {@link #packMode} is
|
247 | * {@link PackedLayout.Fit} or {@link PackedLayout.ExpandToFit}.
|
248 | *
|
249 | * The default value is 500x500.
|
250 | */
|
251 | get size(): go.Size { return this._size; }
|
252 | set size(value: go.Size) {
|
253 | // check if both width and height are NaN, as per https://stackoverflow.com/a/16988441
|
254 | if (value.width !== value.width && value.height !== value.height) {
|
255 | this._size = value;
|
256 | this._fillViewport = true;
|
257 | this.invalidateLayout();
|
258 | } else if (this.isNumeric(value.width) && isFinite(value.width) && value.width >= 0
|
259 | && this.isNumeric(value.height) && isFinite(value.height) && value.height >= 0) {
|
260 | this._size = value;
|
261 | this.invalidateLayout();
|
262 | }
|
263 | }
|
264 |
|
265 | /**
|
266 | * Gets or sets the spacing between nodes. This value can be set to any
|
267 | * real number (a negative spacing will compress nodes together, and a
|
268 | * positive spacing will leave space between them).
|
269 | *
|
270 | * Note that the spacing value is only respected in the {@link PackedLayout.Fit}
|
271 | * {@link #packMode} if it does not cause the layout to grow outside
|
272 | * of the specified bounds. In the {@link PackedLayout.ExpandToFit}
|
273 | * {@link #packMode}, this property does not do anything.
|
274 | *
|
275 | * The default value is 0.
|
276 | */
|
277 | get spacing(): number { return this._spacing; }
|
278 | set spacing(value: number) {
|
279 | if (this.isNumeric(value) && isFinite(value)) {
|
280 | this._spacing = value;
|
281 | this.invalidateLayout();
|
282 | }
|
283 | }
|
284 |
|
285 | /**
|
286 | * Gets or sets whether or not to assume that nodes are circular. This changes
|
287 | * the packing algorithm to one that is much more efficient for circular nodes.
|
288 | *
|
289 | * As this algorithm expects circles, it is assumed that if this property is set
|
290 | * to true that the given nodes will all have the same height and width. All
|
291 | * calculations are done using the width of the given nodes, so unexpected results
|
292 | * may occur if the height differs from the width.
|
293 | *
|
294 | * The default value is false.
|
295 | */
|
296 | get hasCircularNodes(): boolean { return this._hasCircularNodes; }
|
297 | set hasCircularNodes(value: boolean) {
|
298 | if (typeof(value) === typeof(true) && value !== this._hasCircularNodes) {
|
299 | this._hasCircularNodes = value;
|
300 | this.invalidateLayout();
|
301 | }
|
302 | }
|
303 |
|
304 | /**
|
305 | * This read-only property is the effective spacing calculated after {@link PackedLayout#doLayout}.
|
306 | *
|
307 | * If the {@link #packMode} is {@link PackedLayout.AspectOnly}, this will simply be the
|
308 | * {@link #spacing} property. However, in the {@link PackedLayout.Fit} and
|
309 | * {@link PackedLayout.ExpandToFit} modes, this property will include the forced spacing added by
|
310 | * the modes themselves.
|
311 | *
|
312 | * Note that this property will only return a valid value after a layout has been performed. Before
|
313 | * then, its behavior is undefined.
|
314 | */
|
315 | get actualSpacing(): number { return this.spacing + this._fixedSizeModeSpacing; }
|
316 |
|
317 | /**
|
318 | * This read-only property returns the actual rectangular bounds occupied by the packed nodes.
|
319 | * This property does not take into account any kind of spacing around the packed nodes.
|
320 | *
|
321 | * Note that this property will only return a valid value after a layout has been performed. Before
|
322 | * then, its behavior is undefined.
|
323 | */
|
324 | get actualBounds(): go.Rect { return this._actualBounds; }
|
325 |
|
326 | /**
|
327 | * This read-only property returns the smallest enclosing circle around the packed nodes. It makes
|
328 | * use of the {@link #hasCircularNodes} property to determine whether or not to make
|
329 | * enclosing circle calculations for rectangles or for circles. This property does not take into
|
330 | * account any kind of spacing around the packed nodes. The enclosing circle calculation is
|
331 | * performed the first time this property is retrieved, and then cached to prevent slow accesses
|
332 | * in the future.
|
333 | *
|
334 | * Note that this property will only return a valid value after a layout has been performed. Before
|
335 | * then, its behavior is undefined.
|
336 | *
|
337 | * This property is included as it may be useful for some data visualizations.
|
338 | */
|
339 | get enclosingCircle(): go.Rect {
|
340 | if (this._enclosingCircle === null) {
|
341 | if (this.hasCircularNodes || this.packShape === PackedLayout.Spiral) { // remember, spiral mode assumes hasCircularNodes
|
342 | const circles = new Array<Circle>(this._nodeBounds.length);
|
343 | for (let i = 0; i < circles.length; i++) {
|
344 | const bounds = this._nodeBounds[i];
|
345 | const r = bounds.width / 2;
|
346 | circles[i] = new Circle(bounds.x + r, bounds.y + r, r);
|
347 | }
|
348 | this._enclosingCircle = enclose(circles);
|
349 | } else {
|
350 | const points = new Array<go.Point>(); // TODO: make this work with segments, not the whole nodeboudns list
|
351 | let segment = this._segments.start;
|
352 | if (segment !== null) {
|
353 | do {
|
354 | points.push(new go.Point(segment.data.x1, segment.data.y1));
|
355 | segment = segment.next;
|
356 | } while (segment !== this._segments.start);
|
357 | }
|
358 | this._enclosingCircle = enclose(points);
|
359 | }
|
360 | }
|
361 |
|
362 | return this._enclosingCircle;
|
363 | }
|
364 |
|
365 | /**
|
366 | * Gets or sets whether or not to use the {@link Layout#arrangementOrigin}
|
367 | * property when placing nodes.
|
368 | *
|
369 | * The default value is true.
|
370 | */
|
371 | get arrangesToOrigin(): boolean { return this._arrangesToOrigin; }
|
372 | set arrangesToOrigin(value: boolean) {
|
373 | if (typeof(value) === typeof(true) && value !== this._arrangesToOrigin) {
|
374 | this._arrangesToOrigin = value;
|
375 | this.invalidateLayout();
|
376 | }
|
377 | }
|
378 |
|
379 |
|
380 | /********************** Configuration constants **********************/
|
381 |
|
382 | // These values determine the shape of the final layout
|
383 | /**
|
384 | * This value for {@link #packShape} causes nodes to be packed
|
385 | * into an ellipse.
|
386 | *
|
387 | * The aspect ratio of this ellipse is determined by either
|
388 | * {@link #aspectRatio} or {@link #size}.
|
389 | * @constant
|
390 | */
|
391 | public static readonly Elliptical = 0;
|
392 | /**
|
393 | * Causes nodes to be packed into a rectangle; this value is used for
|
394 | * {@link #packShape}.
|
395 | *
|
396 | * The aspect ratio of this rectangle is determined by either
|
397 | * {@link #aspectRatio} or {@link #size}.
|
398 | * @constant
|
399 | */
|
400 | public static readonly Rectangular = 1;
|
401 | /**
|
402 | * Causes nodes to be packed into a spiral shape; this value is used
|
403 | * for {@link #packShape}.
|
404 | *
|
405 | * The {@link #aspectRatio} property is ignored in this mode, the
|
406 | * {@link #size} is expected to be square, and {@link #hasCircularNodes}
|
407 | * will be assumed 'true'. Please see {@link #packShape} for more details.
|
408 | */
|
409 | public static readonly Spiral = 2;
|
410 |
|
411 | // These values determine the size of the layout
|
412 | /**
|
413 | * Nodes will be packed using the {@link #aspectRatio} property, with
|
414 | * no size considerations; this value is used for {@link #packMode}.
|
415 | *
|
416 | * The {@link #spacing} property will be respected in this mode.
|
417 | * @constant
|
418 | */
|
419 | public static readonly AspectOnly = 10;
|
420 | /**
|
421 | * Nodes will be compressed if necessary (using negative spacing) to fit the given
|
422 | * {@link #size}. However, if the {@link #size} is bigger
|
423 | * than the packed shape (with 0 spacing), it will not expand to fit it. This value
|
424 | * is used for {@link #packMode}.
|
425 | *
|
426 | * The {@link #spacing} property will be respected in this mode, but only
|
427 | * if it does not cause the layout to grow larger than the {@link #size}.
|
428 | * @constant
|
429 | */
|
430 | public static readonly Fit = 11;
|
431 | /**
|
432 | * Nodes will be either compressed or spaced evenly to fit the given
|
433 | * {@link #size}; this value is used for {@link #packMode}.
|
434 | *
|
435 | * The {@link #spacing} property will not be respected in this mode, and
|
436 | * will not do anything if set.
|
437 | * @constant
|
438 | */
|
439 | public static readonly ExpandToFit = 12;
|
440 |
|
441 | // These values specify an optional method by which to sort nodes before packing
|
442 | /**
|
443 | * Nodes will not be sorted before packing; this value is used for {@link #sortMode}.
|
444 | * @constant
|
445 | */
|
446 | public static readonly None = 20;
|
447 | /**
|
448 | * Nodes will be sorted by their maximum side length before packing; this value is
|
449 | * used for {@link #sortMode}.
|
450 | * @constant
|
451 | */
|
452 | public static readonly MaxSide = 21;
|
453 | /**
|
454 | * Nodes will be sorted by their area; this value is used for {@link #sortMode}.
|
455 | * @constant
|
456 | */
|
457 | public static readonly Area = 22;
|
458 |
|
459 | // These values specify the order that nodes will be sorted, if applicable
|
460 | /**
|
461 | * Nodes will be sorted in descending order; this value is used for {@link #sortOrder}.
|
462 | *
|
463 | * Does nothing if {@link #sortMode} is set to {@link PackedLayout.None}.
|
464 | * @constant
|
465 | */
|
466 | public static readonly Descending = 30;
|
467 | /**
|
468 | * Nodes will be sorted in ascending order; this value is used for {@link #sortOrder}.
|
469 | *
|
470 | * Does nothing if {@link #sortMode} is set to {@link PackedLayout.None}.
|
471 | * @constant
|
472 | */
|
473 | public static readonly Ascending = 31;
|
474 |
|
475 |
|
476 | // configuration defaults
|
477 | /** @hidden @internal */ private _packShape = PackedLayout.Elliptical;
|
478 | /** @hidden @internal */ private _packMode = PackedLayout.AspectOnly;
|
479 | /** @hidden @internal */ private _sortMode = PackedLayout.None;
|
480 | /** @hidden @internal */ private _sortOrder = PackedLayout.Descending;
|
481 | /** @hidden @internal */ private _comparer: ((a: go.Node, b: go.Node) => number) | undefined = undefined;
|
482 | /** @hidden @internal */ private _aspectRatio: number = 1;
|
483 | /** @hidden @internal */ private _size: go.Size = new go.Size(500, 500);
|
484 | /** @hidden @internal */ private _defaultSize: go.Size = this._size.copy();
|
485 | /** @hidden @internal */ private _fillViewport: boolean = false; // true if size is (NaN, NaN)
|
486 | /** @hidden @internal */ private _spacing: number = 0;
|
487 | /** @hidden @internal */ private _hasCircularNodes: boolean = false;
|
488 | /** @hidden @internal */ private _arrangesToOrigin: boolean = true;
|
489 |
|
490 | /**
|
491 | * @hidden @internal
|
492 | * The forced spacing value applied in the {@link PackedLayout.Fit}
|
493 | * and {@link PackedLayout.ExpandToFit} modes.
|
494 | */
|
495 | private _fixedSizeModeSpacing: number = 0;
|
496 |
|
497 | /**
|
498 | * @hidden @internal
|
499 | * The actual target aspect ratio, set from either {@link #aspectRatio}
|
500 | * or from the {@link #size}, depending on the {@link #packMode}.
|
501 | */
|
502 | private _eAspectRatio: number = this._aspectRatio;
|
503 |
|
504 | // layout state
|
505 | /** @hidden @internal */ private _center = new go.Point();
|
506 | /** @hidden @internal */ private _bounds = new go.Rect();
|
507 | /** @hidden @internal */ private _actualBounds = new go.Rect();
|
508 | /** @hidden @internal */ private _enclosingCircle: go.Rect | null = null;
|
509 | /** @hidden @internal */ private _minXSegment: Segment | null = null;
|
510 | /** @hidden @internal */ private _minYSegment: Segment | null = null;
|
511 | /** @hidden @internal */ private _maxXSegment: Segment | null = null;
|
512 | /** @hidden @internal */ private _maxYSegment: Segment | null = null;
|
513 | /** @hidden @internal */ private _tree = new Quadtree<Segment>();
|
514 |
|
515 | // saved node bounds and segment list to use to calculate enclosing circle in the enclosingCircle getter
|
516 | /** @hidden @internal */ private _nodeBounds: Array<go.Rect> = [];
|
517 | /** @hidden @internal */ private _segments: CircularDoublyLinkedList<Segment> = new CircularDoublyLinkedList<Segment>();
|
518 |
|
519 |
|
520 | /**
|
521 | * Performs the PackedLayout.
|
522 | * @this {PackedLayout}
|
523 | * @param {Diagram|Group|Iterable.<Part>} coll A {@link Diagram} or a {@link Group} or a collection of {@link Part}s.
|
524 | */
|
525 | public doLayout(coll: go.Diagram | go.Group | go.Iterable<go.Part>) {
|
526 | const diagram = this.diagram;
|
527 | if (diagram !== null) diagram.startTransaction('Layout');
|
528 | this._bounds = new go.Rect();
|
529 | this._enclosingCircle = null;
|
530 |
|
531 | // push all nodes in parts iterator to an array for easy sorting
|
532 | const it = this.collectParts(coll).iterator;
|
533 | const nodes: Array<go.Node> = [];
|
534 | let averageSize = 0;
|
535 | let maxSize = 0;
|
536 | while (it.next()) {
|
537 | const node = it.value;
|
538 | if (node instanceof go.Node) {
|
539 | nodes.push(node);
|
540 | averageSize += node.actualBounds.width + node.actualBounds.height;
|
541 | if (node.actualBounds.width > maxSize) {
|
542 | maxSize = node.actualBounds.width;
|
543 | } else if (node.actualBounds.height > maxSize) {
|
544 | maxSize = node.actualBounds.height;
|
545 | }
|
546 | }
|
547 | }
|
548 | averageSize = averageSize / (nodes.length * 2);
|
549 | if (averageSize < 1) {
|
550 | averageSize = 1;
|
551 | }
|
552 |
|
553 | this.arrangementOrigin = this.initialOrigin(this.arrangementOrigin);
|
554 |
|
555 | if (this.sortMode !== PackedLayout.None) {
|
556 | if (!this.comparer) {
|
557 | const sortOrder = this.sortOrder;
|
558 | const sortMode = this.sortMode;
|
559 | this.comparer = (a: go.Node, b: go.Node): number => {
|
560 | const sortVal = sortOrder === PackedLayout.Ascending ? 1 : -1;
|
561 | if (sortMode === PackedLayout.MaxSide) {
|
562 | const aMax = Math.max(a.actualBounds.width, a.actualBounds.height);
|
563 | const bMax = Math.max(b.actualBounds.width, b.actualBounds.height);
|
564 | if (aMax > bMax) {
|
565 | return sortVal;
|
566 | } else if (bMax > aMax) {
|
567 | return -sortVal;
|
568 | }
|
569 | return 0;
|
570 | } else if (sortMode === PackedLayout.Area) {
|
571 | const area1 = a.actualBounds.width * a.actualBounds.height;
|
572 | const area2 = b.actualBounds.width * b.actualBounds.height;
|
573 | if (area1 > area2) {
|
574 | return sortVal;
|
575 | } else if (area2 > area1) {
|
576 | return -sortVal;
|
577 | }
|
578 | return 0;
|
579 | }
|
580 | return 0;
|
581 | };
|
582 | }
|
583 | nodes.sort(this.comparer);
|
584 | }
|
585 |
|
586 | let targetWidth = this.size.width !== 0 ? this.size.width : 1;
|
587 | let targetHeight = this.size.height !== 0 ? this.size.height : 1;
|
588 | if (this._fillViewport && this.diagram !== null) {
|
589 | targetWidth = this.diagram.viewportBounds.width !== 0 ? this.diagram.viewportBounds.width : 1;
|
590 | targetHeight = this.diagram.viewportBounds.height !== 0 ? this.diagram.viewportBounds.height : 1;
|
591 | } else if (this._fillViewport) {
|
592 | targetWidth = this._defaultSize.width !== 0 ? this._defaultSize.width : 1;
|
593 | targetHeight = this._defaultSize.height !== 0 ? this._defaultSize.height : 1;
|
594 | }
|
595 |
|
596 |
|
597 | if (this.packMode === PackedLayout.Fit || this.packMode === PackedLayout.ExpandToFit) {
|
598 | this._eAspectRatio = targetWidth / targetHeight;
|
599 | } else {
|
600 | this._eAspectRatio = this.aspectRatio;
|
601 | }
|
602 |
|
603 | let fits = this.hasCircularNodes || this.packShape === PackedLayout.Spiral ? this.fitCircles(nodes) : this.fitRects(nodes);
|
604 |
|
605 |
|
606 |
|
607 | if (this.packMode === PackedLayout.Fit || this.packMode === PackedLayout.ExpandToFit) {
|
608 | const bounds0 = this._bounds.copy();
|
609 | this._bounds = new go.Rect();
|
610 | this._fixedSizeModeSpacing = Math.floor(averageSize);
|
611 | fits = this.hasCircularNodes || this.packShape === PackedLayout.Spiral ? this.fitCircles(nodes) : this.fitRects(nodes);
|
612 |
|
613 | if ((this.hasCircularNodes || this.packShape === PackedLayout.Spiral) && this.packShape === PackedLayout.Spiral) {
|
614 | const targetDiameter = Math.max(targetWidth, targetHeight);
|
615 | const oldDiameter = targetDiameter === targetWidth ? bounds0.width : bounds0.height;
|
616 | const newDiameter = targetDiameter === targetWidth ? this._bounds.width : this._bounds.height;
|
617 |
|
618 | const diff = (newDiameter - oldDiameter) / this._fixedSizeModeSpacing;
|
619 |
|
620 | this._fixedSizeModeSpacing = (targetDiameter - oldDiameter) / diff;
|
621 | } else {
|
622 | const dx = (this._bounds.width - bounds0.width) / this._fixedSizeModeSpacing;
|
623 | const dy = (this._bounds.height - bounds0.height) / this._fixedSizeModeSpacing;
|
624 | const paddingX = (targetWidth - bounds0.width) / dx;
|
625 | const paddingY = (targetHeight - bounds0.height) / dy;
|
626 |
|
627 | this._fixedSizeModeSpacing = Math.abs(paddingX) > Math.abs(paddingY) ? paddingX : paddingY;
|
628 | }
|
629 |
|
630 |
|
631 | if (this.packMode === PackedLayout.Fit) {
|
632 |
|
633 | this._fixedSizeModeSpacing = Math.min(this._fixedSizeModeSpacing, 0);
|
634 | }
|
635 | if (this._fixedSizeModeSpacing === Infinity) {
|
636 | this._fixedSizeModeSpacing = -maxSize;
|
637 | }
|
638 |
|
639 | this._bounds = new go.Rect();
|
640 | fits = this.hasCircularNodes || this.packShape === PackedLayout.Spiral ? this.fitCircles(nodes) : this.fitRects(nodes);
|
641 | }
|
642 |
|
643 |
|
644 | if (this.arrangesToOrigin) {
|
645 | this._actualBounds = new go.Rect(this.arrangementOrigin.x, this.arrangementOrigin.y, 0, 0);
|
646 | }
|
647 | const nodeBounds = new Array<go.Rect>(nodes.length);
|
648 | for (let i = 0; i < nodes.length; i++) {
|
649 | const fit = fits[i];
|
650 | const node = nodes[i];
|
651 | if (this.arrangesToOrigin) {
|
652 |
|
653 |
|
654 | fit.x = fit.x - this._bounds.x + this.arrangementOrigin.x;
|
655 | fit.y = fit.y - this._bounds.y + this.arrangementOrigin.y;
|
656 | }
|
657 | node.moveTo(fit.x, fit.y);
|
658 | nodeBounds[i] = node.actualBounds;
|
659 | this._actualBounds.unionRect(node.actualBounds);
|
660 | }
|
661 | this._nodeBounds = nodeBounds;
|
662 |
|
663 |
|
664 | this.commitLayout();
|
665 |
|
666 | if (diagram !== null) diagram.commitTransaction('Layout');
|
667 |
|
668 | this.isValidLayout = true;
|
669 | }
|
670 |
|
671 | |
672 |
|
673 |
|
674 |
|
675 |
|
676 |
|
677 |
|
678 | public commitLayout(): void {}
|
679 |
|
680 | |
681 |
|
682 |
|
683 |
|
684 |
|
685 |
|
686 |
|
687 |
|
688 |
|
689 |
|
690 | private fitCircles(nodes: Array<go.Node>): Array<go.Rect> {
|
691 | function place(a: go.Rect, b: go.Rect, c: go.Rect): go.Rect {
|
692 | const ax = a.centerX;
|
693 | const ay = a.centerY;
|
694 | let da = (b.width + c.width) / 2;
|
695 | let db = (a.width + c.width) / 2;
|
696 | const dx = b.centerX - ax;
|
697 | const dy = b.centerY - ay;
|
698 | const dc = dx * dx + dy * dy;
|
699 | if (dc) {
|
700 | const x = 0.5 + ((db *= db) - (da *= da)) / (2 * dc);
|
701 | const y = Math.sqrt(Math.max(0, 2 * da * (db + dc) - (db -= dc) * db - da * da)) / (2 * dc);
|
702 | c.x = (ax + x * dx + y * dy) - (c.width / 2);
|
703 | c.y = (ay + x * dy - y * dx) - (c.height / 2);
|
704 | } else {
|
705 | c.x = ax + db;
|
706 | c.y = ay;
|
707 | }
|
708 | return c;
|
709 | }
|
710 |
|
711 | function intersects(a: go.Rect, b: go.Rect): boolean {
|
712 | const ar = a.height / 2;
|
713 | const br = b.height / 2;
|
714 | const dist = Math.sqrt(a.center.distanceSquaredPoint(b.center));
|
715 | const difference = dist - (ar + br);
|
716 | return difference < -0.0000001;
|
717 | }
|
718 |
|
719 | const aspect = this._eAspectRatio;
|
720 | const shape = this.packShape;
|
721 | const placementCost = this.placementCost;
|
722 | function score(n: ListNode<go.Rect>) {
|
723 | const a = n.data;
|
724 | const b = n.next.data;
|
725 | const ar = a.width / 2;
|
726 | const br = b.width / 2;
|
727 | const ab = ar + br;
|
728 | const dx = (a.centerX * br + b.centerX * ar) / ab;
|
729 | const dy = (a.centerY * br + b.centerY * ar) / ab * aspect;
|
730 | return shape === PackedLayout.Elliptical ? dx * dx + dy * dy : Math.max(dx * dx, dy * dy);
|
731 | }
|
732 |
|
733 |
|
734 | const sideSpacing = (this.spacing + this._fixedSizeModeSpacing) / 2;
|
735 | const fits: Array<go.Rect> = [];
|
736 | const frontChain = new CircularDoublyLinkedList<go.Rect>();
|
737 |
|
738 | if (!nodes.length) return fits;
|
739 |
|
740 | let r1: go.Rect = nodes[0].actualBounds.copy().inflate(sideSpacing, sideSpacing);
|
741 | r1.setTo(0, 0, r1.width === 0 ? 0.1 : r1.width, r1.height === 0 ? 0.1 : r1.height);
|
742 | fits.push(r1.setTo(0, 0, r1.width, r1.height));
|
743 | this._bounds.unionRect(r1);
|
744 | if (nodes.length < 2) return fits;
|
745 |
|
746 | let r2: go.Rect = nodes[1].actualBounds.copy().inflate(sideSpacing, sideSpacing);
|
747 | r2.setTo(0, 0, r2.width === 0 ? 0.1 : r2.width, r2.height === 0 ? 0.1 : r2.height);
|
748 | fits.push(r2.setTo(-r2.width, r1.centerY - r2.width / 2, r2.width, r2.height));
|
749 | this._bounds.unionRect(r2);
|
750 | if (nodes.length < 3) return fits;
|
751 |
|
752 | let r3: go.Rect = nodes[2].actualBounds.copy().inflate(sideSpacing, sideSpacing);
|
753 | r3.setTo(0, 0, r3.width === 0 ? 0.1 : r3.width, r3.height === 0 ? 0.1 : r3.height);
|
754 | fits.push(place(r2, r1, r3));
|
755 | this._bounds.unionRect(r3);
|
756 |
|
757 |
|
758 | let n2: ListNode<go.Rect> = frontChain.push(r2);
|
759 | let n3: ListNode<go.Rect> = frontChain.push(r3);
|
760 | let n1: ListNode<go.Rect> = frontChain.push(r1);
|
761 |
|
762 | pack: for (let i = 3; i < nodes.length; i++) {
|
763 | r3 = nodes[i].actualBounds.copy().inflate(sideSpacing, sideSpacing);
|
764 | r3.setTo(0, 0, r3.width === 0 ? 0.1 : r3.width, r3.height === 0 ? 0.1 : r3.height);
|
765 | place(n1.data, n2.data, r3);
|
766 |
|
767 | let j = n2.next;
|
768 | let k = n1.prev;
|
769 | let sj = n2.data.width / 2;
|
770 | let sk = n1.data.width / 2;
|
771 | do {
|
772 | if (sj <= sk) {
|
773 | if (intersects(j.data, r3)) {
|
774 | n2 = frontChain.removeBetween(n1, j), i--;
|
775 | continue pack;
|
776 | }
|
777 | sj += j.data.width / 2, j = j.next;
|
778 | } else {
|
779 | if (intersects(k.data, r3)) {
|
780 | frontChain.removeBetween(k, n2);
|
781 | n1 = k, i--;
|
782 | continue pack;
|
783 | }
|
784 | sk += k.data.width / 2, k = k.prev;
|
785 | }
|
786 | } while (j !== k.next);
|
787 |
|
788 | fits.push(r3);
|
789 | this._bounds.unionRect(r3);
|
790 |
|
791 | n2 = n3 = frontChain.insertAfter(r3, n1);
|
792 |
|
793 | if (this.packShape !== PackedLayout.Spiral) {
|
794 | let aa = score(n1);
|
795 | while ((n3 = n3.next) !== n2) {
|
796 | const ca = score(n3);
|
797 | if (ca < aa) {
|
798 | n1 = n3, aa = ca;
|
799 | }
|
800 | }
|
801 | n2 = n1.next;
|
802 | }
|
803 |
|
804 | }
|
805 |
|
806 | return fits;
|
807 | }
|
808 |
|
809 | |
810 |
|
811 |
|
812 |
|
813 |
|
814 |
|
815 |
|
816 |
|
817 |
|
818 |
|
819 |
|
820 |
|
821 |
|
822 |
|
823 |
|
824 |
|
825 |
|
826 |
|
827 |
|
828 |
|
829 |
|
830 |
|
831 |
|
832 |
|
833 |
|
834 |
|
835 |
|
836 |
|
837 |
|
838 |
|
839 |
|
840 |
|
841 |
|
842 |
|
843 |
|
844 |
|
845 |
|
846 | private fitRects(nodes: Array<go.Node>): Array<go.Rect> {
|
847 | const sideSpacing = (this.spacing + this._fixedSizeModeSpacing) / 2;
|
848 | const fits: Array<go.Rect> = [];
|
849 | const segments = new CircularDoublyLinkedList<Segment>();
|
850 |
|
851 |
|
852 | this._tree.clear();
|
853 | this._minXSegment = null;
|
854 | this._maxXSegment = null;
|
855 | this._minYSegment = null;
|
856 | this._maxYSegment = null;
|
857 |
|
858 | if (nodes.length < 1) {
|
859 | return fits;
|
860 | }
|
861 |
|
862 |
|
863 | const bounds0 = nodes[0].actualBounds;
|
864 | fits.push(new go.Rect(sideSpacing, sideSpacing, bounds0.width, bounds0.height));
|
865 | fits[0].inflate(sideSpacing, sideSpacing);
|
866 | fits[0].setTo(0, 0, fits[0].width === 0 ? 0.1 : fits[0].width, fits[0].height === 0 ? 0.1 : fits[0].height);
|
867 | this._bounds.unionRect(fits[0]);
|
868 | this._center = fits[0].center;
|
869 |
|
870 | const s1 = new Segment(0, 0, fits[0].width, 0, false);
|
871 | const s2 = new Segment(fits[0].width, 0, fits[0].width, fits[0].height, false);
|
872 | const s3 = new Segment(fits[0].width, fits[0].height, 0, fits[0].height, false);
|
873 | const s4 = new Segment(0, fits[0].height, 0, 0, false);
|
874 | this._tree.add(s1, this.rectFromSegment(s1));
|
875 | this._tree.add(s2, this.rectFromSegment(s2));
|
876 | this._tree.add(s3, this.rectFromSegment(s3));
|
877 | this._tree.add(s4, this.rectFromSegment(s4));
|
878 | segments.push(s1, s2, s3, s4);
|
879 | this.fixMissingMinMaxSegments(true);
|
880 |
|
881 | for (let i = 1; i < nodes.length; i++) {
|
882 | const node = nodes[i];
|
883 | const bounds = node.actualBounds.copy().inflate(sideSpacing, sideSpacing);
|
884 | bounds.setTo(0, 0, bounds.width === 0 ? 0.1 : bounds.width, bounds.height === 0 ? 0.1 : bounds.height);
|
885 | const possibleFits = new Array<Fit>(segments.length);
|
886 | let j = 0;
|
887 | let s = segments.start as ListNode<Segment>;
|
888 | do {
|
889 |
|
890 |
|
891 | const sdata = s.data;
|
892 | sdata.x1 = s.prev.data.x2;
|
893 | sdata.y1 = s.prev.data.y2;
|
894 | if (sdata.isHorizontal) {
|
895 | sdata.y2 = sdata.y1;
|
896 | } else {
|
897 | sdata.x2 = sdata.x1;
|
898 | }
|
899 |
|
900 | const fitBounds = this.getBestFitRect(s, bounds.width, bounds.height);
|
901 | const cost = this.placementCost(fitBounds);
|
902 | possibleFits[j] = new Fit(fitBounds, cost, s);
|
903 |
|
904 | s = s.next;
|
905 | j++;
|
906 | } while (s !== segments.start);
|
907 |
|
908 | possibleFits.sort((a, b) => {
|
909 | return a.cost - b.cost;
|
910 | });
|
911 |
|
912 | |
913 |
|
914 |
|
915 |
|
916 |
|
917 |
|
918 | const skipFitScaleFactor = 0.98;
|
919 |
|
920 | let bestFit: Fit | null = null;
|
921 | let onlyCheckSkipFits = false;
|
922 | for (const fit of possibleFits) {
|
923 | if (bestFit && bestFit.cost <= fit.cost) {
|
924 | onlyCheckSkipFits = true;
|
925 | }
|
926 |
|
927 | let hasIntersections = true;
|
928 | if (!onlyCheckSkipFits) {
|
929 | hasIntersections = this.fastFitHasIntersections(fit) || this.fitHasIntersections(fit);
|
930 | if (!hasIntersections) {
|
931 | bestFit = fit;
|
932 | continue;
|
933 | }
|
934 | }
|
935 |
|
936 |
|
937 | if (hasIntersections && !fit.s1.data.p1Concave && (fit.s1.next.data.p1Concave || fit.s1.next.next.data.p1Concave)) {
|
938 | let [nextSegment, usePreviousSegment] = this.findNextOrientedSegment(fit, fit.s1.next);
|
939 | let nextSegmentTouchesFit = false;
|
940 | while (hasIntersections && nextSegment !== null) {
|
941 | fit.bounds = this.rectAgainstMultiSegment(fit.s1, nextSegment, bounds.width, bounds.height);
|
942 | hasIntersections = this.fastFitHasIntersections(fit) || this.fitHasIntersections(fit);
|
943 | nextSegmentTouchesFit = this.segmentIsOnFitPerimeter(nextSegment.data, fit.bounds);
|
944 |
|
945 | if (hasIntersections || !nextSegmentTouchesFit) {
|
946 | [nextSegment, usePreviousSegment] = this.findNextOrientedSegment(fit, nextSegment);
|
947 | }
|
948 | }
|
949 |
|
950 | if (!hasIntersections && nextSegment !== null && nextSegmentTouchesFit) {
|
951 | fit.cost = this.placementCost(fit.bounds) * skipFitScaleFactor;
|
952 | if (bestFit === null || fit.cost <= bestFit.cost) {
|
953 | bestFit = fit;
|
954 | bestFit.s2 = nextSegment;
|
955 | if (usePreviousSegment) {
|
956 | bestFit.s1 = bestFit.s1.prev;
|
957 | }
|
958 | }
|
959 | }
|
960 | }
|
961 | }
|
962 |
|
963 | if (bestFit !== null) {
|
964 | this.updateSegments(bestFit, segments);
|
965 |
|
966 | fits.push(bestFit.bounds);
|
967 | this._bounds.unionRect(bestFit.bounds);
|
968 | }
|
969 |
|
970 | }
|
971 |
|
972 |
|
973 | this._segments = segments;
|
974 |
|
975 | return fits;
|
976 | }
|
977 |
|
978 | |
979 |
|
980 |
|
981 |
|
982 |
|
983 |
|
984 |
|
985 |
|
986 |
|
987 |
|
988 |
|
989 |
|
990 |
|
991 |
|
992 |
|
993 |
|
994 |
|
995 | private findNextOrientedSegment(fit: Fit, lastSegment: ListNode<Segment>): [ListNode<Segment> | null, boolean] {
|
996 | lastSegment = lastSegment.next;
|
997 | const orientation = this.segmentOrientation(fit.s1.prev.data, fit.s1.data);
|
998 | const targetOrientation = (orientation + 1) % 4;
|
999 |
|
1000 | while (!this.segmentIsMinOrMax(lastSegment.data)) {
|
1001 | const usePreviousSegment = lastSegment.data.isHorizontal === fit.s1.data.isHorizontal;
|
1002 |
|
1003 | let lastOrientation: Orientation;
|
1004 | if (usePreviousSegment) {
|
1005 | lastOrientation = this.segmentOrientation(lastSegment.data, lastSegment.next.data);
|
1006 | if (lastSegment.next.data.p1Concave) {
|
1007 | lastOrientation = (lastOrientation + 1) % 4;
|
1008 | }
|
1009 | } else {
|
1010 | lastOrientation = this.segmentOrientation(lastSegment.prev.data, lastSegment.data);
|
1011 | if (lastSegment.data.p1Concave) {
|
1012 | lastOrientation = (lastOrientation + 1) % 4;
|
1013 | }
|
1014 | }
|
1015 | const validLastOrientation = lastOrientation === targetOrientation;
|
1016 |
|
1017 | const exceededPrimaryDimension = fit.s1.data.isHorizontal ?
|
1018 | Math.abs(lastSegment.data.y1 - fit.s1.data.y1) + 1e-7 > fit.bounds.height :
|
1019 | Math.abs(lastSegment.data.x1 - fit.s1.data.x1) + 1e-7 > fit.bounds.width;
|
1020 |
|
1021 | let validCornerPlacement: boolean;
|
1022 | let exceededSecondaryDimension: boolean;
|
1023 | switch (orientation) {
|
1024 | case Orientation.NE:
|
1025 | validCornerPlacement = fit.s1.data.x1 < lastSegment.data.x1;
|
1026 | exceededSecondaryDimension = usePreviousSegment ? fit.s1.data.y1 - fit.bounds.height >= lastSegment.data.y1 : fit.s1.data.y2 + fit.bounds.height <= lastSegment.data.y1;
|
1027 | break;
|
1028 | case Orientation.NW:
|
1029 | validCornerPlacement = fit.s1.data.y1 > lastSegment.data.y1;
|
1030 | exceededSecondaryDimension = usePreviousSegment ? fit.s1.data.x1 - fit.bounds.width >= lastSegment.data.x1 : fit.s1.data.x2 + fit.bounds.width <= lastSegment.data.x1;
|
1031 | break;
|
1032 | case Orientation.SW:
|
1033 | validCornerPlacement = fit.s1.data.x1 > lastSegment.data.x1;
|
1034 | exceededSecondaryDimension = usePreviousSegment ? fit.s1.data.y1 + fit.bounds.height <= lastSegment.data.y1 : fit.s1.data.y2 - fit.bounds.height >= lastSegment.data.y1;
|
1035 | break;
|
1036 | case Orientation.SE:
|
1037 | validCornerPlacement = fit.s1.data.y1 < lastSegment.data.y1;
|
1038 | exceededSecondaryDimension = usePreviousSegment ? fit.s1.data.x1 + fit.bounds.width <= lastSegment.data.x1 : fit.s1.data.x2 - fit.bounds.width >= lastSegment.data.x1;
|
1039 | break;
|
1040 | default:
|
1041 | throw new Error('Unknown orientation ' + orientation);
|
1042 | }
|
1043 |
|
1044 | if (!exceededPrimaryDimension && !exceededSecondaryDimension && validCornerPlacement && validLastOrientation) {
|
1045 | return [lastSegment, usePreviousSegment];
|
1046 | }
|
1047 |
|
1048 | lastSegment = lastSegment.next;
|
1049 | }
|
1050 |
|
1051 | return [null, false];
|
1052 | }
|
1053 |
|
1054 | |
1055 |
|
1056 |
|
1057 |
|
1058 |
|
1059 |
|
1060 |
|
1061 |
|
1062 | private segmentOrientation(s1: Segment, s2: Segment): Orientation {
|
1063 | if (s1.isHorizontal) {
|
1064 | if (s1.x1 < s2.x1) {
|
1065 | return s2.p1Concave ? Orientation.SE : Orientation.NE;
|
1066 | } else {
|
1067 | return s2.p1Concave ? Orientation.NW : Orientation.SW;
|
1068 | }
|
1069 | } else {
|
1070 | if (s1.y1 < s2.y1) {
|
1071 | return s2.p1Concave ? Orientation.SW : Orientation.SE;
|
1072 | } else {
|
1073 | return s2.p1Concave ? Orientation.NE : Orientation.NW;
|
1074 | }
|
1075 | }
|
1076 | }
|
1077 |
|
1078 | |
1079 |
|
1080 |
|
1081 |
|
1082 |
|
1083 |
|
1084 |
|
1085 |
|
1086 |
|
1087 |
|
1088 |
|
1089 |
|
1090 |
|
1091 | private rectAgainstMultiSegment(a: ListNode<Segment>, b: ListNode<Segment>, width: number, height: number): go.Rect {
|
1092 | switch (this.segmentOrientation(a.prev.data, a.data)) {
|
1093 | case Orientation.NE:
|
1094 | if (a.data.y1 > b.data.y2) {
|
1095 | return new go.Rect(b.data.x1 - width, a.data.y1 - height, width, height);
|
1096 | } else {
|
1097 | return new go.Rect(a.data.x1, b.data.y1 - height, width, height);
|
1098 | }
|
1099 | case Orientation.NW:
|
1100 | if (a.data.x1 > b.data.x2) {
|
1101 | return new go.Rect(a.data.x1 - width, b.data.y1, width, height);
|
1102 | } else {
|
1103 | return new go.Rect(b.data.x1 - width, a.data.y1 - height, width, height);
|
1104 | }
|
1105 | case Orientation.SW:
|
1106 | if (a.data.y1 < b.data.y2) {
|
1107 | return new go.Rect(b.data.x1, a.data.y1, width, height);
|
1108 | } else {
|
1109 | return new go.Rect(a.data.x1 - width, b.data.y1, width, height);
|
1110 | }
|
1111 | case Orientation.SE:
|
1112 | if (a.data.x1 < b.data.x2) {
|
1113 | return new go.Rect(a.data.x1, b.data.y1 - height, width, height);
|
1114 | } else {
|
1115 | return new go.Rect(b.data.x1, a.data.y1, width, height);
|
1116 | }
|
1117 | }
|
1118 |
|
1119 | }
|
1120 |
|
1121 | |
1122 |
|
1123 |
|
1124 |
|
1125 |
|
1126 |
|
1127 |
|
1128 |
|
1129 |
|
1130 |
|
1131 |
|
1132 |
|
1133 | private getBestFitRect(s: ListNode<Segment>, width: number, height: number): go.Rect {
|
1134 | let x1 = s.data.x1;
|
1135 | let y1 = s.data.y1;
|
1136 | let x2 = s.data.x2;
|
1137 | let y2 = s.data.y2;
|
1138 | let dir = this.segmentOrientation(s.prev.data, s.data);
|
1139 | if (s.data.p1Concave) {
|
1140 | dir = (dir + 3) % 4;
|
1141 | }
|
1142 |
|
1143 | const coordIsX = dir === Orientation.NW || dir === Orientation.SE;
|
1144 | if (dir === Orientation.NE) {
|
1145 | y2 -= height;
|
1146 | } else if (dir === Orientation.SE) {
|
1147 | x1 -= width;
|
1148 | } else if (dir === Orientation.SW) {
|
1149 | x1 -= width;
|
1150 | y1 -= height;
|
1151 | x2 -= width;
|
1152 | } else if (dir === Orientation.NW) {
|
1153 | y1 -= height;
|
1154 | x2 -= width;
|
1155 | y2 -= height;
|
1156 | }
|
1157 |
|
1158 | const r = new go.Rect(x1, y1, width, height);
|
1159 | const cost1 = this.placementCost(r);
|
1160 | const cost2 = this.placementCost(r.setTo(x2, y2, width, height));
|
1161 | let cost3 = Infinity;
|
1162 | if (coordIsX && (this._center.x - (x1 + width / 2)) * (this._center.x - (x2 + width / 2 )) < 0) {
|
1163 | cost3 = this.placementCost(r.setTo(this._center.x - width / 2, y1, width, height));
|
1164 | } else if (!coordIsX && (this._center.y - (y1 + height / 2)) * (this._center.y - (y2 + height / 2)) < 0) {
|
1165 | cost3 = this.placementCost(r.setTo(x1, this._center.y - height / 2, width, height));
|
1166 | }
|
1167 |
|
1168 | return cost3 < cost2 && cost3 < cost1 ? r
|
1169 | : (cost2 < cost1 ? r.setTo(x2, y2, width, height)
|
1170 | : r.setTo(x1, y1, width, height));
|
1171 |
|
1172 | }
|
1173 |
|
1174 | |
1175 |
|
1176 |
|
1177 |
|
1178 |
|
1179 |
|
1180 |
|
1181 |
|
1182 |
|
1183 | private segmentIsOnFitPerimeter(s: Segment, bounds: go.Rect) {
|
1184 | const xCoordinatesTogether = this.numberIsBetween(s.x1, bounds.left, bounds.right)
|
1185 | || this.numberIsBetween(s.x2, bounds.left, bounds.right)
|
1186 | || this.numberIsBetween(bounds.left, s.x1, s.x2)
|
1187 | || this.numberIsBetween(bounds.right, s.x1, s.x2);
|
1188 | const yCoordinatesTogether = this.numberIsBetween(s.y1, bounds.top, bounds.bottom)
|
1189 | || this.numberIsBetween(s.y2, bounds.top, bounds.bottom)
|
1190 | || this.numberIsBetween(bounds.top, s.y1, s.y2)
|
1191 | || this.numberIsBetween(bounds.bottom, s.y1, s.y2);
|
1192 | return (s.isHorizontal && (this.approxEqual(s.y1, bounds.top) || this.approxEqual(s.y1, bounds.bottom)) && xCoordinatesTogether)
|
1193 | || (!s.isHorizontal && (this.approxEqual(s.x1, bounds.left) || this.approxEqual(s.x1, bounds.right)) && yCoordinatesTogether);
|
1194 | }
|
1195 |
|
1196 | |
1197 |
|
1198 |
|
1199 |
|
1200 |
|
1201 |
|
1202 |
|
1203 |
|
1204 |
|
1205 |
|
1206 | private pointIsOnFitPerimeter(x: number, y: number, bounds: go.Rect): boolean {
|
1207 | return (x >= bounds.left - 1e-7 && x <= bounds.right + 1e-7 && y >= bounds.top - 1e-7 && y <= bounds.bottom + 1e-7);
|
1208 | }
|
1209 |
|
1210 | |
1211 |
|
1212 |
|
1213 |
|
1214 |
|
1215 |
|
1216 |
|
1217 |
|
1218 | private pointIsFitCorner(x: number, y: number, bounds: go.Rect) {
|
1219 | return (this.approxEqual(x, bounds.left) && this.approxEqual(y, bounds.top)) ||
|
1220 | (this.approxEqual(x, bounds.right) && this.approxEqual(y, bounds.top)) ||
|
1221 | (this.approxEqual(x, bounds.left) && this.approxEqual(y, bounds.bottom)) ||
|
1222 | (this.approxEqual(x, bounds.right) && this.approxEqual(y, bounds.bottom));
|
1223 | }
|
1224 |
|
1225 | |
1226 |
|
1227 |
|
1228 |
|
1229 |
|
1230 |
|
1231 |
|
1232 |
|
1233 |
|
1234 |
|
1235 |
|
1236 | private updateSegments(fit: Fit, segments: CircularDoublyLinkedList<Segment>): void {
|
1237 | let s0 = fit.s1;
|
1238 | while (this.pointIsOnFitPerimeter(s0.data.x1, s0.data.y1, fit.bounds)) {
|
1239 | s0 = s0.prev;
|
1240 | }
|
1241 | if (!this.segmentIsMinOrMax(s0.data) || !this.segmentIsMinOrMax(s0.prev.data)) {
|
1242 | let sTest = s0.prev.prev;
|
1243 | let sFound: ListNode<Segment> | null = null;
|
1244 | let minMaxCount = 0;
|
1245 | while (minMaxCount < 2) {
|
1246 | if (this.segmentIsOnFitPerimeter(sTest.data, fit.bounds)) {
|
1247 | sFound = sTest;
|
1248 | }
|
1249 | sTest = sTest.prev;
|
1250 | if (this.segmentIsMinOrMax(sTest.next.data)) {
|
1251 | minMaxCount++;
|
1252 | }
|
1253 | }
|
1254 | if (sFound !== null) {
|
1255 | while (this.pointIsOnFitPerimeter(sFound.data.x1, sFound.data.y1, fit.bounds)) {
|
1256 | sFound = sFound.prev;
|
1257 | }
|
1258 | this.removeBetween(segments, sFound, s0);
|
1259 | s0 = sFound;
|
1260 | }
|
1261 | }
|
1262 |
|
1263 | let nextConvexCornerOrientation: Orientation;
|
1264 | let lastConvexCornerOrientation: Orientation;
|
1265 |
|
1266 | let testOrientation = this.segmentOrientation(s0.prev.data, s0.data);
|
1267 | if (s0.data.p1Concave) {
|
1268 | testOrientation = (testOrientation + 3) % 4;
|
1269 | }
|
1270 | let [cornerX, cornerY] = this.cornerFromRect(testOrientation, fit.bounds);
|
1271 | const extended0 = this.approxEqual(cornerX, s0.data.x2) && this.approxEqual(cornerY, s0.data.y2);
|
1272 | let shortened0Precond: boolean;
|
1273 | let [cornerX2, cornerY2] = this.cornerFromRect((testOrientation + 1) % 4, fit.bounds);
|
1274 | if (s0.data.isHorizontal) {
|
1275 | shortened0Precond = this.numberIsBetween(cornerX2, s0.data.x1, s0.data.x2) && this.approxEqual(cornerY2, s0.data.y1);
|
1276 | } else {
|
1277 | shortened0Precond = this.numberIsBetween(cornerY2, s0.data.y1, s0.data.y2) && this.approxEqual(cornerX2, s0.data.x1);
|
1278 | }
|
1279 | const shortened0 = !extended0 && this.pointIsFitCorner(s0.data.x2, s0.data.y2, fit.bounds)
|
1280 | || !this.pointIsOnFitPerimeter(s0.data.x2, s0.data.y2, fit.bounds)
|
1281 | || (this.pointIsOnFitPerimeter(s0.data.x2, s0.data.y2, fit.bounds)
|
1282 | && !this.pointIsOnFitPerimeter(s0.data.x1, s0.data.y1, fit.bounds)
|
1283 | && shortened0Precond);
|
1284 | if (extended0) {
|
1285 |
|
1286 | [s0.data.x2, s0.data.y2] = this.cornerFromRect((testOrientation + 3) % 4, fit.bounds);
|
1287 | this._tree.setTo(s0.data, this.rectFromSegment(s0.data));
|
1288 | nextConvexCornerOrientation = (testOrientation + 3) % 4;
|
1289 | this.updateMinMaxSegments(s0.data);
|
1290 | } else {
|
1291 | if (shortened0) {
|
1292 | [s0.data.x2, s0.data.y2] = this.cornerFromRect((testOrientation + 1) % 4, fit.bounds);
|
1293 | this._tree.setTo(s0.data, this.rectFromSegment(s0.data));
|
1294 | }
|
1295 | const newSegment = new Segment(s0.data.x2, s0.data.y2, cornerX, cornerY, true);
|
1296 | s0 = segments.insertAfter(newSegment, s0);
|
1297 | this._tree.add(newSegment, this.rectFromSegment(newSegment));
|
1298 | nextConvexCornerOrientation = testOrientation;
|
1299 | this.updateMinMaxSegments(newSegment);
|
1300 | }
|
1301 |
|
1302 | let sNext = fit.s2 ? fit.s2 : s0;
|
1303 | while (this.pointIsOnFitPerimeter(sNext.data.x2, sNext.data.y2, fit.bounds)) {
|
1304 | sNext = sNext.next;
|
1305 | }
|
1306 | if (!this.segmentIsMinOrMax(sNext.data) || !this.segmentIsMinOrMax(sNext.next.data)) {
|
1307 | let sTest = sNext.next.next;
|
1308 | let sFound: ListNode<Segment> | null = null;
|
1309 | let minMaxCount = 0;
|
1310 | while (minMaxCount < 2) {
|
1311 | if (this.segmentIsOnFitPerimeter(sTest.data, fit.bounds)) {
|
1312 | sFound = sTest;
|
1313 | }
|
1314 | sTest = sTest.next;
|
1315 | if (this.segmentIsMinOrMax(sTest.prev.data)) {
|
1316 | minMaxCount++;
|
1317 | }
|
1318 | }
|
1319 | if (sFound !== null) {
|
1320 | sNext = sFound;
|
1321 | while (this.pointIsOnFitPerimeter(sNext.data.x2, sNext.data.y2, fit.bounds)) {
|
1322 | sNext = sNext.next;
|
1323 | }
|
1324 | }
|
1325 | }
|
1326 |
|
1327 | testOrientation = this.segmentOrientation(sNext.data, sNext.next.data);
|
1328 | if (sNext.data.p1Concave) {
|
1329 | testOrientation = (testOrientation + 2) % 4;
|
1330 | }
|
1331 | if (sNext.next.data.p1Concave) {
|
1332 | testOrientation = (testOrientation + 1) % 4;
|
1333 | }
|
1334 | [cornerX2, cornerY2] = this.cornerFromRect((testOrientation + 3) % 4, fit.bounds);
|
1335 | if (sNext.data.isHorizontal && this.numberIsBetween(cornerX2, sNext.data.x1, sNext.data.x2) && this.approxEqual(cornerY2, sNext.data.y1)
|
1336 | || (!sNext.data.isHorizontal && this.numberIsBetween(cornerY2, sNext.data.y1, sNext.data.y2) && this.approxEqual(cornerX2, sNext.data.x1))
|
1337 | || (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)
|
1338 | && (this.approxEqual(fit.bounds.top, sNext.data.y1) || this.approxEqual(fit.bounds.bottom, sNext.data.y1)))
|
1339 | || (!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)
|
1340 | && (this.approxEqual(fit.bounds.left, sNext.data.x1) || this.approxEqual(fit.bounds.right, sNext.data.x1)))) {
|
1341 | sNext = sNext.next;
|
1342 | testOrientation = this.segmentOrientation(sNext.data, sNext.next.data);
|
1343 | if (sNext.data.p1Concave) {
|
1344 | testOrientation = (testOrientation + 2) % 4;
|
1345 | }
|
1346 | if (sNext.next.data.p1Concave) {
|
1347 | testOrientation = (testOrientation + 1) % 4;
|
1348 | }
|
1349 | }
|
1350 |
|
1351 | this.removeBetween(segments, s0, sNext);
|
1352 |
|
1353 | [cornerX, cornerY] = this.cornerFromRect(testOrientation, fit.bounds);
|
1354 |
|
1355 | if (this.approxEqual(cornerX, sNext.data.x1) && this.approxEqual(cornerY, sNext.data.y1)) {
|
1356 |
|
1357 | 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))) {
|
1358 | s0.data.x2 = sNext.data.x2;
|
1359 | s0.data.y2 = sNext.data.y2;
|
1360 | this.removeSegmentFromLayoutState(sNext);
|
1361 | segments.remove(sNext);
|
1362 | this._tree.setTo(s0.data, this.rectFromSegment(s0.data));
|
1363 | lastConvexCornerOrientation = nextConvexCornerOrientation;
|
1364 | this.updateMinMaxSegments(s0.data);
|
1365 | } else {
|
1366 | [sNext.data.x1, sNext.data.y1] = this.cornerFromRect((testOrientation + 1) % 4, fit.bounds);
|
1367 | this._tree.setTo(sNext.data, this.rectFromSegment(sNext.data));
|
1368 | lastConvexCornerOrientation = (testOrientation + 1) % 4;
|
1369 | this.updateMinMaxSegments(sNext.data);
|
1370 | }
|
1371 | } else if (extended0 && (s0.data.isHorizontal ?
|
1372 | this.approxEqual(s0.data.y1, sNext.data.y1) && this.numberIsBetween(sNext.data.x1, s0.data.x1, s0.data.x2) :
|
1373 | this.approxEqual(s0.data.x1, sNext.data.x1) && this.numberIsBetween(sNext.data.y1, s0.data.y1, s0.data.y2))) {
|
1374 | if (s0.data.isHorizontal) {
|
1375 | s0.data.x2 = sNext.data.x1;
|
1376 | } else {
|
1377 | s0.data.y2 = sNext.data.y1;
|
1378 | }
|
1379 | this._tree.setTo(s0.data, this.rectFromSegment(s0.data));
|
1380 | lastConvexCornerOrientation = nextConvexCornerOrientation;
|
1381 | sNext.data.p1Concave = true;
|
1382 | this.updateMinMaxSegments(s0.data);
|
1383 | } else if (!this.pointIsFitCorner(sNext.data.x1, sNext.data.y1, fit.bounds)) {
|
1384 |
|
1385 | const newSegment = new Segment(cornerX, cornerY, sNext.data.x1, sNext.data.y1, false);
|
1386 | if (this.pointIsOnFitPerimeter(sNext.data.x1, sNext.data.y1, fit.bounds)) {
|
1387 | sNext.data.p1Concave = true;
|
1388 | } else {
|
1389 | newSegment.p1Concave = true;
|
1390 | }
|
1391 | if (this.approxEqual(sNext.prev.data.x1, cornerX) && this.approxEqual(sNext.prev.data.y1, cornerY) && newSegment.isHorizontal === sNext.prev.data.isHorizontal) {
|
1392 | sNext.prev.data.x2 = sNext.data.x1;
|
1393 | sNext.prev.data.y2 = sNext.data.y1;
|
1394 | this._tree.setTo(sNext.prev.data, this.rectFromSegment(sNext.prev.data));
|
1395 | lastConvexCornerOrientation = nextConvexCornerOrientation;
|
1396 | } else {
|
1397 | segments.insertAfter(newSegment, sNext.prev);
|
1398 | this._tree.add(newSegment, this.rectFromSegment(newSegment));
|
1399 | lastConvexCornerOrientation = testOrientation;
|
1400 | this.updateMinMaxSegments(newSegment);
|
1401 | }
|
1402 | } else {
|
1403 |
|
1404 | [sNext.data.x1, sNext.data.y1] = this.cornerFromRect((testOrientation + 3) % 4, fit.bounds);
|
1405 | sNext.data.p1Concave = true;
|
1406 | this._tree.setTo(sNext.data, this.rectFromSegment(sNext.data));
|
1407 | lastConvexCornerOrientation = (testOrientation + 3) % 4;
|
1408 | }
|
1409 |
|
1410 | while (nextConvexCornerOrientation !== lastConvexCornerOrientation) {
|
1411 | [cornerX, cornerY] = this.cornerFromRect((nextConvexCornerOrientation + 3) % 4, fit.bounds);
|
1412 | const newSegment = new Segment(s0.data.x2, s0.data.y2, cornerX, cornerY, false);
|
1413 | s0 = segments.insertAfter(newSegment, s0);
|
1414 | this._tree.add(newSegment, this.rectFromSegment(newSegment));
|
1415 | nextConvexCornerOrientation = (nextConvexCornerOrientation + 3) % 4;
|
1416 | this.updateMinMaxSegments(newSegment);
|
1417 | }
|
1418 |
|
1419 | this.fixMissingMinMaxSegments();
|
1420 | }
|
1421 |
|
1422 | |
1423 |
|
1424 |
|
1425 |
|
1426 |
|
1427 |
|
1428 |
|
1429 |
|
1430 | private fixMissingMinMaxSegments(force = false) {
|
1431 | if (!this._minXSegment || !this._maxXSegment || !this._minYSegment || !this._maxYSegment || force) {
|
1432 | [this._minXSegment, this._maxXSegment, this._minYSegment, this._maxYSegment] = this._tree.findExtremeObjects();
|
1433 | }
|
1434 | }
|
1435 |
|
1436 | |
1437 |
|
1438 |
|
1439 |
|
1440 |
|
1441 |
|
1442 |
|
1443 | private updateMinMaxSegments(s: Segment) {
|
1444 | const centerX = (s.x1 + s.x2) / 2;
|
1445 | const centerY = (s.y1 + s.y2) / 2;
|
1446 | if (this._minXSegment && centerX < (this._minXSegment.x1 + this._minXSegment.x2) / 2) {
|
1447 | this._minXSegment = s;
|
1448 | }
|
1449 | if (this._minYSegment && centerY < (this._minYSegment.y1 + this._minYSegment.y2) / 2) {
|
1450 | this._minYSegment = s;
|
1451 | }
|
1452 | if (this._maxXSegment && centerX > (this._maxXSegment.x1 + this._maxXSegment.x2) / 2) {
|
1453 | this._maxXSegment = s;
|
1454 | }
|
1455 | if (this._maxYSegment && centerY > (this._maxYSegment.y1 + this._maxYSegment.y2) / 2) {
|
1456 | this._maxYSegment = s;
|
1457 | }
|
1458 | }
|
1459 |
|
1460 | |
1461 |
|
1462 |
|
1463 |
|
1464 |
|
1465 |
|
1466 |
|
1467 | private cornerFromRect(orientation: Orientation, bounds: go.Rect): [number, number] {
|
1468 | let x = bounds.x;
|
1469 | let y = bounds.y;
|
1470 | if (orientation === Orientation.NE || orientation === Orientation.SE) {
|
1471 | x = bounds.right;
|
1472 | }
|
1473 | if (orientation === Orientation.SW || orientation === Orientation.SE) {
|
1474 | y = bounds.bottom;
|
1475 | }
|
1476 | return [x, y];
|
1477 | }
|
1478 |
|
1479 | |
1480 |
|
1481 |
|
1482 |
|
1483 |
|
1484 |
|
1485 |
|
1486 | private rectFromSegment(segment: Segment): go.Rect {
|
1487 | if (this.approxEqual(segment.x1, segment.x2)) {
|
1488 | return new go.Rect(segment.x1, Math.min(segment.y1, segment.y2), 0, Math.abs(segment.y1 - segment.y2));
|
1489 | }
|
1490 | return new go.Rect(Math.min(segment.x1, segment.x2), segment.y1, Math.abs(segment.x1 - segment.x2), 0);
|
1491 | }
|
1492 |
|
1493 | |
1494 |
|
1495 |
|
1496 |
|
1497 |
|
1498 |
|
1499 |
|
1500 |
|
1501 |
|
1502 |
|
1503 | private numberIsBetween(n: number, b1: number, b2: number) {
|
1504 | const tmp = b1;
|
1505 | b1 = Math.min(b1, b2);
|
1506 | b2 = Math.max(tmp, b2);
|
1507 | return n + 1e-7 >= b1 && n - 1e-7 <= b2;
|
1508 | }
|
1509 |
|
1510 | |
1511 |
|
1512 |
|
1513 |
|
1514 |
|
1515 |
|
1516 | private segmentIsMinOrMax(s: Segment): boolean {
|
1517 | return s === this._minXSegment || s === this._minYSegment || s === this._maxXSegment || s === this._maxYSegment;
|
1518 | }
|
1519 |
|
1520 | |
1521 |
|
1522 |
|
1523 |
|
1524 |
|
1525 |
|
1526 |
|
1527 |
|
1528 |
|
1529 | private removeSegmentFromLayoutState(s: ListNode<Segment>) {
|
1530 | if (s.data === this._minXSegment) {
|
1531 | this._minXSegment = null;
|
1532 | }
|
1533 | if (s.data === this._maxXSegment) {
|
1534 | this._maxXSegment = null;
|
1535 | }
|
1536 | if (s.data === this._minYSegment) {
|
1537 | this._minYSegment = null;
|
1538 | }
|
1539 | if (s.data === this._maxYSegment) {
|
1540 | this._maxYSegment = null;
|
1541 | }
|
1542 |
|
1543 | this._tree.remove(s.data);
|
1544 | }
|
1545 |
|
1546 | |
1547 |
|
1548 |
|
1549 |
|
1550 |
|
1551 |
|
1552 |
|
1553 |
|
1554 |
|
1555 |
|
1556 | private removeBetween(segments: CircularDoublyLinkedList<Segment>, s1: ListNode<Segment>, s2: ListNode<Segment>) {
|
1557 | if (s1 === s2) return;
|
1558 | let last = s1.next;
|
1559 | let count = 0;
|
1560 | while (last !== s2) {
|
1561 | if (last === segments.start) {
|
1562 | segments.start = s2;
|
1563 | }
|
1564 |
|
1565 | this.removeSegmentFromLayoutState(last);
|
1566 |
|
1567 | count++;
|
1568 | last = last.next;
|
1569 | }
|
1570 | s1.next = s2;
|
1571 | s2.prev = s1;
|
1572 | segments.length -= count;
|
1573 | }
|
1574 |
|
1575 | |
1576 |
|
1577 |
|
1578 |
|
1579 |
|
1580 |
|
1581 |
|
1582 | private placementCost(fit: go.Rect): number {
|
1583 | if (this.packShape === PackedLayout.Rectangular) {
|
1584 | if (this._bounds.containsRect(fit)) {
|
1585 | return 0;
|
1586 | }
|
1587 | return Math.max(Math.abs(this._center.x - fit.center.x), Math.abs(this._center.y - fit.center.y) * this._eAspectRatio);
|
1588 | } else {
|
1589 | return Math.pow((fit.center.x - this._center.x) / this._eAspectRatio, 2) + Math.pow(fit.center.y - this._center.y, 2);
|
1590 | }
|
1591 | }
|
1592 |
|
1593 | |
1594 |
|
1595 |
|
1596 |
|
1597 |
|
1598 |
|
1599 |
|
1600 | private fitHasIntersections(fit: Fit) {
|
1601 | return this._tree.intersecting(fit.bounds).length > 0;
|
1602 | }
|
1603 |
|
1604 | |
1605 |
|
1606 |
|
1607 |
|
1608 |
|
1609 |
|
1610 |
|
1611 |
|
1612 |
|
1613 |
|
1614 | private fastFitHasIntersections(fit: Fit): boolean {
|
1615 | let sNext = fit.s1.next;
|
1616 | let sPrev = fit.s1.prev;
|
1617 | for (let i = 0; i < 2; i++) {
|
1618 | if (this.segmentIntersectsRect(sNext.data, fit.bounds)) {
|
1619 | return true;
|
1620 | }
|
1621 | if (this.segmentIntersectsRect(sPrev.data, fit.bounds)) {
|
1622 | return true;
|
1623 | }
|
1624 | sNext = sNext.next;
|
1625 | sPrev = sPrev.prev;
|
1626 | }
|
1627 | return false;
|
1628 | }
|
1629 |
|
1630 | |
1631 |
|
1632 |
|
1633 |
|
1634 |
|
1635 |
|
1636 |
|
1637 |
|
1638 | private segmentIntersectsRect(s: Segment, r: go.Rect): boolean {
|
1639 | const left = Math.min(s.x1, s.x2);
|
1640 | const right = Math.max(s.x1, s.x2);
|
1641 | const top = Math.min(s.y1, s.y2);
|
1642 | const bottom = Math.min(s.y1, s.y2);
|
1643 | return !(left + 1e-7 >= r.right || right - 1e-7 <= r.left || top + 1e-7 >= r.bottom || bottom - 1e-7 <= r.top);
|
1644 | }
|
1645 |
|
1646 | |
1647 |
|
1648 |
|
1649 |
|
1650 |
|
1651 |
|
1652 |
|
1653 |
|
1654 | private approxEqual(x: number, y: number): boolean {
|
1655 | return Math.abs(x - y) < 1e-7;
|
1656 | }
|
1657 |
|
1658 | |
1659 |
|
1660 |
|
1661 |
|
1662 |
|
1663 |
|
1664 | private isNumeric(value: number): boolean {
|
1665 | return !isNaN(Number(value.toString()));
|
1666 | }
|
1667 |
|
1668 | |
1669 |
|
1670 |
|
1671 |
|
1672 |
|
1673 |
|
1674 | public cloneProtected(copy: this): void {
|
1675 | copy._packShape = this._packShape;
|
1676 | copy._packMode = this._packMode;
|
1677 | copy._sortMode = this._sortMode;
|
1678 | copy._sortOrder = this._sortOrder;
|
1679 | copy._comparer = this._comparer;
|
1680 | copy._aspectRatio = this._aspectRatio;
|
1681 | copy._size = this._size;
|
1682 | copy._spacing = this._spacing;
|
1683 | copy._hasCircularNodes = this._hasCircularNodes;
|
1684 | copy._arrangesToOrigin = this._arrangesToOrigin;
|
1685 | }
|
1686 |
|
1687 | }
|
1688 |
|
1689 |
|
1690 |
|
1691 |
|
1692 |
|
1693 |
|
1694 |
|
1695 | class ListNode<T> {
|
1696 | public data: T;
|
1697 | public prev: ListNode<T>;
|
1698 | public next: ListNode<T>;
|
1699 |
|
1700 | constructor(data: T, prev?: ListNode<T>, next?: ListNode<T>) {
|
1701 | this.data = data;
|
1702 | this.prev = prev !== undefined ? prev : this;
|
1703 | this.next = next !== undefined ? next : this;
|
1704 | }
|
1705 | }
|
1706 |
|
1707 |
|
1708 |
|
1709 |
|
1710 |
|
1711 |
|
1712 |
|
1713 | class CircularDoublyLinkedList<T> {
|
1714 |
|
1715 | |
1716 |
|
1717 |
|
1718 | public start: ListNode<T> | null = null;
|
1719 | |
1720 |
|
1721 |
|
1722 | public length = 0;
|
1723 |
|
1724 | |
1725 |
|
1726 |
|
1727 |
|
1728 | constructor(...vals: Array<T>) {
|
1729 | if (vals.length > 0) {
|
1730 | this.push(...vals);
|
1731 | }
|
1732 | }
|
1733 |
|
1734 | |
1735 |
|
1736 |
|
1737 |
|
1738 |
|
1739 |
|
1740 |
|
1741 | public insertAfter(val: T, node: ListNode<T> | null): ListNode<T> {
|
1742 | if (node === null) {
|
1743 | const newnode = new ListNode<T>(val);
|
1744 | newnode.prev = newnode;
|
1745 | newnode.next = newnode;
|
1746 | this.length = 1;
|
1747 | return this.start = newnode;
|
1748 | }
|
1749 | const tmp = node.next;
|
1750 | node.next = new ListNode<T>(val, node, tmp);
|
1751 | tmp.prev = node.next;
|
1752 | this.length++;
|
1753 | return node.next;
|
1754 | }
|
1755 |
|
1756 | |
1757 |
|
1758 |
|
1759 |
|
1760 |
|
1761 |
|
1762 | public push(...vals: Array<T>): ListNode<T> {
|
1763 | if (vals.length === 0) {
|
1764 | throw new Error('You must push at least one element!');
|
1765 | }
|
1766 | const sp = this.start !== null ? this.start.prev : null;
|
1767 | let last = this.insertAfter(vals[0], sp);
|
1768 | for (let i = 1; i < vals.length; i++) {
|
1769 | last = this.insertAfter(vals[i], last);
|
1770 | }
|
1771 | return last;
|
1772 | }
|
1773 |
|
1774 | |
1775 |
|
1776 |
|
1777 |
|
1778 |
|
1779 | public remove(node: ListNode<T>): void {
|
1780 | this.length--;
|
1781 | if (this.length) {
|
1782 | node.prev.next = node.next;
|
1783 | node.next.prev = node.prev;
|
1784 | if (node === this.start) {
|
1785 | this.start = node.next;
|
1786 | }
|
1787 | } else {
|
1788 | this.start = null;
|
1789 | }
|
1790 | }
|
1791 |
|
1792 | |
1793 |
|
1794 |
|
1795 |
|
1796 |
|
1797 |
|
1798 |
|
1799 |
|
1800 | public removeBetween(start: ListNode<T>, end: ListNode<T>): ListNode<T> {
|
1801 | if (start !== end) {
|
1802 | let last = start.next;
|
1803 | let count = 0;
|
1804 | while (last !== end) {
|
1805 | if (last === this.start) {
|
1806 | this.start = end;
|
1807 | }
|
1808 | count++;
|
1809 | last = last.next;
|
1810 | }
|
1811 | start.next = end;
|
1812 | end.prev = start;
|
1813 | this.length -= count;
|
1814 | return end;
|
1815 | }
|
1816 | return start;
|
1817 | }
|
1818 |
|
1819 | }
|
1820 |
|
1821 |
|
1822 |
|
1823 |
|
1824 |
|
1825 |
|
1826 |
|
1827 |
|
1828 |
|
1829 |
|
1830 |
|
1831 |
|
1832 |
|
1833 |
|
1834 |
|
1835 |
|
1836 |
|
1837 |
|
1838 |
|
1839 |
|
1840 |
|
1841 |
|
1842 |
|
1843 |
|
1844 |
|
1845 |
|
1846 |
|
1847 |
|
1848 |
|
1849 |
|
1850 |
|
1851 |
|
1852 |
|
1853 |
|
1854 |
|
1855 |
|
1856 |
|
1857 |
|
1858 |
|
1859 |
|
1860 |
|
1861 |
|
1862 |
|
1863 |
|
1864 |
|
1865 | class Circle extends go.Point {
|
1866 | public r: number;
|
1867 | constructor(x: number, y: number, r: number) {
|
1868 | super(x, y);
|
1869 | this.r = r;
|
1870 | }
|
1871 | }
|
1872 |
|
1873 |
|
1874 |
|
1875 |
|
1876 |
|
1877 | function enclose(circles: Array<Circle | go.Point>): go.Rect {
|
1878 | let i = 0;
|
1879 | const n = (circles = shuffle(circles.slice())).length;
|
1880 | let B = new Array<Circle | go.Point>();
|
1881 | let p: Circle | go.Point;
|
1882 | let e: Circle | null = null;
|
1883 |
|
1884 | while (i < n) {
|
1885 | p = circles[i];
|
1886 | if (e !== null && enclosesWeak(e, p)) ++i;
|
1887 | else e = encloseBasis(B = extendBasis(B, p)), i = 0;
|
1888 | }
|
1889 |
|
1890 | if (e !== null) {
|
1891 | return circleToRect(e);
|
1892 | } else {
|
1893 | throw new Error('Assertion error');
|
1894 | }
|
1895 | }
|
1896 |
|
1897 |
|
1898 |
|
1899 |
|
1900 |
|
1901 |
|
1902 | function circleToRect(c: Circle): go.Rect {
|
1903 | return new go.Rect(c.x - c.r, c.y - c.r, c.r * 2, c.r * 2);
|
1904 | }
|
1905 |
|
1906 |
|
1907 |
|
1908 |
|
1909 | function extendBasis(B: Array<Circle | go.Point>, p: Circle | go.Point): Array<Circle | go.Point> {
|
1910 | if (enclosesWeakAll(p, B)) return [p];
|
1911 |
|
1912 |
|
1913 | for (let i = 0; i < B.length; ++i) {
|
1914 | if (enclosesNot(p, B[i])
|
1915 | && enclosesWeakAll(encloseBasis2(B[i], p), B)) {
|
1916 | return [B[i], p];
|
1917 | }
|
1918 | }
|
1919 |
|
1920 |
|
1921 | for (let i = 0; i < B.length - 1; ++i) {
|
1922 | for (let j = i + 1; j < B.length; ++j) {
|
1923 | if (enclosesNot(encloseBasis2(B[i], B[j]), p)
|
1924 | && enclosesNot(encloseBasis2(B[i], p), B[j])
|
1925 | && enclosesNot(encloseBasis2(B[j], p), B[i])
|
1926 | && enclosesWeakAll(encloseBasis3(B[i], B[j], p), B)) {
|
1927 | return [B[i], B[j], p];
|
1928 | }
|
1929 | }
|
1930 | }
|
1931 |
|
1932 |
|
1933 | throw new Error('Assertion error');
|
1934 | }
|
1935 |
|
1936 |
|
1937 |
|
1938 |
|
1939 | function enclosesNot(a: Circle | go.Point, b: Circle | go.Point): boolean {
|
1940 | const ar = a instanceof Circle ? a.r : 0;
|
1941 | const br = b instanceof Circle ? b.r : 0;
|
1942 | const dr = ar - br;
|
1943 | const dx = b.x - a.x;
|
1944 | const dy = b.y - a.y;
|
1945 | return dr < 0 || dr * dr < dx * dx + dy * dy;
|
1946 | }
|
1947 |
|
1948 |
|
1949 |
|
1950 |
|
1951 | function enclosesWeak(a: Circle | go.Point, b: Circle | go.Point): boolean {
|
1952 | const ar = a instanceof Circle ? a.r : 0;
|
1953 | const br = b instanceof Circle ? b.r : 0;
|
1954 | const dr = ar - br + 1e-6;
|
1955 | const dx = b.x - a.x;
|
1956 | const dy = b.y - a.y;
|
1957 | return dr > 0 && dr * dr > dx * dx + dy * dy;
|
1958 | }
|
1959 |
|
1960 |
|
1961 |
|
1962 |
|
1963 | function enclosesWeakAll(a: Circle | go.Point, B: Array<Circle | go.Point>): boolean {
|
1964 | for (let i = 0; i < B.length; ++i) {
|
1965 | if (!enclosesWeak(a, B[i])) {
|
1966 | return false;
|
1967 | }
|
1968 | }
|
1969 | return true;
|
1970 | }
|
1971 |
|
1972 |
|
1973 |
|
1974 |
|
1975 | function encloseBasis(B: Array<Circle | go.Point>): Circle {
|
1976 | switch (B.length) {
|
1977 | case 2: return encloseBasis2(B[0], B[1]);
|
1978 | case 3: return encloseBasis3(B[0], B[1], B[2]);
|
1979 | default: return encloseBasis1(B[0]);
|
1980 | }
|
1981 | }
|
1982 |
|
1983 |
|
1984 |
|
1985 |
|
1986 | function encloseBasis1(a: Circle | go.Point): Circle {
|
1987 | const ar = a instanceof Circle ? a.r : 0;
|
1988 | return new Circle(a.x, a.y, ar);
|
1989 | }
|
1990 |
|
1991 |
|
1992 |
|
1993 |
|
1994 | function encloseBasis2(a: Circle | go.Point, b: Circle | go.Point): Circle {
|
1995 | const ar = a instanceof Circle ? a.r : 0;
|
1996 | const br = b instanceof Circle ? b.r : 0;
|
1997 | const x1 = a.x;
|
1998 | const y1 = a.y;
|
1999 | const r1 = ar;
|
2000 | const x2 = b.x;
|
2001 | const y2 = b.y;
|
2002 | const r2 = br;
|
2003 | const x21 = x2 - x1;
|
2004 | const y21 = y2 - y1;
|
2005 | const r21 = r2 - r1;
|
2006 | const l = Math.sqrt(x21 * x21 + y21 * y21);
|
2007 | return new Circle(
|
2008 | (x1 + x2 + x21 / l * r21) / 2,
|
2009 | (y1 + y2 + y21 / l * r21) / 2,
|
2010 | (l + r1 + r2) / 2
|
2011 | );
|
2012 | }
|
2013 |
|
2014 |
|
2015 |
|
2016 |
|
2017 | function encloseBasis3(a: Circle | go.Point, b: Circle | go.Point, c: Circle | go.Point): Circle {
|
2018 | const ar = a instanceof Circle ? a.r : 0;
|
2019 | const br = b instanceof Circle ? b.r : 0;
|
2020 | const cr = c instanceof Circle ? c.r : 0;
|
2021 | const x1 = a.x;
|
2022 | const y1 = a.y;
|
2023 | const r1 = ar;
|
2024 | const x2 = b.x;
|
2025 | const y2 = b.y;
|
2026 | const r2 = br;
|
2027 | const x3 = c.x;
|
2028 | const y3 = c.y;
|
2029 | const r3 = cr;
|
2030 | const a2 = x1 - x2;
|
2031 | const a3 = x1 - x3;
|
2032 | const b2 = y1 - y2;
|
2033 | const b3 = y1 - y3;
|
2034 | const c2 = r2 - r1;
|
2035 | const c3 = r3 - r1;
|
2036 | const d1 = x1 * x1 + y1 * y1 - r1 * r1;
|
2037 | const d2 = d1 - x2 * x2 - y2 * y2 + r2 * r2;
|
2038 | const d3 = d1 - x3 * x3 - y3 * y3 + r3 * r3;
|
2039 | const ab = a3 * b2 - a2 * b3;
|
2040 | const xa = (b2 * d3 - b3 * d2) / (ab * 2) - x1;
|
2041 | const xb = (b3 * c2 - b2 * c3) / ab;
|
2042 | const ya = (a3 * d2 - a2 * d3) / (ab * 2) - y1;
|
2043 | const yb = (a2 * c3 - a3 * c2) / ab;
|
2044 | const A = xb * xb + yb * yb - 1;
|
2045 | const B = 2 * (r1 + xa * xb + ya * yb);
|
2046 | const C = xa * xa + ya * ya - r1 * r1;
|
2047 | const r = -(A ? (B + Math.sqrt(B * B - 4 * A * C)) / (2 * A) : C / B);
|
2048 | return new Circle(
|
2049 | x1 + xa + xb * r,
|
2050 | y1 + ya + yb * r,
|
2051 | r
|
2052 | );
|
2053 | }
|
2054 |
|
2055 |
|
2056 |
|
2057 |
|
2058 |
|
2059 |
|
2060 | function shuffle(a: Array<any>): Array<any> {
|
2061 | let j: any;
|
2062 | let x: any;
|
2063 | let i: any;
|
2064 | for (i = a.length - 1; i > 0; i--) {
|
2065 | j = Math.floor(Math.random() * (i + 1));
|
2066 | x = a[i];
|
2067 | a[i] = a[j];
|
2068 | a[j] = x;
|
2069 | }
|
2070 | return a;
|
2071 | }
|