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

Question

我正在使用 Google Maps SDK 以允许用户通过点击在地图上绘制多边形。一切都很完美，用户要沿着一条路径绘制一个多边形，并在不跨越线的情况下继续沿着该路径前进。如果发生这种情况，将产生以下结果：. However. if the user is to make an error and cross over or change the direction of their "tapping" path this happens: 我需要 A）警告用户他们创建了一个无效的多边形，并且必须撤消该操作，或者 B) 校正多边形形状，形成完整的多边形。

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

我进行了研究并找到了检测线相交的算法和公式，但我还没有在 Swift 中找到任何解决方案来识别多边形是否基于点自相交（在在这种情况下，纬度和经度）。我不需要知道问题的重点，只需要知道问题的真假即可，"Does this Polygon self-intersect?" 多边形通常少于 20 条边。

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

Answer 1

我猜您正试图找出从一点到另一点的最快方法，就像乌鸦飞一样。您可能还想考虑道路方向，我不会在这里考虑。

你的两种选择都是可能的。添加新行时遍历每条现有行并确定它们是否交叉非常容易。但是您的用户肯定不愿意被告知他们搞砸了，您的应用程序应该为他们修复它。这就是有趣的地方。

我确信存在用于查找包含所有点的最小多边形的某些算法，但我没有查找它们，因为其中的乐趣在哪里。

这是我的做法。在伪代码中：

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.

Answer 2

这似乎能很好地满足我的需要。采纳自 Rob's answer here

 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)")


                }
            }
        }
    }

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

Detect self intersection of a polygon with n sides?

algorithm

google-maps

polygon

google-maps-sdk-ios

swift