Converts a polygon to a planar straight line graph
16989
function polygonToPSLG(loops, options) {
  if(!Array.isArray(loops)) {
    throw new Error('poly-to-pslg: Error, invalid polygon')
  }
  if(loops.length === 0) {
    return {
      points: [],
      edges:  []
    }
  }

  options = options || {}

  var nested = true
  if('nested' in options) {
    nested = !!options.nested
  } else if(loops[0].length === 2 && typeof loops[0][0] === 'number') {
    //Hack:  If use doesn't pass in a loop, then try to guess if it is nested
    nested = false
  }
  if(!nested) {
    loops = [loops]
  }

  //First we just unroll all the points in the dumb/obvious way
  var points = []
  var edges = []
  for(var i=0; i<loops.length; ++i) {
    var loop = loops[i]
    var offset = points.length
    for(var j=0; j<loop.length; ++j) {
      points.push(loop[j])
      edges.push([ offset+j, offset+(j+1)%loop.length ])
    }
  }

  //Then we run snap rounding to clean up self intersections and duplicate verts
  var clean = 'clean' in options ? true : !!options.clean
  if(clean) {
    cleanPSLG(points, edges)
  }

  //Finally, we return the resulting PSLG
  return {
    points: points,
    edges:  edges
  }
}
897868
def extract_line(geom, dem, **kwargs):
    
    kwargs.setdefault('masked', True)

    coords_in = coords_array(geom)

    # Transform geometry into pixels
    f = lambda *x: ~dem.transform * x
    px = transform(f,geom)

    # Subdivide geometry segments if option is given
    interval = kwargs.pop('subdivide', 1)
    if interval is not None:
        px = subdivide(px, interval=interval)

    # Transform pixels back to geometry
    # to capture subdivisions
    f = lambda *x: dem.transform * (x[0],x[1])
    geom = transform(f,px)

    # Get min and max coords for windowing
    # Does not deal with edge cases where points
    # are outside of footprint of DEM

    coords_px = coords_array(px)
    mins = N.floor(coords_px.min(axis=0))
    maxs = N.ceil(coords_px.max(axis=0))

    window = tuple((int(mn),int(mx))
        for mn,mx in zip(mins[::-1],maxs[::-1]))

    aff = Affine.translation(*(-mins))

    f = lambda *x: aff * x
    px_to_extract = transform(f,px)

    band = dem.read(1, window=window, **kwargs)
    extracted = bilinear(band, px_to_extract)
    coords = coords_array(extracted)

    coords[:,:2] = coords_array(geom)
    return coords
807590
def to_polygon(self):
        
        x,y = self.corners.T
        vertices = PixCoord(x=x, y=y)
        return PolygonPixelRegion(vertices=vertices, meta=self.meta,
                                  visual=self.visual)
878640
def polygon(self, points, stroke=None, fill=None, stroke_width=1, disable_anti_aliasing=False):
        
        self.put(' <polygon points="')
        self.put(' '.join(['%s,%s' % p for p in points]))
        self.put('" stroke-width="')
        self.put(str(stroke_width))
        self.put('"')
        if fill:
            self.put(' fill="')
            self.put(fill)
            self.put('"')
        if stroke:
            self.put(' stroke="')
            self.put(stroke)
            self.put('"')
        if disable_anti_aliasing:
            self.put(' shape-rendering="crispEdges"')
        self.put('/>\n')
942739
function polygonSlice(polygon, cutEdges){
    if(cutEdges.length === 0){
		return [polygon];
    }
    if(cutEdges instanceof Array && cutEdges.length && cutEdges[0] instanceof Array && cutEdges[0].length===2 && cutEdges[0][0] instanceof Array){

        var polys = [polygon];

        for(var i=0; i<cutEdges.length; i++){
            var cutEdge = cutEdges[i];
            // Cut all polys
            for(var j=0; j<polys.length; j++){
                var poly = polys[j];
                var result = polygonSlice(poly, cutEdge);
                if(result){
                    // Found poly! Cut and quit
                    polys.splice(j,1);
                    polys.push(result[0],result[1]);
                    break;
                }
            }
        }

        return polys;
    } else {

        // Was given one edge
        var cutEdge = cutEdges;
        var i = polygon.indexOf(cutEdge[0]);
        var j = polygon.indexOf(cutEdge[1]);

        if(i !== -1 && j !== -1){
            return [polygonCopy(polygon, i,j),
                    polygonCopy(polygon, j,i)];
        } else {
            return false;
        }
    }
}
15886
def features_node_edge_graph(obj):
    
    points = {}
    features = obj['features']
    for feature in tqdm(obj['features']):
        for (lon, lat) in geojson.utils.coords(feature):
            points.setdefault((lon, lat), 0)
            points[(lon, lat)] += 1
    points = [p for (p, c) in points.items() if c > 1]
    features = [geojson.Point(p) for p in points]

    # For each feature, split it into "edge" features
    # that occur between every point.
    for f in tqdm(obj['features']):
        seqs = []
        seq = []
        for point in geojson.utils.coords(f):
            if len(seq) > 0:
                seq.append(point)
            if point in points:
                seq.append(point)
                if len(seq) > 1 and seq[0] in points:
                    seqs.append(seq)
                    seq = [point]
        for seq in seqs:
            features.append(geojson.Feature(geometry={"coordinates":seq, "type":f['geometry']['type']}, properties=f['properties'], type=f['type']))

    obj['features'] = features
    return obj
748549
function poly2path(polygon) {
  var pos = polygon.pos;
  var points = polygon.calcPoints;
  var result = 'M' + pos.x + ' ' + pos.y;
  result += 'M' + (pos.x + points[0].x) + ' ' + (pos.y + points[0].y);
  for (var i = 1; i < points.length; i++) {
    var point = points[i];
    result += 'L' + (pos.x + point.x) + ' ' + (pos.y + point.y);
  }
  result += 'Z';
  return result;
}
524505
function isOverlay_(obj) {
  var o = obj;
  if (isArray_(obj) && obj.length > 0) {
    o = obj[0];
  }
  if (isArray_(o) && o.length > 0) {
    o = o[0];
  }
  if (o instanceof G.LatLng || o instanceof G.Marker ||
  o instanceof G.Polyline ||
  o instanceof G.Polygon ||
  o instanceof G.LatLngBounds) {
    return true;
  }
  return false;
}
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.")
808844
private static Collection<Polygon> splitPolygonizer(Polygon polygon, LineString lineString) throws SQLException {
        LinkedList<LineString> result = new LinkedList<LineString>();
        ST_ToMultiSegments.createSegments(polygon.getExteriorRing(), result);
        result.add(lineString);
        int holes = polygon.getNumInteriorRing();
        for (int i = 0; i < holes; i++) {
            ST_ToMultiSegments.createSegments(polygon.getInteriorRingN(i), result);
        }
        // Perform union of all extracted LineStrings (the edge-noding process)  
        UnaryUnionOp uOp = new UnaryUnionOp(result);
        Geometry union = uOp.union();

        // Create polygons from unioned LineStrings  
        Polygonizer polygonizer = new Polygonizer();
        polygonizer.add(union);
        Collection<Polygon> polygons = polygonizer.getPolygons();

        if (polygons.size() > 1) {
            return polygons;
        }
        return null;
    }
857713
def multi_polygons_data(element):
    
    paths = element.split(datatype='array', dimensions=element.kdims)
    xs, ys = ([path[:, idx] for path in paths] for idx in (0, 1))
    holes = element.holes()
    xsh, ysh = [], []
    for x, y, multi_hole in zip(xs, ys, holes):
        xhs = [[h[:, 0] for h in hole] for hole in multi_hole]
        yhs = [[h[:, 1] for h in hole] for hole in multi_hole]
        array = np.column_stack([x, y])
        splits = np.where(np.isnan(array[:, :2].astype('float')).sum(axis=1))[0]
        arrays = np.split(array, splits+1) if len(splits) else [array]
        multi_xs, multi_ys = [], []
        for i, (path, hx, hy) in enumerate(zip(arrays, xhs, yhs)):
            if i != (len(arrays)-1):
                path = path[:-1]
            multi_xs.append([path[:, 0]]+hx)
            multi_ys.append([path[:, 1]]+hy)
        xsh.append(multi_xs)
        ysh.append(multi_ys)
    return xsh, ysh
232990
function splitPolygonByPlane (splane, polygon) {
  let result = {
    type: null,
    front: null,
    back: null
  }
  // cache in local lets (speedup):
  let vertices = polygon.vertices
  let numvertices = vertices.length
  if (plane.equals(polygon.plane, splane)) {
    result.type = 0
  } else {
    let hasfront = false
    let hasback = false
    let vertexIsBack = []
    let MINEPS = -EPS
    for (let i = 0; i < numvertices; i++) {
      let t = vec3.dot(splane, vertices[i]) - splane[3]
      let isback = (t < 0)
      vertexIsBack.push(isback)
      if (t > EPS) hasfront = true
      if (t < MINEPS) hasback = true
    }
    if ((!hasfront) && (!hasback)) {
      // all points coplanar
      let t = vec3.dot(splane, polygon.plane)
      result.type = (t >= 0) ? 0 : 1
    } else if (!hasback) {
      result.type = 2
    } else if (!hasfront) {
      result.type = 3
    } else {
      // spanning
      result.type = 4
      let frontvertices = []
      let backvertices = []
      let isback = vertexIsBack[0]
      for (let vertexindex = 0; vertexindex < numvertices; vertexindex++) {
        let vertex = vertices[vertexindex]
        let nextvertexindex = vertexindex + 1
        if (nextvertexindex >= numvertices) nextvertexindex = 0
        let nextisback = vertexIsBack[nextvertexindex]
        if (isback === nextisback) {
          // line segment is on one side of the plane:
          if (isback) {
            backvertices.push(vertex)
          } else {
            frontvertices.push(vertex)
          }
        } else {
          // line segment intersects plane:
          let point = vertex
          let nextpoint = vertices[nextvertexindex]
          let intersectionpoint = splitLineSegmentByPlane(splane, point, nextpoint)
          if (isback) {
            backvertices.push(vertex)
            backvertices.push(intersectionpoint)
            frontvertices.push(intersectionpoint)
          } else {
            frontvertices.push(vertex)
            frontvertices.push(intersectionpoint)
            backvertices.push(intersectionpoint)
          }
        }
        isback = nextisback
      } // for vertexindex
      // remove duplicate vertices:
      let EPS_SQUARED = EPS * EPS
      if (backvertices.length >= 3) {
        let prevvertex = backvertices[backvertices.length - 1]
        for (let vertexindex = 0; vertexindex < backvertices.length; vertexindex++) {
          let vertex = backvertices[vertexindex]
          if (vec3.squaredDistance(vertex, prevvertex) < EPS_SQUARED) {
            backvertices.splice(vertexindex, 1)
            vertexindex--
          }
          prevvertex = vertex
        }
      }
      if (frontvertices.length >= 3) {
        let prevvertex = frontvertices[frontvertices.length - 1]
        for (let vertexindex = 0; vertexindex < frontvertices.length; vertexindex++) {
          let vertex = frontvertices[vertexindex]
          if (vec3.squaredDistance(vertex, prevvertex) < EPS_SQUARED) {
            frontvertices.splice(vertexindex, 1)
            vertexindex--
          }
          prevvertex = vertex
        }
      }
      if (frontvertices.length >= 3) {
        result.front = poly3.fromPoints(frontvertices, polygon.plane)
      }
      if (backvertices.length >= 3) {
        result.back = poly3.fromPoints(backvertices, polygon.plane)
      }
    }
  }
  return result
}
850389
function polygonCopy(polygon, i,j,targetPoly){
    var p = targetPoly || [];
    polygonClear(p);
    if (i < j) {
        // Insert all vertices from i to j
        for(var k=i; k<=j; k++){
            p.push(polygon[k]);
        }

    } else {

        // Insert vertices 0 to j
        for(var k=0; k<=j; k++){
            p.push(polygon[k]);
        }

        // Insert vertices i to end
        for(var k=i; k<polygon.length; k++){
            p.push(polygon[k]);
        }
    }

    return p;
}
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);

    }
391089
function(polygon) {
            var result = {
                type: null,
                front: null,
                back: null
            };
            // cache in local vars (speedup):
            var planenormal = this.normal;
            var vertices = polygon.vertices;
            var numvertices = vertices.length;
            if (polygon.plane.equals(this)) {
                result.type = 0;
            } else {
                var EPS = CSG.Plane.EPSILON;
                var thisw = this.w;
                var hasfront = false;
                var hasback = false;
                var vertexIsBack = [];
                var MINEPS = -EPS;
                for (var i = 0; i < numvertices; i++) {
                    var t = planenormal.dot(vertices[i].pos) - thisw;
                    var isback = (t < 0);
                    vertexIsBack.push(isback);
                    if (t > EPS) hasfront = true;
                    if (t < MINEPS) hasback = true;
                }
                if ((!hasfront) && (!hasback)) {
                    // all points coplanar
                    var t = planenormal.dot(polygon.plane.normal);
                    result.type = (t >= 0) ? 0 : 1;
                } else if (!hasback) {
                    result.type = 2;
                } else if (!hasfront) {
                    result.type = 3;
                } else {
                    // spanning
                    result.type = 4;
                    var frontvertices = [],
                        backvertices = [];
                    var isback = vertexIsBack[0];
                    for (var vertexindex = 0; vertexindex < numvertices; vertexindex++) {
                        var vertex = vertices[vertexindex];
                        var nextvertexindex = vertexindex + 1;
                        if (nextvertexindex >= numvertices) nextvertexindex = 0;
                        var nextisback = vertexIsBack[nextvertexindex];
                        if (isback == nextisback) {
                            // line segment is on one side of the plane:
                            if (isback) {
                                backvertices.push(vertex);
                            } else {
                                frontvertices.push(vertex);
                            }
                        } else {
                            // line segment intersects plane:
                            var point = vertex.pos;
                            var nextpoint = vertices[nextvertexindex].pos;
                            var intersectionpoint = this.splitLineBetweenPoints(point, nextpoint);
                            var intersectionvertex = new CSG.Vertex(intersectionpoint);
                            if (isback) {
                                backvertices.push(vertex);
                                backvertices.push(intersectionvertex);
                                frontvertices.push(intersectionvertex);
                            } else {
                                frontvertices.push(vertex);
                                frontvertices.push(intersectionvertex);
                                backvertices.push(intersectionvertex);
                            }
                        }
                        isback = nextisback;
                    } // for vertexindex
                    // remove duplicate vertices:
                    var EPS_SQUARED = CSG.Plane.EPSILON * CSG.Plane.EPSILON;
                    if (backvertices.length >= 3) {
                        var prevvertex = backvertices[backvertices.length - 1];
                        for (var vertexindex = 0; vertexindex < backvertices.length; vertexindex++) {
                            var vertex = backvertices[vertexindex];
                            if (vertex.pos.distanceToSquared(prevvertex.pos) < EPS_SQUARED) {
                                backvertices.splice(vertexindex, 1);
                                vertexindex--;
                            }
                            prevvertex = vertex;
                        }
                    }
                    if (frontvertices.length >= 3) {
                        var prevvertex = frontvertices[frontvertices.length - 1];
                        for (var vertexindex = 0; vertexindex < frontvertices.length; vertexindex++) {
                            var vertex = frontvertices[vertexindex];
                            if (vertex.pos.distanceToSquared(prevvertex.pos) < EPS_SQUARED) {
                                frontvertices.splice(vertexindex, 1);
                                vertexindex--;
                            }
                            prevvertex = vertex;
                        }
                    }
                    if (frontvertices.length >= 3) {
                        result.front = new CSG.Polygon(frontvertices, polygon.shared, polygon.plane);
                    }
                    if (backvertices.length >= 3) {
                        result.back = new CSG.Polygon(backvertices, polygon.shared, polygon.plane);
                    }
                }
            }
            return result;
        }
473213
def polygon_bounds(points):
    ''''''
    (minx, miny) = (points[0][0], points[0][1])
    (maxx, maxy) = (minx, miny)
    for p in points:
        minx = min(minx, p[0])
        maxx = max(maxx, p[0])
        miny = min(miny, p[1])
        maxy = max(maxy, p[1])
    return (minx, miny, maxx-minx, maxy-miny)
872116
def smoothpolygon(document, coords):
	""
	
	element = document.createElement('path')
	path    = []
	points  = [(coords[i], coords[i+1]) for i  in range(0, len(coords), 2)]
	def pt(points):
		p = points
		n = len(points)
		for i in range(0, len(points)):
			a = p[(i-1) % n]
			b = p[i]
			c = p[(i+1) % n]

			yield lerp(a, b, 0.5), b, lerp(b, c, 0.5)
		
	for i, (A, B, C) in enumerate(pt(points)):
		if i == 0:
			path.append("M%s,%s Q%s,%s %s,%s" % (A[0], A[1], B[0], B[1], C[0], C[1]))
		else:
			path.append("T%s,%s" % (C[0], C[1]))
	
	path.append("z")

	element.setAttribute('d', ' '.join(path))
	return element