Thuật toán để tìm tất cả các tứ giác lồi từ danh sách 2d điểm

Question

Tôi phải thực hiện một chương trình để tìm tất cả các tứ giác lồi từ danh sách 2d đã cho. Tôi đã thử nó với sản phẩm vector chéo nhưng nó không có vẻ là một giải pháp đúng.

Có thể có một số thuật toán hiệu quả cho vấn đề này nhưng tôi không thể tìm thấy nó.

Đây là một trường hợp ví dụ với các đầu vào và đầu ra:

Input

 
Number of Points: 
6 

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

Output

 
Number of convex quadrilaterals: 
9 

Answer 1

Một tứ giác là lồi nếu đường chéo của nó giao nhau. Ngược lại, nếu hai đoạn thẳng cắt nhau thì bốn điểm cuối của chúng tạo thành tứ giác lồi.

Mỗi cặp điểm cung cấp cho bạn một đoạn thẳng, và tất cả các điểm giao nhau giữa hai đoạn thẳng tương ứng với một tứ giác lồi.

Bạn có thể tìm thấy points of intersection bằng cách sử dụng thuật toán ngây thơ so sánh tất cả các cặp phân đoạn hoặc Bentley–Ottmann algorithm. Tên cũ lấy O (n); và O sau ((n + q) đăng n) (nơi q là số tứ giác lồi). Trong trường hợp xấu nhất q = Θ (n ) - xem xét n điểm trên một vòng tròn - vì vậy Bentley-Ottmann không phải lúc nào cũng nhanh hơn.

Dưới đây là phiên bản ngây thơ bằng 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 

Và một ví dụ chạy:

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