A corner can be an origin if the corner's orientation (a line between the two adjacent black squares) and
the line splitting the direction to the two connecting nodes are the same.
162146
boolean isCornerValidOrigin( Node candidate ) {
		candidate.putEdgesIntoList(edgeList);
		if( edgeList.size() != 2 ) {
			throw new RuntimeException("BUG! Should be a corner and have two edges");
		}

		Node a = edgeList.get(0);
		Node b = edgeList.get(1);

		// Find the average angle from the two vectors defined by the two connected nodes
		double dirA = Math.atan2(a.y-candidate.y, a.x-candidate.x);
		double dirB = Math.atan2(b.y-candidate.y, b.x-candidate.x);

		double dirAB = UtilAngle.boundHalf(dirA+UtilAngle.distanceCCW(dirA,dirB)/2.0);

		// Find the acute angle between the corner's orientation and the vector
		double acute = UtilAngle.distHalf(dirAB,candidate.orientation);

		return acute < Math.PI/4.0;
	}
617367
function middleInside (data, start, a, b) {
  var node = start,
    inside = false,
    px = (data[a] + data[b]) / 2,
    py = (data[a + 1] + data[b + 1]) / 2
  do {
    var p1 = node.i,
      p2 = node.next.i

    if (((data[p1 + 1] > py) !== (data[p2 + 1] > py)) &&
      (px < (data[p2] - data[p1]) * (py - data[p1 + 1]) / (data[p2 + 1] - data[p1 + 1]) + data[p1])) {
      inside = !inside
    }

    node = node.next
  } while (node !== start)

  return inside
}
1155947
def is_intersect(line_a, line_b):
    
    # Find the four orientations needed for general and special cases
    orientation_1 = orientation(line_a.endpoint_a, line_a.endpoint_b,
                                line_b.endpoint_a)
    orientation_2 = orientation(line_a.endpoint_a, line_a.endpoint_b,
                                line_b.endpoint_b)
    orientation_3 = orientation(line_b.endpoint_a, line_b.endpoint_b,
                                line_a.endpoint_a)
    orientation_4 = orientation(line_b.endpoint_a, line_b.endpoint_b,
                                line_a.endpoint_b)

    # General case
    if (orientation_1 != orientation_2 and orientation_3 != orientation_4):
        return True

    # Special cases
    if (orientation_1 == 0 and on_segment(line_a.endpoint_a, line_b.endpoint_a,
                                          line_a.endpoint_b)):
        return True
    if (orientation_2 == 0 and on_segment(line_a.endpoint_a, line_b.endpoint_b,
                                          line_a.endpoint_b)):
        return True
    if (orientation_3 == 0 and on_segment(line_b.endpoint_a, line_a.endpoint_a,
                                          line_b.endpoint_b)):
        return True
    if (orientation_4 == 0 and on_segment(line_b.endpoint_a, line_a.endpoint_b,
                                          line_b.endpoint_b)):
        return True

    return False
1352254
def a(self):
        '''
        

        '''
        a = Point(self.center)

        if self.xAxisIsMajor:
            a.x += self.majorRadius
        else:
            a.y += self.majorRadius
        return a
778037
private void boundaryAreaInteriorLine_(int half_edge, int id_a, int id_b,
			int cluster_index_b) {
		if (m_matrix[MatrixPredicate.BoundaryInterior] == 1)
			return;

		int parentage = m_topo_graph.getHalfEdgeParentage(half_edge);

		if ((parentage & id_a) != 0 && (parentage & id_b) != 0) {
			m_matrix[MatrixPredicate.BoundaryInterior] = 1;
			return;
		}

		if (m_matrix[MatrixPredicate.BoundaryInterior] != 0) {
			if (m_topo_graph.getHalfEdgeUserIndex(m_topo_graph
					.getHalfEdgePrev(m_topo_graph.getHalfEdgeTwin(half_edge)),
					m_visited_index) != 1) {
				int cluster = m_topo_graph.getHalfEdgeTo(half_edge);
				int clusterParentage = m_topo_graph
						.getClusterParentage(cluster);

				if ((clusterParentage & id_a) != 0) {
					int index = m_topo_graph.getClusterUserIndex(cluster,
							cluster_index_b);

					if ((clusterParentage & id_b) != 0 && (index % 2 == 0)) {
						assert (index != -1);
						m_matrix[MatrixPredicate.BoundaryInterior] = 0;
					}
				}
			}
		}
	}
1057124
private void boundaryAreaInteriorPoint_(int cluster, int id_a, int id_b) {
		if (m_matrix[MatrixPredicate.BoundaryInterior] == 0)
			return;

		int clusterParentage = m_topo_graph.getClusterParentage(cluster);

		if ((clusterParentage & id_a) != 0 && (clusterParentage & id_b) != 0) {
			m_matrix[MatrixPredicate.BoundaryInterior] = 0;
		}
	}
416338
Element<Corner> selectCornerToRemove(List<Point2D_I32> contour , ErrorValue sideError , boolean loops ) {
		if( list.size() <= 3 )
			return null;

		// Pick the side that if split would improve the overall score the most
		Element<Corner> target,end;

		// if it loops any corner can be split. If it doesn't look the end points can't be removed
		if( loops ) {
			target = list.getHead();
			end = null;
		} else {
			target = list.getHead().next;
			end = list.getTail();
		}

		Element<Corner> best = null;
		double bestScore = -Double.MAX_VALUE;

		while( target != end ) {
			Element<Corner> p = previous(target);
			Element<Corner> n = next(target);

			// just contributions of the corners in question
			double before = (p.object.sideError + target.object.sideError)/2.0 + cornerScorePenalty;
			double after = computeSideError(contour, p.object.index, n.object.index);

			if( before-after > bestScore ) {
				bestScore = before-after;
				best = target;
				sideError.value = after;
			}
			target = target.next;
		}

		return best;
	}
62037
def rotatePolygon(polygon, theta, origin=None):
    
    if origin is None:
        origin = np.mean(polygon, axis=0, dtype=polygon.dtype)
    #polygon = polygon.copy()
    polygon -= origin
    for n, corner in enumerate(polygon):
        polygon[n] = corner[0] * np.cos(theta) - corner[1] * np.sin(theta), corner[
            0] * np.sin(theta) + corner[1] * np.cos(theta)
    polygon += origin
    return polygon
307808
int selectCorner( GridInfo info ) {

		info.lookupGridCorners(cornerList);

		int bestCorner = -1;
		double bestScore = Double.MAX_VALUE;
		boolean bestIsCornerSquare = false;

		for (int i = 0; i < cornerList.size(); i++) {
			Node n = cornerList.get(i);

			boolean corner = isCornerValidOrigin(n);

			// If there are no corner points which are valid corners, then any corner can be the origin if
			// allowNoCorner is true
			if( corner || (allowNoCorner && !bestIsCornerSquare) ) {
				// sanity check the shape
				if( checkShape != null ) {
					if( i%2==0 ) {
						if( !checkShape.isValidShape(info.rows,info.cols)) {
							continue;
						}
					} else {
						if( !checkShape.isValidShape(info.cols,info.rows)) {
							continue;
						}
					}
				}

				// If the distance is to (0,0) pixel is smaller or this is a corner square and the other best
				// is not a corner square
				double distance = n.normSq();
				if( distance < bestScore || (!bestIsCornerSquare && corner )) {
					bestIsCornerSquare |= corner;
					bestScore = distance;
					bestCorner = i;
				}
			}
		}
		info.hasCornerSquare = bestIsCornerSquare;
		return bestCorner;
	}
362881
function(rect) {
        var minX = rect.origin.x,
            maxX = minX + rect.extent.x;
        var minY = rect.origin.y,
            maxY = minY + rect.extent.y;

        if (rect.extent.x < 0) {
            minX = maxX;
            maxX = rect.origin.x;
        }

        if (rect.extent.y < 0) {
            minY = maxY;
            maxY = rect.origin.y;
        }

        return (
            minX <= this.x && this.x < maxX &&
            minY <= this.y && this.y < maxY
        );
    }
882492
public void queryCorners(Point2D[] corners) {
		if ((corners == null) || (corners.length < 4))
			throw new IllegalArgumentException();
		if (corners[0] != null)
			corners[0].setCoords(xmin, ymin);
		else
			corners[0] = new Point2D(xmin, ymin);

		if (corners[1] != null)
			corners[1].setCoords(xmin, ymax);
		else
			corners[1] = new Point2D(xmin, ymax);

		if (corners[2] != null)
			corners[2].setCoords(xmax, ymax);
		else
			corners[2] = new Point2D(xmax, ymax);

		if (corners[3] != null)
			corners[3].setCoords(xmax, ymin);
		else
			corners[3] = new Point2D(xmax, ymin);
	}
1053223
function() {
        var geometry = this.feature.geometry;
        var bounds = geometry.getBounds();
        var center = bounds.getCenterLonLat();
        var originGeometry = new OpenLayers.Geometry.Point(
            center.lon, center.lat
        );
        var radiusGeometry = new OpenLayers.Geometry.Point(
            bounds.right, bounds.bottom
        );
        var radius = new OpenLayers.Feature.Vector(radiusGeometry);
        var resize = (this.mode & OpenLayers.Control.ModifyFeature.RESIZE);
        var reshape = (this.mode & OpenLayers.Control.ModifyFeature.RESHAPE);
        var rotate = (this.mode & OpenLayers.Control.ModifyFeature.ROTATE);

        radiusGeometry.move = function(x, y) {
            OpenLayers.Geometry.Point.prototype.move.call(this, x, y);
            var dx1 = this.x - originGeometry.x;
            var dy1 = this.y - originGeometry.y;
            var dx0 = dx1 - x;
            var dy0 = dy1 - y;
            if(rotate) {
                var a0 = Math.atan2(dy0, dx0);
                var a1 = Math.atan2(dy1, dx1);
                var angle = a1 - a0;
                angle *= 180 / Math.PI;
                geometry.rotate(angle, originGeometry);
            }
            if(resize) {
                var scale, ratio;
                // 'resize' together with 'reshape' implies that the aspect 
                // ratio of the geometry will not be preserved whilst resizing 
                if (reshape) {
                    scale = dy1 / dy0;
                    ratio = (dx1 / dx0) / scale;
                } else {
                    var l0 = Math.sqrt((dx0 * dx0) + (dy0 * dy0));
                    var l1 = Math.sqrt((dx1 * dx1) + (dy1 * dy1));
                    scale = l1 / l0;
                }
                geometry.resize(scale, originGeometry, ratio);
            }
        };
        radius._sketch = true;
        this.radiusHandle = radius;
        this.radiusHandle.renderIntent = this.vertexRenderIntent;
        this.layer.addFeatures([this.radiusHandle], {silent: true});
    }
633485
private void interiorAreaInteriorLine_(int half_edge, int id_a, int id_b) {
		if (m_matrix[MatrixPredicate.InteriorInterior] == 1)
			return;

		int faceParentage = m_topo_graph.getHalfEdgeFaceParentage(half_edge);
		int twinFaceParentage = m_topo_graph
				.getHalfEdgeFaceParentage(m_topo_graph
						.getHalfEdgeTwin(half_edge));

		if ((faceParentage & id_a) != 0 && (twinFaceParentage & id_a) != 0)
			m_matrix[MatrixPredicate.InteriorInterior] = 1;
	}
387525
private static int winding(Point2d a, Point2d b, Point2d c) {
        return (int) Math.signum((b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x));
    }
841030
function (origin) {
            if (origin == null) {
                return;
            }
            var /** @type {?} */ dir = this._getLayoutDirection();
            if ((dir == 'ltr' && origin <= 0) || (dir == 'rtl' && origin > 0)) {
                this._origin = 'left';
            }
            else {
                this._origin = 'right';
            }
        }
1106294
static boolean isOpenEdge( SquareNode node , int index ) {
		if( node.edges[index] == null )
			return false;
		int marker = node.edges[index].destination(node).graph;
		return marker == SquareNode.RESET_GRAPH;
	}
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;
	}