如何对谷歌地图多边形中的点进行排序以使线不交叉？
我正在尝试制作一张地图，用户可以在其中勾勒出他们想要的任何形状。但我遇到了一个问题，用户可以选择使多边形的线交叉并排除我想要包含的区域的点。
要了解我所说的内容，请转至此页面并执行以下步骤：
- 单击 4 个点以将4个角 框
- 在 4 个 之间单击 你刚才提出的要点是为了进一步 定义框的周长
- 单击完成
您应该看到类似这样的内容：
是有一个简单的方法来解决这个问题，还是我基本上在这里处理“旅行推销员”类型的情况？所有逻辑都是在 JavaScript 中完成的，因此如果您想了解我是如何做到这一点的，请随意“查看源代码”。
I am trying to make a map where a user can outline any shape they would like. But I am running into an issue where users can select points that will make the lines of the polygon cross and exclude area's that I would like to include.
To see what i'm talking about go to this page and take the following steps:
- click 4 points to make the 4 corners
of a box - click in between each of the 4
points you just made to further
define the perimter of the box - click done
You should see something like this:
Is there an easy way to solve this problem, or am I basically dealing with a "Traveling Salesman" type situation here? All the logic is done in javascript so feel free to "view source" if you would like to see how i'm doing this.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
凸包可能包括用户希望排除的区域。这是解决此问题的另一种方法，可能会产生更令人满意的结果。检查每条线，看看哪些线交叉（有很多方法可以做到这一点）。然后反转这两条线之间出现的点的子序列。
例如，假设给定点 ABCDEFA，其中 BC 和 EF 交叉。您可以通过反转子序列 C..E 来取消它们的交叉，从而得到 ABEDCFA。
无论如何，这是值得尝试的事情。
A convex hull might include areas that the user wishes to exclude. Here is another way to approach this that might give more satisfactory results. Check each line to see which ones cross (there are lots of ways to do that). Then reverse the subsequence of points that appear between those two lines.
For example, suppose you are given points A-B-C-D-E-F-A, where B-C and E-F cross. You can uncross them by reversing the subsequence C..E resulting in A-B-E-D-C-F-A.
It's something to try anyway.
它不是凸包。
想象一下，如果您在这两条线交叉点附近的“Linfield Oaks”停留。凸包会跳过此步骤并在“international”和“82”之间绘制一条直线
您要做的是确定每个新点是否位于由现有点形成的多边形内部 - 如果是，那么您需要打破最近的多边形边并在该边插入新点。
请参阅 http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm 了解要点在多边形测试中。
It's not a convex hull.
Imagine if you had a stop at "Linfield Oaks" near where those two lines cross. A convex hull would skip this and draw a straight line between "international" and "82"
What you are trying to do is determine if each new point is inside the polygon formed by the existing points - if it is then you need to break the nearest polygon side and insert the new point in that edge.
See http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm for point in polygon tests.
我过去解决了一个类似的问题，并遇到了 Jeffrey 提到的关于不知道用户到底期望什么形状的问题。我最终通过要求用户选择他们想要新点位于之间的两个点来解决这个问题。它需要更多的点击次数（3 次对 1 次），但用户完全可以控制他们想要的形状。如果您有兴趣，我可能仍然拥有我在某个地方使用过的代码（用于 Google 地图）。
I solved a similar problem in the past and ran into the issue that Jeffrey mentioned about not knowing exactly what shape the user is expecting. I ended up solving that issue by requiring the user to select the two points that they wanted the new point to be between. It requires more clicks (3 versus 1), but the user is entirely in control about what shape they want. I might still have the code that I used around somewhere (it was for Google Maps) if you're interested.