1
// Copyright 2007 The Closure Library Authors. All Rights Reserved.
2
//
3
// Licensed under the Apache License, Version 2.0 (the "License");
4
// you may not use this file except in compliance with the License.
5
// You may obtain a copy of the License at
6
//
7
//      http://www.apache.org/licenses/LICENSE-2.0
8
//
9
// Unless required by applicable law or agreed to in writing, software
10
// distributed under the License is distributed on an "AS-IS" BASIS,
11
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12
// See the License for the specific language governing permissions and
13
// limitations under the License.
14

15

16
/**
17
 * @fileoverview Represents a path used with a Graphics implementation.
18
 * @author [email protected] (Erik Arvidsson)
19
 */
20

21
goog.provide('goog.math.Path');
22
goog.provide('goog.math.Path.Segment');
23

24
goog.require('goog.array');
25
goog.require('goog.math');
26
goog.require('goog.math.AffineTransform');
27

28

29

30
/**
31
 * Creates a path object. A path is a sequence of segments and may be open or
32
 * closed. Path uses the EVEN-ODD fill rule for determining the interior of the
33
 * path. A path must start with a moveTo command.
34
 *
35
 * A "simple" path does not contain any arcs and may be transformed using
36
 * the {@code transform} method.
37
 *
38
 * @struct
39
 * @constructor
40
 * @final
41
 */
42
goog.math.Path = function() {
43
  /**
44
   * The segment types that constitute this path.
45
   * @private {!Array<goog.math.Path.Segment>}
46
   */
47
  this.segments_ = [];
48

49
  /**
50
   * The number of repeated segments of the current type.
51
   * @type {!Array<number>}
52
   * @private
53
   */
54
  this.count_ = [];
55

56
  /**
57
   * The arguments corresponding to each of the segments.
58
   * @type {!Array<number>}
59
   * @private
60
   */
61
  this.arguments_ = [];
62

63
  /**
64
   * The coordinates of the point which closes the path (the point of the
65
   * last moveTo command).
66
   * @type {Array<number>?}
67
   * @private
68
   */
69
  this.closePoint_ = null;
70

71
  /**
72
   * The coordinates most recently added to the end of the path.
73
   * @type {Array<number>?}
74
   * @private
75
   */
76
  this.currentPoint_ = null;
77

78
  /**
79
   * Flag for whether this is a simple path (contains no arc segments).
80
   * @type {boolean}
81
   * @private
82
   */
83
  this.simple_ = true;
84
};
85

86

87
/**
88
 * Path segment types.
89
 * @enum {number}
90
 */
91
goog.math.Path.Segment = {
92
  MOVETO: 0,
93
  LINETO: 1,
94
  CURVETO: 2,
95
  ARCTO: 3,
96
  CLOSE: 4
97
};
98

99

100
/**
101
 * The number of points for each segment type.
102
 * @type {!Array<number>}
103
 * @private
104
 */
105
goog.math.Path.segmentArgCounts_ = (function() {
106
  var counts = [];
107
  counts[goog.math.Path.Segment.MOVETO] = 2;
108
  counts[goog.math.Path.Segment.LINETO] = 2;
109
  counts[goog.math.Path.Segment.CURVETO] = 6;
110
  counts[goog.math.Path.Segment.ARCTO] = 6;
111
  counts[goog.math.Path.Segment.CLOSE] = 0;
112
  return counts;
113
})();
114

115

116
/**
117
 * Returns an array of the segment types in this path, in the order of their
118
 * appearance. Adjacent segments of the same type are collapsed into a single
119
 * entry in the array. The returned array is a copy; modifications are not
120
 * reflected in the Path object.
121
 * @return {!Array<number>}
122
 */
123
goog.math.Path.prototype.getSegmentTypes = function() {
124
  return this.segments_.concat();
125
};
126

127

128
/**
129
 * Returns an array of the number of times each segment type repeats in this
130
 * path, in order. The returned array is a copy; modifications are not reflected
131
 * in the Path object.
132
 * @return {!Array<number>}
133
 */
134
goog.math.Path.prototype.getSegmentCounts = function() {
135
  return this.count_.concat();
136
};
137

138

139
/**
140
 * Returns an array of all arguments for the segments of this path object, in
141
 * order. The returned array is a copy; modifications are not reflected in the
142
 * Path object.
143
 * @return {!Array<number>}
144
 */
145
goog.math.Path.prototype.getSegmentArgs = function() {
146
  return this.arguments_.concat();
147
};
148

149

150
/**
151
 * Returns the number of points for a segment type.
152
 *
153
 * @param {number} segment The segment type.
154
 * @return {number} The number of points.
155
 */
156
goog.math.Path.getSegmentCount = function(segment) {
157
  return goog.math.Path.segmentArgCounts_[segment];
158
};
159

160

161
/**
162
 * Appends another path to the end of this path.
163
 *
164
 * @param {!goog.math.Path} path The path to append.
165
 * @return {!goog.math.Path} This path.
166
 */
167
goog.math.Path.prototype.appendPath = function(path) {
168
  if (path.currentPoint_) {
169
    Array.prototype.push.apply(this.segments_, path.segments_);
170
    Array.prototype.push.apply(this.count_, path.count_);
171
    Array.prototype.push.apply(this.arguments_, path.arguments_);
172
    this.currentPoint_ = path.currentPoint_.concat();
173
    this.closePoint_ = path.closePoint_.concat();
174
    this.simple_ = this.simple_ && path.simple_;
175
  }
176
  return this;
177
};
178

179

180
/**
181
 * Clears the path.
182
 *
183
 * @return {!goog.math.Path} The path itself.
184
 */
185
goog.math.Path.prototype.clear = function() {
186
  this.segments_.length = 0;
187
  this.count_.length = 0;
188
  this.arguments_.length = 0;
189
  this.closePoint_ = null;
190
  this.currentPoint_ = null;
191
  this.simple_ = true;
192
  return this;
193
};
194

195

196
/**
197
 * Adds a point to the path by moving to the specified point. Repeated moveTo
198
 * commands are collapsed into a single moveTo.
199
 *
200
 * @param {number} x X coordinate of destination point.
201
 * @param {number} y Y coordinate of destination point.
202
 * @return {!goog.math.Path} The path itself.
203
 */
204
goog.math.Path.prototype.moveTo = function(x, y) {
205
  if (goog.array.peek(this.segments_) == goog.math.Path.Segment.MOVETO) {
206
    this.arguments_.length -= 2;
207
  } else {
208
    this.segments_.push(goog.math.Path.Segment.MOVETO);
209
    this.count_.push(1);
210
  }
211
  this.arguments_.push(x, y);
212
  this.currentPoint_ = this.closePoint_ = [x, y];
213
  return this;
214
};
215

216

217
/**
218
 * Adds points to the path by drawing a straight line to each point.
219
 *
220
 * @param {...number} var_args The coordinates of each destination point as x, y
221
 *     value pairs.
222
 * @return {!goog.math.Path} The path itself.
223
 */
224
goog.math.Path.prototype.lineTo = function(var_args) {
225
  return this.lineTo_(arguments);
226
};
227

228

229
/**
230
 * Adds points to the path by drawing a straight line to each point.
231
 *
232
 * @param {!Array<number>} coordinates The coordinates of each
233
 *     destination point as x, y value pairs.
234
 * @return {!goog.math.Path} The path itself.
235
 */
236
goog.math.Path.prototype.lineToFromArray = function(coordinates) {
237
  return this.lineTo_(coordinates);
238
};
239

240

241
/**
242
 * Adds points to the path by drawing a straight line to each point.
243
 *
244
 * @param {!Array<number>|Arguments} coordinates The coordinates of each
245
 *     destination point as x, y value pairs.
246
 * @return {!goog.math.Path} The path itself.
247
 * @private
248
 */
249
goog.math.Path.prototype.lineTo_ = function(coordinates) {
250
  var lastSegment = goog.array.peek(this.segments_);
251
  if (lastSegment == null) {
252
    throw Error('Path cannot start with lineTo');
253
  }
254
  if (lastSegment != goog.math.Path.Segment.LINETO) {
255
    this.segments_.push(goog.math.Path.Segment.LINETO);
256
    this.count_.push(0);
257
  }
258
  for (var i = 0; i < coordinates.length; i += 2) {
259
    var x = coordinates[i];
260
    var y = coordinates[i + 1];
261
    this.arguments_.push(x, y);
262
  }
263
  this.count_[this.count_.length - 1] += i / 2;
264
  this.currentPoint_ = [x, y];
265
  return this;
266
};
267

268

269
/**
270
 * Adds points to the path by drawing cubic Bezier curves. Each curve is
271
 * specified using 3 points (6 coordinates) - two control points and the end
272
 * point of the curve.
273
 *
274
 * @param {...number} var_args The coordinates specifying each curve in sets of
275
 *     6 points: {@code [x1, y1]} the first control point, {@code [x2, y2]} the
276
 *     second control point and {@code [x, y]} the end point.
277
 * @return {!goog.math.Path} The path itself.
278
 */
279
goog.math.Path.prototype.curveTo = function(var_args) {
280
  return this.curveTo_(arguments);
281
};
282

283

284
/**
285
 * Adds points to the path by drawing cubic Bezier curves. Each curve is
286
 * specified using 3 points (6 coordinates) - two control points and the end
287
 * point of the curve.
288
 *
289
 * @param {!Array<number>} coordinates The coordinates specifying
290
 *     each curve in sets of 6 points: {@code [x1, y1]} the first control point,
291
 *     {@code [x2, y2]} the second control point and {@code [x, y]} the end
292
 *     point.
293
 * @return {!goog.math.Path} The path itself.
294
 */
295
goog.math.Path.prototype.curveToFromArray = function(coordinates) {
296
  return this.curveTo_(coordinates);
297
};
298

299

300
/**
301
 * Adds points to the path by drawing cubic Bezier curves. Each curve is
302
 * specified using 3 points (6 coordinates) - two control points and the end
303
 * point of the curve.
304
 *
305
 * @param {!Array<number>|Arguments} coordinates The coordinates specifying
306
 *     each curve in sets of 6 points: {@code [x1, y1]} the first control point,
307
 *     {@code [x2, y2]} the second control point and {@code [x, y]} the end
308
 *     point.
309
 * @return {!goog.math.Path} The path itself.
310
 * @private
311
 */
312
goog.math.Path.prototype.curveTo_ = function(coordinates) {
313
  var lastSegment = goog.array.peek(this.segments_);
314
  if (lastSegment == null) {
315
    throw Error('Path cannot start with curve');
316
  }
317
  if (lastSegment != goog.math.Path.Segment.CURVETO) {
318
    this.segments_.push(goog.math.Path.Segment.CURVETO);
319
    this.count_.push(0);
320
  }
321
  for (var i = 0; i < coordinates.length; i += 6) {
322
    var x = coordinates[i + 4];
323
    var y = coordinates[i + 5];
324
    this.arguments_.push(
325
        coordinates[i], coordinates[i + 1], coordinates[i + 2],
326
        coordinates[i + 3], x, y);
327
  }
328
  this.count_[this.count_.length - 1] += i / 6;
329
  this.currentPoint_ = [x, y];
330
  return this;
331
};
332

333

334
/**
335
 * Adds a path command to close the path by connecting the
336
 * last point to the first point.
337
 *
338
 * @return {!goog.math.Path} The path itself.
339
 */
340
goog.math.Path.prototype.close = function() {
341
  var lastSegment = goog.array.peek(this.segments_);
342
  if (lastSegment == null) {
343
    throw Error('Path cannot start with close');
344
  }
345
  if (lastSegment != goog.math.Path.Segment.CLOSE) {
346
    this.segments_.push(goog.math.Path.Segment.CLOSE);
347
    this.count_.push(1);
348
    this.currentPoint_ = this.closePoint_;
349
  }
350
  return this;
351
};
352

353

354
/**
355
 * Adds a path command to draw an arc centered at the point {@code (cx, cy)}
356
 * with radius {@code rx} along the x-axis and {@code ry} along the y-axis from
357
 * {@code startAngle} through {@code extent} degrees. Positive rotation is in
358
 * the direction from positive x-axis to positive y-axis.
359
 *
360
 * @param {number} cx X coordinate of center of ellipse.
361
 * @param {number} cy Y coordinate of center of ellipse.
362
 * @param {number} rx Radius of ellipse on x axis.
363
 * @param {number} ry Radius of ellipse on y axis.
364
 * @param {number} fromAngle Starting angle measured in degrees from the
365
 *     positive x-axis.
366
 * @param {number} extent The span of the arc in degrees.
367
 * @param {boolean} connect If true, the starting point of the arc is connected
368
 *     to the current point.
369
 * @return {!goog.math.Path} The path itself.
370
 * @deprecated Use {@code arcTo} or {@code arcToAsCurves} instead.
371
 */
372
goog.math.Path.prototype.arc = function(
373
    cx, cy, rx, ry, fromAngle, extent, connect) {
374
  var startX = cx + goog.math.angleDx(fromAngle, rx);
375
  var startY = cy + goog.math.angleDy(fromAngle, ry);
376
  if (connect) {
377
    if (!this.currentPoint_ || startX != this.currentPoint_[0] ||
378
        startY != this.currentPoint_[1]) {
379
      this.lineTo(startX, startY);
380
    }
381
  } else {
382
    this.moveTo(startX, startY);
383
  }
384
  return this.arcTo(rx, ry, fromAngle, extent);
385
};
386

387

388
/**
389
 * Adds a path command to draw an arc starting at the path's current point,
390
 * with radius {@code rx} along the x-axis and {@code ry} along the y-axis from
391
 * {@code startAngle} through {@code extent} degrees. Positive rotation is in
392
 * the direction from positive x-axis to positive y-axis.
393
 *
394
 * This method makes the path non-simple.
395
 *
396
 * @param {number} rx Radius of ellipse on x axis.
397
 * @param {number} ry Radius of ellipse on y axis.
398
 * @param {number} fromAngle Starting angle measured in degrees from the
399
 *     positive x-axis.
400
 * @param {number} extent The span of the arc in degrees.
401
 * @return {!goog.math.Path} The path itself.
402
 */
403
goog.math.Path.prototype.arcTo = function(rx, ry, fromAngle, extent) {
404
  var cx = this.currentPoint_[0] - goog.math.angleDx(fromAngle, rx);
405
  var cy = this.currentPoint_[1] - goog.math.angleDy(fromAngle, ry);
406
  var ex = cx + goog.math.angleDx(fromAngle + extent, rx);
407
  var ey = cy + goog.math.angleDy(fromAngle + extent, ry);
408
  this.segments_.push(goog.math.Path.Segment.ARCTO);
409
  this.count_.push(1);
410
  this.arguments_.push(rx, ry, fromAngle, extent, ex, ey);
411
  this.simple_ = false;
412
  this.currentPoint_ = [ex, ey];
413
  return this;
414
};
415

416

417
/**
418
 * Same as {@code arcTo}, but approximates the arc using bezier curves.
419
.* As a result, this method does not affect the simplified status of this path.
420
 * The algorithm is adapted from {@code java.awt.geom.ArcIterator}.
421
 *
422
 * @param {number} rx Radius of ellipse on x axis.
423
 * @param {number} ry Radius of ellipse on y axis.
424
 * @param {number} fromAngle Starting angle measured in degrees from the
425
 *     positive x-axis.
426
 * @param {number} extent The span of the arc in degrees.
427
 * @return {!goog.math.Path} The path itself.
428
 */
429
goog.math.Path.prototype.arcToAsCurves = function(rx, ry, fromAngle, extent) {
430
  var cx = this.currentPoint_[0] - goog.math.angleDx(fromAngle, rx);
431
  var cy = this.currentPoint_[1] - goog.math.angleDy(fromAngle, ry);
432
  var extentRad = goog.math.toRadians(extent);
433
  var arcSegs = Math.ceil(Math.abs(extentRad) / Math.PI * 2);
434
  var inc = extentRad / arcSegs;
435
  var angle = goog.math.toRadians(fromAngle);
436
  for (var j = 0; j < arcSegs; j++) {
437
    var relX = Math.cos(angle);
438
    var relY = Math.sin(angle);
439
    var z = 4 / 3 * Math.sin(inc / 2) / (1 + Math.cos(inc / 2));
440
    var c0 = cx + (relX - z * relY) * rx;
441
    var c1 = cy + (relY + z * relX) * ry;
442
    angle += inc;
443
    relX = Math.cos(angle);
444
    relY = Math.sin(angle);
445
    this.curveTo(
446
        c0, c1, cx + (relX + z * relY) * rx, cy + (relY - z * relX) * ry,
447
        cx + relX * rx, cy + relY * ry);
448
  }
449
  return this;
450
};
451

452

453
/**
454
 * Iterates over the path calling the supplied callback once for each path
455
 * segment. The arguments to the callback function are the segment type and
456
 * an array of its arguments.
457
 *
458
 * The {@code LINETO} and {@code CURVETO} arrays can contain multiple
459
 * segments of the same type. The number of segments is the length of the
460
 * array divided by the segment length (2 for lines, 6 for  curves).
461
 *
462
 * As a convenience the {@code ARCTO} segment also includes the end point as the
463
 * last two arguments: {@code rx, ry, fromAngle, extent, x, y}.
464
 *
465
 * @param {function(!goog.math.Path.Segment, !Array<number>)} callback
466
 *     The function to call with each path segment.
467
 */
468
goog.math.Path.prototype.forEachSegment = function(callback) {
469
  var points = this.arguments_;
470
  var index = 0;
471
  for (var i = 0, length = this.segments_.length; i < length; i++) {
472
    var seg = this.segments_[i];
473
    var n = goog.math.Path.segmentArgCounts_[seg] * this.count_[i];
474
    callback(seg, points.slice(index, index + n));
475
    index += n;
476
  }
477
};
478

479

480
/**
481
 * Returns the coordinates most recently added to the end of the path.
482
 *
483
 * @return {Array<number>?} An array containing the ending coordinates of the
484
 *     path of the form {@code [x, y]}.
485
 */
486
goog.math.Path.prototype.getCurrentPoint = function() {
487
  return this.currentPoint_ && this.currentPoint_.concat();
488
};
489

490

491
/**
492
 * @return {!goog.math.Path} A copy of this path.
493
 */
494
goog.math.Path.prototype.clone = function() {
495
  var path = new goog.math.Path();
496
  path.segments_ = this.segments_.concat();
497
  path.count_ = this.count_.concat();
498
  path.arguments_ = this.arguments_.concat();
499
  path.closePoint_ = this.closePoint_ && this.closePoint_.concat();
500
  path.currentPoint_ = this.currentPoint_ && this.currentPoint_.concat();
501
  path.simple_ = this.simple_;
502
  return path;
503
};
504

505

506
/**
507
 * Returns true if this path contains no arcs. Simplified paths can be
508
 * created using {@code createSimplifiedPath}.
509
 *
510
 * @return {boolean} True if the path contains no arcs.
511
 */
512
goog.math.Path.prototype.isSimple = function() {
513
  return this.simple_;
514
};
515

516

517
/**
518
 * A map from segment type to the path function to call to simplify a path.
519
 * @private {!Object<goog.math.Path.Segment, function(this: goog.math.Path)>}
520
 */
521
goog.math.Path.simplifySegmentMap_ = (function() {
522
  var map = {};
523
  map[goog.math.Path.Segment.MOVETO] = goog.math.Path.prototype.moveTo;
524
  map[goog.math.Path.Segment.LINETO] = goog.math.Path.prototype.lineTo;
525
  map[goog.math.Path.Segment.CLOSE] = goog.math.Path.prototype.close;
526
  map[goog.math.Path.Segment.CURVETO] = goog.math.Path.prototype.curveTo;
527
  map[goog.math.Path.Segment.ARCTO] = goog.math.Path.prototype.arcToAsCurves;
528
  return map;
529
})();
530

531

532
/**
533
 * Creates a copy of the given path, replacing {@code arcTo} with
534
 * {@code arcToAsCurves}. The resulting path is simplified and can
535
 * be transformed.
536
 *
537
 * @param {!goog.math.Path} src The path to simplify.
538
 * @return {!goog.math.Path} A new simplified path.
539
 */
540
goog.math.Path.createSimplifiedPath = function(src) {
541
  if (src.isSimple()) {
542
    return src.clone();
543
  }
544
  var path = new goog.math.Path();
545
  src.forEachSegment(function(segment, args) {
546
    goog.math.Path.simplifySegmentMap_[segment].apply(path, args);
547
  });
548
  return path;
549
};
550

551

552
// TODO(chrisn): Delete this method
553
/**
554
 * Creates a transformed copy of this path. The path is simplified
555
 * {@see #createSimplifiedPath} prior to transformation.
556
 *
557
 * @param {!goog.math.AffineTransform} tx The transformation to perform.
558
 * @return {!goog.math.Path} A new, transformed path.
559
 */
560
goog.math.Path.prototype.createTransformedPath = function(tx) {
561
  var path = goog.math.Path.createSimplifiedPath(this);
562
  path.transform(tx);
563
  return path;
564
};
565

566

567
/**
568
 * Transforms the path. Only simple paths are transformable. Attempting
569
 * to transform a non-simple path will throw an error.
570
 *
571
 * @param {!goog.math.AffineTransform} tx The transformation to perform.
572
 * @return {!goog.math.Path} The path itself.
573
 */
574
goog.math.Path.prototype.transform = function(tx) {
575
  if (!this.isSimple()) {
576
    throw Error('Non-simple path');
577
  }
578
  tx.transform(
579
      this.arguments_, 0, this.arguments_, 0, this.arguments_.length / 2);
580
  if (this.closePoint_) {
581
    tx.transform(this.closePoint_, 0, this.closePoint_, 0, 1);
582
  }
583
  if (this.currentPoint_ && this.closePoint_ != this.currentPoint_) {
584
    tx.transform(this.currentPoint_, 0, this.currentPoint_, 0, 1);
585
  }
586
  return this;
587
};
588

589

590
/**
591
 * @return {boolean} Whether the path is empty.
592
 */
593
goog.math.Path.prototype.isEmpty = function() {
594
  return this.segments_.length == 0;
595
};
596

597