1 /*
  2     Copyright 2008-2018
  3         Matthias Ehmann,
  4         Michael Gerhaeuser,
  5         Carsten Miller,
  6         Bianca Valentin,
  7         Alfred Wassermann,
  8         Peter Wilfahrt
  9 
 10     This file is part of JSXGraph.
 11 
 12     JSXGraph is free software dual licensed under the GNU LGPL or MIT License.
 13 
 14     You can redistribute it and/or modify it under the terms of the
 15 
 16       * GNU Lesser General Public License as published by
 17         the Free Software Foundation, either version 3 of the License, or
 18         (at your option) any later version
 19       OR
 20       * MIT License: https://github.com/jsxgraph/jsxgraph/blob/master/LICENSE.MIT
 21 
 22     JSXGraph is distributed in the hope that it will be useful,
 23     but WITHOUT ANY WARRANTY; without even the implied warranty of
 24     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 25     GNU Lesser General Public License for more details.
 26 
 27     You should have received a copy of the GNU Lesser General Public License and
 28     the MIT License along with JSXGraph. If not, see <http://www.gnu.org/licenses/>
 29     and <http://opensource.org/licenses/MIT/>.
 30  */
 31 
 32 
 33 /*global JXG:true, define: true*/
 34 /*jslint nomen: true, plusplus: true*/
 35 
 36 /* depends:
 37  jxg
 38  base/constants
 39  base/coords
 40  math/statistics
 41  utils/type
 42  base/element
 43   elements:
 44    segment
 45    transform
 46  */
 47 
 48 define([
 49     'jxg', 'base/constants', 'base/coords', 'math/statistics', 'math/geometry', 'utils/type', 'base/element', 'base/line', 'base/transformation'
 50 ], function (JXG, Const, Coords, Statistics, Geometry, Type, GeometryElement, Line, Transform) {
 51 
 52     "use strict";
 53 
 54     /**
 55      * Creates a new instance of JXG.Polygon.
 56      * @class Polygon stores all style and functional properties that are required
 57      * to draw and to interactact with a polygon.
 58      * @param {JXG.Board} board Reference to the board the polygon is to be drawn on.
 59      * @param {Array} vertices Unique identifiers for the points defining the polygon.
 60      * Last point must be first point. Otherwise, the first point will be added at the list.
 61      * @param {Object} attributes An object which contains properties as given in {@link JXG.Options.elements}
 62      * and {@link JXG.Options.polygon}.
 63      * @constructor
 64      * @extends JXG.GeometryElement
 65      */
 66 
 67     JXG.Polygon = function (board, vertices, attributes) {
 68         this.constructor(board, attributes, Const.OBJECT_TYPE_POLYGON, Const.OBJECT_CLASS_AREA);
 69 
 70         var i, l, len, j,
 71             attr_line = Type.copyAttributes(attributes, board.options, 'polygon', 'borders');
 72 
 73         this.withLines = attributes.withlines;
 74         this.attr_line = attr_line;
 75 
 76         /**
 77          * References to the points defining the polygon. The last vertex is the same as the first vertex.
 78          * @type Array
 79          */
 80         this.vertices = [];
 81         for (i = 0; i < vertices.length; i++) {
 82             this.vertices[i] = this.board.select(vertices[i]);
 83         }
 84 
 85         // Close the polygon
 86         if (this.vertices.length > 0 && this.vertices[this.vertices.length - 1].id !== this.vertices[0].id) {
 87             this.vertices.push(this.vertices[0]);
 88         }
 89 
 90         /**
 91          * References to the border lines of the polygon.
 92          * @type Array
 93          */
 94         this.borders = [];
 95 
 96         if (this.withLines) {
 97             len = this.vertices.length - 1;
 98             for (j = 0; j < len; j++) {
 99                 // This sets the "correct" labels for the first triangle of a construction.
100                 i = (j + 1) % len;
101                 attr_line.id = attr_line.ids && attr_line.ids[i];
102                 attr_line.name = attr_line.names && attr_line.names[i];
103                 attr_line.strokecolor = (Type.isArray(attr_line.colors) && attr_line.colors[i % attr_line.colors.length]) ||
104                                             attr_line.strokecolor;
105                 attr_line.visible = Type.exists(attributes.borders.visible) ? attributes.borders.visible : attributes.visible;
106 
107                 if (attr_line.strokecolor === false) {
108                     attr_line.strokecolor = 'none';
109                 }
110 
111                 l = board.create('segment', [this.vertices[i], this.vertices[i + 1]], attr_line);
112                 l.dump = false;
113                 this.borders[i] = l;
114                 l.parentPolygon = this;
115             }
116         }
117         this.inherits.push(this.vertices, this.borders);
118 
119         // Register polygon at board
120         // This needs to be done BEFORE the points get this polygon added in their descendants list
121         this.id = this.board.setId(this, 'Py');
122 
123         // Add polygon as child to defining points
124         for (i = 0; i < this.vertices.length - 1; i++) {
125             this.board.select(this.vertices[i]).addChild(this);
126         }
127 
128         this.board.renderer.drawPolygon(this);
129         this.board.finalizeAdding(this);
130 
131         this.createGradient();
132         this.elType = 'polygon';
133 
134         // create label
135         this.createLabel();
136 
137         this.methodMap = JXG.deepCopy(this.methodMap, {
138             borders: 'borders',
139             vertices: 'vertices',
140             A: 'Area',
141             Area: 'Area',
142             Perimeter: 'Perimeter',
143             L: 'Perimeter',
144             Length: 'Perimeter',
145             boundingBox: 'boundingBox',
146             bounds: 'bounds',
147             addPoints: 'addPoints',
148             insertPoints: 'insertPoints',
149             removePoints: 'removePoints'
150         });
151     };
152 
153     JXG.Polygon.prototype = new GeometryElement();
154 
155     JXG.extend(JXG.Polygon.prototype, /** @lends JXG.Polygon.prototype */ {
156         /**
157          * Checks whether (x,y) is near the polygon.
158          * @param {Number} x Coordinate in x direction, screen coordinates.
159          * @param {Number} y Coordinate in y direction, screen coordinates.
160          * @returns {Boolean} Returns true, if (x,y) is inside or at the boundary the polygon, otherwise false.
161          */
162         hasPoint: function (x, y) {
163 
164             var i, j, len, c = false;
165 
166             if (Type.evaluate(this.visProp.hasinnerpoints)) {
167                 // All points of the polygon trigger hasPoint: inner and boundary points
168                 len = this.vertices.length;
169                 // See http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
170                 // for a reference of Jordan method
171                 for (i = 0, j = len - 2; i < len - 1; j = i++) {
172                     if (((this.vertices[i].coords.scrCoords[2] > y) !== (this.vertices[j].coords.scrCoords[2] > y)) &&
173                             (x < (this.vertices[j].coords.scrCoords[1] - this.vertices[i].coords.scrCoords[1]) * (y - this.vertices[i].coords.scrCoords[2]) /
174                             (this.vertices[j].coords.scrCoords[2] - this.vertices[i].coords.scrCoords[2]) + this.vertices[i].coords.scrCoords[1])) {
175                         c = !c;
176                     }
177                 }
178                 if (c) {
179                     return true;
180                 }
181             }
182 
183             // Only boundary points trigger hasPoint
184             // We additionally test the boundary also in case hasInnerPoints.
185             // Since even if the above test has failed, the strokewidth may be large and (x, y) may
186             // be inside of hasPoint() of a vertices.
187             len = this.borders.length;
188             for (i = 0; i < len; i++) {
189                 if (this.borders[i].hasPoint(x, y)) {
190                     c = true;
191                     break;
192                 }
193             }
194 
195             return c;
196         },
197 
198         /**
199          * Uses the boards renderer to update the polygon.
200          */
201         updateRenderer: function () {
202             var i, len; // wasReal,
203 
204 
205             if (!this.needsUpdate) {
206                 return this;
207             }
208 
209             if (this.visPropCalc.visible) {
210                 // wasReal = this.isReal;
211 
212                 len = this.vertices.length;
213                 this.isReal = true;
214                 for (i = 0; i < len; ++i) {
215                     if (!this.vertices[i].isReal) {
216                         this.isReal = false;
217                         break;
218                     }
219                 }
220 
221                 if (//wasReal &&
222                     !this.isReal) {
223                     this.updateVisibility(false);
224                 }
225             }
226 
227             if (this.visPropCalc.visible) {
228                 this.board.renderer.updatePolygon(this);
229             }
230 
231             /* Update the label if visible. */
232             if (this.hasLabel && this.visPropCalc.visible && this.label &&
233                 this.label.visPropCalc.visible && this.isReal) {
234 
235                 this.label.update();
236                 this.board.renderer.updateText(this.label);
237             }
238 
239             // Update rendNode display
240             this.setDisplayRendNode();
241             // if (this.visPropCalc.visible !== this.visPropOld.visible) {
242             //     this.board.renderer.display(this, this.visPropCalc.visible);
243             //     this.visPropOld.visible = this.visPropCalc.visible;
244             //
245             //     if (this.hasLabel) {
246             //         this.board.renderer.display(this.label, this.label.visPropCalc.visible);
247             //     }
248             // }
249 
250             this.needsUpdate = false;
251             return this;
252         },
253 
254         /**
255          * return TextAnchor
256          */
257         getTextAnchor: function () {
258             var a, b, x, y, i;
259 
260             if (this.vertices.length === 0) {
261                 return new Coords(Const.COORDS_BY_USER, [1, 0, 0], this.board);
262             }
263 
264             a = this.vertices[0].X();
265             b = this.vertices[0].Y();
266             x = a;
267             y = b;
268             for (i = 0; i < this.vertices.length; i++) {
269                 if (this.vertices[i].X() < a) {
270                     a = this.vertices[i].X();
271                 }
272 
273                 if (this.vertices[i].X() > x) {
274                     x = this.vertices[i].X();
275                 }
276 
277                 if (this.vertices[i].Y() > b) {
278                     b = this.vertices[i].Y();
279                 }
280 
281                 if (this.vertices[i].Y() < y) {
282                     y = this.vertices[i].Y();
283                 }
284             }
285 
286             return new Coords(Const.COORDS_BY_USER, [(a + x) * 0.5, (b + y) * 0.5], this.board);
287         },
288 
289         getLabelAnchor: JXG.shortcut(JXG.Polygon.prototype, 'getTextAnchor'),
290 
291         // documented in geometry element
292         cloneToBackground: function () {
293             var copy = {}, er;
294 
295             copy.id = this.id + 'T' + this.numTraces;
296             this.numTraces++;
297             copy.vertices = this.vertices;
298             copy.visProp = Type.deepCopy(this.visProp, this.visProp.traceattributes, true);
299             copy.visProp.layer = this.board.options.layer.trace;
300             copy.board = this.board;
301             Type.clearVisPropOld(copy);
302 
303             er = this.board.renderer.enhancedRendering;
304             this.board.renderer.enhancedRendering = true;
305             this.board.renderer.drawPolygon(copy);
306             this.board.renderer.enhancedRendering = er;
307             this.traces[copy.id] = copy.rendNode;
308 
309             return this;
310         },
311 
312         /**
313          * Hide the polygon including its border lines. It will still exist but not visible on the board.
314          * @param {Boolean} [borderless=false] If set to true, the polygon is treated as a polygon without
315          * borders, i.e. the borders will not be hidden.
316          */
317         hideElement: function (borderless) {
318             var i;
319 
320             JXG.deprecated('Element.hideElement()', 'Element.setDisplayRendNode()');
321 
322             this.visPropCalc.visible = false;
323             this.board.renderer.display(this, false);
324 
325             if (!borderless) {
326                 for (i = 0; i < this.borders.length; i++) {
327                     this.borders[i].hideElement();
328                 }
329             }
330 
331             if (this.hasLabel && Type.exists(this.label)) {
332                 this.label.hiddenByParent = true;
333                 if (this.label.visPropCalc.visible) {
334                     this.label.hideElement();
335                 }
336             }
337         },
338 
339         /**
340          * Make the element visible.
341          * @param {Boolean} [borderless=false] If set to true, the polygon is treated as a polygon without
342          * borders, i.e. the borders will not be shown.
343          */
344         showElement: function (borderless) {
345             var i;
346 
347             JXG.deprecated('Element.showElement()', 'Element.setDisplayRendNode()');
348 
349             this.visPropCalc.visible = true;
350             this.board.renderer.display(this, true);
351 
352             if (!borderless) {
353                 for (i = 0; i < this.borders.length; i++) {
354                     this.borders[i].showElement().updateRenderer();
355                 }
356             }
357 
358             if (Type.exists(this.label) && this.hasLabel && this.label.hiddenByParent) {
359                 this.label.hiddenByParent = false;
360                 if (!this.label.visPropCalc.visible) {
361                     this.label.showElement().updateRenderer();
362                 }
363             }
364             return this;
365         },
366 
367         /**
368          * Area of (not self-intersecting) polygon
369          * @returns {Number} Area of (not self-intersecting) polygon
370          */
371         Area: function () {
372             return Math.abs(Geometry.signedPolygon(this.vertices, true));
373         },
374 
375         /**
376          * Perimeter of polygon.
377          * @returns {Number} Perimeter of polygon in user units.
378          *
379          * @example
380          * var p = [[0.0, 2.0], [2.0, 1.0], [4.0, 6.0], [1.0, 3.0]];
381          *
382          * var pol = board.create('polygon', p, {hasInnerPoints: true});
383          * var t = board.create('text', [5, 5, function() { return pol.Perimeter(); }]);
384          * </pre><div class="jxgbox" id="b10b734d-89fc-4b9d-b4a7-e3f0c1c6bf77" style="width: 400px; height: 400px;"></div>
385          * <script type="text/javascript">
386          *  (function () {
387          *   var board = JXG.JSXGraph.initBoard('b10b734d-89fc-4b9d-b4a7-e3f0c1c6bf77', {boundingbox: [-1, 9, 9, -1], axis: false, showcopyright: false, shownavigation: false}),
388          *       p = [[0.0, 2.0], [2.0, 1.0], [4.0, 6.0], [1.0, 4.0]],
389          *       cc1 = board.create('polygon', p, {hasInnerPoints: true}),
390          *       t = board.create('text', [5, 5, function() { return cc1.Perimeter(); }]);
391          *  })();
392          * </script><pre>
393          *
394          */
395         Perimeter: function() {
396             var i,
397                 len = this.vertices.length,
398                 val = 0.0;
399 
400             for (i = 1; i < len; ++i) {
401                 val += this.vertices[i].Dist(this.vertices[i - 1]);
402             }
403 
404             return val;
405         },
406 
407         /**
408          * Bounding box of a polygon. The bounding box is an array of four numbers: the first two numbers
409          * determine the upper left corner, the last two number determine the lower right corner of the bounding box.
410          *
411          * The width and height of a polygon can then determined like this:
412          * @example
413          * var box = polygon.boundingBox();
414          * var width = box[2] - box[0];
415          * var height = box[1] - box[3];
416          *
417          * @returns {Array} Array containing four numbers: [minX, maxY, maxX, minY]
418          */
419         boundingBox: function () {
420             var box = [0, 0, 0, 0], i, v,
421                 le = this.vertices.length - 1;
422 
423             if (le === 0) {
424                 return box;
425             }
426             box[0] = this.vertices[0].X();
427             box[2] = box[0];
428             box[1] = this.vertices[0].Y();
429             box[3] = box[1];
430 
431             for (i = 1; i < le; ++i) {
432                 v = this.vertices[i].X();
433                 if (v < box[0]) {
434                     box[0] = v;
435                 } else if (v > box[2]) {
436                     box[2] = v;
437                 }
438 
439                 v = this.vertices[i].Y();
440                 if (v > box[1]) {
441                     box[1] = v;
442                 } else if (v < box[3]) {
443                     box[3] = v;
444                 }
445             }
446 
447             return box;
448         },
449 
450         // already documented in GeometryElement
451         bounds: function () {
452             return this.boundingBox();
453         },
454 
455         /**
456          * This method removes the SVG or VML nodes of the lines and the filled area from the renderer, to remove
457          * the object completely you should use {@link JXG.Board#removeObject}.
458          */
459         remove: function () {
460             var i;
461 
462             for (i = 0; i < this.borders.length; i++) {
463                 this.board.removeObject(this.borders[i]);
464             }
465 
466             GeometryElement.prototype.remove.call(this);
467         },
468 
469         /**
470          * Finds the index to a given point reference.
471          * @param {JXG.Point} p Reference to an element of type {@link JXG.Point}
472          */
473         findPoint: function (p) {
474             var i;
475 
476             if (!Type.isPoint(p)) {
477                 return -1;
478             }
479 
480             for (i = 0; i < this.vertices.length; i++) {
481                 if (this.vertices[i].id === p.id) {
482                     return i;
483                 }
484             }
485 
486             return -1;
487         },
488 
489         /**
490          * Add more points to the polygon. The new points will be inserted at the end.
491          * @param {JXG.Point} p Arbitrary number of points
492          * @returns {JXG.Polygon} Reference to the polygon
493          */
494         addPoints: function (p) {
495             var args = Array.prototype.slice.call(arguments);
496 
497             return this.insertPoints.apply(this, [this.vertices.length - 2].concat(args));
498         },
499 
500         /**
501          * Adds more points to the vertex list of the polygon, starting with index <tt><i</tt>
502          * @param {Number} idx The position where the new vertices are inserted, starting with 0.
503          * @param {JXG.Point} p Arbitrary number of points to insert.
504          * @returns {JXG.Polygon} Reference to the polygon object
505          */
506         insertPoints: function (idx, p) {
507             var i, npoints = [], tmp;
508 
509             if (arguments.length === 0) {
510                 return this;
511             }
512 
513 
514             if (idx < 0 || idx > this.vertices.length - 2) {
515                 return this;
516             }
517 
518             for (i = 1; i < arguments.length; i++) {
519                 if (Type.isPoint(arguments[i])) {
520                     npoints.push(arguments[i]);
521                 }
522             }
523 
524             tmp = this.vertices.slice(0, idx + 1).concat(npoints);
525             this.vertices = tmp.concat(this.vertices.slice(idx + 1));
526 
527             if (this.withLines) {
528                 tmp = this.borders.slice(0, idx);
529                 this.board.removeObject(this.borders[idx]);
530 
531                 for (i = 0; i < npoints.length; i++) {
532                     tmp.push(this.board.create('segment', [this.vertices[idx + i], this.vertices[idx + i + 1]], this.attr_line));
533                 }
534 
535                 tmp.push(this.board.create('segment', [this.vertices[idx + npoints.length], this.vertices[idx + npoints.length + 1]], this.attr_line));
536                 this.borders = tmp.concat(this.borders.slice(idx + 1));
537             }
538 
539             this.board.update();
540 
541             return this;
542         },
543 
544         /**
545          * Removes given set of vertices from the polygon
546          * @param {JXG.Point} p Arbitrary number of vertices as {@link JXG.Point} elements or index numbers
547          * @returns {JXG.Polygon} Reference to the polygon
548          */
549         removePoints: function (p) {
550             var i, j, idx, nvertices = [], nborders = [],
551                 nidx = [], partition = [];
552 
553             // partition:
554             // in order to keep the borders which could be recycled, we have to partition
555             // the set of removed points. I.e. if the points 1, 2, 5, 6, 7, 10 are removed,
556             // the partitions are
557             //       1-2, 5-7, 10-10
558             // this gives us the borders, that can be removed and the borders we have to create.
559 
560 
561             // remove the last vertex which is identical to the first
562             this.vertices = this.vertices.slice(0, this.vertices.length - 1);
563 
564             // collect all valid parameters as indices in nidx
565             for (i = 0; i < arguments.length; i++) {
566                 idx = arguments[i];
567                 if (Type.isPoint(idx)) {
568                     idx = this.findPoint(idx);
569                 }
570 
571                 if (Type.isNumber(idx) && idx > -1 && idx < this.vertices.length && Type.indexOf(nidx, idx) === -1) {
572                     nidx.push(idx);
573                 }
574             }
575 
576             // remove the polygon from each removed point's children
577             for (i = 0; i < nidx.length; i++) {
578                 this.vertices[nidx[i]].removeChild(this);
579             }
580 
581             // sort the elements to be eliminated
582             nidx = nidx.sort();
583             nvertices = this.vertices.slice();
584             nborders = this.borders.slice();
585 
586             // initialize the partition
587             if (this.withLines) {
588                 partition.push([nidx[nidx.length - 1]]);
589             }
590 
591             // run through all existing vertices and copy all remaining ones to nvertices
592             // compute the partition
593             for (i = nidx.length - 1; i > -1; i--) {
594                 nvertices[nidx[i]] = -1;
595 
596                 if (this.withLines && (nidx[i] - 1 > nidx[i - 1])) {
597                     partition[partition.length - 1][1] = nidx[i];
598                     partition.push([nidx[i - 1]]);
599                 }
600             }
601 
602             // finalize the partition computation
603             if (this.withLines) {
604                 partition[partition.length - 1][1] = nidx[0];
605             }
606 
607             // update vertices
608             this.vertices = [];
609             for (i = 0; i < nvertices.length; i++) {
610                 if (Type.isPoint(nvertices[i])) {
611                     this.vertices.push(nvertices[i]);
612                 }
613             }
614             if (this.vertices[this.vertices.length - 1].id !== this.vertices[0].id) {
615                 this.vertices.push(this.vertices[0]);
616             }
617 
618             // delete obsolete and create missing borders
619             if (this.withLines) {
620                 for (i = 0; i < partition.length; i++) {
621                     for (j = partition[i][1] - 1; j < partition[i][0] + 1; j++) {
622                         // special cases
623                         if (j < 0) {
624                             // first vertex is removed, so the last border has to be removed, too
625                             j = 0;
626                             this.board.removeObject(this.borders[nborders.length - 1]);
627                             nborders[nborders.length - 1] = -1;
628                         } else if (j > nborders.length - 1) {
629                             j = nborders.length - 1;
630                         }
631 
632                         this.board.removeObject(this.borders[j]);
633                         nborders[j] = -1;
634                     }
635 
636                     // only create the new segment if it's not the closing border. the closing border is getting a special treatment at the end
637                     // the if clause is newer than the min/max calls inside createSegment; i'm sure this makes the min/max calls obsolete, but
638                     // just to be sure...
639                     if (partition[i][1] !== 0 && partition[i][0] !== nvertices.length - 1) {
640                         nborders[partition[i][0] - 1] = this.board.create('segment', [nvertices[Math.max(partition[i][1] - 1, 0)], nvertices[Math.min(partition[i][0] + 1, this.vertices.length - 1)]], this.attr_line);
641                     }
642                 }
643 
644                 this.borders = [];
645                 for (i = 0; i < nborders.length; i++) {
646                     if (nborders[i] !== -1) {
647                         this.borders.push(nborders[i]);
648                     }
649                 }
650 
651                 // if the first and/or the last vertex is removed, the closing border is created at the end.
652                 if (partition[0][1] === this.vertices.length - 1 || partition[partition.length - 1][1] === 0) {
653                     this.borders.push(this.board.create('segment', [this.vertices[0], this.vertices[this.vertices.length - 2]], this.attr_line));
654                 }
655             }
656 
657             this.board.update();
658 
659             return this;
660         },
661 
662         // documented in element.js
663         getParents: function () {
664             this.setParents(this.vertices);
665             return this.parents;
666         },
667 
668         getAttributes: function () {
669             var attr = GeometryElement.prototype.getAttributes.call(this), i;
670 
671             if (this.withLines) {
672                 attr.lines = attr.lines || {};
673                 attr.lines.ids = [];
674                 attr.lines.colors = [];
675 
676                 for (i = 0; i < this.borders.length; i++) {
677                     attr.lines.ids.push(this.borders[i].id);
678                     attr.lines.colors.push(this.borders[i].visProp.strokecolor);
679                 }
680             }
681 
682             return attr;
683         },
684 
685         snapToGrid: function () {
686             var i, force;
687 
688             if (Type.evaluate(this.visProp.snaptogrid)) {
689                 force = true;
690             } else {
691                 force = false;
692             }
693 
694             for (i = 0; i < this.vertices.length; i++) {
695                 this.vertices[i].handleSnapToGrid(force, true);
696             }
697 
698         },
699 
700         /**
701          * Moves the polygon by the difference of two coordinates.
702          * @param {Number} method The type of coordinates used here. Possible values are {@link JXG.COORDS_BY_USER} and {@link JXG.COORDS_BY_SCREEN}.
703          * @param {Array} coords coordinates in screen/user units
704          * @param {Array} oldcoords previous coordinates in screen/user units
705          * @returns {JXG.Polygon} this element
706          */
707         setPositionDirectly: function (method, coords, oldcoords) {
708             var dc, t, i, len,
709                 c = new Coords(method, coords, this.board),
710                 oldc = new Coords(method, oldcoords, this.board);
711 
712             len = this.vertices.length - 1;
713             for (i = 0; i < len; i++) {
714                 if (!this.vertices[i].draggable()) {
715                     return this;
716                 }
717             }
718 
719             dc = Statistics.subtract(c.usrCoords, oldc.usrCoords);
720             t = this.board.create('transform', dc.slice(1), {type: 'translate'});
721             t.applyOnce(this.vertices.slice(0, -1));
722 
723             return this;
724         },
725 
726         /**
727         * Algorithm by Sutherland and Hodgman to compute the intersection of two convex polygons.
728         * The polygon itself is the clipping polygon, it expects as parameter a polygon to be clipped.
729         * See <a href="https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm">wikipedia entry</a>.
730         * Called by {@link JXG.Polygon#intersect}.
731         *
732         * @private
733         *
734         * @param {JXG.Polygon} polygon Polygon which will be clipped.
735         *
736         * @returns {Array} of (normalized homogeneous user) coordinates (i.e. [z, x, y], where z==1 in most cases,
737         *   representing the vertices of the intersection polygon.
738         *
739         */
740         sutherlandHodgman: function(polygon) {
741             // First the two polygons are sorted counter clockwise
742             var clip = JXG.Math.Geometry.sortVertices(this.vertices),   // "this" is the clipping polygon
743                 subject = JXG.Math.Geometry.sortVertices(polygon.vertices), // "polygon" is the subject polygon
744 
745                 lenClip = clip.length - 1,
746                 lenSubject = subject.length - 1,
747                 lenIn,
748 
749                 outputList = [],
750                 inputList, i, j, S, E, cross,
751 
752 
753                 // Determines if the point c3 is right of the line through c1 and c2.
754                 // Since the polygons are sorted counter clockwise, "right of" and therefore >= is needed here
755                 isInside = function(c1, c2, c3) {
756                     return ((c2[1] - c1[1]) * (c3[2] - c1[2]) - (c2[2] - c1[2]) * (c3[1] - c1[1])) >= 0;
757                 };
758 
759             for (i = 0; i < lenSubject; i++) {
760                 outputList.push(subject[i]);
761             }
762 
763             for (i = 0; i < lenClip; i++) {
764                 inputList = outputList.slice(0);
765                 lenIn = inputList.length;
766                 outputList = [];
767 
768                 S = inputList[lenIn - 1];
769 
770                 for (j = 0; j < lenIn; j++) {
771                     E = inputList[j];
772                     if (isInside(clip[i], clip[i + 1], E)) {
773                         if (!isInside(clip[i], clip[i + 1], S)) {
774                             cross = JXG.Math.Geometry.meetSegmentSegment(S, E, clip[i], clip[i + 1]);
775                             cross[0][1] /= cross[0][0];
776                             cross[0][2] /= cross[0][0];
777                             cross[0][0] = 1;
778                             outputList.push(cross[0]);
779                         }
780                         outputList.push(E);
781                     } else if (isInside(clip[i], clip[i + 1], S)) {
782                         cross = JXG.Math.Geometry.meetSegmentSegment(S, E, clip[i], clip[i + 1]);
783                         cross[0][1] /= cross[0][0];
784                         cross[0][2] /= cross[0][0];
785                         cross[0][0] = 1;
786                         outputList.push(cross[0]);
787                     }
788                     S = E;
789                 }
790             }
791 
792             return outputList;
793         },
794 
795         /**
796          * Generic method for the intersection of this polygon with another polygon.
797          * The parent object is the clipping polygon, it expects as parameter a polygon to be clipped.
798          * Both polygons have to be convex.
799          * Calls {@link JXG.Polygon#sutherlandHodgman}.
800          *
801          * @param {JXG.Polygon} polygon Polygon which will be clipped.
802          *
803          * @returns {Array} of (normalized homogeneous user) coordinates (i.e. [z, x, y], where z==1 in most cases,
804          *   representing the vertices of the intersection polygon.
805          *
806          * @example
807          *  // Static intersection of two polygons pol1 and pol2
808          *  var pol1 = board.create('polygon', [[-2, 3], [-4, -3], [2, 0], [4, 4]], {
809          *                name:'pol1', withLabel: true,
810          *                fillColor: 'yellow'
811          *             });
812          *  var pol2 = board.create('polygon', [[-2, -3], [-4, 1], [0, 4], [5, 1]], {
813          *                name:'pol2', withLabel: true
814          *             });
815          *
816          *  // Static version:
817          *  // the intersection polygon does not adapt to changes of pol1 or pol2.
818          *  var pol3 = board.create('polygon', pol1.intersect(pol2), {fillColor: 'blue'});
819          * </pre><div class="jxgbox" id="d1fe5ea9-309f-494a-af07-ee3d033acb7c" style="width: 300px; height: 300px;"></div>
820          * <script type="text/javascript">
821          *   (function() {
822          *       var board = JXG.JSXGraph.initBoard('d1fe5ea9-309f-494a-af07-ee3d033acb7c', {boundingbox: [-8, 8, 8,-8], axis: true, showcopyright: false, shownavigation: false});
823          *       // Intersect two polygons pol1 and pol2
824          *       var pol1 = board.create('polygon', [[-2, 3], [-4, -3], [2, 0], [4, 4]], {
825          *                name:'pol1', withLabel: true,
826          *                fillColor: 'yellow'
827          *             });
828          *       var pol2 = board.create('polygon', [[-2, -3], [-4, 1], [0, 4], [5, 1]], {
829          *                name:'pol2', withLabel: true
830          *             });
831          *
832          *       // Static version: the intersection polygon does not adapt to changes of pol1 or pol2.
833          *       var pol3 = board.create('polygon', pol1.intersect(pol2), {fillColor: 'blue'});
834          *   })();
835          * </script><pre>
836          *
837          * @example
838          *  // Dynamic intersection of two polygons pol1 and pol2
839          *  var pol1 = board.create('polygon', [[-2, 3], [-4, -3], [2, 0], [4, 4]], {
840          *                name:'pol1', withLabel: true,
841          *                fillColor: 'yellow'
842          *             });
843          *  var pol2 = board.create('polygon', [[-2, -3], [-4, 1], [0, 4], [5, 1]], {
844          *                name:'pol2', withLabel: true
845          *             });
846          *
847          *  // Dynamic version:
848          *  // the intersection polygon does  adapt to changes of pol1 or pol2.
849          *  // For this a curve element is used.
850          *  var curve = board.create('curve', [[],[]], {fillColor: 'blue', fillOpacity: 0.4});
851          *  curve.updateDataArray = function() {
852          *      var mat = JXG.Math.transpose(pol1.intersect(pol2));
853          *
854          *      if (mat.length == 3) {
855          *          this.dataX = mat[1];
856          *          this.dataY = mat[2];
857          *      } else {
858          *          this.dataX = [];
859          *          this.dataY = [];
860          *      }
861          *  };
862          *  board.update();
863          * </pre><div class="jxgbox" id="f870d516-ca1a-4140-8fe3-5d64fb42e5f2" style="width: 300px; height: 300px;"></div>
864          * <script type="text/javascript">
865          *   (function() {
866          *       var board = JXG.JSXGraph.initBoard('f870d516-ca1a-4140-8fe3-5d64fb42e5f2', {boundingbox: [-8, 8, 8,-8], axis: true, showcopyright: false, shownavigation: false});
867          *       // Intersect two polygons pol1 and pol2
868          *       var pol1 = board.create('polygon', [[-2, 3], [-4, -3], [2, 0], [4, 4]], {
869          *                name:'pol1', withLabel: true,
870          *                fillColor: 'yellow'
871          *             });
872          *       var pol2 = board.create('polygon', [[-2, -3], [-4, 1], [0, 4], [5, 1]], {
873          *                name:'pol2', withLabel: true
874          *             });
875          *
876          *  // Dynamic version:
877          *  // the intersection polygon does  adapt to changes of pol1 or pol2.
878          *  // For this a curve element is used.
879          *    var curve = board.create('curve', [[],[]], {fillColor: 'blue', fillOpacity: 0.4});
880          *    curve.updateDataArray = function() {
881          *        var mat = JXG.Math.transpose(pol1.intersect(pol2));
882          *
883          *        if (mat.length == 3) {
884          *            this.dataX = mat[1];
885          *            this.dataY = mat[2];
886          *        } else {
887          *            this.dataX = [];
888          *            this.dataY = [];
889          *        }
890          *    };
891          *    board.update();
892          *   })();
893          * </script><pre>
894          *
895          */
896         intersect: function(polygon) {
897             return this.sutherlandHodgman(polygon);
898         }
899 
900 
901     });
902 
903 
904     /**
905      * @class A polygon is an area enclosed by a set of border lines which are determined by
906      * <ul>
907      *    <li> a list of points or
908      *    <li> a list of coordinate arrays or
909      *    <li> a function returning a list of coordinate arrays.
910      * </ul>
911      * Each two consecutive points of the list define a line.
912      * @pseudo
913      * @constructor
914      * @name Polygon
915      * @type Polygon
916      * @augments JXG.Polygon
917      * @throws {Exception} If the element cannot be constructed with the given parent objects an exception is thrown.
918      * @param {Array} vertices The polygon's vertices. If the first and the last vertex don't match the first one will be
919      * added to the array by the creator.
920      *
921      * Additionally, a polygon can be created by providing a polygon and a transformation (or an array of transformations).
922      * The result is a polygon which is the transformation of the supplied polygon.
923      *
924      * @example
925      * var p1 = board.create('point', [0.0, 2.0]);
926      * var p2 = board.create('point', [2.0, 1.0]);
927      * var p3 = board.create('point', [4.0, 6.0]);
928      * var p4 = board.create('point', [1.0, 4.0]);
929      *
930      * var pol = board.create('polygon', [p1, p2, p3, p4]);
931      * </pre><div class="jxgbox" id="682069e9-9e2c-4f63-9b73-e26f8a2b2bb1" style="width: 400px; height: 400px;"></div>
932      * <script type="text/javascript">
933      *  (function () {
934      *   var board = JXG.JSXGraph.initBoard('682069e9-9e2c-4f63-9b73-e26f8a2b2bb1', {boundingbox: [-1, 9, 9, -1], axis: false, showcopyright: false, shownavigation: false}),
935      *       p1 = board.create('point', [0.0, 2.0]),
936      *       p2 = board.create('point', [2.0, 1.0]),
937      *       p3 = board.create('point', [4.0, 6.0]),
938      *       p4 = board.create('point', [1.0, 4.0]),
939      *       cc1 = board.create('polygon', [p1, p2, p3, p4]);
940      *  })();
941      * </script><pre>
942      *
943      * @example
944      * var p = [[0.0, 2.0], [2.0, 1.0], [4.0, 6.0], [1.0, 3.0]];
945      *
946      * var pol = board.create('polygon', p, {hasInnerPoints: true});
947      * </pre><div class="jxgbox" id="9f9a5946-112a-4768-99ca-f30792bcdefb" style="width: 400px; height: 400px;"></div>
948      * <script type="text/javascript">
949      *  (function () {
950      *   var board = JXG.JSXGraph.initBoard('9f9a5946-112a-4768-99ca-f30792bcdefb', {boundingbox: [-1, 9, 9, -1], axis: false, showcopyright: false, shownavigation: false}),
951      *       p = [[0.0, 2.0], [2.0, 1.0], [4.0, 6.0], [1.0, 4.0]],
952      *       cc1 = board.create('polygon', p, {hasInnerPoints: true});
953      *  })();
954      * </script><pre>
955      *
956      * @example
957      *   var f1 = function() { return [0.0, 2.0]; },
958      *       f2 = function() { return [2.0, 1.0]; },
959      *       f3 = function() { return [4.0, 6.0]; },
960      *       f4 = function() { return [1.0, 4.0]; },
961      *       cc1 = board.create('polygon', [f1, f2, f3, f4]);
962      *
963      * </pre><div class="jxgbox" id="ceb09915-b783-44db-adff-7877ae3534c8" style="width: 400px; height: 400px;"></div>
964      * <script type="text/javascript">
965      *  (function () {
966      *   var board = JXG.JSXGraph.initBoard('ceb09915-b783-44db-adff-7877ae3534c8', {boundingbox: [-1, 9, 9, -1], axis: false, showcopyright: false, shownavigation: false}),
967      *       f1 = function() { return [0.0, 2.0]; },
968      *       f2 = function() { return [2.0, 1.0]; },
969      *       f3 = function() { return [4.0, 6.0]; },
970      *       f4 = function() { return [1.0, 4.0]; },
971      *       cc1 = board.create('polygon', [f1, f2, f3, f4]);
972      *  })();
973      * </script><pre>
974      */
975     JXG.createPolygon = function (board, parents, attributes) {
976         var el, i, le, obj,
977             points = [],
978             attr, p;
979 
980         obj = board.select(parents[0]);
981         if (Type.isObject(obj) && obj.type === Const.OBJECT_TYPE_POLYGON &&
982             Type.isTransformationOrArray(parents[1])) {
983 
984             le = obj.vertices.length - 1;
985             attr = Type.copyAttributes(attributes, board.options, 'polygon', 'vertices');
986             for (i = 0; i < le; i++) {
987                 points.push(board.create('point', [obj.vertices[i], parents[1]], attr));
988             }
989 
990         } else {
991             points = Type.providePoints(board, parents, attributes, 'polygon', ['vertices']);
992             if (points === false) {
993                 throw new Error("JSXGraph: Can't create polygon with parent types other than 'point' and 'coordinate arrays' or a function returning an array of coordinates. Alternatively, a polygon and a transformation can be supplied");
994             }
995         }
996 
997         attr = Type.copyAttributes(attributes, board.options, 'polygon');
998         el = new JXG.Polygon(board, points, attr);
999         el.isDraggable = true;
1000 
1001         return el;
1002     };
1003 
1004     /**
1005      * @class Constructs a regular polygon. It needs two points which define the base line and the number of vertices.
1006      * @pseudo
1007      * @description Constructs a regular polygon. It needs two points which define the base line and the number of vertices, or a set of points.
1008      * @constructor
1009      * @name RegularPolygon
1010      * @type Polygon
1011      * @augments Polygon
1012      * @throws {Exception} If the element cannot be constructed with the given parent objects an exception is thrown.
1013      * @param {JXG.Point_JXG.Point_Number} p1,p2,n The constructed regular polygon has n vertices and the base line defined by p1 and p2.
1014      * @example
1015      * var p1 = board.create('point', [0.0, 2.0]);
1016      * var p2 = board.create('point', [2.0, 1.0]);
1017      *
1018      * var pol = board.create('regularpolygon', [p1, p2, 5]);
1019      * </pre><div class="jxgbox" id="682069e9-9e2c-4f63-9b73-e26f8a2b2bb1" style="width: 400px; height: 400px;"></div>
1020      * <script type="text/javascript">
1021      *  (function () {
1022      *   var board = JXG.JSXGraph.initBoard('682069e9-9e2c-4f63-9b73-e26f8a2b2bb1', {boundingbox: [-1, 9, 9, -1], axis: false, showcopyright: false, shownavigation: false}),
1023      *       p1 = board.create('point', [0.0, 2.0]),
1024      *       p2 = board.create('point', [2.0, 1.0]),
1025      *       cc1 = board.create('regularpolygon', [p1, p2, 5]);
1026      *  })();
1027      * </script><pre>
1028      * @example
1029      * var p1 = board.create('point', [0.0, 2.0]);
1030      * var p2 = board.create('point', [4.0,4.0]);
1031      * var p3 = board.create('point', [2.0,0.0]);
1032      *
1033      * var pol = board.create('regularpolygon', [p1, p2, p3]);
1034      * </pre><div class="jxgbox" id="096a78b3-bd50-4bac-b958-3be5e7df17ed" style="width: 400px; height: 400px;"></div>
1035      * <script type="text/javascript">
1036      * (function () {
1037      *   var board = JXG.JSXGraph.initBoard('096a78b3-bd50-4bac-b958-3be5e7df17ed', {boundingbox: [-1, 9, 9, -1], axis: false, showcopyright: false, shownavigation: false}),
1038      *       p1 = board.create('point', [0.0, 2.0]),
1039      *       p2 = board.create('point', [4.0, 4.0]),
1040      *       p3 = board.create('point', [2.0,0.0]),
1041      *       cc1 = board.create('regularpolygon', [p1, p2, p3]);
1042      * })();
1043      * </script><pre>
1044      *
1045      * @example
1046      *         // Line of reflection
1047      *         var li = board.create('line', [1,1,1], {strokeColor: '#aaaaaa'});
1048      *         var reflect = board.create('transform', [li], {type: 'reflect'});
1049      *         var pol1 = board.create('polygon', [[-3,-2], [-1,-4], [-2,-0.5]]);
1050      *         var pol2 = board.create('polygon', [pol1, reflect]);
1051      *
1052      * </pre><div id="58fc3078-d8d1-11e7-93b3-901b0e1b8723" class="jxgbox" style="width: 300px; height: 300px;"></div>
1053      * <script type="text/javascript">
1054      *     (function() {
1055      *         var board = JXG.JSXGraph.initBoard('58fc3078-d8d1-11e7-93b3-901b0e1b8723',
1056      *             {boundingbox: [-8, 8, 8,-8], axis: true, showcopyright: false, shownavigation: false});
1057      *             var li = board.create('line', [1,1,1], {strokeColor: '#aaaaaa'});
1058      *             var reflect = board.create('transform', [li], {type: 'reflect'});
1059      *             var pol1 = board.create('polygon', [[-3,-2], [-1,-4], [-2,-0.5]]);
1060      *             var pol2 = board.create('polygon', [pol1, reflect]);
1061      *
1062      *     })();
1063      *
1064      * </script><pre>
1065      *
1066      */
1067     JXG.createRegularPolygon = function (board, parents, attributes) {
1068         var el, i, n,
1069             p = [], rot, c, len, pointsExist, attr;
1070 
1071         len = parents.length;
1072         n = parents[len - 1];
1073 
1074         if (Type.isNumber(n) && (parents.length !== 3 || n < 3)) {
1075             throw new Error("JSXGraph: A regular polygon needs two point types and a number > 2 as input.");
1076         }
1077 
1078         if (Type.isNumber(board.select(n))) { // Regular polygon given by 2 points and a number
1079             len--;
1080             pointsExist = false;
1081         } else {                              // Regular polygon given by n points
1082             n = len;
1083             pointsExist = true;
1084         }
1085 
1086         p = Type.providePoints(board, parents.slice(0, len), attributes, 'regularpolygon', ['vertices']);
1087         if (p === false) {
1088             throw new Error("JSXGraph: Can't create regular polygon with parent types other than 'point' and 'coordinate arrays' or a function returning an array of coordinates");
1089         }
1090 
1091         attr = Type.copyAttributes(attributes, board.options, 'regularpolygon', 'vertices');
1092         for (i = 2; i < n; i++) {
1093             rot = board.create('transform', [Math.PI * (2 - (n - 2) / n), p[i - 1]], {type: 'rotate'});
1094             if (pointsExist) {
1095                 p[i].addTransform(p[i - 2], rot);
1096                 p[i].fullUpdate();
1097             } else {
1098                 if (Type.isArray(attr.ids) && attr.ids.length >= n - 2) {
1099                     attr.id = attr.ids[i - 2];
1100                 }
1101                 p[i] = board.create('point', [p[i - 2], rot], attr);
1102                 p[i].type = Const.OBJECT_TYPE_CAS;
1103 
1104                 // The next two lines of code are needed to make regular polgonmes draggable
1105                 // The new helper points are set to be draggable.
1106                 p[i].isDraggable = true;
1107                 p[i].visProp.fixed = false;
1108             }
1109         }
1110 
1111         attr = Type.copyAttributes(attributes, board.options, 'regularpolygon');
1112         el = board.create('polygon', p, attr);
1113         el.elType = 'regularpolygon';
1114 
1115         return el;
1116     };
1117 
1118     JXG.registerElement('polygon', JXG.createPolygon);
1119     JXG.registerElement('regularpolygon', JXG.createRegularPolygon);
1120 
1121     return {
1122         Polygon: JXG.Polygon,
1123         createPolygon: JXG.createPolygon,
1124         createRegularPolygon: JXG.createRegularPolygon
1125     };
1126 });
1127