The algorithm for finding all convex quadrangles from a given list of 2d points

Question

I need to make a program to find all convex quadrangles from a given list of 2d points. I tried it with vector cross-product, but it does not seem to be the right solution.

Maybe there is some effective algorithm for this problem, but I can not find it.

This is an example with inputs and outputs:

Enter

  Number of points:
 6

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

Exit

  The number of convex quadrangles:
 nine

Answer 1

A quadrangle is convex if its diagonals intersect. On the contrary, if two line segments intersect, then their four end points form a convex quadrangle.

Each pair of points gives you a line segment, and each intersection point between two segments corresponds to convex quadrangles.

You can find the intersection points using either a naive algorithm that compares all pairs of segments or the Bentley-Ottman algorithm . The first takes O (n ⁴ ); and the last O ((n ² + q) log n) (where q is the number of convex quadrangles). In the worst case, q = Θ (n ⁴ ) - consider n points on the circle, so Bentley-Ottmann is not always faster.

Here's a 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 

And the launch example:

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