标签: computational-geometry

我的要求: 用户应该能够手工绘制一些东西.然后,在他取下笔(或手指)后,算法会平滑并将其转换为一些基本形状.

首先,我想将绘图转换为尽可能类似于原始的矩形.(当然,如果用户故意绘制其他东西,这将不起作用.)现在我正在计算平均x和y位置,我区分水平线和垂直线.但它还不是一个矩形,而是某种正交线.

我想知道是否有一些众所周知的算法,因为我在一些触摸屏应用程序中看到过几次.你有阅读提示吗？

更新:也许模式识别算法可以帮助我.有些手机要求用户绘制图案以解锁其密钥.

PS:我认为这个问题与特定的编程语言无关,但如果你感兴趣,我将用RaphaelGWT构建一个Web应用程序.

我已成功实现了一种使用Fortune方法生成2维维度Voronoi图的方法.但是现在我正在尝试将它用于一个点的最近邻查询(这不是用于生成图的原始点之一).我一直看到人们说它可以在O(lg n)时间内完成(我相信它们),但我找不到它是如何实际完成的描述.

我熟悉二进制搜索,但我无法找出保证上限的良好标准.我也想过可能它可能与将点插入图表并更新周围的单元格有关,但不能思考(或找到)这样做的好方法.

任何人都可以提醒我,或指向一个描述更全面的地方？

计算几何问题:
在多边形(例如)P0的边缘(例如EB)上随机选择该点BCDE,以P1,P2,P3,...基于给定距离(即,r)在其他边缘上找到可能的点(即).以下演示通过查找以点为中心的圆P0与多边形边之间的交点来显示解决方案.因此问题基本上可以通过Circle--Line-Segment交叉点分析来解决.

我想知道在计算成本方面有没有更有效的方法解决这个非常简单的问题？该过程将进行几次评估,million times因此任何改进都是有意义的.

• 最终的解决方案将受益于Python的强大功能;
• 如果需要,核心计算将在Fortran中.

更新:
感谢您的评论.请考虑我对评论的评论,这有助于更多地澄清问题.不愿意在这里重复,鼓励考虑所有的评论和答案;).

我刚刚实现了Circle--Line-Segment Intersection基于[here]找到的算法的方法.实际上我改编它用于线段.Python中实现的算法基准如下:


线段的数量是:100,000并且系统通常是桌面.经过的时间是:15 seconds.希望这些有助于对计算成本有所了解.在Fortan中实施核心可以显着提高性能.
然而,翻译是最后一步.

下午好.

我的情况:

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

问题:

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

谢谢 :-).

我已经成功实现了行进立方体算法.我使用标准材料作为参考,但我完全从头开始重写.它有效,但我观察到导致网格中的洞的模糊性.

我正在考虑行进的四面体算法,据说这种算法不会产生歧义.我看不出这是怎么可能的.

行进四面体算法使用六个四面体代替立方体,每个四面体具有三角剖分.但是,假设我要实现行进立方体算法,但对于256个三角测量中的每一个,只需选择多维数据集四面体三角剖分的"和"(并集)？据我所知,这就是行军四面体的作用 -那为什么会神奇地修复模糊性？

我认为有16个独特的案例,其他240个只是那些16的反思/轮换.我记得在某个地方阅读一些解决含糊之处的文章,你需要33个案例.这可能与为什么行进四面体不会出现问题有关？

所以,问题:

1. 为什么行军四面体不会有歧义？
2. 如果没有,为什么人们不使用行进立方体算法,而是使用四面体的三角剖分？

我觉得我在这里错过了一些东西.谢谢.

我有许多简单的多边形,它们彼此不相交,但有些多边形可能嵌入到其他多边形中.

例如:

+--------------------------------------------+
|                                            |
|   +----------------+          +--------+   |
|   |                |         /         |   |
|   |   +--------+   |        /          |   |
|   |   |        |   |       /  +----(2)-+   |
|   |   |        |   |      /   |            |
|   |   +----(3)-+   |     /    |   +---+    |
|   |                |    +-----+   |   |    |
|   +------------(2)-+              +(2)+    |
|                                            |
+----------------------------------------(1)-+

如何找出所有多边形的"深度"？换句话说,如何找出多边形包含多少个多边形？"深度"是括号中的数字.

我可以计算多边形点在所有其他多边形内部的次数,但这具有二次复杂性.如何更快地计算这些深度？

我正在尝试使用SVG路径创建高性能,美观的铅笔工具.

我正在记录鼠标坐标以绘制路径.为了获得高保真路径(精确到用户的动作),我需要为每个像素移动记录一个点.

保持路径中的每个点都会产生大量的点,这对于后来的协作功能来说并不理想(来回发送大量的点效率不高),而且每次我需要操作它们时解析大路径是瓶颈

在路径的线性区域上,删除冗余点,仅保留表示段所需的点 - 我使用Ramer-Douglas-Peucker算法执行此操作.

但是简化路径会将其转换为低保真多边形

此时,路径实际上只是连接线 - 因此路径看起来是锯齿状的.

一种可能的解决方案是将路径点与Cubic Bezier连接 - 但是这在简化路径上不起作用.每个点之间的距离太大,以至于Cubic Bezier"坐得"不错,因此平滑的路径不再准确地表示用户的预期路径.

另一个解决方案是在原始路径上简单地使用"后处理"算法,例如Schneider算法 - 这个算法实际上不会实时工作,因为它是一个性能猪

理想的解决方案

(我认为)可以使用的解决方案是使用Centripetal Catmull-Rom插值.

在我研究过的所有算法中,这似乎是最有希望的:

1. 它不会在狭窄的角落产生自我交叉
2. 它更适合点,因此它更准确地代表原始路径.

是的Catmull-ROM,其插入了一系列的常规X/Y点或完成原始路径必须由曲线的算法？

我正在考虑为我的Computational Geometry类(2D)编写几个例子,我想使用html5和javascript.

任何人都可以推荐一个JavaScript库或html5有我需要启动的一切吗？

我将主要使用点和线,但是有一些东西可以绘制笛卡尔平面作为参考,也许可以使用一些数据结构.

起初,我认为这个问题等同于确定多边形是否是凸面,但似乎仍然可以通过一个三角形扇形绘制非凸多边形. 考虑这个形状,一个非凸多边形.可以很容易地想象一些中心点区域允许用三角形扇形绘制这个多边形(尽管会有其他中心点不会).给定一个固定的中心点,我希望能够确定定义多边形的2d点的集合是否允许使用单个三角形扇形绘制它.

看起来关键是要确保从中心点到任何顶点绘制的线条没有"妨碍",这意味着顶点的其他边缘线.但是,重要的是尽可能使计算成本低廉,并且我不确定这样做是否有一个很好的数学捷径.

最终,我将要让多边形的顶点移动,并且我需要确定允许顶点移动的"边界",因为其余的是固定的(并且可能稍后甚至允许直接同时反应移动)还有2个邻居),以保持多边形能够在单个三角形扇形中绘制.但这就是未来,希望对整个多边形的测试可以分解为一个计算子集,以假设已经凸出的多边形来测试单个顶点运动的边界.

给定两条共线线段AB和CD,如何找到它们是否重叠？如何找到重叠的起点和终点？

以下是我正在使用的方法.我首先确保A <B和C <D.

if(pa < pc){
  if(pc < pb){
    if(pd < pb){
      //  overlap exists; CD falls entirely within AB
    }
    else {
      //  overlap exists; CB is the overlapping segment
    }
  }
  else {
    //  no overlap exists; AB lies before CD
  }
}
else {
  if(pa < pd){
    if(pb < pd){
      //  overlap exists; AB lies entirely within CD
    }
    else {
      //  overlap exists; AD is the overlapping segment
    }
  }
  else {
    //  no overlap …