如何对Google地图多边形中的点进行排序,以便线条不会交叉？

Question

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

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

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

你应该看到这样的东西:

替代文字http://polygon.abemiester.com/1.bmp

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

Answer 1

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

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

无论如何，这是值得尝试的事情。