classes/polygon.js

  1. /**
  2.  * Created by Alex Bol on 3/15/2017.
  3.  */
  5. "use strict";
  7. module.exports = function(Flatten) {
  8.     let {Edge, Face, PlanarSet, Box} = Flatten;
  9.     let {ray_shoot} = Flatten;
  10.     /**
  11.      * Class representing a polygon.<br/>
  12.      * Polygon in FlattenJS is a multipolygon comprised from a set of [faces]{@link Flatten.Face}. <br/>
  13.      * Face, in turn, is a closed loop of [edges]{@link Flatten.Edge}, where edge may be segment or circular arc<br/>
  14.      * @type {Polygon}
  15.      */
  16.     Flatten.Polygon = class Polygon {
  17.         /**
  18.          * Constructor creates new instance of polygon.<br/>
  19.          * New polygon is empty. Add face to the polygon using method <br/>
  20.          * <code>
  21.          *     polygon.addFace(Points[]|Segments[]|Arcs[])
  22.          * </code>
  23.          */
  24.         constructor() {
  25.             /**
  26.              * Container of faces (closed loops), may be empty
  27.              * @type {PlanarSet}
  28.              */
  29.             this.faces = new PlanarSet();
  30.             /**
  31.              * Container of edges
  32.              * @type {PlanarSet}
  33.              */
  34.             this.edges = new PlanarSet();
  35.         }
  37.         /**
  38.          * (Getter) Returns bounding box of the polygon
  39.          * @returns {Box}
  40.          */
  41.         get box() {
  42.             return [...this.faces].reduce( (acc, face) => acc.merge(face.box), new Box() );
  43.         }
  45.         /**
  46.          * (Getter) Returns array of vertices
  47.          * @returns {Array}
  48.          */
  49.         get vertices() {
  50.             return [...this.edges].map( edge => edge.start);
  51.         }
  53.         /**
  54.          * Return true is polygon has no edges
  55.          * @returns {boolean}
  56.          */
  57.         isEmpty() {
  58.             return this.edges.size === 0;
  59.         }
  61.         /**
  62.          * Add new face to polygon. Returns added face
  63.          * @param {Points[]|Segments[]|Arcs[]|Circle|Box} args -  new face may be create with one of the following ways: <br/>
  64.          * 1) array of points that describe closed path (edges are segments) <br/>
  65.          * 2) array of shapes (segments and arcs) which describe closed path <br/>
  66.          * 3) circle - will be added as counterclockwise arc <br/>
  67.          * 4) box - will be added as counterclockwise rectangle <br/>
  68.          * You can chain method face.reverse() is you need to change direction of the creates face
  69.          * @returns {Face}
  70.          */
  71.         addFace(...args) {
  72.             let face = new Face(this, ...args);
  73.             this.faces.add(face);
  74.             return face;
  75.         }
  77.         /**
  78.          * Delete existing face from polygon
  79.          * @param {Face} face Face to be deleted
  80.          * @returns {boolean}
  81.          */
  82.         deleteFace(face) {
  83.             for (let edge of face) {
  84.                 let deleted = this.edges.delete(edge);
  85.             }
  86.             let deleted = this.faces.delete(face);
  87.             return deleted;
  88.         }
  90.         /**
  91.          * Delete chain of edges from the face.
  92.          * @param {Face} face Face to remove chain
  93.          * @param {Edge} edgeFrom Start of the chain of edges to be removed
  94.          * @param {Edge} edgeTo End of the chain of edges to be removed
  95.          */
  96.         removeChain(face, edgeFrom, edgeTo) {
  97.             // Special case: all edges removed
  98.             if (edgeTo.next === edgeFrom) {
  99.                 this.deleteFace(face);
  100.                 return;
  101.             }
  102.             for (let edge = edgeFrom; edge !== edgeTo.next; edge = edge.next ) {
  103.                 face.remove(this.edges, edge);
  104.                 // this.edges.delete(edge);      // delete from PlanarSet of edges and update index
  105.                 if (face.isEmpty()) {
  106.                     this.deleteFace(face);    // delete from PlanarSet of faces and update index
  107.                     break;
  108.                 }
  109.             }
  110.         }
  112.         /**
  113.          * Add point as a new vertex and split edge. Point supposed to belong to an edge.
  114.          * When edge is split, new edge created from the start of the edge to the new vertex
  115.          * and inserted before current edge.
  116.          * Current edge is trimmed and updated. Method returns new edge added.
  117.          * @param {Edge} edge Edge to be split with new vertex and then trimmed from start
  118.          * @param {Point} pt Point to be added as a new vertex
  119.          * @returns {Edge}
  120.          */
  121.         addVertex(pt, edge) {
  122.             let shapes = edge.shape.split(pt);
  123.             if (shapes.length < 2) return;
  124.             let newEdge = new Flatten.Edge(shapes[0]);
  125.             let edgeBefore = edge.prev;
  127.             /* Insert first split edge into linked list after edgeBefore */
  128.             edge.face.insert(this.edges, newEdge, edgeBefore);
  130.             // Remove old edge from edges container and 2d index
  131.             this.edges.delete(edge);
  133.             // Update edge shape with second split edge keeping links
  134.             edge.shape = shapes[1];
  136.             // Add updated edge to the edges container and 2d index
  137.             this.edges.add(edge);
  139.             return newEdge;
  140.         }
  142.         reverse() {
  143.             for (let face of this.faces) {
  144.                 face.reverse();
  145.             }
  146.             return this;
  147.         }
  149.         /**
  150.          * Create new copied instance of the polygon
  151.          * @returns {Polygon}
  152.          */
  153.         clone() {
  154.             let polygon = new Polygon();
  155.             for (let face of this.faces) {
  156.                 let shapes = [];
  157.                 for (let edge of face) {
  158.                     shapes.push(edge.shape.clone());
  159.                 }
  160.                 polygon.addFace(shapes);
  161.             }
  162.             return polygon;
  163.         }
  165.         /**
  166.          * Returns area of the polygon. Area of an island will be added, area of a hole will be subtracted
  167.          * @returns {number}
  168.          */
  169.         area() {
  170.             let signedArea = [...this.faces].reduce((acc,face) => acc + face.signedArea(), 0);
  171.             return Math.abs(signedArea);
  172.         }
  174.         /**
  175.          * Returns true if polygon contains point, including polygon boundary, false otherwise
  176.          * Point in polygon test based on ray shooting algorithm
  177.          * @param {Point} point - test point
  178.          * @returns {boolean}
  179.          */
  180.         contains(point) {
  181.             let rel = ray_shoot(this, point);
  182.             return (rel == Flatten.INSIDE || rel == Flatten.BOUNDARY) ? true : false;
  183.         }
  185.         /**
  186.          * Return distance and shortest segment between polygon and other shape as array [distance, shortest_segment]
  187.          * @param {Shape} shape Shape of one of the types Point, Circle, Line, Segment, Arc or Polygon
  188.          * @returns {Number | Segment}
  189.          */
  190.         distanceTo(shape) {
  191.             let {Distance} = Flatten;
  193.             if (shape instanceof Flatten.Point) {
  194.                 let [dist, shortest_segment] = Distance.point2polygon(shape, this);
  195.                 shortest_segment = shortest_segment.reverse();
  196.                 return [dist, shortest_segment];
  197.             }
  199.             if (shape instanceof Flatten.Circle ||
  200.             shape instanceof Flatten.Line ||
  201.             shape instanceof Flatten.Segment ||
  202.             shape instanceof Flatten.Arc) {
  203.                 let [dist, shortest_segment] = Distance.shape2polygon(shape, this);
  204.                 shortest_segment = shortest_segment.reverse();
  205.                 return [dist, shortest_segment];
  206.             }
  208.             /* this method is bit faster */
  209.             if (shape instanceof  Flatten.Polygon) {
  210.                 let min_dist_and_segment = [Number.POSITIVE_INFINITY, new Flatten.Segment()];
  211.                 let dist, shortest_segment;
  213.                 for (let edge of this.edges) {
  214.                     // let [dist, shortest_segment] = Distance.shape2polygon(edge.shape, shape);
  215.                     let min_stop = min_dist_and_segment[0];
  216.                     [dist, shortest_segment] = Distance.shape2planarSet(edge.shape, shape.edges, min_stop);
  217.                     if (Flatten.Utils.LT(dist, min_stop)) {
  218.                         min_dist_and_segment = [dist, shortest_segment];
  219.                     }
  220.                 }
  221.                 return min_dist_and_segment;
  222.             }
  223.         }
  225.         /**
  226.          * Return array of intersection points between polygon and other shape
  227.          * @param shape Shape of the one of supported types <br/>
  228.          * @returns {Point[]}
  229.          */
  230.         intersect(shape) {
  231.             if (shape instanceof Flatten.Point) {
  232.                 return this.contains(shape) ? [shape] : [];
  233.             }
  235.             if (shape instanceof Flatten.Line) {
  236.                 return Polygon.intersectLine2Polygon(shape, this);
  237.             }
  239.             if (shape instanceof Flatten.Circle ||
  240.                 shape instanceof Flatten.Segment ||
  241.                 shape instanceof Flatten.Arc) {
  242.                 return Polygon.intersectShape2Polygon(shape, this);
  243.             }
  245.             if (shape instanceof Flatten.Polygon) {
  246.                 return Polygon.intersectPolygon2Polygon(shape, this);
  247.             }
  248.         }
  250.         /**
  251.          * Return true if polygon is valid for boolean operations
  252.          * Polygon is valid if <br/>
  253.          * 1. All faces are simple polygons (there are no self-intersected polygons) <br/>
  254.          * 2. All faces are orientable and there is no island inside island or hole inside hole - TODO <br/>
  255.          * 3. There is no intersections between faces (excluding touching) - TODO <br/>
  256.          * @returns {boolean}
  257.          */
  258.         isValid() {
  259.             let valid = true;
  260.             // 1. Polygon is invalid if at least one face is not simple
  261.             for (let face of this.faces) {
  262.                 if (!face.isSimple(this.edges)) {
  263.                     valid = false;
  264.                     break;
  265.                 }
  266.             }
  267.             // 2. TODO: check if no island inside island and no hole inside hole
  268.             // 3. TODO: check the there is no intersection between faces
  269.             return valid;
  270.         }
  272.         /**
  273.          * Returns new polygon translated by vector vec
  274.          * @param {Vector} vec
  275.          * @returns {Polygon}
  276.          */
  277.         translate(vec) {
  278.             let newPolygon = new Polygon();
  279.             for (let face of this.faces) {
  280.                 let shapes = [];
  281.                 for (let edge of face) {
  282.                     shapes.push(edge.shape.translate(vec));
  283.                 }
  284.                 newPolygon.addFace(shapes);
  285.             }
  286.             return newPolygon;
  287.         }
  289.         /**
  290.          * Return new polygon rotated by given angle around given point
  291.          * If point omitted, rotate around origin (0,0)
  292.          * Positive value of angle defines rotation counter clockwise, negative - clockwise
  293.          * @param {number} angle - rotation angle in radians
  294.          * @param {Point} center - rotation center, default is (0,0)
  295.          * @returns {Polygon} - new rotated polygon
  296.          */
  297.         rotate(angle=0, center=new Flatten.Point()) {
  298.             let newPolygon = new Polygon();
  299.             for (let face of this.faces) {
  300.                 let shapes = [];
  301.                 for (let edge of face) {
  302.                     shapes.push(edge.shape.rotate(angle, center));
  303.                 }
  304.                 newPolygon.addFace(shapes);
  305.             }
  306.             return newPolygon;
  307.         }
  309.         /**
  310.          * Return new polygon transformed using affine transformation matrix
  311.          * @param {Matrix} matrix - affine transformation matrix
  312.          * @returns {Polygon} - new polygon
  313.          */
  314.         transform(matrix = new Flatten.Matrix()) {
  315.             let newPolygon = new Polygon();
  316.             for (let face of this.faces) {
  317.                 let shapes = [];
  318.                 for (let edge of face) {
  319.                     shapes.push(edge.shape.transform(matrix));
  320.                 }
  321.                 newPolygon.addFace(shapes);
  322.             }
  323.             return newPolygon;
  324.         }
  326.         static intersectShape2Polygon(shape, polygon) {
  327.             let ip = [];
  329.             if ( polygon.isEmpty() || shape.box.not_intersect(polygon.box) ) {
  330.                 return ip;
  331.             }
  333.             let resp_edges = polygon.edges.search(shape.box);
  335.             for (let edge of resp_edges) {
  336.                 for (let pt of shape.intersect(edge.shape)) {
  337.                     ip.push(pt);
  338.                 }
  339.             }
  341.             return ip;
  342.         }
  344.         static intersectLine2Polygon(line, polygon) {
  345.             let ip = [];
  347.             if ( polygon.isEmpty() ) {
  348.                 return ip;
  349.             }
  351.             for (let edge of polygon.edges) {
  352.                 for (let pt of line.intersect(edge.shape)) {
  353.                     ip.push(pt);
  354.                 }
  355.             }
  357.             return ip;
  358.         }
  360.         static intersectPolygon2Polygon(polygon1, polygon2) {
  361.             let ip = [];
  363.             if (polygon1.isEmpty() || polygon2.isEmpty()) {
  364.                 return ip;
  365.             }
  367.             if (polygon1.box.not_intersect(polygon2.box)) {
  368.                 return ip;
  369.             }
  371.             for (let edge1 of polygon1.edges) {
  372.                 for (let pt of Polygon.intersectShape2Polygon(edge1.shape, polygon2)) {
  373.                     ip.push(pt);
  374.                 }
  375.             }
  377.             return ip;
  378.         }
  380.         /**
  381.          * Return string to draw polygon in svg
  382.          * @param attrs  - an object with attributes for svg path element,
  383.          * like "stroke", "strokeWidth", "fill", "fillRule", "fillOpacity"
  384.          * Defaults are stroke:"black", strokeWidth:"1", fill:"lightcyan", fillRule:"evenodd", fillOpacity: "1"
  385.          * @returns {string}
  386.          */
  387.         svg(attrs = {}) {
  388.             let {stroke, strokeWidth, fill, fillRule, fillOpacity, id, className} = attrs;
  389.             // let restStr = Object.keys(rest).reduce( (acc, key) => acc += ` ${key}="${rest[key]}"`, "");
  390.             let id_str = (id && id.length > 0) ? `id="${id}"` : "";
  391.             let class_str = (className && className.length > 0) ? `class="${className}"` : "";
  393.             let svgStr = `\n<path stroke="${stroke || "black"}" stroke-width="${strokeWidth || 1}" fill="${fill || "lightcyan"}" fill-rule="${fillRule || "evenodd"}" fill-opacity="${fillOpacity || 1.0}" ${id_str} ${class_str} d="`;
  394.             for (let face of this.faces) {
  395.                 svgStr += face.svg();
  396.             }
  397.             svgStr += `" >\n</path>`;
  398.             return svgStr;
  399.         }
  401.         /**
  402.          * This method returns an object that defines how data will be
  403.          * serialized when called JSON.stringify() method
  404.          * @returns {Object}
  405.          */
  406.         toJSON() {
  407.             return [...this.faces].map(face => face.toJSON());
  408.         }
  409.     }
  410. };