// ConvexHullFlat computes the convex hull of the geometry.
// A convex hull is the smallest convex geometry that contains
// all the points in the input coordinates
// Uses the Graham Scan algorithm
433555
func ConvexHullFlat(layout geom.Layout, coords []float64) geom.T {
	calc := convexHullCalculator{
		inputPts: coords,
		layout:   layout,
		stride:   layout.Stride(),
	}
	return calc.getConvexHull()
}
507869
func rayIntersect(p, s, e orb.Point) (intersects, on bool) {
	if s[0] > e[0] {
		s, e = e, s
	}

	if p[0] == s[0] {
		if p[1] == s[1] {
			// p == start
			return false, true
		} else if s[0] == e[0] {
			// vertical segment (s -> e)
			// return true if within the line, check to see if start or end is greater.
			if s[1] > e[1] && s[1] >= p[1] && p[1] >= e[1] {
				return false, true
			}

			if e[1] > s[1] && e[1] >= p[1] && p[1] >= s[1] {
				return false, true
			}
		}

		// Move the y coordinate to deal with degenerate case
		p[0] = math.Nextafter(p[0], math.Inf(1))
	} else if p[0] == e[0] {
		if p[1] == e[1] {
			// matching the end point
			return false, true
		}

		p[0] = math.Nextafter(p[0], math.Inf(1))
	}

	if p[0] < s[0] || p[0] > e[0] {
		return false, false
	}

	if s[1] > e[1] {
		if p[1] > s[1] {
			return false, false
		} else if p[1] < e[1] {
			return true, false
		}
	} else {
		if p[1] > e[1] {
			return false, false
		} else if p[1] < s[1] {
			return true, false
		}
	}

	rs := (p[1] - s[1]) / (p[0] - s[0])
	ds := (e[1] - s[1]) / (e[0] - s[0])

	if rs == ds {
		return false, true
	}

	return rs <= ds, false
}
1271185
func pointInPolygon(x float64, y float64, points []float64) bool {
	if len(points) < 8 { // 只有2个以上的点，才能组成闭合多边形
		return false
	}

	// 大致算法如下：
	// 把整个平面以给定的测试点为原点分两部分:
	// - y>0，包含(x>0 && y==0)
	// - y<0，包含(x<0 && y==0)
	// 依次扫描每一个点，当该点与前一个点处于不同部分时（即一个在 y>0 区，一个在 y<0 区），
	// 则判断从前一点到当前点是顺时针还是逆时针（以给定的测试点为原点），如果是顺时针 r++，否则 r--。
	// 结果为：2==abs(r)。

	r := 0
	x1, y1 := points[0], points[1]
	prev := (y1 > y) || ((x1 > x) && (y1 == y))
	for i := 2; i < len(points); i += 2 {
		x2, y2 := points[i], points[i+1]
		curr := (y2 > y) || ((x2 > x) && (y2 == y))

		if curr == prev {
			x1, y1 = x2, y2
			continue
		}

		mul := (x1-x)*(y2-y) - (x2-x)*(y1-y)
		if mul > 0 {
			r++
		} else if mul < 0 {
			r--
		}
		x1, y1 = x2, y2
		prev = curr
	}

	return r == 2 || r == -2
}
231087
func (s *Surface) GradientAt(point *Point) *Point {
	if !s.bound.Contains(point) {
		return NewPoint(0, 0)
	}

	xi, yi, deltaX, deltaY := s.gridCoordinate(point)

	xi1 := xi + 1
	if limit := s.Width - 1; xi1 > limit {
		xi = limit - 1
		xi1 = limit
		deltaX = 1.0
	}

	yi1 := yi + 1
	if limit := s.Height - 1; yi1 > limit {
		yi = limit - 1
		yi1 = limit
		deltaY = 1.0
	}

	u1 := s.Grid[xi][yi]*(1-deltaX) + s.Grid[xi1][yi]*deltaX
	u2 := s.Grid[xi][yi1]*(1-deltaX) + s.Grid[xi1][yi1]*deltaX

	w1 := (1 - deltaY) * (s.Grid[xi1][yi] - s.Grid[xi][yi])
	w2 := deltaY * (s.Grid[xi1][yi1] - s.Grid[xi][yi1])

	return NewPoint((w1+w2)/s.gridBoxWidth(), (u2-u1)/s.gridBoxHeight())
}
1341031
def is_convex(mesh):
    
    # don't consider zero- area faces
    nonzero = mesh.area_faces > tol.merge

    # adjacencies with two nonzero faces
    adj_ok = nonzero[mesh.face_adjacency].all(axis=1)

    # make threshold of convexity scale- relative
    threshold = tol.planar * mesh.scale
    # if projections of vertex onto plane of adjacent
    # face is negative, it means the face pair is locally
    # convex, and if that is true for all faces the mesh is convex
    convex = bool(mesh.face_adjacency_projections[adj_ok].max() < threshold)

    return convex
541260
func (c Cell) distanceInternal(targetXYZ Point, toInterior bool) s1.ChordAngle {
	// All calculations are done in the (u,v,w) coordinates of this cell's face.
	target := faceXYZtoUVW(int(c.face), targetXYZ)

	// Compute dot products with all four upward or rightward-facing edge
	// normals. dirIJ is the dot product for the edge corresponding to axis
	// I, endpoint J. For example, dir01 is the right edge of the Cell
	// (corresponding to the upper endpoint of the u-axis).
	dir00 := target.X - target.Z*c.uv.X.Lo
	dir01 := target.X - target.Z*c.uv.X.Hi
	dir10 := target.Y - target.Z*c.uv.Y.Lo
	dir11 := target.Y - target.Z*c.uv.Y.Hi
	inside := true
	if dir00 < 0 {
		inside = false // Target is to the left of the cell
		if c.vEdgeIsClosest(target, false) {
			return edgeDistance(-dir00, c.uv.X.Lo)
		}
	}
	if dir01 > 0 {
		inside = false // Target is to the right of the cell
		if c.vEdgeIsClosest(target, true) {
			return edgeDistance(dir01, c.uv.X.Hi)
		}
	}
	if dir10 < 0 {
		inside = false // Target is below the cell
		if c.uEdgeIsClosest(target, false) {
			return edgeDistance(-dir10, c.uv.Y.Lo)
		}
	}
	if dir11 > 0 {
		inside = false // Target is above the cell
		if c.uEdgeIsClosest(target, true) {
			return edgeDistance(dir11, c.uv.Y.Hi)
		}
	}
	if inside {
		if toInterior {
			return s1.ChordAngle(0)
		}
		// Although you might think of Cells as rectangles, they are actually
		// arbitrary quadrilaterals after they are projected onto the sphere.
		// Therefore the simplest approach is just to find the minimum distance to
		// any of the four edges.
		return minChordAngle(edgeDistance(-dir00, c.uv.X.Lo),
			edgeDistance(dir01, c.uv.X.Hi),
			edgeDistance(-dir10, c.uv.Y.Lo),
			edgeDistance(dir11, c.uv.Y.Hi))
	}

	// Otherwise, the closest point is one of the four cell vertices. Note that
	// it is *not* trivial to narrow down the candidates based on the edge sign
	// tests above, because (1) the edges don't meet at right angles and (2)
	// there are points on the far side of the sphere that are both above *and*
	// below the cell, etc.
	return minChordAngle(c.vertexChordDist2(target, false, false),
		c.vertexChordDist2(target, true, false),
		c.vertexChordDist2(target, false, true),
		c.vertexChordDist2(target, true, true))
}
734956
func ChordAngleFromAngle(a Angle) ChordAngle {
	if a < 0 {
		return NegativeChordAngle
	}
	if a.isInf() {
		return InfChordAngle()
	}
	l := 2 * math.Sin(0.5*math.Min(math.Pi, a.Radians()))
	return ChordAngle(l * l)
}
1249705
func (s VertexSet) Contains(v int) bool {
	switch {
	case s.set == nil:
		return true
	case len(s.set) == 0 || v < s.set[0].a:
		return false
	}
	// The smallest index i such that v < set[i].a
	i := sort.Search(len(s.set), func(i int) bool {
		return v < s.set[i].a
	})
	if v >= s.set[i-1].b {
		return false
	}
	return true
}
752660
func (a *ArgType) convext(prefix string, f *Field, t *Field) string {
	expr := prefix + "." + f.Name
	if f.Type == t.Type {
		return expr
	}

	ft := f.Type
	if strings.HasPrefix(ft, "sql.Null") {
		expr = expr + "." + f.Type[8:]
		ft = strings.ToLower(f.Type[8:])
	}

	if t.Type != ft {
		expr = t.Type + "(" + expr + ")"
	}

	return expr
}
850437
func FlatTop(L int) []float64 {
	const (
		alpha0 = float64(0.21557895)
		alpha1 = float64(0.41663158)
		alpha2 = float64(0.277263158)
		alpha3 = float64(0.083578947)
		alpha4 = float64(0.006947368)
	)

	r := make([]float64, L)

	if L == 1 {
		r[0] = 1
		return r
	}

	N := L - 1
	coef := 2 * math.Pi / float64(N)

	for n := 0; n <= N; n++ {
		factor := float64(n) * coef

		term0 := alpha0
		term1 := alpha1 * math.Cos(factor)
		term2 := alpha2 * math.Cos(2*factor)
		term3 := alpha3 * math.Cos(3*factor)
		term4 := alpha4 * math.Cos(4*factor)

		r[n] = term0 - term1 + term2 - term3 + term4
	}

	return r
}
935293
func (aabb *AABB) ContainsVect(v vect.Vect) bool {
	return aabb.Lower.X <= v.X &&
		aabb.Upper.X >= v.X &&
		aabb.Lower.Y <= v.Y &&
		aabb.Upper.Y >= v.Y
}
1070270
def convexhull(data, col, fill=True, point_size=4):
    
    from geoplotlib.layers import ConvexHullLayer
    _global_config.layers.append(ConvexHullLayer(data, col, fill, point_size))
1087580
func (nm *nelderMead) checkIteration(vertices vertices) bool {
	// this will never be true for += inf
	if math.Abs(vertices[0].result-nm.config.Target) < delta {
		return false
	}

	best := vertices[0]
	// here we are checking distance convergence.  If all vertices
	// are near convergence, that is they are all within some delta
	// from the expected value, we can go ahead and quit early.  This
	// can only be performed on convergence checks, not for finding
	// min/max.
	if !isInf(nm.config.Target) {
		for _, v := range vertices[1:] {
			if math.Abs(best.distance-v.distance) >= delta {
				return true
			}
		}
	}

	// next we want to check to see if the changes in our polytopes
	// dip below some threshold.  That is, we want to look at the
	// euclidean distances between the best guess and all the other
	// guesses to see if they are converged upon some point.  If
	// all of the vertices have converged close enough, it may be
	// worth it to cease iteration.
	for _, v := range vertices[1:] {
		if best.euclideanDistance(v) >= delta {
			return true
		}
	}

	return false
}
834955
func QuatBetweenVectors(start, dest Vec3) Quat {
	// http://www.opengl-tutorial.org/intermediate-tutorials/tutorial-17-quaternions/#I_need_an_equivalent_of_gluLookAt__How_do_I_orient_an_object_towards_a_point__
	// https://github.com/g-truc/glm/blob/0.9.5/glm/gtx/quaternion.inl#L225
	// https://bitbucket.org/sinbad/ogre/src/d2ef494c4a2f5d6e2f0f17d3bfb9fd936d5423bb/OgreMain/include/OgreVector3.h?at=default#cl-654

	start = start.Normalize()
	dest = dest.Normalize()
	epsilon := float32(0.001)

	cosTheta := start.Dot(dest)
	if cosTheta < -1.0+epsilon {
		// special case when vectors in opposite directions:
		// there is no "ideal" rotation axis
		// So guess one; any will do as long as it's perpendicular to start
		axis := Vec3{1, 0, 0}.Cross(start)
		if axis.Dot(axis) < epsilon {
			// bad luck, they were parallel, try again!
			axis = Vec3{0, 1, 0}.Cross(start)
		}

		return QuatRotate(math.Pi, axis.Normalize())
	}

	axis := start.Cross(dest)
	s := float32(math.Sqrt(float64(1.0+cosTheta) * 2.0))

	return Quat{
		s * 0.5,
		axis.Mul(1.0 / s),
	}
}
700345
func Mat3x2FromRows(row0, row1, row2 Vec2) Mat3x2 {
	return Mat3x2{row0[0], row1[0], row2[0], row0[1], row1[1], row2[1]}
}
755020
func FloatAtLeast(min float64) schema.SchemaValidateFunc {
	return func(i interface{}, k string) (s []string, es []error) {
		v, ok := i.(float64)
		if !ok {
			es = append(es, fmt.Errorf("expected type of %s to be float", k))
			return
		}

		if v < min {
			es = append(es, fmt.Errorf("expected %s to be at least (%f), got %f", k, min, v))
			return
		}

		return
	}
}
1242928
func (rot *Rotation) RotateVect(v vect.Vect) vect.Vect {
	return vect.Vect{
		X: (v.X * rot.C) - (v.Y * rot.S),
		Y: (v.X * rot.S) + (v.Y * rot.C),
	}
}