标签: computational-geometry

我有一个凸多边形P1的N点.该多边形可以是任何形状或比例(只要它仍然是凸的).

我需要P2使用原始多边形几何计算另一个多边形,但是"扩展"给定数量的单位.算法可以用于扩展凸多边形？

我正在寻找一种算法来解决这个问题:

给定笛卡尔坐标上的N个矩形,找出这些矩形的交集是否为空.每个矩形可以位于任何方向(不必使其边缘平行于Ox和Oy)

你有什么建议可以解决这个问题吗？:)我可以考虑测试每个矩形对的交集.但是,它是O(N*N)并且非常慢:(

这个问题在这里已经有了答案:
Point in Polygon aka hit test
C#Point in polygon

给定在笛卡尔坐标系中用N线方程组成的随机多边形,是否有任何标准公式用于检查点(x,y)的隶属度？

简单的解决办法是让所有的线公式和检查点X这条线之下,高于线和其他线路,等权但这可能会是乏味的.

我应该注意,多边形可以是任何形状,具有任意数量的边,并且可以是凹的或凸的.

为方便起见,我已经添加了这些实用功能:

float slope(CGPoint p1, CGPoint p2)
{
    return (p2.y - p1.y) / (p2.x - p1.x);
}

CGPoint pointOnLineWithY(CGPoint p, float m, float y)
{
    float x = (y - p.y)/m + p.x;
    return CGPointMake(x,y);
}

CGPoint pointOnLineWithX(CGPoint p, float m, float x)
{
    float y = m*(x - p.x) + p.y;
    return CGPointMake(x, y);
}

我正在尝试使用给定的makefile 制作/编译wykobi库(计算几何),但我不断收到错误:

错误:显式实例化不应使用'inline'说明符[-fpermissive]

我怎么解决这个问题？

我有一组表示多边形顶点(x,y)的点.

points= [(421640.3639270504, 4596366.353552659), (421635.79361391126, 4596369.054192241), (421632.6774913164, 4596371.131607305), (421629.14588570886, 4596374.870954419), (421625.6142801013, 4596377.779335507), (421624.99105558236, 4596382.14190714), (421630.1845932406, 4596388.062540068), (421633.3007158355, 4596388.270281575), (421637.87102897465, 4596391.8018871825), (421642.4413421138, 4596394.918009778), (421646.5961722403, 4596399.903805929), (421649.71229483513, 4596403.850894549), (421653.8940752105, 4596409.600842565), (421654.69809098693, 4596410.706364258), (421657.60647207545, 4596411.329588776), (421660.514853164, 4596409.875398233), (421661.3458191893, 4596406.136051118), (421661.5535606956, 4596403.22767003), (421658.85292111343, 4596400.94251346), (421656.5677645438, 4596399.696064423), (421655.52905701223, 4596396.164458815), (421652.82841743, 4596394.502526765), (421648.46584579715, 4596391.8018871825), (421646.38843073393, 4596388.270281575), (421645.55746470863, 4596386.400608018), (421647.21939675923, 4596384.115451449), (421649.5045533288, 4596382.661260904), (421650.7510023668, 4596378.714172284), (421647.8426212782, 4596375.8057911955), (421644.9342401897, 4596372.897410107), (421643.6877911517, 4596370.404512031), (421640.3639270504, 4596366.353552659)]

我需要找到最小的封闭圆(区域,中心的x和y,以及半径)

我正在使用从此页面派生的python代码:Nayuki的最小封闭圈

当我运行代码时,结果每次都会改变,例如:

>>> make_circle(points)
(421643.0645666326, 4596393.82736687, 23.70763190712525)
>>> make_circle(points)
(421647.8426212782, 4596375.8057911955, 0.0) …

我想知道一个返回true或false的算法,告诉我是否可以围绕一组点A绘制一个圆,这样点B组中的任何点都不在其中,或者反过来(可能)围绕一组点B绘制圆圈,使得来自点集A的任何点不在其内部).

基本上,你有两组点作为输入,你需要确定是否可以围绕任何一个绘制一个圆,这样另一个点的任何一个点都不在其中.

我已经看过Megiddo的线性时间算法来解决最小的圆周问题,但问题是它只绘制了最小的圆,这意味着它在你需要一个大圆的情况下不起作用.

这是我的意思的图片:

在这张图片中,可以围绕红点集绘制一个非常大的圆圈,这样任何一个绿点都不在其中,因此Megiddo的算法将无法工作.

截至2014年初,SVG规范没有任何内置的布尔运算支持

布尔运算是用于改变大多数重叠路径的固有几何的方法.它们允许通过对更简单的形状执行操作来构造复杂的形状,并且在某种程度上类似于构造实体几何(CSG).

然而,这个问题涉及2D矢量路径.流行的路径操作是:Union,Substraction,Intersection,XOR(Exclusive Or).

周围是否有任何图书馆可以帮助我解决这个问题？

我有一组折线(数字为100,每条折线有大约200-300个顶点).这些代表地图上的路线(如果有帮助,则全部来自Google Maps API).顶点是纬度/经度坐标.

我现在得到一个查询折线,我必须找到查询折线与任何现有折线的"重叠".因此,结果本身将是折线,按最大到最小重叠的顺序排序.我只需要前100个结果左右.另一个问题是重叠不一定是精确的,但可以是近似的(即,被认为是重叠的线段的部分不需要位于另一个上,而是仅需要彼此"接近").

为了给出具体的表示,在下图的左侧部分,蓝色折线(折线A)是数据库中的折线,红色折线(折线B)是查询折线.该算法应确定以粗黑标记的折线,如右图所示.

我目前倾向于使用空间数据库(正在考虑的选项是PostgreSQL + PostGIS),但我不确定延迟是否可以接受 - 查询需要立即返回结果.我的计算几何 - fu确实很弱,但我想知道:是否有任何现有的算法或方法可能对解决这个特定问题有用？

提前谢谢了!

是否有一些方法可以在2D中获得更加有序的三角测量,就像Matlab Delaunay产生的那样？这是Matlab的2D Delaunay三角剖分的一个例子.

使用此代码:

xPoints = np.arange(0,11,1)
yPoints = np.arange(0,11,1)
gridPoints = np.array([[x,y] for y in yPoints for x in xPoints])
tri = Delaunay(gridPoints)
plt.triplot(gridPoints[:,0],gridPoints[:,1],tri.simplices.copy())
plt.plot(gridPoints[:,0],gridPoints[:,1],'bo')
plt.title("Triangulation Visualization")

我得到以下三角测量:

注意Matlab结果中的对角弧如何具有相同的斜率; 但那些在scipy结果中的人是变化的.由于Matlab和Scipy都在内部使用QHull,我认为有一些方法来模仿Matlab结果.

是否存在一种算法,用于查找具有最小半径的圆形圆柱以获得3D云点？我知道解决了最小封闭圆的2D情况(例如这个线程在Python中最小的封闭圆圈,代码中有错误),但有没有3D的工作方法？

编辑1:OBB.下面是弧形云点的示例.这个工具找到了最小的圈圈https://www.nayuki.io/page/smallest-enclosing-circle

圆由三个点定义,其中两个几乎位于直径上,因此很容易估计中心轴的位置."拳击"点将产生一个明显偏离真正中心的盒子中心.

我的结论是,OBB方法并不普遍.

EDIT2:PCA.下面是紧密点云对比的PCA分析示例.点云与异常值.对于紧密点云,PCA令人满意地预测气缸方向.但是,如果存在少量的异常值,与主云相比,PCA基本上会忽略它们,产生的矢量距离封闭圆柱体的真实轴线很远.在下面的示例中,封闭圆柱体的真实几何轴以黑色显示.

我的结论是,PCA方法并不普遍.

EDIT3:OBB与PCA和OLS.一个主要区别 - OBB仅依赖于几何形状,而PCA和OLS依赖于总点数,包括那些不影响形状的中间点.为了使它们更有效,可以包括数据准备步骤.首先,找到凸壳.其次,排除所有内部要点.然后,沿着船体的点可以不均匀地分布.我建议删除所有这些,只留下多边形船体,并用网格覆盖它,其中节点将是新点.将PCA或OLS应用于这个新的点云应该可以更准确地估计气缸轴.

如果OBB提供尽可能平行于封闭圆柱轴的轴,则所有这些都是不必要的.

EDIT4:已发布的方法.@meowgoesthedog:Michel Petitjean撰写的论文("关于最小封闭圆柱问题的代数解决方案")可能有所帮助,但我没有足够资格将其转换为工作程序.作者自己也做到了(这里的模块CYL http://petitjeanmichel.free.fr/itoweb.petitjean.freeware.html).但根据论文中的结论,他说:" 现在的软件,名为CYL,可以在http://petitjeanmichel.free.fr/itoweb.petitjean.freeware.html免费下载,并没有声称提供最好的实现这些方法也没有声称比其他气缸计算软件更好地工作. "论文中的其他短语也给人留下了印象,它是一种实验方法,未经过彻底验证.无论如何,我会尝试使用它.

@Ripi2:Timothy M. Chan撰写的这篇论文对我来说也有点复杂.我不是数学水平的专家,能够转换为工具.

@ Helium_1s2:可能,这是一个很好的建议,然而,与上面的两篇论文相比,它的细节要少得多.此外,未经验证.

EDIT5:回复用户1717828.两个最远点与圆柱轴.一个反例 - 立方体形状的8个点,适合圆柱体.两点之间的最大距离 - 绿色对角线.显然不与气缸轴线平行.

Ripi2的"中间点"方法:它仅适用于2D.在3D情况下,圆柱轴可以不与任何两个点之间的单个段相交.