问题标签 [computational-geometry]

有没有办法以几何方式计算一条线和任意图形路径的交点？我知道所有直线和曲线在路径中的位置，如果有帮助的话，我正在使用 HTML5 画布元素。基本上，我可以访问所有画布绘图命令及其参数。例如，如果使用 lineTo、moveTo、arc 调用 API，那么我拥有所有这些信息。对 API 的每次调用都存储在一个数组中。我有路径定义，我只想找出线与路径相交的位置。下图显示了我需要找到的点的示例。

谢谢你的帮助！同样，如果可能的话，我宁愿以几何方式而不是基于像素来执行此操作。

给定平面上的 n 个点。No 3 是共线的。

给定数字 k。

找到 k 点的子集，使得 k 点的凸包在 k 点子集的任何凸包中具有最小周长。

我可以想到一个天真的方法在 O(n^kk log k) 中运行。（找到每个大小为 k 的子集的凸包并输出最小值）。

我认为这是一个 NP 问题，但我找不到任何适合归约的东西。

有人对这个问题有想法吗？

一个例子，

结果：

由于该集合包含 3 个点，因此结果的凸包和周长小于任何其他 3 个点的集合。

给定一个二维平面，其中有 n 个点。我需要生成分割平面的直线方程，使得一侧有 n/2 个点，另一侧有 n/2 个点。

我有两个位图，只有当像素位于由四个角（四边形）定义的区域内时，我才想将像素从 A 复制到 B。位图 A 和 B 大小相同，四边形定义为图像像素空间中的四个 {x,y} 坐标。

在最坏的情况下，我可以针对四边形测试每个像素的中心，以查看像素的中心是否在四边形内，但这非常慢。什么是更好的算法？

我正在尝试设计一个 MySQL 模式，该模式可以存储具有相关纬度和经度的用户列表。

然后，对于给定的用户，我想构建一个查询，该查询可以将最近的 50 个用户返回给他/她，并按距离对这些用户进行排序（首先显示最近的用户）。

鉴于此表中可能有数千个用户，存储和查询此数据的最有效方法是什么？

我有两个地形的 TIN（三角形不规则网络）。第一个（TIN1）是原始的，假设有 X 个点。另一个（TIN2）被简化（点的数量被一些抽取算法减少了），假设它是从 Y 点构建的，其中 X>Y。现在，我如何在这两个 TIN 之间进行以下比较：

1) TIN2 与 TIN1 有何相似之处？或 TIN2 如何偏离 TIN1？或者我如何比较 TIN2 与 TIN1 的精度？

2) 有哪些工具或方法可以帮助我获得关于 TIN2 相对于 TIN1 准确性的大部分信息？

如果你能指出我的任何论文、书籍、链接……？非常感谢！

我想计算两条线段 A 和 B 之间的顺时针角度。所以得到的角度必须在 0 到 360-1 度之间。我在 SO 中看到了所有其他答案，但他们给了我负面的角度。谢谢。

我有一个从一堆 LineSegments 构建的 PathGeometry，我想将它分成两个 PathGeometry，由一条与几何图形中间相交的线划分。这就是我说这张照片的意思：

http://i30.tinypic.com/2noyvm.png

我可以通过 LineSegments 并创建一组简单的线对象（带有 Point1、Point2 属性的简单对象，以便它表示一条线）。但我需要以某种方式弄清楚哪些线在相交线的一端，哪些线在相交线的另一端......

这有点像几何组合方法的对立面，就像我试图组合在一起的几何分割方法。

有任何想法吗？

谢谢！

在n维欧几里得度量空间中，给定一组S点的 Voronoi 分解（使用 Bowyer-Watson 算法计算），是否可以通过收敛多个 Dirichlet 域来概括k（k<S ）几何簇？

我试图找到目的地点，给定起点纬度/经度，方位和距离。下面这个网站的计算器给了我想要的结果。

http://www.movable-type.co.uk/scripts/latlong.html

当我尝试通过代码实现相同的功能时，我没有得到正确的结果。

下面是我的代码 -

从主程序中，我调用子程序如下 -

我得到以下结果 -

我期望的答案是-40.939722,175.646389（来自上面的网站链接）。

谁能建议我在这里的代码中犯了什么错误？