AABB
AlignmentBehavior
ArriveBehavior
AStar
BFS
BoundingSphere
BVH
BVHNode
Cell
CellSpacePartitioning
CohesionBehavior
CompositeGoal
ConvexHull
Corridor
CostTable
DFS
Dijkstra
Edge
EntityManager
EvadeBehavior
EventDispatcher
Behavior
FollowPathBehavior
FuzzyAND
FuzzyCompositeTerm
FuzzyFAIRLY
FuzzyModule
FuzzyOR
FuzzyRule
FuzzySet
FuzzyTerm
FuzzyVariable
FuzzyVERY
GameEntity
Goal
GoalEvaluator
Graph
GraphUtils
HalfEdge
HeuristicPolicyDijkstra
HeuristicPolicyEuclid
HeuristicPolicyEuclidSquared
HeuristicPolicyManhattan
InterposeBehavior
LeftSCurveFuzzySet
LeftShoulderFuzzySet
LineSegment
Logger
MathUtils
Matrix3
Matrix4
MemoryRecord
MemorySystem
MeshGeometry
MessageDispatcher
MovingEntity
NavEdge
NavMesh
NavMeshLoader
NavNode
Node
NormalDistFuzzySet
OBB
ObstacleAvoidanceBehavior
OffsetPursuitBehavior
OnPathBehavior
Path
Plane
Polygon
Polyhedron
PriorityQueue
PursuitBehavior
Quaternion
Ray
RectangleTriggerRegion
Regular
RightSCurveFuzzySet
RightShoulderFuzzySet
SAT
SeekBehavior
SeparationBehavior
SingletonFuzzySet
Smoother
SphericalTriggerRegion
State
StateMachine
SteeringBehavior
SteeringManager
Task
TaskQueue
Telegram
Think
Time
TriangularFuzzySet
Trigger
TriggerRegion
Vector3
Vehicle
Version
WanderBehavior

fromPoints

fromPoints() 方法可以接受一组点,然后返回这些点组成的凸包。

语法

ConvexHull.fromPoints(points)

参数

points: 一个二维数组,包含一系列点的坐标。每个点需要包含两个数字,分别代表点在二维空间中的 xy 坐标。

返回值

fromPoints() 方法返回一个新的二维数组,其中包含凸包上的所有点坐标。

示例

const points = [
  [0, 0],
  [0, 1],
  [1, 1],
  [1, 0],
  [0.5, 0.5]
];

const convexHull = ConvexHull.fromPoints(points);

console.log(convexHull);
// [[0, 0], [0, 1], [1, 1], [1, 0]]

异常

当传递给 fromPoints() 方法的参数无效时,该方法将抛出一个 TypeError 异常。

实现详情

fromPoints() 方法使用 Graham's 扫描方法来计算凸包。该算法先找出所有点中最左边的点,然后将这个点作为凸包的起点。接下来,算法按照极角逆时针排序所有点,之后扫描这些点,如果扫过的点的向量与前两个点之间的向量不是右转,就把它加入到凸包段中。尽管 Graham's 扫描算法的时间复杂度在最坏情况下为 $O(n\log n)$,但只要不处于最坏情况,它的表现是相当不错的。