1. 重要函数

def is_convex_and_ordered(self, points: NDArray[np.float64]) -> tuple[bool, str]

这个函数的作用是判断按照顺序排列的顶点是否构成凸集，并判断点是顺时针排列"CW"还是逆时针排列"CCW"

实现思路：按顺序取三个点o,a,bo,a,b，判断oa→\overrightarrow{oa}和ob→\overrightarrow{ob}的叉积，如果所有叉积同号则说明aa点在ob→\overrightarrow{ob}的外侧，那么所有内角都为凸角，同时根据叉积的正负还可以判断点是顺时针排列（负）还是逆时针排列（正）

def gen_inequal_global(self, vertex: NDArray[np.float64])-> tuple[NDArray[np.float64], NDArray[np.float64]]

此函数的作用是根据顶点生成半空间不等式Ax≤b\bm{Ax} \leq \bm{b}

实现思路：先判断顶点的凸性和排列顺序，统一为逆时针排列。随后按顺序遍历相邻的两个顶点，计算半空间表达式

每个超平面可以表达为a⊤(x−x0)=0\bm{a}^\top (\bm{x} - \bm{x}_0) = 0，即与x0\bm{x}_0的连线与a\bm{a}垂直的点，因此a\bm{a}为法向量；x0\bm{x}_0为超平面上的点。变换后为a⊤x=b\bm{a}^\top \bm{x} =\bm{b}，变为不等号即得到半空间

计算半空间的过程

  1. 求直线向量v=p2−p1=(x2−x1,y2−y1)\bm{v} = \bm{p}_2 - \bm{p}_1 = (x_2 - x_1 , y_2 - y_1)，向量指向顺时针方向
  2. 令v\bm{v}与a\bm{a}的叉乘结果为负，可以求连线左侧的法向向量。注意，对于凸多边形，由于表达式是≤\leq，因此法向量必须指向多边形外侧
  3. 用a⊤p1\bm{a}^\top \bm{p}_1求解b\bm{b}