标签: convex-polygon

检测线是否与凸多边形相交的O(n)算法包括检查多边形的任何边是否与线相交,并查看交点的数量是奇数还是偶数.

是否存在渐近更快的算法,例如O(log n)算法？

我有一个三角网格.假设它看起来像一个凹凸不平的表面.我希望能够找到落在网格周围边缘的所有边缘.(忘记内顶点)

我知道我必须找到只连接到一个三角形的边缘,并将所有这些收集在一起,这就是答案.但我想确保这些边的顶点按顺时针顺序排列.

我想这样做是因为我想在网格外部得到一条多边形线.

我希望这很清楚,可以理解.在某种意义上,我试图"去三角化"网格.哈!如果有这样一个词.

我找到了一些解决方案,但它们太乱了.

鉴于凸多边形,我试图在保持其直径的同时增长其形状(如"最大区域").直径定义为可放置在多边形内的最长段的长度.由于多边形是凸的,我假设通过扫描所有顶点对总能找到这个直径.

例如,给定等边三角形作为输入多边形,三角形的直径是任何边的长度; 平滑这将导致3个圆段,如图所示

对于任意凸多边形,一种非常低效的算法是计算以每个多边形顶点为中心的最大直径半径圆的交点; 这就是我目前使用的(Java).有更好的吗？任何伪代码或指向算法的指针都将受到赞赏.

另一个例子:压扁的五边形及其相应的直径保持最大形状.这个想法是你不能在不增加直径的情况下增加这种形状的面积(也就是说,可以在比原始直径更长的形状范围内画出一条直线).在这种特殊情况下,似乎半径= polygon_diameter/2(粉红色)的单个圆优于半径= polygon_diameter(浅蓝色)的多个较大圆的交点.第二个图像叠加两个区域以使比较更容易,但区域应完全包围多边形.

假设我在6维空间中给出了一个点云,我可以根据需要进行密集.这些点变成位于低维多面体的表面上(即点矢量(x1,x2,... x6)看起来是共面的).

我想找到这个未知多面体的顶点,我当前的尝试通过Python中的scipy接口使用qhull算法.在开始时,我只会得到错误消息,显然是由较低维度输入和/或许多退化点引起的.我尝试了几种蛮力方法来消除退化点,但不是很成功,所以最后,我想所有这些点都必须位于凸壳上.

这个问题非常有用,因为它建议通过主成分分析减少尺寸.如果我将点投影到4D超平面,则qhull算法运行时没有错误(对于任何更高的维度,它不会运行).

from scipy.spatial import ConvexHull
from sklearn.decomposition import PCA

model = PCA(n_components=4).fit(initial_points)
proj_points = model.transform(initial_points)
hull = ConvexHull(proj_points, qhull_options = "Qx")

上述问题的答案提到,在计算出投影点的凸包后,需要将单纯形变换回来.但是qhull输出只包含索引,为什么这些索引与初始点的索引不匹配？

现在我的问题是我不知道使用哪种精度来实际获得正确的顶点.无论我对点云的密集程度如何,所获得的顶点随着精度的不同而不同.例如,对于(10000,6)数组中的初始点,我得到(其中E0.03是其工作的最大值):

hull1 = ConvexHull(proj_points, qhull_options = "Qx, E0.03")
print len(hull1.vertices)
print hull1.vertices

5
[ 437 2116 3978 7519 9381]

并将其绘制在轴0,1,2(其中蓝点代表初始点云的选择)的某些(非信息丰富的)投影中:

但是为了获得更高的精度(当然),我会得到一个不同的集合:

hull2 = ConvexHull(proj_points, qhull_options = "Qx, E0.003")
print len(hull2.vertices)
print hull2.vertices

29
[  74   75  436  437  756 1117 2116 2366 2618 2937 3297 3615 3616 3978 3979
 4340 4561 4657 4659 4924 …

我想检查一组N个点是否描述凸多边形

我想知道是否有一个好的算法呢？

以下是我想到的一些方法:

1.凸壳赫尔算法:

如果该集合等于他的凸包,那么它是凸的.这种算法的复杂性是O(n*LN(N)).但我感觉就像是在一个轮子上打破一只蝴蝶.

3.寻找角度:

然后我想到检查2个连续矢量的角度是否永远不会超过180°.但由于我的点数没有被排序,我需要检查3个连续点的所有组合,这就像O(n3)复杂度一样.(应该有一种比这更好的方法)

我尝试从右到左选择点,但结果并不总是预期的结果:

例如,在这种情况下,如果从左到右,我会发现凸形:

所以对于这个解决方案,我可能需要一个好的算法来选择点.

3.看着重心:

我认为检查所有3个连续点的中心是否在形状内部将告诉我形状是否凸出.

这就是我的意思(G是每个三角形的中心):

对于这个解决方案,我可以从左到右选择点没有问题.如果检查G是否在形状中的复杂性是O(N)那么总体复杂度将是O(N2).

你能告诉我一个好的算法来解决这个问题或改进我想到的解决方案

提前致谢

我最近问过这个问题,关于如何将凹多边形切割成凸多边形,我建议做三角剖分或多边形分区.

我正在使用的库(SFML\Box2D)只采用凸形.

这就是我想知道的:

1. 多边形分区或多边形的三角测量更快吗？

2. Polygon Partitioning如何工作/你是如何做到的？

不要忘记三角测量不需要凸起的形状......

有没有人知道一个相对快速的算法,用于将一组多边形分解为不同的重叠和非重叠区域,即给定一组n个多边形,找到它们中的所有不同区域？

例如,输入将是4个表示圆的多边形,如下所示

输出将是表示不同颜色的不同区域的所有多边形.

我可以使用多边形操作编写自己的实现,但算法可能会很慢且耗时.我想知道是否存在针对此类问题的任何优化算法.

我在飞机上有一组点,我想找到所有凸多边形而不包括它们内部的一个点.

例如,我想找到所有三角形,所有四个大小的多边形,所有四个五个大小的多边形,依此类推,直到可以找到它们而不包括它们内部的一个点.

在图像中,行a对应于大小为3的凸多边形.虽然第1列和第2列显示了我想要的正确示例,但第3列显示了一个三角形,其中包含两个点,我不想要它.

行b和c示出了尺寸为4和5的多边形的示例.

b3示出了非凸多边形的示例

我想知道MATLAB中是否有函数或任何其他语言,或者有人知道可以做到的算法.

除了点之外,算法可以接收要搜索的多边形的大小,它将返回所有可能正确的多边形,如果不包含该大小的任何多边形,则返回空.

我很感激帮助.

我正在尝试使用Scipy和ConvexHull库创建一个Convex Hull.据我所知,它叫QHull.

当我想要添加的点没有"全尺寸"时,会出现问题.例:

from scipy.spatial import ConvexHull
import numpy as np
points = np.append([[0,2]],[[2,0]],axis=0)
hull = ConvexHull(points)

有输出:

Traceback (most recent call last):
  File "C:/folder/vertices_scipy2.py", line 5, in <module>
hull = ConvexHull(points)
  File "scipy\spatial\qhull.pyx", line 2230, in scipy.spatial.qhull.ConvexHull.__init__ (scipy\spatial\qhull.c:20317)
  File "scipy\spatial\qhull.pyx", line 328, in scipy.spatial.qhull._Qhull.__init__ (scipy\spatial\qhull.c:3639)
QhullError: Qhull error

但是,如果我添加一个额外的点,那么凸包具有完整的尺寸:

from scipy.spatial import ConvexHull
import numpy as np
points = np.append([[0,0],[0,2]],[[2,0]],axis=0)
hull = ConvexHull(points)

一切正常.一个例子和另一个例子之间的区别(我做了很多其他的例子,所以我确定)是第一种情况下的凸包在二维空间中是1维的,而在第二种情况下是2二维空间中的维度(即全维度).

有任何想法吗？自从文档指出以来,我认为传递了一些qhull_options,因为在答案中已经提到:

QHullError当Qhull遇到错误条件时引发,例如当未启用要解析的选项时的几何退化.

但是,我已经阅读了QHull中的许多选项,但它们似乎都没有解决这个问题.我随机尝试了其中一些,收效甚微.

任何帮助都会有所帮助.我正在开发一个程序,可以创建数百个这样的船体,其中一些不是全维的.

我有一个 array V[1,2,....,n]，其中数组的每个元素代表坐标对 (x,y) 形式的凸多边形的顶点。

已知V[1]是具有最小 x 坐标的顶点，并且顶点V[1,2,....,n]按逆时针顺序排列，如 \xef\xac\x81gure 中所示。还假定顶点的 x 坐标都是不同的，顶点的 y 坐标也是不同的。\n

现在，我想找到具有最大 y 坐标值的顶点。我们都知道简单的 O(n) 方法，但是有可能在 O(log(n)) 中找到它吗？

我使用具有最小 x 坐标的顶点的信息V[1]在 O(log(n)) 时间内找到具有最大 x 坐标的顶点。但是是否可以实现最大 y 坐标呢？

谢谢您的帮助！

如何获得随机地理点[lat/long in decimal],放置在100米半径范围内的任何位置？圆的中心是另一个参考GeoPoint.有没有实现这个的函数/公式？

基本上我正在阅读我的Android设备的GPS输入,需要在设备周围生成随机的地理点[在我的设备中心的半径100米的圆圈].

请注意:数据库中没有预先存储的地理点.如上所述,我需要动态创建所有地理点.

我想解析以蓝色显示的以下多边形,从多边形中删除导致凹陷的所有点.

目前,我一直试图做的是:

• 从多边形中取出每个点
• 测试该点以查看它是否属于由该组的其余部分创建的多边形
• 如果为true则删除该点
• 如果错误保持重点

这在大多数情况下都有效,但在前一种情况下,(2,3)和(2,4)处的点都不会被删除.在这两种情况下,其中一个点将被删除,但另一个点将不依赖于传入数组的顺序.

我想知道的是:

1. 有没有办法测试,看看我正在处理的多边形是否恰好有这些情况之一(IE:连续3个故障点？)
   或
2. 有没有更简单的方法来创建凸多边形？

谢谢.