c++ - 检测凸多边形的极值点

Question

如何获得从确定点看的凸多边形的极值点？我试图通过点角度来实现这一点，较小和较大的角度是极值点，但是当观察者更接近点时，这是无效的。

这是我的代码:

Vec2* bigger = &points[0]; // pointer to point with bigger angle
Vec2* smaller = &points[0]; // pointer to point with smaller angle

Vec2 observer = rayCenter;

// iterate through all points of polygon
for(unsigned u = 0 ; u < points.size() ; u++)
{
    Vec2 distance = observer - points[u];

    if(distance.angle() < (observer - *smaller).angle())
        smaller = &points[u];
    if(distance.angle() > (observer - *bigger).angle())
        bigger = &points[u];
}

结果:

其中蓝线是被排除的点和黄色的可取点。有解决此问题的最佳方法吗？

对不起我的英语。

Answer 1

多边形顶点 A 对于观察者的给定位置是极端，当且仅当多边形的所有其他点都位于在同一侧 observer-to-A 线(或者可能位于该线上)。

如果已知多边形是凸的，那么标准就大大简化了。无需分析多边形的所有 其他点。通过分析其两个直接邻居的位置，可以轻松识别极值点。

如果 A 是我们的候选点，P 和 N 是它在多边形中的相邻点(上一个和下一个)，那么 A 是一个极值点当且仅当 P 和 N 都位于观察者到 A 线的同一侧。

vec_of_A = A - observer; // observer-to-A vector
vec_of_P = P - observer;
vec_of_N = N - observer;

productP = vec_of_A.x * vec_of_P.y - vec_of_A.y * vec_of_P.x;
productN = vec_of_A.x * vec_of_N.y - vec_of_A.y * vec_of_N.x;

if (sign(productP) == sign(productN))
  // A is an extreme point
else
  // A is not an extreme point

如果 P 和/或 N 恰好位于观察者到 A 线上(取决于您认为极端的点个案)。