标签: computational-geometry

如何找到可以放入凹多边形内的最大圆？

只要能够实时处理具有~50个顶点的多边形,蛮力算法就可以了.

如何在给定点的线段上绘制垂线？我的线段定义为(x1,y1),(x2,y2),如果我从点(x3,y3)绘制一个垂直线并且它在点(x4,y4)上遇到线.我想找出这个(x4,y4).

所以我一直在Haskell编写一个计算几何库,因为我在Hackage上找不到一个,而且我觉得无论如何都会很有趣.但是,我已经在一个特定的算法上被困了将近一个星期,我似乎无法进入一个很好的'类似haskell'的形式.该算法是用于在一组线段中找到交叉点的Bentley-Ottmann算法.如果您熟悉算法,可以跳到最后一段为我的求助:)

我选择实现此函数的方式是一个函数,它获取一个线段列表并返回一个点列表,以及在该点相交的线段.这让我们可以处理多个段在同一点相交的情况.

bentleyOttmann :: [Segment] -> [(Point, [Segment])]

该算法是扫描线算法.我们想象一条扫过飞机的线,在不同的点上进行算法工作.Bentley-Ottmann算法中的事件点是:

• 线段的起始端点.
• 线段的结束终点.
• 一堆段的交叉点.

请注意,事件点可以以多种方式与多个线段相关联.为了跟踪哪些段对应于哪些端点,我使用容器包中的映射.此贴图的关键点是点,值是段的列表,标记为它们是从该点开始,在该点结束还是在该点处相交.

扫描线确定点的顺序.想象一下垂直线扫过飞机,在事件点停下来做功.事件点首先按其x值排序,首先处理较小的点.一般来说,这就是我们所需要的.在退化情况下,事件点可以具有相同的x坐标.我们还按其y坐标排序,如果存在x坐标关系,则首先处理具有较小y坐标的事件点.

所以我自然使用的结构是一个优先级队列.我使用的是来自Hackage的堆包.

我们在每个活动点做的工作是什么？好吧,首先我们检查哪些段与事件点相关联.如果有多个,则为交叉点.我们可以将它添加到目前为止我们找到的交叉点列表中.

这是棘手的部分.当我们扫过飞机时,我们会跟踪一组段,这些段相对于它们与扫描线相交的点排序.当我们处理事件点时,我们首先删除在该事件点结束的所有段.然后,在该点交叉的所有段按顺序颠倒.最后,我们将从该事件点开始的段添加到有序集.注意,由于这些段都在事件点处相交,因此必须针对前方略微扰动的扫描线进行排序.

在每个事件点,我们必须添加任何新的事件点,发生的新交叉点.因为我们跟踪与扫描线相交的段的相对顺序,所以我们做以下两件事之一:

• 如果我们交换了两个段或添加了一个新段,我们找到最下面的(相对于扫描线)修改的段,最顶层的修改段,并测试它们与它们的直接非修改邻居的交叉点.

• 如果我们没有交换或添加新的段,那么我们至少会移除一个段,从而使其前邻居现在相邻.我们测试这些新邻居的交叉点.

这是Bentley-Ottmann算法的关键,当我们扫过飞机时,我们只测试与其邻居的新候选区段.这意味着当交叉点相对较少时,我们击败了天真的O(n ^ 2)算法.

我的问题(最后,我很抱歉这是如此啰嗦)是这样的:我不知道如何实现这个排序逻辑.我不能使用Data.Set,因为顺序随着扫描而改变.我正在尝试实现我自己的数据结构以跟踪信息,但它是蹩脚的,错误的,可能是低效的,也是丑陋的!我讨厌丑陋的代码.

我知道Haskell就是漂亮的代码.我也相信如果我不能以一种漂亮的方式实现算法,那就意味着我并不真正理解它.任何人都可以让我深入了解这个算法吗？

编辑:我现在有一个"工作"的实现.我打算使用通用输入,以及在同一点和垂直段相交的多个段.它似乎通过我做的微不足道的测试来处理这些输入.它并没有在段重叠的工作.我不知道如何处理这些问题.我希望得到关于如何容纳它们的意见.目前,我的扫描线结构在同一节点中跟踪它们,但它只会在相交测试中使用其中一个,并且可能会产生不一致的结果.

我使用Data.Set作为我的事件队列,使用Data.Map进行查找,以及使用拉链的红黑树的实现,我在他的书中使用了Okasaki的.如果我的代码段没有足够的上下文,我可以添加更多内容.

我很欣赏关于重组实施的提示,所以它不那么难看.我不知道它是多么正确,它让我感到紧张.

代码可以在hpaste上找到

CGAL似乎只为我即将开展的项目做了我需要的一切.它可以从弧线段创建多边形并对它们运行布尔运算.它已经有空间排序软件包,可以节省很多时间用于一些事情,整个图书馆似乎非常标准化和精心策划.

对于大多数软件包(非常基本的软件包除外),许可证只是QPL(即将推出的4.0版本的GPL)的问题.我的预算微薄,可能无法收集资金购买CGAL中需要它的特定包装的商业许可证.

我对这种图书馆的具体需求是:

• 精确的2D欧几里德空间
• 复杂的多边形
• 多边形能够具有曲线(弧)段
• 对这些多边形的布尔运算
• 多边形偏移
• 多边形分区或有效三角测量
• 刻有面积和多边形拟合算法
• 可能是一些具有圆形范围搜索的空间排序结构

总而言之,我正在寻找一个精确的精确的二维几何C++库. 最好是麻省理工学院,LGPL一次性或低成本的一次性免版税许可证低于500美元.

Boost得到了一些基本结构,但据我所知,他们缺乏很多更高级别的功能.任何已扩展的图书馆？我会考虑自己做,但我缺乏做得好的专业知识,它会延长我的项目相当多.

为了清楚起见,我不是在寻找2D 图形库,只是纯粹的几何结构.

我正在寻找一个简单的(如果存在的)算法来找到球体表面上一组点的Voronoi图.源代码会很棒.我是德尔福人(是的,我知道......),但我也吃C代码.

找到数据数组中给定点的最近点的最快方法是什么？

例如,假设我有一个A3D点阵列(像往常一样坐标x,y和z)和点(x_p,y_p,z_p).如何找到A(x_p,y_p,z_p)中的最近点？

据我所知,最慢的方法是使用线性搜索.还有更好的解决方案吗？

可以添加任何辅助数据结构.

我不知道如何解决这个问题.我不确定它的任务有多复杂.我的目标是拥有一个生成任何多边形的算法.我唯一的要求是多边形不复杂(即边不相交).我正在使用Matlab进行数学运算,但欢迎任何抽象的东西.

任何援助/指导？

编辑:

我正在考虑更多可以生成任何多边形的代码甚至是这样的:

我有两个点(一个线段)和一个矩形.我想知道如何计算线段是否与矩形相交.

我想知道如何使用反向运动学计算旋转角度.我打算用它来实时制作3D动画.有人知道一些详细介绍特定解决方案的优秀文献吗？

我正在寻找一种算法来检测一个圆是否与同一平面内的任何其他圆相交(假设一个平面中可能有多个圆).

我发现的一种方法是进行分离轴测试.它说:

如果您可以找到分隔两个对象的线,即一条线,使得对象的所有对象或点位于线的不同侧,则两个对象不相交.

但是,我不知道如何将此方法应用于我的案例.

有谁能够帮我？