0

是否有任何方法或算法可以从外部（周长）确定区域的凸（或非凸）属性？

一种方法是在周长的每个点上绘制切线，并讨论这条线与周长点相交的次数。如果没有显示相交（对于周长的所有点），我们可以断定区域是凸的。在其他情况下，区域是非凸的。

第二种方法是确定周长每个点的内角，并讨论它是否大于180。如果周边至少有一个点存在，则该区域是非凸的，它的内角大于 180。

还有其他更简单的方法吗？

任何想法或解决方案将不胜感激，谢谢。

4

2 回答 2

3

这样做时要注意的一件事是，当您遍历凸多边形的边时，所有转弯都将指向同一侧。也就是说，如果您以逆时针方向遍历顶点，则所有转弯都将向左；如果您以顺时针方向遍历顶点，则所有转弯都将向右。如果您曾经观察到转向与观察到的任何其他人相反的一侧，那么您就知道您正在处理一个非凸多边形。如果所有的转弯都在一侧，那么它是一个凸多边形。

因此，您需要做的就是一次查看三个顶点，将它们称为v n、v n+1和v n+2。然后，您可以确定顶点v n+1位于连接v n和v n+2的线段的哪一侧。对于 CCW，v n+1应该在线段的右侧，对于 CW，它应该在左侧。另一个问题的答案提供了确定这一点的方法。

您应该解决其他实施细节（例如如何处理 n=N，多边形中的点数，但这应该为您提供一个开始的地方。

基于这种方法的实现将在 O(N) 时间和空间中运行。

更新：针对下面的问题，“非多边形区域怎么样”？一般来说，这要困难得多。从数学上讲，可以通过找到一条端点在区域内部但线段的某些部分在区域外部的线段来显示该区域是非凸的。我怀疑您正在寻找一种使用数字计算机实现此功能的方法，因此纯数学方法不实用。

因此，在问题变得棘手之前，您将不得不对类型区域提供某种约束。也就是说，您必须限制您的问题空间，以便诸如边界周长的奈奎斯特采样之类的事情不会错误地将非凸区域识别为凸区域。

假设您可以适当地限制问题，那么您可以提出的任何可以在数字计算机上实施的解决方案都必须近似该区域。您可以生成相关区域的分段线性近似值并运行上述算法，或者沿着区域边界选择适当的点集并计算它们的导数。每个连续的样本都应将切线的角度沿同一方向旋转一些增量。但同样，它会降低采样率。

If you have other information about the nature of any nonlinearities which comprise the boundary of your region, you may be able to symbolically demonstrate whether a segment of the boundary is convex. The problem then reduces to showing that it remains convex when joined to the adjacent sections, which again is going to be problem specific.

So, my suggestion is, for digital computer implementation, approximate as needed the boundary of the region by a polygon and run the method defined above on that approximation.

于 2013-08-01T19:19:40.730 回答
1

我使用的算法（在伪代码中）：

function isConvex(vertices[Count] V):
  convex = true
  if Count <= 3 return convex
  for N = 0 to Count while convex:
    // line segment between previous and subsequent vertices
    LineSegment segment1 = new LineSegment(
         V[(N + Count - 1) % Count], V[(N + 1) % Count]);
    // line segment between the point and any other point
    LineSegment segment2 = new LineSegment((V[N], V[N+2 % Count]);
    if not segment1.intersects(segment2) then convex = false;
  return convex

我不知道这是否比您已经尝试过的算法最佳或更简单。LineSegment.intersects() 方法已经存在，这使得它非常容易编写。

实际代码使用上一次迭代中的段 2 作为当前迭代的段 1，即使在伪代码中也可以更快但更复杂地编写。

而且，就其价值而言，该算法的原始代码是在一个不再存在的处理器上用汇编语言编写的，因此我不会提供实际代码；-)。

于 2013-08-01T16:09:49.000 回答