从给定的2d点列表中找到所有凸四边形的算法

Question

我必须制作一个程序,从给定的2d点列表中找到所有凸四边形.我用矢量交叉产品尝试了它,但它似乎不是一个正确的解决方案.

也许这个问题有一些有效的算法,但我找不到它.

这是输入和输出的示例:

输入

__PRE__

__PRE__

产量

__PRE__

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