如何使用计算几何技术处理不准确的地图坐标
How to use computational geometry techniques to deal with inaccurate map coordinates
我正在尝试构建路线优化软件，我正在使用 openstreetmaps 作为界面。我在后端实现了储蓄算法，可帮助确定进行一系列交付的最佳路线。
我遇到的问题是，为在地图上单击的地点编辑的某些坐标 return 是错误的。假设我必须在 2 个不同的地方交货。这两个地方的坐标加上我开始的地方和 return 到我完成的地方应该形成一个三角形。有时坐标 returned 可能错误到违反三角不等式定理。
我一直在阅读 Skiena 的算法设计手册并且想知道，给定一对错误的坐标是否可以使用所讨论的任何技术（凸包、Voronoi 图、Delaunay 三角剖分等）来确定最可能正确的坐标不违反三角不等式定理的坐标?
谢谢
一般来说，（据我所知）有 4 种方法可以解决这个问题：
- 受控扰动
- 四舍五入
- 精确几何计算
- (EGC) 临时
已对前 2 个进行了部分尝试，但作为解决问题的自动方法，它们远非实用。例如，有几篇关于 2D 中的 snap-rounding 方法的出版物，但不是 3D 中的。应用四舍五入可能很容易，但您必须能够理解生成的拓扑结构，最重要的是，软件必须变得健壮。
接受近似相等的浮点值属于 Ad-hoc 类别。由此产生的软件几乎总是不完全健壮——一个破坏健壮性的输入案例就在那里等待被喂养。此外，对代码的轻微更改可能会进一步破坏它，并且需要不断调整这些容差条件。
CGAL 遵循 EGC 范式。与任何软件一样，CGAL 也不是没有错误，但健壮性问题已被消除。您可以在 CGAL 网站或例如 "CGAL Arrangements and Their Applications" 一书中阅读更多相关信息。虽然本书专门针对 CGAL 的特定包，但它确实涉及了 EGC 主题；参见第 1.3.2 节。
我正在尝试构建路线优化软件，我正在使用 openstreetmaps 作为界面。我在后端实现了储蓄算法，可帮助确定进行一系列交付的最佳路线。
我遇到的问题是，为在地图上单击的地点编辑的某些坐标 return 是错误的。假设我必须在 2 个不同的地方交货。这两个地方的坐标加上我开始的地方和 return 到我完成的地方应该形成一个三角形。有时坐标 returned 可能错误到违反三角不等式定理。
我一直在阅读 Skiena 的算法设计手册并且想知道，给定一对错误的坐标是否可以使用所讨论的任何技术（凸包、Voronoi 图、Delaunay 三角剖分等）来确定最可能正确的坐标不违反三角不等式定理的坐标?
谢谢
一般来说，（据我所知）有 4 种方法可以解决这个问题：
- 受控扰动
- 四舍五入
- 精确几何计算
- (EGC) 临时
已对前 2 个进行了部分尝试，但作为解决问题的自动方法，它们远非实用。例如，有几篇关于 2D 中的 snap-rounding 方法的出版物，但不是 3D 中的。应用四舍五入可能很容易，但您必须能够理解生成的拓扑结构，最重要的是，软件必须变得健壮。
接受近似相等的浮点值属于 Ad-hoc 类别。由此产生的软件几乎总是不完全健壮——一个破坏健壮性的输入案例就在那里等待被喂养。此外，对代码的轻微更改可能会进一步破坏它，并且需要不断调整这些容差条件。
CGAL 遵循 EGC 范式。与任何软件一样，CGAL 也不是没有错误，但健壮性问题已被消除。您可以在 CGAL 网站或例如 "CGAL Arrangements and Their Applications" 一书中阅读更多相关信息。虽然本书专门针对 CGAL 的特定包，但它确实涉及了 EGC 主题；参见第 1.3.2 节。