我必须编写一个程序来从给定的二维点列表中找到所有凸四边形。我已经尝试过使用矢量叉积,但它似乎不是一个正确的解决方案。
也许有一些有效的算法可以解决这个问题,但我找不到。
这是一个带有输入和输出的示例:
输入
点数: 6
点坐标(x,y): 0 0 0 1 1 0 1 1 2 0 2 1
输出
凸四边形的数量: 9
我必须编写一个程序来从给定的二维点列表中找到所有凸四边形。我已经尝试过使用矢量叉积,但它似乎不是一个正确的解决方案。
也许有一些有效的算法可以解决这个问题,但我找不到。
这是一个带有输入和输出的示例:
输入
点数: 6
点坐标(x,y): 0 0 0 1 1 0 1 1 2 0 2 1
输出
凸四边形的数量: 9
一个四边形是凸的,如果它的对角线相交。相反,如果两条线段相交,则它们的四个端点构成一个凸四边形。
每对点都给你一条线段,两条线段之间的每个交点对应一个凸四边形。
您可以使用比较所有线段对的朴素算法或Bentley-Ottmann 算法找到交点。前者取 O( n 4 );和后者 O(( n 2 + q ) log n ) (其中q是凸四边形的数量)。在最坏的情况下q = Θ( n 4 )——考虑一个圆上的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