算法來尋找從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點

回答

相關問題