Assigns a depth to all trapezoids; 0: outside, 1: main polygon, 2: holes, 3:polygons in holes, ... Checks segment orientation and marks those polygon chains for reversal where the polygon inside lies to their right (contour in CW, holes in CCW)
175180
function ( inPolyData ) {
		var thisDepth = [ this.trapArray[0] ];
		var nextDepth = [];

		var thisTrap, borderSeg, curDepth = 0;
		do {
			// rseg should exactely go upward on trapezoids inside the polygon (odd depth)
			var expectedRsegUpward = ( ( curDepth % 2 ) == 1 );
			while ( thisTrap = thisDepth.pop() ) {			// assignment !
				if ( thisTrap.depth != -1 )	continue;
				thisTrap.depth = curDepth;
				//
				if ( thisTrap.uL )	thisDepth.push( thisTrap.uL );
				if ( thisTrap.uR )	thisDepth.push( thisTrap.uR );
				if ( thisTrap.dL )	thisDepth.push( thisTrap.dL );
				if ( thisTrap.dR )	thisDepth.push( thisTrap.dR );
				//
				if ( ( borderSeg = thisTrap.lseg ) && ( borderSeg.trLeft.depth == -1 ) )	// assignment !
					nextDepth.push( borderSeg.trLeft );
				if ( borderSeg = thisTrap.rseg ) {											// assignment !
					if ( borderSeg.trRight.depth == -1 )
						nextDepth.push( borderSeg.trRight );
					if ( borderSeg.upward != expectedRsegUpward )
						inPolyData.set_PolyLeft_wrong( borderSeg.chainId );
				}
			}
			thisDepth = nextDepth; nextDepth = [];
			curDepth++;
		} while ( thisDepth.length > 0 );
	}
917770
function buildLidFaces() {

			var start = verticesArray.length / 3;

			if ( bevelEnabled ) {

				var layer = 0; // steps + 1
				var offset = vlen * layer;

				// Bottom faces

				for ( i = 0; i < flen; i ++ ) {

					face = faces[ i ];
					f3( face[ 2 ] + offset, face[ 1 ] + offset, face[ 0 ] + offset );

				}

				layer = steps + bevelSegments * 2;
				offset = vlen * layer;

				// Top faces

				for ( i = 0; i < flen; i ++ ) {

					face = faces[ i ];
					f3( face[ 0 ] + offset, face[ 1 ] + offset, face[ 2 ] + offset );

				}

			} else {

				// Bottom faces

				for ( i = 0; i < flen; i ++ ) {

					face = faces[ i ];
					f3( face[ 2 ], face[ 1 ], face[ 0 ] );

				}

				// Top faces

				for ( i = 0; i < flen; i ++ ) {

					face = faces[ i ];
					f3( face[ 0 ] + vlen * steps, face[ 1 ] + vlen * steps, face[ 2 ] + vlen * steps );

				}

			}

			scope.addGroup( start, verticesArray.length / 3 - start, 0 );

		}
87111
function assignLayerCandidate(vertices, incoming, outgoing, W, c, getTo) {
  const layerBelow = new Set()
  const assigned = new Set()
  const layers = [new Set()]

  let widthCurrent = 0
  let widthUp = 0

  while (assigned.size !== vertices.size) {
    let selected = null
    let selectedDegree = -Infinity
    let okay = true
    for (let vertex of vertices) {
      if (assigned.has(vertex)) {
        continue
      }
      let vertexOutgoing = outgoing.get(vertex) || φ

      okay = true

      // N+G(v) ⊆ Z
      for (let edge of vertexOutgoing) {
        if (!layerBelow.has(getTo(edge))) {
          okay = false
          break
        }
      }

      if (!okay && vertexOutgoing.size) continue

      if (selectedDegree < vertexOutgoing.size) {
        selectedDegree = vertexOutgoing.size
        selected = vertex
      }
    }

    if (selected) {
      layers[layers.length - 1].add(selected)
      assigned.add(selected)
      widthCurrent = widthCurrent - selectedDegree + 1
      widthUp = widthUp + (incoming.get(selected) || φ).size
    }

    if (!selected || (widthCurrent >= W && selectedDegree < 1) || widthUp >= W * c) {
      widthCurrent = widthUp
      widthUp = 0
      layers.push(new Set())
      for (let vertex of layers[layers.length - 2]) {
        layerBelow.add(vertex)
      }
    }
  }

  return layers
}
390019
function polygon2contour(points) {

    if (!points || !points.length) {
        return null;
    }

    var contours = [];
    var segments = parseParams(points);
    for (var i = 0, l = segments.length; i < l; i += 2) {
        contours.push({
            x: segments[i],
            y: segments[i + 1],
            onCurve: true
        });
    }

    return contours;
}
1368515
function(segments) {
        var previousSegment = [-1, -1];
        var segmentIndicesToRemove = [];
        var cleanedSegmentArray = [];
        var i, ii;
        for (i = 0, ii = segments.length; i < ii; ++i) {
            if (!(previousSegment[0] <= segments[i][0] &&
                    previousSegment[1] >= segments[i][1])) {
                cleanedSegmentArray.push(segments[i]);
            }
            previousSegment = segments[i];
        }

        segments.length = 0;
        for (i = 0, ii = cleanedSegmentArray.length; i < ii; ++i) {
            segments.push(cleanedSegmentArray[i]);
        }
    }
194532
function() {
    var polygon = this._shape;
    for (var i = 0, len = polygon._latlngs.length; i < len; i++) {
      // update marker
      var marker = this._resizeMarkers[i];
      marker.setLatLng(polygon._latlngs[i]);

      // this one's needed to update the path
      marker._origLatLng = polygon._latlngs[i];
      if (marker._middleLeft) {
        marker._middleLeft.setLatLng(this._getMiddleLatLng(marker._prev, marker));
      }
      if (marker._middleRight) {
        marker._middleRight.setLatLng(this._getMiddleLatLng(marker, marker._next));
      }
    }
    // this._moveMarker.setLatLng(polygon.getBounds().getCenter());

    // show vertices
    this._shape._map.addLayer(this._markerGroup);
    this._updateMoveMarker();

    this._repositionCornerMarkers();
    this._fireEdit();
  }
180462
function (options) {
  options = options || {}
  if (('points' in options) !== ('faces' in options)) {
    throw new Error("polyhedron needs 'points' and 'faces' arrays")
  }
  let vertices = parseOptionAs3DVectorList(options, 'points', [
            [1, 1, 0],
            [1, -1, 0],
            [-1, -1, 0],
            [-1, 1, 0],
            [0, 0, 1]
  ])
        .map(function (pt) {
          return new Vertex3(pt)
        })
  let faces = parseOption(options, 'faces', [
            [0, 1, 4],
            [1, 2, 4],
            [2, 3, 4],
            [3, 0, 4],
            [1, 0, 3],
            [2, 1, 3]
  ])
    // Openscad convention defines inward normals - so we have to invert here
  faces.forEach(function (face) {
    face.reverse()
  })
  let polygons = faces.map(function (face) {
    return new Polygon3(face.map(function (idx) {
      return vertices[idx]
    }))
  })

    // TODO: facecenters as connectors? probably overkill. Maybe centroid
    // the re-tesselation here happens because it's so easy for a user to
    // create parametrized polyhedrons that end up with 1-2 dimensional polygons.
    // These will create infinite loops at CSG.Tree()
  return fromPolygons(polygons).reTesselated()
}
1311866
function ( contour, holes ) {

		var shape = contour.concat(); // work on this shape
		var allpoints = shape.concat();

		/* For each isolated shape, find the closest points and break to the hole to allow triangulation */


		var prevShapeVert, nextShapeVert,
			prevHoleVert, nextHoleVert,
			holeIndex, shapeIndex,
			shapeId, shapeGroup,
			h, h2,
			hole, shortest, d,
			p, pts1, pts2,
			tmpShape1, tmpShape2,
			tmpHole1, tmpHole2,
			verts = [];

		for ( h = 0; h < holes.length; h ++ ) {

			hole = holes[ h ];

			/*
			shapeholes[ h ].concat(); // preserves original
			holes.push( hole );
			*/

			Array.prototype.push.apply( allpoints, hole );

			shortest = Number.POSITIVE_INFINITY;


			// Find the shortest pair of pts between shape and hole

			// Note: Actually, I'm not sure now if we could optimize this to be faster than O(m*n)
			// Using distanceToSquared() intead of distanceTo() should speed a little
			// since running square roots operations are reduced.

			for ( h2 = 0; h2 < hole.length; h2 ++ ) {

				pts1 = hole[ h2 ];
				var dist = [];

				for ( p = 0; p < shape.length; p++ ) {

					pts2 = shape[ p ];
					d = pts1.distanceToSquared( pts2 );
					dist.push( d );

					if ( d < shortest ) {

						shortest = d;
						holeIndex = h2;
						shapeIndex = p;

					}

				}

			}

			//console.log("shortest", shortest, dist);

			prevShapeVert = ( shapeIndex - 1 ) >= 0 ? shapeIndex - 1 : shape.length - 1;
			prevHoleVert = ( holeIndex - 1 ) >= 0 ? holeIndex - 1 : hole.length - 1;

			var areaapts = [

				hole[ holeIndex ],
				shape[ shapeIndex ],
				shape[ prevShapeVert ]

			];

			var areaa = THREE.FontUtils.Triangulate.area( areaapts );

			var areabpts = [

				hole[ holeIndex ],
				hole[ prevHoleVert ],
				shape[ shapeIndex ]

			];

			var areab = THREE.FontUtils.Triangulate.area( areabpts );

			var shapeOffset = 1;
			var holeOffset = -1;

			var oldShapeIndex = shapeIndex, oldHoleIndex = holeIndex;
			shapeIndex += shapeOffset;
			holeIndex += holeOffset;

			if ( shapeIndex < 0 ) { shapeIndex += shape.length;  }
			shapeIndex %= shape.length;

			if ( holeIndex < 0 ) { holeIndex += hole.length;  }
			holeIndex %= hole.length;

			prevShapeVert = ( shapeIndex - 1 ) >= 0 ? shapeIndex - 1 : shape.length - 1;
			prevHoleVert = ( holeIndex - 1 ) >= 0 ? holeIndex - 1 : hole.length - 1;

			areaapts = [

				hole[ holeIndex ],
				shape[ shapeIndex ],
				shape[ prevShapeVert ]

			];

			var areaa2 = THREE.FontUtils.Triangulate.area( areaapts );

			areabpts = [

				hole[ holeIndex ],
				hole[ prevHoleVert ],
				shape[ shapeIndex ]

			];

			var areab2 = THREE.FontUtils.Triangulate.area( areabpts );
			//console.log(areaa,areab ,areaa2,areab2, ( areaa + areab ),  ( areaa2 + areab2 ));

			if ( ( areaa + areab ) > ( areaa2 + areab2 ) ) {

				// In case areas are not correct.
				//console.log("USE THIS");

				shapeIndex = oldShapeIndex;
				holeIndex = oldHoleIndex ;

				if ( shapeIndex < 0 ) { shapeIndex += shape.length;  }
				shapeIndex %= shape.length;

				if ( holeIndex < 0 ) { holeIndex += hole.length;  }
				holeIndex %= hole.length;

				prevShapeVert = ( shapeIndex - 1 ) >= 0 ? shapeIndex - 1 : shape.length - 1;
				prevHoleVert = ( holeIndex - 1 ) >= 0 ? holeIndex - 1 : hole.length - 1;

			} else {

				//console.log("USE THAT ")

			}

			tmpShape1 = shape.slice( 0, shapeIndex );
			tmpShape2 = shape.slice( shapeIndex );
			tmpHole1 = hole.slice( holeIndex );
			tmpHole2 = hole.slice( 0, holeIndex );

			// Should check orders here again?

			var trianglea = [

				hole[ holeIndex ],
				shape[ shapeIndex ],
				shape[ prevShapeVert ]

			];

			var triangleb = [

				hole[ holeIndex ] ,
				hole[ prevHoleVert ],
				shape[ shapeIndex ]

			];

			verts.push( trianglea );
			verts.push( triangleb );

			shape = tmpShape1.concat( tmpHole1 ).concat( tmpHole2 ).concat( tmpShape2 );

		}

		return {

			shape:shape, 		/* shape with no holes */
			isolatedPts: verts, /* isolated faces */
			allpoints: allpoints

		}


	}
1136206
function (face, v) {
                //Get the indices of triangles for each polygon
                getTriangles(face, v);
                //For each element in the triangles array.
                //This var could contains 1 to an infinity of triangles
                for (var k = 0; k < triangles.length; k++) {
                    // Set position indice
                    var indicePositionFromObj = parseInt(triangles[k]) - 1;
                    setData(indicePositionFromObj, 0, 0, //In the pattern 1, normals and uvs are not defined
                    positions[indicePositionFromObj], //Get the vectors data
                    BABYLON.Vector2.Zero(), BABYLON.Vector3.Up() //Create default vectors
                    );
                }
                //Reset variable for the next line
                triangles = [];
            }
1071368
function () {
    var dressing = new THREE.Object3D();
    this.dressing.setAttribute('visible', this.data.dressing != 'none');
    if (this.data.dressing == 'none') {
      return;
    }
    var geometry = new THREE.Geometry(); // mother geometry that will hold all instances

    // get array of geometries
    var geoset;
    switch (this.data.dressing){
      case 'cubes': {
        geoset = [new THREE.BoxGeometry(1, 1, 1)];
        geoset[0].applyMatrix(new THREE.Matrix4().makeTranslation(0, 0.5, 0));
        break;
      }
      case 'pyramids': {
        geoset = [new THREE.ConeGeometry(1, 1, 4, 1, true)];
        geoset[0].applyMatrix(new THREE.Matrix4().makeTranslation(0, 0.5, 0));
        break;
      }
      case 'cylinders': {
        geoset = [new THREE.CylinderGeometry(0.5, 0.5, 1, 8, 1, true)];
        geoset[0].applyMatrix(new THREE.Matrix4().makeTranslation(0, 0.5, 0));
        break;
      }
      default: {
        geoset = this.getAssetGeometry(this.assets[this.data.dressing]);
        if (!geoset) return;
        break;
      }
    }

    for (var i = 0, r = 88343; i < this.data.dressingAmount; i++, r++) {

      var geo = geoset[Math.floor(this.random(33 + i) * geoset.length)];
/*
      // change vertex colors
      var color = new THREE.Color(0xFFFFFF).multiplyScalar(1 - this.random(66 + i) * 0.3);

      for (var f = 0, fl = geo.faces.length; f < fl; f++) {
        var face = geo.faces[f];
        for (var v = 0; v < 3; v++) {
          p = geo.vertices[face[faceindex[v]]]; // get vertex position
          var floorao =  p.y / 4 + 0.75;
          face.vertexColors[v] = new THREE.Color(color.r * floorao, color.g * floorao, color.b * floorao);
        }
      }
*/
      // set random position, rotation and scale
      var ds = this.data.dressingScale;
      var dv = new THREE.Vector3(this.data.dressingVariance.x, this.data.dressingVariance.y, this.data.dressingVariance.z);
      var distance;
      var onPlayArea = this.random(r) < this.data.dressingOnPlayArea;
      if (onPlayArea) {
        distance = this.random(r + 1) * 15;
      }
      else {
        distance = 10 + Math.max(dv.x, dv.z) + 10 * this.random(r + 1) + this.random(r + 2) * this.STAGE_SIZE / 3;
      }

      var direction = this.random(r + 3) * Math.PI * 2;
      var matrix = new THREE.Matrix4();
      var scale = this.random(r + 4);
      var uniformScale = this.data.dressingUniformScale;

      matrix.compose(
        // position
        new THREE.Vector3(
          Math.cos(direction) * distance,
          0,
          Math.sin(direction) * distance
          ),
        // rotation
        new THREE.Quaternion().setFromAxisAngle(
          new THREE.Vector3(0, 1, 0),
          (this.random(r + 5) - 0.5) * dv.length() * Math.PI * 2
          ),
        // scale
        new THREE.Vector3(
           ds + (uniformScale ? scale : this.random(r + 6)) * dv.x,
           ds + (uniformScale ? scale : this.random(r + 7)) * dv.y,
           ds + (uniformScale ? scale : this.random(r + 8)) * dv.z
          )
        );

      // merge with mother geometry
      geometry.merge(geo, matrix);
    }

    // convert geometry to buffergeometry
    var bufgeo = new THREE.BufferGeometry();
    bufgeo.fromGeometry(geometry);

    // setup material
    var material = new THREE.MeshLambertMaterial({
      color: new THREE.Color(this.data.dressingColor),
      vertexColors: THREE.VertexColors
    });

    if (this.data.flatShading) {
      bufgeo.computeVertexNormals();
    }

    // create mesh
    var mesh = new THREE.Mesh(bufgeo, material);
    dressing.add(mesh);
    // add to scene
    this.dressing.setObject3D('mesh', dressing);
  }
638713
function(options) {
            // normals are going to be correct as long as toConn2.point - toConn1.point
            // points into cag normal direction (check in caller)
            // arguments: options.toConnector1, options.toConnector2, options.cag
            //     walls go from toConnector1 to toConnector2
            //     optionally, target cag to point to - cag needs to have same number of sides as this!
            var origin = [0, 0, 0], defaultAxis = [0, 0, 1], defaultNormal = [0, 1, 0];
            var thisConnector = new CSG.Connector(origin, defaultAxis, defaultNormal);
            // arguments:
            var toConnector1 = options.toConnector1;
            // var toConnector2 = new CSG.Connector([0, 0, -30], defaultAxis, defaultNormal);
            var toConnector2 = options.toConnector2;
            if (!(toConnector1 instanceof CSG.Connector && toConnector2 instanceof CSG.Connector)) {
                throw('could not parse CSG.Connector arguments toConnector1 or toConnector2');
            }
            if (options.cag) {
                if (options.cag.sides.length != this.sides.length) {
                    throw('target cag needs same sides count as start cag');
                }
            }
            // target cag is same as this unless specified
            var toCag = options.cag || this;
            var m1 = thisConnector.getTransformationTo(toConnector1, false, 0);
            var m2 = thisConnector.getTransformationTo(toConnector2, false, 0);
            var vps1 = this._toVector3DPairs(m1);
            var vps2 = toCag._toVector3DPairs(m2);

            var polygons = [];
            vps1.forEach(function(vp1, i) {
                polygons.push(new CSG.Polygon([
                    new CSG.Vertex(vps2[i][1]), new CSG.Vertex(vps2[i][0]), new CSG.Vertex(vp1[0])]));
                polygons.push(new CSG.Polygon([
                    new CSG.Vertex(vps2[i][1]), new CSG.Vertex(vp1[0]), new CSG.Vertex(vp1[1])]));
            });
            return polygons;
        }
1049203
def d(self, useSandT=False, use_closed_attrib=False):
        """"""

        if use_closed_attrib:
            self_closed = self.closed(warning_on=False)
            if self_closed:
                segments = self[:-1]
            else:
                segments = self[:]
        else:
            self_closed = False
            segments = self[:]

        current_pos = None
        parts = []
        previous_segment = None
        end = self[-1].end

        for segment in segments:
            seg_start = segment.start
            # If the start of this segment does not coincide with the end of
            # the last segment or if this segment is actually the close point
            # of a closed path, then we should start a new subpath here.
            if current_pos != seg_start or \
                    (self_closed and seg_start == end and use_closed_attrib):
                parts.append('M {},{}'.format(seg_start.real, seg_start.imag))

            if isinstance(segment, Line):
                args = segment.end.real, segment.end.imag
                parts.append('L {},{}'.format(*args))
            elif isinstance(segment, CubicBezier):
                if useSandT and segment.is_smooth_from(previous_segment,
                                                       warning_on=False):
                    args = (segment.control2.real, segment.control2.imag,
                            segment.end.real, segment.end.imag)
                    parts.append('S {},{} {},{}'.format(*args))
                else:
                    args = (segment.control1.real, segment.control1.imag,
                            segment.control2.real, segment.control2.imag,
                            segment.end.real, segment.end.imag)
                    parts.append('C {},{} {},{} {},{}'.format(*args))
            elif isinstance(segment, QuadraticBezier):
                if useSandT and segment.is_smooth_from(previous_segment,
                                                       warning_on=False):
                    args = segment.end.real, segment.end.imag
                    parts.append('T {},{}'.format(*args))
                else:
                    args = (segment.control.real, segment.control.imag,
                            segment.end.real, segment.end.imag)
                    parts.append('Q {},{} {},{}'.format(*args))

            elif isinstance(segment, Arc):
                args = (segment.radius.real, segment.radius.imag,
                        segment.rotation,int(segment.large_arc),
                        int(segment.sweep),segment.end.real, segment.end.imag)
                parts.append('A {},{} {} {:d},{:d} {},{}'.format(*args))
            current_pos = segment.end
            previous_segment = segment

        if self_closed:
            parts.append('Z')

        return ' '.join(parts)
910761
def allPolygons(self):
        
        polygons = self.polygons[:]
        if self.front: 
            polygons.extend(self.front.allPolygons())
        if self.back: 
            polygons.extend(self.back.allPolygons())
        return polygons
745891
@Override
	protected void addCoordinateToGeometry(Coordinate newCoordinate) {
		boolean geometryHasCoordinates = geometry.getCoordinates() != null;

		// determine length and coordinates
		int length = geometryHasCoordinates ? geometry.getCoordinates().length : 0;
		Coordinate[] oldCoords = geometryHasCoordinates ? geometry.getCoordinates() : null;
		Coordinate[] newCoords = new Coordinate[length + 1];
		if (geometryHasCoordinates) {
			System.arraycopy(oldCoords, 0, newCoords, 0, length);
		}

		// put new coordinate in right position
		if (newCoords.length < 2) {
			newCoords[length] = newCoordinate;
		} else {
			newCoords[length] = newCoords[length - 1];
			newCoords[length - 1] = newCoordinate;
		}

		// create new geometry
		LinearRing linearRing = factory.createLinearRing(newCoords);
		geometry = factory.createPolygon(linearRing, null);

		// update drawing
		updateTempLineAfterClick();
	}
953960
function ( inOutSegListArray ) {
		// makes sure that the first N segments are one from each of the N polygon chains
		var mainIdx = 0;
		var helpIdx = this.polyData.nbPolyChains();
		if ( helpIdx == 1 )		return;
		var chainMarker = new Array(helpIdx);
		var oldSegListArray = inOutSegListArray.concat();
		for (var i=0; i<oldSegListArray.length; i++) {
			var chainId = oldSegListArray[i].chainId;
			if ( chainMarker[chainId] ) {
				inOutSegListArray[helpIdx++] = oldSegListArray[i];
			} else {
				inOutSegListArray[mainIdx++] = oldSegListArray[i];
				chainMarker[chainId] = true;
			}
		}
	}
543185
function insidePolygon(rings, p) {
    var inside = false;
    for (var i = 0, len = rings.length; i < len; i++) {
        var ring = rings[i];
        for (var j = 0, len2 = ring.length, k = len2 - 1; j < len2; k = j++) {
            if (rayIntersect(p, ring[j], ring[k])) inside = !inside;
        }
    }
    return inside;
}
114406
function () {						// <<<<<< public
		var newMono, newMonoTo, toFirstOutSeg, fromRevSeg;
		for ( var i = 0, j = this.segments.length; i < j; i++) {
			newMono = this.segments[i];
			if ( this.PolyLeftArr[newMono.chainId] ) {
				// preserve winding order
				newMonoTo = newMono.vTo;			// target of segment
				newMono.mprev = newMono.sprev;		// doubly linked list for monotone chains (sub-polygons)
				newMono.mnext = newMono.snext;
			} else {
				// reverse winding order
				newMonoTo = newMono.vFrom;
				newMono = newMono.snext;
				newMono.mprev = newMono.snext;
				newMono.mnext = newMono.sprev;
			}
			if ( fromRevSeg = newMono.vFrom.lastInDiag ) {		// assignment !
				fromRevSeg.mnext = newMono;
				newMono.mprev = fromRevSeg;
				newMono.vFrom.lastInDiag = null;		// cleanup
			}
			if ( toFirstOutSeg = newMonoTo.firstOutDiag ) {		// assignment !
				toFirstOutSeg.mprev = newMono;
				newMono.mnext = toFirstOutSeg;
				newMonoTo.firstOutDiag = null;			// cleanup
			}
		}
	}