检测具有n个边的多边形自相交？

Question

我正在使用Google Maps SDK，允许用户通过点击在地图上绘制多边形。如果用户按照一条路径绘制多边形并沿着该路径继续而不穿过线路，那么一切都可以完美地工作。但如果出现穿越线路的情况，则会出现此结果：

然而，如果用户犯了错误，跨越或改变了他们“点击”路径的方向，就会发生这种情况：

我需要做以下两件事之一： A）警告用户他们创建了无效的多边形，并且必须撤消该操作；或者 B）更正多边形形状以形成完整的多边形。

根据我所做的研究，选项A似乎更可行和简单，因为选项B需要重新排列多边形点的路径。

我已经进行了研究，并找到了检测线交叉的算法和公式，但是我还没有找到任何在Swift中识别基于点（在这种情况下是纬度和经度）的多边形自相交的解决方案。我不需要知道点，只需要回答“这个多边形是否自相交？”的TRUE或FALSE。多边形通常会有不到20个面。

也许GoogleMaps SDK中已经内置了解决方案，但我还没有找到它。此外，我了解到已经存在解决这些问题的算法，但我在将它们实现到Swift 2或3中遇到了麻烦。感谢任何帮助！

- Baylor Mitchell

---

既然你已经找到要使用的算法，那么你在实现方面遇到了什么问题？ - Alejandro C.

这个答案展示了如何在Swift中进行线线相交。当用户添加新的线时，只需测试新线与所有现有线的相交情况即可。 - samgak

非常简单。检查所有未连接的边缘（侧面）是否相互交错。详见链接：https://dev59.com/k2Yr5IYBdhLWcg3wH2zK#40953705。 - Redu

你解决了吗？我没有回答，因为我太忙了，而且实际上会相当复杂，我对谷歌地图 SDK 不熟悉，但可以用核心图形编写代码。 - twiz_

是的，这个解决方案似乎功能正常。我发布了我的答案。它没有纠正多边形，而是向用户警告它是自相交的。 - Baylor Mitchell

Answer 1

对于我所需的内容来说，这似乎运作得非常好。源自Rob在这里的回答

 func intersectionBetweenSegmentsCL(p0: CLLocationCoordinate2D, _ p1: CLLocationCoordinate2D, _ p2: CLLocationCoordinate2D, _ p3: CLLocationCoordinate2D) -> CLLocationCoordinate2D? {
    var denominator = (p3.longitude - p2.longitude) * (p1.latitude - p0.latitude) - (p3.latitude - p2.latitude) * (p1.longitude - p0.longitude)
    var ua = (p3.latitude - p2.latitude) * (p0.longitude - p2.longitude) - (p3.longitude - p2.longitude) * (p0.latitude - p2.latitude)
    var ub = (p1.latitude - p0.latitude) * (p0.longitude - p2.longitude) - (p1.longitude - p0.longitude) * (p0.latitude - p2.latitude)

    if (denominator < 0) {
        ua = -ua; ub = -ub; denominator = -denominator
    }

    if ua >= 0.0 && ua <= denominator && ub >= 0.0 && ub <= denominator && denominator != 0 {
        print("INTERSECT")
        return CLLocationCoordinate2D(latitude: p0.latitude + ua / denominator * (p1.latitude - p0.latitude), longitude: p0.longitude + ua / denominator * (p1.longitude - p0.longitude))
    }
    return nil
}

我然后像这样实施：

 if coordArray.count > 2 {
        let n = coordArray.count - 1

        for i in 1 ..< n {
            for j in 0 ..< i-1 {
                if let intersection = intersectionBetweenSegmentsCL(coordArray[i], coordArray[i+1], coordArray[j], coordArray[j+1]) {
                    // do whatever you want with `intersection`

                    print("Error: Intersection @ \(intersection)")


                }
            }
        }
    }

- Baylor Mitchell

---

这个失败了，以下是经纬度集合： 33.86849360537594，-118.17826767729882 33.86468074440517，-118.15178891086123 33.85851566504107，-118.1980087349346 33.85349061795741，-118.17440529645701 - craya

Answer 2

我猜你正在尝试绘制从一个点到另一个点最快的路径，就像鸟儿飞行一样。你可能还想考虑道路方向，但我这里不会涉及。

两种选项都是可行的。当添加新线时，迭代每条现有线并确定它们是否交叉很容易。但你的用户肯定不想被告知他们已经搞砸了，你的应用程序应该为他们解决问题。这就是乐趣所在。

我确定存在算法可以找到包含所有点的最小多边形，但我没有查找，因为那样哪里有乐趣。

以下是我的做法。伪代码如下：

if (line has intersected existing line)

find mean point (sum x sum y / n)

find nearest point to centre by:
taking min of: points.map(sqrt((x - centrex)^2 + (y-centrey)^2))

from the line between centre and nearest point, determine angle to every other line.

points.remove(nearest)

angles = points.map(cosine law(nearest to centre, centre, this point)) 
<- make sure to check if it crossed pi, at which point you must add pi.

sort angles so minimum is first.

starting at nearest point, add line to next point in the array of minimal angle points

非常抱歉我还没有将这个转换成Swift语言。明天我会更新，并用适当的Swift 3语法。

- twiz_