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

convex

简介

convex 是Polygon类的一个方法,用于计算给定点集的凸包。

语法

Polygon.convex(points)

参数

  • points:类型为数组,表示待计算凸包的点集。数组的每个元素都是一个由两个数字组成的数组,分别表示该点的 x 坐标和 y 坐标。例如 [[0,0], [1,1], [2,0]]

返回值

类型为数组,表示给定点集的凸包。数组的每个元素都是一个由两个数字组成的数组,分别表示该点的 x 坐标和 y 坐标。

例子

const points = [[0,0], [1,1], [2,0], [9,9], [4,4], [5,5], [6,4], [7,7]];
const convexHull = Polygon.convex(points);

console.log(convexHull);
// Output: [[0,0],[2,0],[9,9],[7,7]]

实现原理

凸包求解是计算几何中常见的问题,其基本思想是利用点集中的点来构造一个多边形,使得点集中的所有点都位于该多边形内部。

不同的求解算法会有不同的实现,这里简单介绍一种基于 Graham 扫描算法的实现方式。

  • 首先,选取点集中最左下角的点作为“起点”,并将剩下的点按照极角从小到大排序。
  • 从排序后的列表中选择一个点,如果该点在当前凸包中的右侧,则弹出栈顶,直到该点位于当前凸包左侧。将该点加入凸包中。重复此过程,直到遍历完整个排序后的点列表。
  • 最后弹出栈顶,保证凸包最后一个点与起点相同。

注意事项

  • convex 方法实现的凸包是不包括共线点的。对于包含共线点的点集,其凸包将与其他算法有所差异。

参考资料