实现内点

如果你有博伊德的书,你知道 CVXOPT OOQP

我也喜欢第一版 Numerical Optimization

可以通过两种方式实现:

如果你只有一个点,你将得到多边形的面积,然后检查在该点上有一条垂直线的n个三角形的面积和在两个连续点上的另外两个三角形的面积之和是否等于多边形的面积。如果这是真的,那点就在里面,否则就在外面。

如果你有很多点(比如说M点),你必须找出它是否在里面,你会在多边形里面找到一个点,然后把多边形分成n个三角形,在这个点上有一个垂直点,另外两个连续的点在多边形上(形成一条边)。您将有n条线,在前面选择的点上有一条垂直线,在多边形的每个点上有一个点。你要按角度顺时针排序。然后,您将有M条直线,其中一条垂直线位于选定的点上,另一条垂直线位于其中一个M点上。你会像第一个N一样把它们分类。然后,在o(N+M)中,对于M中的每个点,可以找到距离N最近的左右线(假设这些线是CenterAx和CenterAy)。下一步,你要找出它的点是否在三角形的中心轴上。可以在o(1)中检查三角形CenterAxAy的a是否等于area(CenterAxP)+area(CenterAyP)+area(AxAyP)。