给定2D点列表，找出所有凸四边形的算法

Question

我需要编写一个程序来找到给定的2D点列表中的所有凸四边形。

我已经尝试使用向量叉积，但似乎不是正确的解决方案。

也许有一些有效的算法可以解决这个问题，但我找不到它。

以下是输入和输出的示例：

输入

点的数量：
6

点的坐标(x,y)：
0 0
0 1
1 0
1 1
2 0
2 1

输出

凸四边形的数量：
9

- Serillan

---

你的意思是凸多边形吗？如果它们是四边形，我不明白为什么要指定点的数量。 - Tim Goodman

哦，那就是后续列表中的点数了，是吗？ - Tim Goodman

无论如何，我认为您可以通过检查第四个点是否在由前三个点定义的三角形外部来检查4个点是否是凸四边形的顶点。 - Tim Goodman

抱歉出错了，应该是凸四边形的数量。感谢您的建议。 - Serillan

Answer 1

如果一个四边形的对角线相交，那么它是凸的。反之，如果两条线段相交，则它们的四个端点组成一个凸四边形。

每一对点都可以形成一条线段，而两条线段的交点则对应一个凸四边形。

你可以使用朴素算法比较所有线段对来找到交点，也可以使用Bentley-Ottmann算法。前者的时间复杂度为O(n⁴)；后者的时间复杂度为O((n² + q) log n)（其中q是凸四边形的数量）。在最坏情况下，q = Θ(n⁴)——考虑n个点在一个圆上——因此Bentley-Ottmann并不总是更快。

以下是Python的朴素版本：

import numpy as np
from itertools import combinations

def intersection(s1, s2):
    """
    Return the intersection point of line segments `s1` and `s2`, or
    None if they do not intersect.
    """
    p, r = s1[0], s1[1] - s1[0]
    q, s = s2[0], s2[1] - s2[0]
    rxs = float(np.cross(r, s))
    if rxs == 0: return None
    t = np.cross(q - p, s) / rxs
    u = np.cross(q - p, r) / rxs
    if 0 < t < 1 and 0 < u < 1:
        return p + t * r
    return None

def convex_quadrilaterals(points):
    """
    Generate the convex quadrilaterals among `points`.
    """
    segments = combinations(points, 2)
    for s1, s2 in combinations(segments, 2):
        if intersection(s1, s2) != None:
            yield s1, s2

并且一个运行示例：

>>> points = map(np.array, [(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1)])
>>> len(list(convex_quadrilaterals(points)))
9

- Gareth Rees

---

使用您的示例，我收到以下错误：ValueError: 一个由多个元素组成的数组的真值是不明确的。请使用a.any()或a.all()。 - Ludo Schmidt

@LudoSchmidt：你可能在使用比我2012年12月使用的NumPy版本更高的版本。 - Gareth Rees