A line segment (edge) shape. These can be connected in chains or loops to
other edge shapes. The connectivity information is used to ensure correct
contact normals.
335392
function EdgeShape(v1, v2) {
  if (!(this instanceof EdgeShape)) {
    return new EdgeShape(v1, v2);
  }

  EdgeShape._super.call(this);

  this.m_type = EdgeShape.TYPE;
  this.m_radius = Settings.polygonRadius;

  // These are the edge vertices
  this.m_vertex1 = v1 ? Vec2.clone(v1) : Vec2.zero();
  this.m_vertex2 = v2 ? Vec2.clone(v2) : Vec2.zero();

  // Optional adjacent vertices. These are used for smooth collision.
  // Used by chain shape.
  this.m_vertex0 = Vec2.zero();
  this.m_vertex3 = Vec2.zero();
  this.m_hasVertex0 = false;
  this.m_hasVertex3 = false;
}
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)
386446
public void connectEndToEnd(SGraphSegment segment) {
		if (segment.getGraph() != getGraph()) {
			throw new IllegalArgumentException();
		}
		final SGraphPoint point = new SGraphPoint(getGraph());
		setEnd(point);
		segment.setEnd(point);

		final SGraph g = getGraph();
		assert g != null;
		g.updatePointCount(-1);
	}
492183
void selectConnections( Vertex target ) {
		// There needs to be at least two corners
		if( target.perpendicular.size() <= 1 )
			return;

//		if( target.index == 16 ) {
//			System.out.println("ASDSAD");
//		}
//		System.out.println("======= Connecting "+target.index);

		double bestError = Double.MAX_VALUE;
		List<Edge> bestSolution = target.connections.edges;

		// Greedily select one vertex at a time to connect to. findNext() looks at all possible
		// vertexes it can connect too and minimizes an error function based on projectively invariant features
		for (int i = 0; i < target.perpendicular.size(); i++) {
			Edge e = target.perpendicular.get(i);
			solution.clear();
			solution.add(e);

			double sumDistance = solution.get(0).distance;
			double minDistance = sumDistance;

			if( !findNext(i,target.parallel,target.perpendicular,Double.NaN,results) ) {
				continue;
			}

			solution.add(target.perpendicular.get(results.index));
			sumDistance += solution.get(1).distance;
			minDistance = Math.min(minDistance,solution.get(1).distance);

			// Use knowledge that solution[0] and solution[2] form a line.
			// Lines are straight under projective distortion
			if( findNext(results.index,target.parallel,target.perpendicular,solution.get(0).direction,results) ) {
				solution.add(target.perpendicular.get(results.index));
				sumDistance += solution.get(2).distance;
				minDistance = Math.min(minDistance,solution.get(2).distance);

				// Use knowledge that solution[1] and solution[3] form a line.
				if( findNext(results.index,target.parallel,target.perpendicular,solution.get(1).direction,results) ) {
					solution.add(target.perpendicular.get(results.index));
					sumDistance += solution.get(3).distance;
					minDistance = Math.min(minDistance,solution.get(3).distance);
				}
			}

			// Prefer closer valid sets of edges and larger sets.
			// the extra + minDistance was needed to bias it against smaller sets which would be more likely
			// to have a smaller average error. Division by the square of set/solution size biases it towards larger sets
			double error = (sumDistance+minDistance)/(solution.size()*solution.size());

//			System.out.println("  first="+solution.get(0).dst.index+"  size="+solution.size()+" error="+error);

			if( error < bestError ) {
				bestError = error;
				bestSolution.clear();
				bestSolution.addAll(solution);
			}
		}
	}
339023
static Shape shapeOf(List<Point2D> points) {
        Path2D path = new Path2D.Double();
        if (!points.isEmpty()) {
            path.moveTo(points.get(0).getX(), points.get(0).getY());
            for (Point2D point : points)
                path.lineTo(point.getX(), point.getY());
            path.closePath();
        }
        return path;
    }
736207
private static Point getEllipseIntersection(Shape shape,
                                                Line2D.Double line) {
        double angle = Math.atan2(line.y2 - line.y1,
                                  line.x2 - line.x1);
        double x = shape.getBounds2D().getWidth() / 2 * Math.cos(angle) + shape.getBounds2D().getCenterX();
        double y = shape.getBounds2D().getHeight() / 2 * Math.sin(angle) + shape.getBounds2D().getCenterY();
        Point p = new Point();
        p.setLocation(x,
                      y);
        return p;
    }
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
17411
def connect_edges_pd(graph):
    
    edges = graph.dframe()
    edges.index.name = 'graph_edge_index'
    edges = edges.reset_index()
    nodes = graph.nodes.dframe()
    src, tgt = graph.kdims
    x, y, idx = graph.nodes.kdims[:3]

    df = pd.merge(edges, nodes, left_on=[src.name], right_on=[idx.name])
    df = df.rename(columns={x.name: 'src_x', y.name: 'src_y'})

    df = pd.merge(df, nodes, left_on=[tgt.name], right_on=[idx.name])
    df = df.rename(columns={x.name: 'dst_x', y.name: 'dst_y'})
    df = df.sort_values('graph_edge_index').drop(['graph_edge_index'], axis=1)

    edge_segments = []
    for i, edge in df.iterrows():
        start = edge['src_x'], edge['src_y']
        end = edge['dst_x'], edge['dst_y']
        edge_segments.append(np.array([start, end]))
    return edge_segments
918840
function(model, opt) {

        opt = opt || {};

        var inbound = opt.inbound;
        var outbound = opt.outbound;
        if ((inbound === undefined) && (outbound === undefined)) {
            inbound = outbound = true;
        }

        // the final array of connected link models
        var links = [];
        // a hash table of connected edges of the form: [edgeId] -> true
        // used for quick lookups to check if we already added a link
        var edges = {};

        if (outbound) {
            joint.util.forIn(this.getOutboundEdges(model.id), function(exists, edge) {
                if (!edges[edge]) {
                    links.push(this.getCell(edge));
                    edges[edge] = true;
                }
            }.bind(this));
        }
        if (inbound) {
            joint.util.forIn(this.getInboundEdges(model.id), function(exists, edge) {
                // skip links that were already added
                // (those must be self-loop links)
                // (because they are inbound and outbound edges of the same two elements)
                if (!edges[edge]) {
                    links.push(this.getCell(edge));
                    edges[edge] = true;
                }
            }.bind(this));
        }

        // if `deep` option is `true`, check also all the links that are connected to any of the descendant cells
        if (opt.deep) {

            var embeddedCells = model.getEmbeddedCells({ deep: true });

            // in the first round, we collect all the embedded elements
            var embeddedElements = {};
            embeddedCells.forEach(function(cell) {
                if (cell.isElement()) {
                    embeddedElements[cell.id] = true;
                }
            });

            embeddedCells.forEach(function(cell) {
                if (cell.isLink()) return;
                if (outbound) {
                    joint.util.forIn(this.getOutboundEdges(cell.id), function(exists, edge) {
                        if (!edges[edge]) {
                            var edgeCell = this.getCell(edge);
                            var sourceId = edgeCell.source().id;
                            var targetId = edgeCell.target().id;

                            // if `includeEnclosed` option is falsy, skip enclosed links
                            if (!opt.includeEnclosed
                                && (sourceId && embeddedElements[sourceId])
                                && (targetId && embeddedElements[targetId])) {
                                return;
                            }

                            links.push(this.getCell(edge));
                            edges[edge] = true;
                        }
                    }.bind(this));
                }
                if (inbound) {
                    joint.util.forIn(this.getInboundEdges(cell.id), function(exists, edge) {
                        if (!edges[edge]) {
                            var edgeCell = this.getCell(edge);
                            var sourceId = edgeCell.source().id;
                            var targetId = edgeCell.target().id;

                            // if `includeEnclosed` option is falsy, skip enclosed links
                            if (!opt.includeEnclosed
                                && (sourceId && embeddedElements[sourceId])
                                && (targetId && embeddedElements[targetId])) {
                                return;
                            }

                            links.push(this.getCell(edge));
                            edges[edge] = true;
                        }
                    }.bind(this));
                }
            }, this);
        }

        return links;
    }
387767
private void connectToNeighbors(int x, int y ) {
		List<LineSegment2D_F32> lines = grid.get(x,y);

		Iterator<LineSegment2D_F32> iter = lines.iterator();
		while( iter.hasNext() )
		{
			LineSegment2D_F32 l = iter.next();
			boolean connected = false;

			if( connectTry(l,x+1,y) )
				connected = true;
			if( !connected && connectTry(l,x+1,y+1) )
				connected = true;
			if( !connected && connectTry(l,x,y+1) )
				connected = true;
			if( !connected && connectTry(l,x-1,y+1) )
				connected = true;

			// the line was added to the connecting grid
			// remove it to avoid double counting the line
			if( connected )
				iter.remove();
		}
	}
1326721
private void boundaryAreaExteriorLine_(int half_edge, int id_a, int id_b) {
		if (m_matrix[MatrixPredicate.BoundaryExterior] == 1)
			return;

		int parentage = m_topo_graph.getHalfEdgeParentage(half_edge);

		if ((parentage & id_a) != 0 && (parentage & id_b) == 0)
			m_matrix[MatrixPredicate.BoundaryExterior] = 1;

	}
737469
function (bounds, vertex, next, orthogonal)
	{
		var x = bounds.x;
		var y = bounds.y;
		var w = bounds.width;
		var h = bounds.height;
		
		var cx = x + w / 2;
		var cy = y + h / 2;

		var px = next.x;
		var py = next.y;

		// Special case for intersecting the diamond's corners
		if (cx == px)
		{
			if (cy > py)
			{
				return new mxPoint(cx, y); // top
			}
			else
			{
				return new mxPoint(cx, y + h); // bottom
			}
		}
		else if (cy == py)
		{
			if (cx > px)
			{
				return new mxPoint(x, cy); // left
			}
			else
			{
				return new mxPoint(x + w, cy); // right
			}
		}
		
		var tx = cx;
		var ty = cy;
		
		if (orthogonal)
		{
			if (px >= x && px <= x + w)
			{
				tx = px;
			}
			else if (py >= y && py <= y + h)
			{
				ty = py;
			}
		}
		
		// In which quadrant will the intersection be?
		// set the slope and offset of the border line accordingly
		if (px < cx)
		{
			if (py < cy)
			{
				return mxUtils.intersection(px, py, tx, ty, cx, y, x, cy);
			}
			else
			{
				return mxUtils.intersection(px, py, tx, ty, cx, y + h, x, cy);
			}
		}
		else if (py < cy)
		{
			return mxUtils.intersection(px, py, tx, ty, cx, y, x + w, cy);
		}
		else
		{
			return mxUtils.intersection(px, py, tx, ty, cx, y + h, x + w, cy);
		}
	}
895000
function CollideEdgeCircle(manifold, edgeA, xfA, circleB, xfB) {
  manifold.pointCount = 0;

  // Compute circle in frame of edge
  var Q = Transform.mulTVec2(xfA, Transform.mulVec2(xfB, circleB.m_p));

  var A = edgeA.m_vertex1;
  var B = edgeA.m_vertex2;
  var e = Vec2.sub(B, A);

  // Barycentric coordinates
  var u = Vec2.dot(e, Vec2.sub(B, Q));
  var v = Vec2.dot(e, Vec2.sub(Q, A));

  var radius = edgeA.m_radius + circleB.m_radius;

  // Region A
  if (v <= 0.0) {
    var P = Vec2.clone(A);
    var d = Vec2.sub(Q, P);
    var dd = Vec2.dot(d, d);
    if (dd > radius * radius) {
      return;
    }

    // Is there an edge connected to A?
    if (edgeA.m_hasVertex0) {
      var A1 = edgeA.m_vertex0;
      var B1 = A;
      var e1 = Vec2.sub(B1, A1);
      var u1 = Vec2.dot(e1, Vec2.sub(B1, Q));

      // Is the circle in Region AB of the previous edge?
      if (u1 > 0.0) {
        return;
      }
    }

    manifold.type = Manifold.e_circles;
    manifold.localNormal.setZero();
    manifold.localPoint.set(P);
    manifold.pointCount = 1;
    manifold.points[0].localPoint.set(circleB.m_p);

    // manifold.points[0].id.key = 0;
    manifold.points[0].id.cf.indexA = 0;
    manifold.points[0].id.cf.typeA = Manifold.e_vertex;
    manifold.points[0].id.cf.indexB = 0;
    manifold.points[0].id.cf.typeB = Manifold.e_vertex;
    return;
  }

  // Region B
  if (u <= 0.0) {
    var P = Vec2.clone(B);
    var d = Vec2.sub(Q, P);
    var dd = Vec2.dot(d, d);
    if (dd > radius * radius) {
      return;
    }

    // Is there an edge connected to B?
    if (edgeA.m_hasVertex3) {
      var B2 = edgeA.m_vertex3;
      var A2 = B;
      var e2 = Vec2.sub(B2, A2);
      var v2 = Vec2.dot(e2, Vec2.sub(Q, A2));

      // Is the circle in Region AB of the next edge?
      if (v2 > 0.0) {
        return;
      }
    }

    manifold.type = Manifold.e_circles;
    manifold.localNormal.setZero();
    manifold.localPoint.set(P);
    manifold.pointCount = 1;
    manifold.points[0].localPoint.set(circleB.m_p);

    // manifold.points[0].id.key = 0;
    manifold.points[0].id.cf.indexA = 1;
    manifold.points[0].id.cf.typeA = Manifold.e_vertex;
    manifold.points[0].id.cf.indexB = 0;
    manifold.points[0].id.cf.typeB = Manifold.e_vertex;
    return;
  }

  // Region AB
  var den = Vec2.dot(e, e);
  _ASSERT && common.assert(den > 0.0);
  var P = Vec2.combine(u / den, A, v / den, B);
  var d = Vec2.sub(Q, P);
  var dd = Vec2.dot(d, d);
  if (dd > radius * radius) {
    return;
  }

  var n = Vec2.neo(-e.y, e.x);
  if (Vec2.dot(n, Vec2.sub(Q, A)) < 0.0) {
    n.set(-n.x, -n.y);
  }
  n.normalize();

  manifold.type = Manifold.e_faceA;
  manifold.localNormal = n;
  manifold.localPoint.set(A);
  manifold.pointCount = 1;
  manifold.points[0].localPoint.set(circleB.m_p);

  // manifold.points[0].id.key = 0;
  manifold.points[0].id.cf.indexA = 0;
  manifold.points[0].id.cf.typeA = Manifold.e_face;
  manifold.points[0].id.cf.indexB = 0;
  manifold.points[0].id.cf.typeB = Manifold.e_vertex;
}
19380
def find_next_intersection(edges, i, e)
	    for j in i..(edges.count-1)
		e2 = edges[j][:edge]
		next if !e2 || e.connected?(e2)
		intersection = e.intersection(e2)
		return [intersection, j] if intersection
	    end
	    nil
	end
182506
boolean linesIntoCorners( int numLines, GrowQueue_I32 contourCorners ) {

		skippedCorners.reset();

		// this is the index in the contour of the previous corner.  When a new corner is found this is used
		// to see if the newly fit lines point to the same corner.  If that happens a corner is "skipped"
		int contourIndexPrevious = contourCorners.get(anchor0);
		for (int i = 1; i < numLines; i++) {
			LineGeneral2D_F64 line0 = lines.get(i - 1);
			LineGeneral2D_F64 line1 = lines.get(i);

			int cornerIndex = CircularIndex.addOffset(anchor0, i, contourCorners.size);
			boolean skipped = false;

//			System.out.println("  corner index "+cornerIndex);

			if (null == Intersection2D_F64.intersection(line0, line1, intersection)) {
				if( verbose ) System.out.println("  SKIPPING no intersection");
				// the two lines are parallel (or a bug earlier inserted NaN), so skip and remove one of them
				skipped = true;
			} else {

				int contourIndex = closestPoint(intersection);
				if( contourIndex != contourIndexPrevious ) {

					Point2D_I32 a = contour.get(contourIndexPrevious);
					Point2D_I32 b = contour.get(contourIndex);

					if( a.x == b.x && a.y == b.y ) {
						if( verbose ) System.out.println("  SKIPPING duplicate coordinate");
//						System.out.println("  duplicate "+a+" "+b);
						skipped = true;
					} else {
//						System.out.println("contourCorners[ "+cornerIndex+" ] = "+contourIndex);
						contourCorners.set(cornerIndex, contourIndex);
						contourIndexPrevious = contourIndex;
					}
				} else {
					if( verbose ) System.out.println("  SKIPPING duplicate corner index");
					skipped = true;
				}
			}

			if( skipped ) {
				skippedCorners.add( cornerIndex );
			}

		}
		// check the last anchor to see if there's a duplicate
		int cornerIndex = CircularIndex.addOffset(anchor0, numLines, contourCorners.size);
		Point2D_I32 a = contour.get(contourIndexPrevious);
		Point2D_I32 b = contour.get(contourCorners.get(cornerIndex));
		if( a.x == b.x && a.y == b.y ) {
			skippedCorners.add( cornerIndex );
		}

		// now handle all the skipped corners
		Arrays.sort(skippedCorners.data,0,skippedCorners.size);

		for (int i = skippedCorners.size-1; i >= 0; i--) {
			int index = skippedCorners.get(i);
			contourCorners.remove(index);

			if( anchor0 >= index ) {
				anchor0--;
			}
			if( anchor1 >= index ) {
				anchor1--;
			}
		}
//		cornerIndexes.size -= skippedCorners.size();

		numLines -= skippedCorners.size;
		for (int i = 0; i < numLines; i++) {
			int c0 = CircularIndex.addOffset(anchor0, i, contourCorners.size);
			int c1 = CircularIndex.addOffset(anchor0, i+1, contourCorners.size);
			a = contour.get(contourCorners.get(c0));
			b = contour.get(contourCorners.get(c1));

			if( a.x == b.x && a.y == b.y ) {
				throw new RuntimeException("Well I screwed up");
			}

		}

		return contourCorners.size()>=3;
	}
336312
private Shape combineSingle(Shape target, Shape missing, boolean subtract, int start) {
		Shape current = target;
		Shape other = missing;
		int point = start;
		int dir = 1;
		
		Polygon poly = new Polygon();
		boolean first = true;
		
		int loop = 0;
		
		// while we've not reached the same point
		float px = current.getPoint(point)[0];
		float py = current.getPoint(point)[1];
		
		while (!poly.hasVertex(px, py) || (first) || (current != target)) {
			first = false;
			loop++;
			if (loop > MAX_POINTS) {
				break;
			}
			
			// add the current point to the result shape
			poly.addPoint(px,py);
			if (listener != null) {
				listener.pointUsed(px,py);
			}

			// if the line between the current point and the next one intersect the
			// other shape work out where on the other shape and start traversing it's 
			// path instead
			Line line = getLine(current, px, py, rationalPoint(current, point+dir));
			HitResult hit = intersect(other, line);
			
			if (hit != null) {
				Line hitLine = hit.line;
				Vector2f pt = hit.pt;
				px = pt.x;
				py = pt.y;
				
				if (listener != null) {
					listener.pointIntersected(px,py);
				}
				
				if (other.hasVertex(px, py)) {
					point = other.indexOf(pt.x,pt.y);
					dir = 1;
					px = pt.x;
					py = pt.y;
					
					Shape temp = current;
					current = other;
					other = temp;
					continue;
				}
				
				float dx = hitLine.getDX() / hitLine.length();
				float dy = hitLine.getDY() / hitLine.length();
				dx *= EDGE_SCALE;
				dy *= EDGE_SCALE;
				
				if (current.contains(pt.x + dx, pt.y + dy)) {
					// the point is the next one, we need to take the first and traverse
					// the path backwards
					if (subtract) {
						if (current == missing) {
							point = hit.p2;
							dir = -1;
						} else {
							point = hit.p1;
							dir = 1;
						}
					} else {
						if (current == target) {
							point = hit.p2;
							dir = -1;
						} else {
							point = hit.p2;
							dir = -1;
						}
					}
					
					// swap the shapes over, we'll traverse the other one 
					Shape temp = current;
					current = other;
					other = temp;
				} else if (current.contains(pt.x - dx, pt.y - dy)) {
					if (subtract) {
						if (current == target) {
							point = hit.p2;
							dir = -1;
						} else {
							point = hit.p1;
							dir = 1;
						}
					} else {
						if (current == missing) {
							point = hit.p1;
							dir = 1;
						} else {
							point = hit.p1;
							dir = 1;
						}
					}
					
					// swap the shapes over, we'll traverse the other one 
					Shape temp = current;
					current = other;
					other = temp;
				} else {
					// give up
					if (subtract) {
						break;
					} else {
						point = hit.p1;
						dir = 1;
						Shape temp = current;
						current = other;
						other = temp;
						
						point = rationalPoint(current, point+dir);
						px = current.getPoint(point)[0];
						py = current.getPoint(point)[1];
					}
				}
			} else {
				// otherwise just move to the next point in the current shape
				point = rationalPoint(current, point+dir);
				px = current.getPoint(point)[0];
				py = current.getPoint(point)[1];
			}
		}

		poly.addPoint(px,py);
		if (listener != null) {
			listener.pointUsed(px,py);
		}
		
		return poly;
	}
766292
def segment_midpoints_by_vertices(self, vertices):
        

        segments = set()

        for vertex in vertices:
            neighbours = self.identify_vertex_neighbours(vertex)
            segments.update( min( tuple((vertex, n1)), tuple((n1, vertex))) for n1 in neighbours )

        segs = np.array(list(segments))

        new_midpoint_lonlats = self.segment_midpoints(segments=segs)

        return new_midpoint_lonlats