Algorithm to find all convex quadrilaterals from the given list of 2d points

Question

I have to make a program to find all convex quadrilaterals from the given list of 2d points. I have tried it with vector cross product but it doesn't seem to be a correct solution.

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

This is an example case with inputs and outputs:

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

Do you mean convex polygons? I'm not clear why you are specifying a number of points if they're quadrilaterals (4 sided). — Tim Goodman, Dec 20 '12 at 20:49
Oh, it's the number of points in the subsequent list, is that it? — Tim Goodman, Dec 20 '12 at 20:50
At any rate, I think you can check if 4 points are the vertices of a convex quadrilateral by checking if the 4th point is outside the triangle defined by the first three points. — Tim Goodman, Dec 20 '12 at 20:51
Sorry for mistake, it is Number of convex quadrilaterals. Thx for advice. — Serillan, Dec 20 '12 at 21:10

score 10 · Accepted Answer · edited May 23 '17 at 12:05

A quadrilateral is convex if its diagonals intersect. Conversely, if two line segments intersect, then their four endpoints make a convex quadrilateral.

convex quadrilateral on left, non-convex on right

Every pair of points gives you a line segment, and every point of intersection between two line segments corresponds to a convex quadrilateral.

You can find the points of intersection using either the naïve algorithm that compares all pairs of segments, or the Bentley–Ottmann algorithm. The former takes O(n⁴); and the latter O((n² + q) log n) (where q is the number of convex quadrilaterals). In the worst case q = Θ(n⁴) — consider n points on a circle — so Bentley–Ottmann is not always faster.

Here's the naïve 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 an example run:

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

With your example, I get : ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all() — Ludo Schmidt, Jun 16 '21 at 14:56
@LudoSchmidt: You're probably using a version of NumPy that is newer than I was using in December 2012 — Gareth Rees, Jun 16 '21 at 15:03

Algorithm to find all convex quadrilaterals from the given list of 2d points

1 Answers1