Dynamically inserts each geometry into the convex hull.
359767
private void addMultiVertexGeometry_(MultiVertexGeometry mvg) {
		Point point = new Point();
		Point2D pt_p = new Point2D();

		for (int i = 0; i < mvg.getPointCount(); i++) {
			mvg.getXY(i, pt_p);
			int p = addPoint_(pt_p);

			if (p != -1) {
				mvg.getPointByVal(i, point);
				int tp = m_shape.addPoint(m_path_handle, point);
				m_tree_hull.setElement(p, tp); // reset the place holder to tp
			}
		}
	}
1321876
def convex_hull(self):
        
        points = util.vstack_empty([m.vertices for m in self.dump()])
        hull = convex.convex_hull(points)
        return hull
545143
function (meshes, applyWorldTransform) {

        if (! meshes.length) {
            return;
        }

        var templateMesh = meshes[0];
        var templateGeo = templateMesh.geometry;
        var material = templateMesh.material;

        var geometry = new Geometry({
            dynamic: false
        });
        geometry.boundingBox = new BoundingBox();

        var attributeNames = templateGeo.getEnabledAttributes();

        for (var i = 0; i < attributeNames.length; i++) {
            var name = attributeNames[i];
            var attr = templateGeo.attributes[name];
            // Extend custom attributes
            if (!geometry.attributes[name]) {
                geometry.attributes[name] = attr.clone(false);
            }
        }

        var inverseTransposeMatrix = mat4.create();
        // Initialize the array data and merge bounding box
        var nVertex = 0;
        var nFace = 0;
        for (var k = 0; k < meshes.length; k++) {
            var currentGeo = meshes[k].geometry;
            if (currentGeo.boundingBox) {
                currentGeo.boundingBox.applyTransform(applyWorldTransform ? meshes[k].worldTransform : meshes[k].localTransform);
                geometry.boundingBox.union(currentGeo.boundingBox);
            }
            nVertex += currentGeo.vertexCount;
            nFace += currentGeo.triangleCount;
        }
        for (var n = 0; n < attributeNames.length; n++) {
            var name = attributeNames[n];
            var attrib = geometry.attributes[name];
            attrib.init(nVertex);
        }
        if (nVertex >= 0xffff) {
            geometry.indices = new Uint32Array(nFace * 3);
        }
        else {
            geometry.indices = new Uint16Array(nFace * 3);
        }

        var vertexOffset = 0;
        var indicesOffset = 0;
        var useIndices = templateGeo.isUseIndices();

        for (var mm = 0; mm < meshes.length; mm++) {
            var mesh = meshes[mm];
            var currentGeo = mesh.geometry;

            var nVertex = currentGeo.vertexCount;

            var matrix = applyWorldTransform ? mesh.worldTransform.array : mesh.localTransform.array;
            mat4.invert(inverseTransposeMatrix, matrix);
            mat4.transpose(inverseTransposeMatrix, inverseTransposeMatrix);

            for (var nn = 0; nn < attributeNames.length; nn++) {
                var name = attributeNames[nn];
                var currentAttr = currentGeo.attributes[name];
                var targetAttr = geometry.attributes[name];
                // Skip the unused attributes;
                if (!currentAttr.value.length) {
                    continue;
                }
                var len = currentAttr.value.length;
                var size = currentAttr.size;
                var offset = vertexOffset * size;
                var count = len / size;
                for (var i = 0; i < len; i++) {
                    targetAttr.value[offset + i] = currentAttr.value[i];
                }
                // Transform position, normal and tangent
                if (name === 'position') {
                    vec3.forEach(targetAttr.value, size, offset, count, vec3.transformMat4, matrix);
                }
                else if (name === 'normal' || name === 'tangent') {
                    vec3.forEach(targetAttr.value, size, offset, count, vec3.transformMat4, inverseTransposeMatrix);
                }
            }

            if (useIndices) {
                var len = currentGeo.indices.length;
                for (var i = 0; i < len; i++) {
                    geometry.indices[i + indicesOffset] = currentGeo.indices[i] + vertexOffset;
                }
                indicesOffset += len;
            }

            vertexOffset += nVertex;
        }

        return new Mesh({
            material: material,
            geometry: geometry
        });
    }
1215392
function (baseLine, latLngs) {
			var convexHullBaseLines = [],
				t = this.findMostDistantPointFromBaseLine(baseLine, latLngs);

			if (t.maxPoint) { // if there is still a point "outside" the base line
				convexHullBaseLines =
					convexHullBaseLines.concat(
						this.buildConvexHull([baseLine[0], t.maxPoint], t.newPoints)
					);
				convexHullBaseLines =
					convexHullBaseLines.concat(
						this.buildConvexHull([t.maxPoint, baseLine[1]], t.newPoints)
					);
				return convexHullBaseLines;
			} else {  // if there is no more point "outside" the base line, the current base line is part of the convex hull
				return [baseLine[0]];
			}
		}
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()
}
589237
private void init(DelaunayTriangulation delaunay, int xCellCount, int yCellCount, BoundingBox region) {
        indexDelaunay = delaunay;
        indexRegion = region;
        x_size = region.getWidth() / yCellCount;
        y_size = region.getHeight() / xCellCount;

        // The grid will hold a trinagle for each cell, so a point (x,y) will lie
        // in the cell representing the grid partition of region to a
        //  xCellCount on yCellCount grid
        grid = new Triangle[xCellCount][yCellCount];

        Triangle colStartTriangle = indexDelaunay.find(middleOfCell(0, 0));
        updateCellValues(0, 0, xCellCount - 1, yCellCount - 1, colStartTriangle);
    }
1132453
static Geometry construct(MultiVertexGeometry mvg) {
		if (mvg.isEmpty())
			return new Polygon(mvg.getDescription());

		MultiVertexGeometryImpl mvg_impl = (MultiVertexGeometryImpl) mvg._getImpl();
		int N = mvg_impl.getPointCount();

		if (N <= 2) {
			if (N == 1 || mvg_impl.getXY(0).equals(mvg_impl.getXY(1))) {
				Point point = new Point(mvg_impl.getDescription());
				mvg_impl.getPointByVal(0, point);
				return point;
			} else {
				Point pt = new Point();
				Polyline polyline = new Polyline(mvg_impl.getDescription());
				mvg_impl.getPointByVal(0, pt);
				polyline.startPath(pt);
				mvg_impl.getPointByVal(1, pt);
				polyline.lineTo(pt);
				return polyline;
			}
		}

		AttributeStreamOfDbl stream = (AttributeStreamOfDbl) mvg_impl.getAttributeStreamRef(VertexDescription.Semantics.POSITION);
		ConvexHull convex_hull = new ConvexHull(stream, N);

		int t0 = 0, tm = 1;
		Point2D pt_0 = new Point2D();
		Point2D pt_m = new Point2D();
		Point2D pt_p = new Point2D();

		stream.read(t0 << 1, pt_0);

		while (true) {
			if (tm >= N)
				break;

			stream.read(tm << 1, pt_m);
			if (!pt_m.isEqual(pt_0, NumberUtils.doubleEps()))
				break;

			tm++; // We don't want to close the gap between t0 and tm.
		}

		convex_hull.m_tree_hull.addElement(t0, -1);

		if (tm < N) {
			convex_hull.m_tree_hull.addBiggestElement(tm, -1);

			for (int tp = tm + 1; tp < mvg_impl.getPointCount(); tp++) {// Dynamically insert into the current convex hull

				stream.read(tp << 1, pt_p);
				int p = convex_hull.treeHull_(pt_p);

				if (p != -1)
					convex_hull.m_tree_hull.setElement(p, tp); // reset the place holder to the point index.
			}
		}

		// Extracts the convex hull from the tree. Reading the tree in order from first to last is the resulting convex hull.

		VertexDescription description = mvg_impl.getDescription();
		boolean b_has_attributes = (description.getAttributeCount() > 1);
		int point_count = convex_hull.m_tree_hull.size(-1);

		Geometry hull;

		if (point_count >= 2) {
			if (point_count >= 3)
				hull = new Polygon(description);
			else
				hull = new Polyline(description);

			MultiPathImpl hull_impl = (MultiPathImpl) hull._getImpl();
			hull_impl.addPath((Point2D[]) null, 0, true);

			Point point = null;
			if (b_has_attributes)
				point = new Point();

			for (int i = convex_hull.m_tree_hull.getFirst(-1); i != -1; i = convex_hull.m_tree_hull.getNext(i)) {
				if (b_has_attributes) {
					mvg_impl.getPointByVal(convex_hull.m_tree_hull.getElement(i), point);
					hull_impl.insertPoint(0, -1, point);
				} else {
					stream.read(convex_hull.m_tree_hull.getElement(i) << 1, pt_p);
					hull_impl.insertPoint(0, -1, pt_p);
				}
			}
		} else {
			assert (point_count == 1);

			if (b_has_attributes) {
				Point point = new Point(description);
				mvg_impl.getPointByVal(convex_hull.m_tree_hull.getElement(convex_hull.m_tree_hull.getFirst(-1)), point);
				hull = point;
			} else {
				stream.read(convex_hull.m_tree_hull.getElement(convex_hull.m_tree_hull.getFirst(-1)) << 1, pt_p);
				hull = new Point(pt_p);
			}
		}

		return hull;
	}
336294
def insert(
            self, M_c, T, X_L_list, X_D_list, new_rows=None, N_GRID=31,
            CT_KERNEL=0):
        """"""
        if new_rows is None:
            raise ValueError("new_row must exist")

        if not isinstance(new_rows, list):
            raise TypeError('new_rows must be list of lists')
            if not isinstance(new_rows[0], list):
                raise TypeError('new_rows must be list of lists')

        X_L_list, X_D_list, was_multistate = su.ensure_multistate(
            X_L_list, X_D_list)

        # get insert arg tuples
        arg_tuples = self.get_insert_arg_tuples(
            M_c, T, X_L_list, X_D_list, new_rows, N_GRID, CT_KERNEL)

        chain_tuples = self.mapper(self.do_insert, arg_tuples)
        X_L_list, X_D_list = zip(*chain_tuples)

        if not was_multistate:
            X_L_list, X_D_list = X_L_list[0], X_D_list[0]

        T.extend(new_rows)
        ret_tuple = X_L_list, X_D_list, T
        return ret_tuple
848700
private static Polygon processPolygon(Polygon p, Geometry triangleLines, GeometryFactory factory) {
        Geometry diffExt = p.getExteriorRing().difference(triangleLines);
        final int nbOfHoles = p.getNumInteriorRing();
        final LinearRing[] holes = new LinearRing[nbOfHoles];
        for (int i = 0; i < nbOfHoles; i++) {
            holes[i] = factory.createLinearRing(lineMerge(p.getInteriorRingN(i).difference(triangleLines), factory).getCoordinates());
        }
        return factory.createPolygon(factory.createLinearRing(lineMerge(diffExt, factory).getCoordinates()), holes);

    }
1202191
function ( inPolygonData ) {
		// positional slots for neighboring trapezoid-diagonals
		var DIAG_UL = 0, DIAG_UM = 1, DIAG_ULR = 2, DIAG_UR = 3;
		var DIAG_DR = 4, DIAG_DM = 5, DIAG_DLR = 6, DIAG_DL = 7;

		var i, j;
		var nbVertices = inPolygonData.nbVertices();

		// initialize arrays for neighboring trapezoid-diagonals and vertices
		var myVisibleDiagonals	= new Array(nbVertices);
		for ( i = 0; i < nbVertices; i++ ) {
			myVisibleDiagonals[i] = new Array(DIAG_DL+1);
		}
		// create the list of neighboring trapezoid-diagonals
		//	put into their positional slots
		var myExternalNeighbors = new Array(nbVertices);
		for ( i = 0, j = this.trapArray.length; i < j; i++ ) {
			var curTrap = this.trapArray[i];
			var highPos = curTrap.uL ?
						( curTrap.uR ? DIAG_DM : DIAG_DL ) :
						( curTrap.uR ? DIAG_DR : DIAG_DLR );
			var lowPos = curTrap.dL ?
						( curTrap.dR ? DIAG_UM : DIAG_UL ) :
						( curTrap.dR ? DIAG_UR : DIAG_ULR );

			if ( ( curTrap.depth % 2 ) == 1 ) {		// inside ?
				if ( ( highPos == DIAG_DM ) || ( lowPos == DIAG_UM ) ||
					 ( ( highPos == DIAG_DL ) && ( lowPos == DIAG_UR ) ) ||
					 ( ( highPos == DIAG_DR ) && ( lowPos == DIAG_UL ) ) ) {
					var lhDiag = inPolygonData.appendDiagonalsEntry( {
									vFrom: curTrap.vLow, vTo: curTrap.vHigh,
									mprev: null, mnext: null, marked: false } );
					var hlDiag = inPolygonData.appendDiagonalsEntry( {
									vFrom: curTrap.vHigh, vTo: curTrap.vLow, revDiag: lhDiag,
									mprev: null, mnext: null, marked: false } );
					lhDiag.revDiag = hlDiag;
					myVisibleDiagonals[ curTrap.vLow.id][ lowPos] = lhDiag;
					myVisibleDiagonals[curTrap.vHigh.id][highPos] = hlDiag;
				}
			} else {		// outside, hole
				if ( curTrap.vHigh.id !== null )	myExternalNeighbors[curTrap.vHigh.id] = highPos;
				if ( curTrap.vLow.id  !== null )	myExternalNeighbors[ curTrap.vLow.id] = lowPos;
			}
		}
		// create the list of outgoing diagonals in the right order (CW)
		//	from the ordered list of neighboring trapezoid-diagonals
		//	- starting from an external one
		// and connect those incoming to
		var curDiag, curDiags, firstElem, fromVertex, lastIncoming;
		for ( i = 0; i < nbVertices; i++ ) {
			curDiags  = myVisibleDiagonals[i];
			firstElem = myExternalNeighbors[i];
			if ( firstElem == null )	continue;		// eg. skipped vertices (zero length, co-linear		// NOT: === !
			j = firstElem;
			lastIncoming = null;
			do {
				if ( j++ > DIAG_DL )			j = DIAG_UL;	// circular positional list
				if ( curDiag = curDiags[j] ) {
					if ( lastIncoming ) {
						curDiag.mprev = lastIncoming;
						lastIncoming.mnext = curDiag;
					} else {
						fromVertex = curDiag.vFrom;
						fromVertex.firstOutDiag = curDiag;
					}
					lastIncoming = curDiag.revDiag;
				}
			} while ( j != firstElem );
			if ( lastIncoming )		fromVertex.lastInDiag = lastIncoming;
		}
	}
456862
def _polygon_from_coords(coords, fix_geom=False, swap=True, dims=2):
    
    assert len(coords) % dims == 0
    number_of_points = len(coords)/dims
    coords_as_array = np.array(coords)
    reshaped = coords_as_array.reshape(number_of_points, dims)
    points = [
        (float(i[1]), float(i[0])) if swap else ((float(i[0]), float(i[1])))
        for i in reshaped.tolist()
        ]
    polygon = Polygon(points).buffer(0)
    try:
        assert polygon.is_valid
        return polygon
    except AssertionError:
        if fix_geom:
            return polygon.buffer(0)
        else:
            raise RuntimeError("Geometry is not valid.")
338658
def setup(delta_x, delta_y, delta_z, pos)
      # Set up the provided parameters:
      @delta_x = delta_x
      @delta_y = delta_y
      @delta_z = delta_z
      self.pos = pos
      # Set up the dimensional parameters:
      @nx, @ny, @nz = self.shape
    end
425334
function ( shapes, curveSegments ) {

	BufferGeometry.call( this );

	this.type = '';

	this.parameters = {
		shapes: shapes,
		curveSegments: curveSegments
	};

	curveSegments = curveSegments || 12;

	// buffers

	var indices = [];
	var vertices = [];
	var normals = [];
	var uvs = [];

	// helper variables

	var groupStart = 0;
	var groupCount = 0;

	// allow single and array values for "shapes" parameter

	if ( Array.isArray( shapes ) === false ) {

		addShape( shapes );

	} else {

		for ( var i = 0; i < shapes.length; i ++ ) {

			addShape( shapes[ i ] );

			this.addGroup( groupStart, groupCount, i ); // enables MultiMaterial support

			groupStart += groupCount;
			groupCount = 0;

		}

	}

	// build geometry

	this.setIndex( indices );
	this.addAttribute( 'position', new Float32BufferAttribute( vertices, 3 ) );
	this.addAttribute( 'normal', new Float32BufferAttribute( normals, 3 ) );
	this.addAttribute( 'uv', new Float32BufferAttribute( uvs, 2 ) );


	// helper functions

	function addShape( shape ) {

		var i, l, shapeHole;

		var indexOffset = vertices.length / 3;
		var points = shape.extractPoints( curveSegments );

		var shapeVertices = points.shape;
		var shapeHoles = points.holes;

		// check direction of vertices

		if ( ShapeUtils.isClockWise( shapeVertices ) === false ) {

			shapeVertices = shapeVertices.reverse();

		}

		for ( i = 0, l = shapeHoles.length; i < l; i ++ ) {

			shapeHole = shapeHoles[ i ];

			if ( ShapeUtils.isClockWise( shapeHole ) === true ) {

				shapeHoles[ i ] = shapeHole.reverse();

			}

		}

		var faces = ShapeUtils.triangulateShape( shapeVertices, shapeHoles );

		// join vertices of inner and outer paths to a single array

		for ( i = 0, l = shapeHoles.length; i < l; i ++ ) {

			shapeHole = shapeHoles[ i ];
			shapeVertices = shapeVertices.concat( shapeHole );

		}

		// vertices, normals, uvs

		for ( i = 0, l = shapeVertices.length; i < l; i ++ ) {

			var vertex = shapeVertices[ i ];

			vertices.push( vertex.x, vertex.y, 0 );
			normals.push( 0, 0, 1 );
			uvs.push( vertex.x, vertex.y ); // world uvs

		}

		// incides

		for ( i = 0, l = faces.length; i < l; i ++ ) {

			var face = faces[ i ];

			var a = face[ 0 ] + indexOffset;
			var b = face[ 1 ] + indexOffset;
			var c = face[ 2 ] + indexOffset;

			indices.push( a, b, c );
			groupCount += 3;

		}

	}

}
478879
function addShape( shape ) {

		var i, l, shapeHole;

		var indexOffset = vertices.length / 3;
		var points = shape.extractPoints( curveSegments );

		var shapeVertices = points.shape;
		var shapeHoles = points.holes;

		// check direction of vertices

		if ( ShapeUtils.isClockWise( shapeVertices ) === false ) {

			shapeVertices = shapeVertices.reverse();

		}

		for ( i = 0, l = shapeHoles.length; i < l; i ++ ) {

			shapeHole = shapeHoles[ i ];

			if ( ShapeUtils.isClockWise( shapeHole ) === true ) {

				shapeHoles[ i ] = shapeHole.reverse();

			}

		}

		var faces = ShapeUtils.triangulateShape( shapeVertices, shapeHoles );

		// join vertices of inner and outer paths to a single array

		for ( i = 0, l = shapeHoles.length; i < l; i ++ ) {

			shapeHole = shapeHoles[ i ];
			shapeVertices = shapeVertices.concat( shapeHole );

		}

		// vertices, normals, uvs

		for ( i = 0, l = shapeVertices.length; i < l; i ++ ) {

			var vertex = shapeVertices[ i ];

			vertices.push( vertex.x, vertex.y, 0 );
			normals.push( 0, 0, 1 );
			uvs.push( vertex.x, vertex.y ); // world uvs

		}

		// incides

		for ( i = 0, l = faces.length; i < l; i ++ ) {

			var face = faces[ i ];

			var a = face[ 0 ] + indexOffset;
			var b = face[ 1 ] + indexOffset;
			var c = face[ 2 ] + indexOffset;

			indices.push( a, b, c );
			groupCount += 3;

		}

	}
345654
function ( width, height, widthSegments, heightSegments ) {

	BufferGeometry.call( this );

	this.type = '';

	this.parameters = {
		width: width,
		height: height,
		widthSegments: widthSegments,
		heightSegments: heightSegments
	};

	width = width || 1;
	height = height || 1;

	var width_half = width / 2;
	var height_half = height / 2;

	var gridX = Math.floor( widthSegments ) || 1;
	var gridY = Math.floor( heightSegments ) || 1;

	var gridX1 = gridX + 1;
	var gridY1 = gridY + 1;

	var segment_width = width / gridX;
	var segment_height = height / gridY;

	var ix, iy;

	// buffers

	var indices = [];
	var vertices = [];
	var normals = [];
	var uvs = [];

	// generate vertices, normals and uvs

	for ( iy = 0; iy < gridY1; iy ++ ) {

		var y = iy * segment_height - height_half;

		for ( ix = 0; ix < gridX1; ix ++ ) {

			var x = ix * segment_width - width_half;

			vertices.push( x, - y, 0 );

			normals.push( 0, 0, 1 );

			uvs.push( ix / gridX );
			uvs.push( 1 - ( iy / gridY ) );

		}

	}

	// indices

	for ( iy = 0; iy < gridY; iy ++ ) {

		for ( ix = 0; ix < gridX; ix ++ ) {

			var a = ix + gridX1 * iy;
			var b = ix + gridX1 * ( iy + 1 );
			var c = ( ix + 1 ) + gridX1 * ( iy + 1 );
			var d = ( ix + 1 ) + gridX1 * iy;

			// faces

			indices.push( a, b, d );
			indices.push( b, c, d );

		}

	}

	// build geometry

	this.setIndex( indices );
	this.addAttribute( 'position', new Float32BufferAttribute( vertices, 3 ) );
	this.addAttribute( 'normal', new Float32BufferAttribute( normals, 3 ) );
	this.addAttribute( 'uv', new Float32BufferAttribute( uvs, 2 ) );

}
103971
def _rewrite_geometry(geom, new_lines):
    

    new_geom = []
    x = 0
    y = 0
    for line in new_lines:
        moveto, endsat, lineto_cmds = line

        dx = moveto.x - x
        dy = moveto.y - y
        x = endsat.x
        y = endsat.y

        new_geom.append(9)  # move to, run_length = 1
        new_geom.append(zigzag(dx))
        new_geom.append(zigzag(dy))
        new_geom.extend(lineto_cmds)

    # write the lines back out to geom
    del geom[:]
    geom.extend(new_geom)
248089
private void buildVertexes()
	{
		vertexes.clear();
		if (controlPoints.size() == 0)
			return;

		double step = 1D / (precision + 1);
		double t = 0;
		vertexes.add(controlPoints.get(0));
		for (int i = 1; i <= precision; i++)
		{
			t = i * step;
			vertexes.add(i, interpolateAll(controlPoints, controlPoints.size() - 1, 0, t));
		}
		vertexes.add(controlPoints.get(controlPoints.size() - 1));

		dirty = false;
	}