算法来寻找从2D点

我必须做出一个方案，以找到2D点的给定列表中的所有凸四边形的给定列表中的所有凸四边形。我已经尝试过与矢量交叉产品，但它似乎并不是一个正确的解决方案。算法来寻找从2D点

也许有一些有效的算法来这个问题，但我不能找到它。

这是一个示例情况下与输入和输出：

输入

 
Number of Points: 
6

 
coordinates of points (x,y): 
0 0 
0 1 
1 0 
1 1 
2 0 
2 1

输出

 
Number of convex quadrilaterals: 
9

来源

2012-12-20 Serillan

你的意思是凸多边形？我不清楚为什么你要指定一些点，如果他们是四边形（4面）。 –

哦，这是后续列表中的点数，是吗？ –

无论如何，我认为你可以检查4点是否是凸四边形的顶点，方法是检查第4点是否在前三点定义的三角形之外。 –

甲四边形是凸的，如果它的对角线交叉。相反，如果两条线段相交，则它们的四个端点构成一个凸四边形。

convex quadrilateral on left, non-convex on right

每对点的给你的线段，和两条线段之间的交叉的每一个点对应于凸四边形。

您可以使用比较所有段对的naïve算法或Bentley–Ottmann algorithm找到points of intersection。前者需要O（n ）;和后者O（（Ñ + q）日志Ñ）（其中q是凸四边形的数量）。在最坏的情况下q =Θ（Ñ ） - 考虑在圆上Ñ点 - 所以本特利-奥特曼并不总是快。

这里的幼稚版本的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

来源

2012-12-20 22:17:12

算法来寻找从2D点

回答

相关问题