Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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
like image 322
Serillan Avatar asked Dec 20 '12 20:12

Serillan


People also ask

How do you know if 4 points form a convex quadrilateral?

In order to know if a quadrilateral is convex or not, you can make a triangle of three points and see if the fourth point is located inside that triangle or not. If you manage finding one triangle, which contains the fourth point, then you don't have a convex quadrilateral.

What is the formula of convex quadrilateral?

Observing first the convex quadrilaterals we can see that the area of a convex quadrilateral can be expressed as the sum of the two areas divided by any of the diagonals, A(ABCD)=A(ABC)+A(CDA)=A(BCD)+A(DAB).

How many diagonals does a convex quadrilateral have * 2 points?

A convex quadrilateral is a four sided figure with interior angles of less than 180 degrees each and both of its diagonals contained within the shape.It has got two Diagonals. Was this answer helpful?

What is convex quadrilateral with example?

A trapezoid is a convex quadrilateral. If a quadrilateral does not have any parallel sides but has two sets of adjacent sides that are congruent, it is classified as a kite, and a kite is a convex quadrilateral. This quadrilateral is like the common toy kites that are sold for children.


1 Answers

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(n4); and the latter O((n2 + q) log n) (where q is the number of convex quadrilaterals). In the worst case q = Θ(n4) — 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
like image 118
Gareth Rees Avatar answered Oct 12 '22 22:10

Gareth Rees