标签: computational-geometry

我有一个非常类似的问题:

如何知道一条线是否与C#中的平面相交？

我正在寻找一种方法(在C#中),它告诉一条线是否与任意多边形相交.

我认为Chris Marasti-Georg的算法非常有用,但缺少最重要的方法,即线对线交叉.

有没有人知道一个线交叉方法来完成Chris Marasti-Georg的代码或有类似的东西？

在C#中是否有内置代码？

此方法适用于使用禁区功能增强的Bing Maps算法.生成的路径不得通过禁区(任意多边形).

我有一些凸多边形存储为STL矢量点(或多或少).我想快速镶嵌它们,最好是尺寸相当均匀的碎片,没有"条子".

我打算用它把一些物品分成小块.有没有人知道一个漂亮的图表来镶嵌多边形(将它们分成一个较小的凸多边形或三角形的网格)？

我已经看过一些我已经在网上找到的,但我甚至无法让它们编译.这些学术类型并不重视易用性.

可能重复:
如何在蛮力搜索之外找到凸包中的最大三角形

我有一组随机点,我想从中找到最大的三角形区域,其中每个点都在其中一个点上.

到目前为止,我已经发现最大三角形的顶点将只位于点云(或凸包)的外部点上,所以我编写了一个函数来做到这一点(在nlogn时间使用格雷厄姆扫描).

然而,这就是我被困住的地方.我能弄清楚如何从这些点找到最大三角形的唯一方法是在n ^ 3时使用蛮力,这在平均情况下仍然是可接受的,因为凸壳算法通常会踢出绝大多数点.然而,在最坏的情况下,点在圆上,这种方法会失败.

任何人都知道算法更有效地做到这一点？

注意:我知道CGAL在那里有这个算法,但他们没有详细说明它是如何完成的.我不想使用库,我想学习它并自己编程(并且还允许我将其调整到我希望它操作的方式,就像graham扫描,其中其他实现获取共线点我不想要).

我试图计算任意数量的飞机的最顶部交叉点,没有快乐!我正在使用actionscript,但只需要找到一个我可以实现的算法.

问题:

• 考虑3垂直轴.
• 用户为每个三角形/平面输入3个点,使得三角形的点位于其中一个轴上.
• 用户可以输入任意数量的三角形
• 我需要找到这些三角形的最顶层,并在屏幕上显示它以及相互作用的坐标.

这是一张图片来澄清我对2个三角形的意思:

但是,当我们允许超过2个三角形时,我会遇到尴尬的交叉线.

我有一个问题,我必须测试给定的矩形组的并集是否形成矩形.我没有太多解决计算几何问题的经验.我对问题的处理方法是,因为我知道所有矩形的坐标,所以我可以轻松地对点进行排序,然后推导出最大矩形的角点.然后我可以扫描一条线,看看线上的所有点是否落在矩形内.但是,这种方法是有缺陷的,这会失败,因为联合可能是'U'的形式.如果你能把我推向正确的方向,那将是一个很大的帮助.

我正在实施Fortune的扫描线算法来计算Voronoi图.我的主要参考文献是de Berg等人的"计算几何:算法和应用",虽然他们对这个主题的报道非常清楚,但他们传递了一些我自己一直无法解决的小而重要的细节.我在网上寻求帮助,但其他网站要么比教科书提供更高的概述,要么提供本书提供的完全相同的伪代码.

我需要一种方法来确定由海滩线上的三个弧确定的一对断点是否收敛或发散,以便检测即将到来的圆周事件.似乎要做出决定,我需要了解Voronoi单元边缘的形状,断点随着Fortune算法的进展而逐渐显现出来.例如,如果我能找到断点跟踪的边的斜率,我可以计算断点形成的两条线的位置和它们各自的斜率相交,并根据该结果确定它们是否收敛.但是,我不知道如何获得斜坡上的信息,只知道断点的当前位置.

我必须处理的唯一信息是三个站点的x,y位置和扫描线的当前y坐标(我使用的是水平扫描线).

实际上,我确实有一个确定收敛的想法.给定两个站点,他们定义的海滩线的两个部分之间的断点仅由扫描线的当前位置控制.我考虑记录两个断点的位置,暂时推进扫描线少量,并记录他们的新位置.因为正常Voronoi图中的边不会弯曲,如果新断点之间的距离小于旧对之间的距离,则断点会聚; 否则,他们分歧.但这似乎既危险(我不知道它是否总是有效)和丑陋.当然必须有更好的方法.

任何想法都会受到赞赏,并且伪代码(如果可能的话,使用类似C#的语法)尤其如此.另外我知道有一些计算几何库可以用来获取Voronoi图,但这是一个个人学习练习,所以我想自己实现算法的所有部分.

给定形式的2维平面上的一组n个点(x,y),目的是找到所有点的对的数量,(xi,yi)并且(xj, yj)使得连接这两个点的线具有负斜率.

假设没有两个xi人具有相同的价值.假设所有点都在[-100,100]或在其他范围内.

我N在飞机上有一小组点,N < 50.

我想枚举集合中所有三点的点,形成一个不包含其他点的三角形.

即使明显的蛮力解决方案对我的微小也是可行的N,但它具有复杂性O(N^4).

您是否知道一种降低时间复杂度的方法,比方说O(N³)或O(N²)保持代码简单？没有图书馆允许.

令我惊讶的是,这种三角形的数量相当大.将任意点作为中心,并通过增加其周围的角度来对其他点进行排序.这形成一个星形多边形,给出N-1空三角形,因此总共为?(N²).已经证明这个界限很紧[平面点集与少量空凸多边形,I.Bárány和P. Valtr].

在形成凸多边形的点的情况下,所有三角形都是空的O(N³).快速算法的机会越来越低:(

我正在寻找一种算法来找到闭合折线的最长弦("直径").不幸的是,折线不必是凸的,但是弦应完全位于曲线内.这是一个例子:

我正在寻找的解决方案是虚线红色部分.

你能建议一个有效的算法吗？到目前为止我们能够实现的最好的是N²算法,它尝试所有顶点对,但即使这看起来也不正确,因为和弦不一定通过两个顶点(或者它是什么？).

我也对相关问题很感兴趣,我们正在寻找连接两个顶点的最大段(如果未完全刻录的段,则该段中位于曲线内的最长部分).在这种情况下,N²算法可以工作,但对于大量的点来说速度很慢.

我正在使用多边形的质心在地图应用程序中附加标记.这对于凸多边形非常好,对于许多凹多边形非常有用.

然而,一些多边形(香蕉,甜甜圈)显然不会产生所需的结果:在这些情况下,质心在多边形区域之外.

有没有人知道更好的方法在任何多边形区域(可能包含孔!)中找到合适的点来附加标记？