算法找出从2D点的给定列表中的所有凸四边形

问题描述

我必须做出一个程序，找出从2D点的给定列表中的所有凸四边形。我曾试图与向量跨产品，但它似乎并没有成为一个正确的解决办法。

也许有一些有效的算法来这个问题，但我不能找到它。

这是一个例子例输入和输出：

输入

点数：
6

后坐标点（X，Y）的：
0 0
0 1
1 0
1 1
2 0
2 1

输出

凸四边形的数量：
9

解决方案

一个四边形是凸的，如果它的对角线相交。相反地​​，如果两条线段相交，则他们的四个端点作出的凸四边形。

每对点方式可以提供一个线段，和两条线段之间的每个交叉点对应的凸四边形。

您可以找到交集的点使用无论是天真的算法比较所有对段，或宾利奥特曼算法。前者需要O（ N 的）;而后者为O（（的 N 的 + 问：的）记录的 N 的）（其中的问：是凸四边形的数量）。在最坏的情况下的问：的=Θ（ N 的） - 考虑的在正圆n 的点 - 所以Bentley-奥特曼并不总是快

这里的幼稚版本的Python：

进口numpy的为NP从itertools进口组合高清相交点（S1，S2）：        返回交集的线段点`s1`和`s2`，或    没有，如果他们不相交。        P，R = S1 [0]，S1 [1] - S1 [0]    Q，S = s2的[0]，S2 [1] - S2 [0]    RXS =浮动（np.cross（R，S））    如果RXS == 0：返回None    T = np.cross（Q - P，S）/ RXS    U = np.cross（Q - P，R）/ RXS    如果0℃ T＆LT; 1和0℃下U＆LT; 1：        返回P + T *ṛ    返回None高清convex_quadrilaterals（点）：        生成之中`points`凸四边形。        段=组合（分2）    对于S1，S2在组合（段2）：        如果交叉点（S1，S2）=无！：            收率S1，S2

和一个例子运行：

＆GT;＆GT;＆GT;点=地图（np.array，[（0,0），（0,1），（1,0），（1,1），（2,0），（2，1）]）＆GT;＆GT;＆GT; LEN（名单（convex_quadrilaterals（点）））9

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

解决方案

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

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

这篇关于算法找出从2D点的给定列表中的所有凸四边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！