标签: computational-geometry

由于Chazelle(1991),有一种用于在线性时间内对多边形进行三角测量的算法,但是,AFAIK,在一般的数学软件库中没有他的算法的任何标准实现.

有谁知道这样的实现？

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

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

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

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

我已经设法实现了二次和三次Bezier曲线.因为我们有一个公式,所以非常简单.现在我想用泛化表示一个n阶贝塞尔曲线:

哪里

和

我正在使用位图库来渲染输出,所以这是我的代码:

// binomialCoef(n, k) = (factorial(n) / (factorial(k) * factorial(n- k)))
unsigned int binomialCoef(unsigned int n, const unsigned int k)
{
    unsigned int r = 1;

    if(k > n)
        return 0;

    for(unsigned int d = 1; d <= k; d++)
    {
        r *= n--;
        r /= d;
    }

    return r;
}

void nBezierCurve(Bitmap* obj, const Point* p, const unsigned int nbPoint, float steps, const unsigned char red, const unsigned char green, const unsigned char blue)
{
    int …

我有一个2D点的集合,S我需要测试输入点q是否在凸包的内部或外部S.

由于它是关于二元决策的,我以为我理论上可以O(log(N))通过使用决策树来实现.

但是我不知道如何组织数据以及算法如何真正得到答案O(log(N)).

在研究这个想法的同时,我发现了这个:

我们怎样才能更快地找到这两种情况？二进制搜索.只需在两个链中的第一个坐标点中搜索x即可.如果它在链中,你已经找到了穿过顶点的交叉(并且你也不必小心分辨什么样的交叉).如果x不是链中顶点的坐标,则它的两个最接近的值会告诉您来自(x,y)的光线可能穿过哪个线段.因此,我们可以在时间O(log n)中测试点是否在凸多边形中 .

事实证明,有一些数据结构可以测试一个点是否在同一个O(log n)时间范围内的任意多边形(或它所在的多个多边形中的哪个).但它们更复杂,所以我没有时间在这里描述它们; 我将在ICS 164中的某些方面谈论它们.

(http://www.ics.uci.edu/~eppstein/161/960307.html)

所以你有任何想法:

1. 如何将数据结构放入其中O(log(N))？
2. 该算法应该如何？

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

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

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

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

提前谢谢了!

是否存在一种算法,用于查找具有最小半径的圆形圆柱以获得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情况下,圆柱轴可以不与任何两个点之间的单个段相交.

我想要一个算法来计算4个2D点的凸包.我已经研究了广义问题的算法,但我想知道是否有一个简单的4点解决方案.

我有一组简单的(没有洞,没有自交叉)多边形,我需要检查它们是否相互交叉(一个可以完全包含在另一个中;这没关系).我可以通过简单地检查一个多边形与其他多边形的每个顶点内部的关系来检查这一点.

我还需要确定包含树,它是一组关系,说明哪个多边形包含任何给定的多边形.由于没有多边形可以与任何其他多边形相交,因此任何包含的多边形都具有唯 "下一个更大的".换句话说,如果A包含B包含C,则A是B的父亲,B是C的父亲,我们不认为A是C的父亲.

问题:如何有效地确定包含关系并检查非交叉标准？我问这个问题是因为组合算法可能比单独解决每个问题更有效.该算法应该将多边形列表作为输入,由它们的顶点列表给出.它应该产生一个布尔B,表明没有多边形与任何其他多边形相交,如果B =真,则产生一对(P,C)的列表,其中多边形P是子C的父.

这不是功课.这是我正在做的一个爱好项目.

下午好.

我的情况:

• 在二维空间.
• 输入:一组矩形(也是重叠的矩形).
  • 矩形坐标是整数类型.
  • 矩形大小和矩形位置有任何限制(仅限整数范围).
  • 任何矩形都没有width = 0或height = 0.
• 我需要找到:包含输入点的所有矩形(带整数坐标).

问题:

• 保持矩形的有效结构是什么？
• 在这种情况下,哪种算法是有效的？
  • 什么算法只有在没有移除的情况下添加矩形才有效？

谢谢 :-).

给定定义n ²行的不同点的P = {p ₁,...,p _n },写一个算法,该算法在最坏的情况下找到具有最低斜率(最小绝对值)和时间复杂度的行.O(n*log(n))