google-maps - 如何对谷歌地图多边形中的点进行排序以使线不交叉？

Question

我正在尝试制作一张地图，用户可以在其中勾勒出他们想要的任何形状。但是我遇到了一个问题，用户可以选择使多边形的线交叉并排除我想包括的区域的点。

要查看我在说什么，请转到此页面并执行以下步骤：

1. 单击 4 个点以制作方框的 4 个角
2. 在您刚刚制作的 4 个点之间单击以进一步定义框的周长
3. 点击完成

您应该看到如下内容：

有没有一种简单的方法可以解决这个问题，或者我基本上是在处理“旅行推销员”类型的情况？所有的逻辑都是用 javascript 完成的，所以如果你想看看我是怎么做的，请随意“查看源代码”。

Answer 1

它不是凸包。

想象一下，如果你在这两条线交叉的地方附近的“林菲尔德橡树”停下来。凸包会跳过这个并在“international”和“82”之间画一条直线

您要做的是确定每个新点是否在现有点形成的多边形内 - 如果是，那么您需要打破最近的多边形边并将新点插入该边缘。有关多边形测试中的点，请参见http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm。

Answer 2

凸包可能包括用户希望排除的区域。这是解决此问题的另一种方法，可能会产生更令人满意的结果。检查每条线以查看哪些线交叉（有很多方法可以做到这一点）。然后反转出现在这两条线之间的点的子序列。

例如，假设给定点 ABCDEFA，其中 BC 和 EF 交叉。您可以通过反转子序列 C..E 来取消它们，从而得到 ABEDCFA。

无论如何，这是可以尝试的。

Answer 3

我过去解决了一个类似的问题，遇到了 Jeffrey 提到的不知道用户期望的确切形状的问题。我最终通过要求用户选择他们希望新点介于两者之间的两点来解决该问题。它需要更多的点击（3 对 1），但用户完全可以控制他们想要的形状。如果您有兴趣，我可能仍然有我在某处使用的代码（用于 Google 地图）。