ein Viereck konvex ist, wenn seine Diagonalen schneiden. Umgekehrt, wenn sich zwei Liniensegmente schneiden, bilden ihre vier Endpunkte ein konvexes Viereck.
jedes Paar von Punkten gibt Ihnen ein Liniensegment, und jeder Schnittpunkt zwischen zwei Liniensegmenten entspricht einem konvexen Vierecks.
Sie können die points of intersection entweder mit dem naiven Algorithmus, der alle Paare von Segmenten vergleicht, oder der Bentley–Ottmann algorithm finden. Das erstere nimmt O (n); und letztere O ((n + q) log n) (wobei q ist die Anzahl der konvexen Vierecke). Im schlimmsten Fall q = Θ (n) - betrachten n Punkte auf einem Kreis - so Bentley-Ottmann nicht immer schneller.
Hier ist die naive Version 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
Und ein Beispiel Lauf:
>>> points = map(np.array, [(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1)])
>>> len(list(convex_quadrilaterals(points)))
9
Haben Sie konvexe Polygone bedeuten? Ich bin nicht klar, warum Sie eine Anzahl von Punkten angeben, wenn sie Vierecke sind (4-seitig). –
Oh, es ist die Anzahl der Punkte in der folgenden Liste, ist es das? –
Auf jeden Fall, ich denke, Sie können überprüfen, ob 4 Punkte die Eckpunkte eines konvexen Vierecks sind, indem Sie überprüfen, ob der 4. Punkt außerhalb des durch die ersten drei Punkte definierten Dreiecks liegt. –