Un quadrilatero convesso se relative diagonali si intersecano. Viceversa, se due segmenti di linea si intersecano, i loro quattro endpoint formano un quadrilatero convesso.
Ogni coppia di punti che dà un segmento di linea, e ogni punto di intersezione tra due segmenti di linea corrisponde ad un quadrilatero convesso.
È possibile trovare lo points of intersection utilizzando l'algoritmo naïve che confronta tutte le coppie di segmenti o lo Bentley–Ottmann algorithm. Il primo prende O (n); e quest'ultimo O ((n + q ) log n) (dove q è il numero di quadrilateri convessi). Nel peggiore dei casi q = Θ (n ) - considerare n punti su un cerchio - così Bentley-Ottmann non è sempre più veloce.
Ecco la versione ingenua in 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
E una corsa esempio:
>>> points = map(np.array, [(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1)])
>>> len(list(convex_quadrilaterals(points)))
9
fare vuoi dire poligoni convessi? Non sono chiaro perché stai specificando un numero di punti se sono quadrilateri (4 lati). –
Oh, è il numero di punti nella lista successiva, è così? –
In ogni caso, penso che puoi controllare se 4 punti sono i vertici di un quadrilatero convesso controllando se il 4 ° punto è fuori dal triangolo definito dai primi tre punti. –