查找两个 CGPoint 之间的点

Question

正在尝试找到起点和终点之间最近的点。

点数组：

let pointsArray = [(10.0, 10.0), (70.0, 10.0), (10.0, 200.0), (70.0, 200.0), (73.0, 10.0), (133.0, 10.0), (73.0, 200.0), (133.0, 200.0), (135.5, 10.0), (195.5, 10.0), (135.5, 200.0), (195.5, 200.0), (198.5, 10.0), (258.5, 10.0), (198.5, 200.0), (258.5, 200.0), (261.5, 10.0), (321.5, 10.0), (261.5, 200.0), (321.5, 200.0), (324.0, 10.0), (384.0, 10.0), (324.0, 200.0), (384.0, 200.0), (387.0, 10.0), (447.0, 10.0), (387.0, 200.0), (447.0, 200.0), (450.0, 10.0), (510.0, 10.0), (450.0, 200.0), (510.0, 200.0), (512.5, 10.0), (572.5, 10.0), (512.5, 200.0), (572.5, 200.0), (575.5, 10.0), (635.5, 10.0), (575.5, 200.0), (635.5, 200.0), (638.5, 10.0), (698.5, 10.0), (638.5, 200.0), (698.5, 200.0), (701.0, 10.0), (761.0, 10.0), (701.0, 200.0), (761.0, 200.0), (764.0, 10.0), (824.0, 10.0), (764.0, 200.0), (824.0, 200.0), (10.0, 390.0), (70.0, 390.0), (73.0, 390.0), (133.0, 390.0), (135.5, 390.0), (195.5, 390.0), (198.5, 390.0), (258.5, 390.0), (261.5, 390.0), (321.5, 390.0), (324.0, 390.0), (384.0, 390.0), (387.0, 390.0), (447.0, 390.0), (450.0, 390.0), (510.0, 390.0), (512.5, 390.0), (572.5, 390.0), (575.5, 390.0), (635.5, 390.0), (638.5, 390.0), (698.5, 390.0), (701.0, 390.0), (761.0, 390.0), (764.0, 390.0), (824.0, 390.0), (10.0, 580.0), (70.0, 580.0), (73.0, 580.0), (133.0, 580.0), (135.5, 580.0), (195.5, 580.0), (198.5, 580.0), (258.5, 580.0)]

let startPoint = CGPoint(x: 80, y: 20)
let endPoint = CGPoint(x: 170, y: 440)

这里我试图从现有点数组中找到起点和终点之间的点。

从特定点开始使用下面的扩展距离，但我无法仅获得起点和终点之间的特定点

extension CGPoint {
    func distance(to point: CGPoint) -> CGFloat {
        return sqrt(pow(x - point.x, 2) + pow(y - point.y, 2))
    }
}

Answer 1

这绝不是唯一的解决方案，但这是我会采用的一种方法。

1.从数组中检索有效点

我们只想从数组中获取起点和终点之间的有效点。所以为了形象化，我假设是这样的：

一个区域在iOS坐标系中定义如下，左上角为0,0，但这也适用于其他坐标系，例如左下角为0,0：

因此，要定义有效区域，请遵循以下规则：

开始 x 和开始 y 将 <= 结束 x 和结束 y。
起点和终点可以是一条直线
起点和终点可以是同一点
但end不能在start的下方或左侧

我认为

开始 x 和开始 y 将 <= 结束 x 和结束 y。
起点和终点可以是一条直线
起点和终点可以是同一点
但end不能在start的下方或左侧

所以为了支持这一点，我添加到您的 CGPoint 扩展中以检查该点是否存在于该区域

extension CGPoint
{
    func distance(to point: CGPoint) -> CGFloat
    {
        return sqrt(pow(x - point.x, 2) + pow(y - point.y, 2))
    }
    
    
    /// Checks if the current point exists in a region. The x and y coordinate of
    /// `regionStart` has  to be less than or equal to `regionEnd` for a
    /// valid check to occur.
    /// - Parameters:
    ///   - regionStart: The top left of the region
    ///   - regionEnd: The bottom right of the region
    /// - Returns: True if the current point falls within the region
    func doesExistInRegion(regionStart: CGPoint, regionEnd: CGPoint) -> Bool
    {
        // Check if we have an invalid region
        if regionStart.x > regionEnd.x || regionStart.y > regionEnd.y
        {
            return false
        }
        
        // Check if the current point is outside the region
        if x < regionStart.x ||
            y < regionStart.y ||
            x > regionEnd.x ||
            y > regionEnd.y
        {
            return false
        }
        
        // The point is within the region
        return true
    }
}

然后我使用这样的扩展名只提取有效点：

let pointsArray = [(10.0, 10.0), (70.0, 10.0), (10.0, 200.0), (70.0, 200.0), (73.0, 10.0), (133.0, 10.0), (73.0, 200.0), (133.0, 200.0), (135.5, 10.0), (195.5, 10.0), (135.5, 200.0), (195.5, 200.0), (198.5, 10.0), (258.5, 10.0), (198.5, 200.0), (258.5, 200.0), (261.5, 10.0), (321.5, 10.0), (261.5, 200.0), (321.5, 200.0), (324.0, 10.0), (384.0, 10.0), (324.0, 200.0), (384.0, 200.0), (387.0, 10.0), (447.0, 10.0), (387.0, 200.0), (447.0, 200.0), (450.0, 10.0), (510.0, 10.0), (450.0, 200.0), (510.0, 200.0), (512.5, 10.0), (572.5, 10.0), (512.5, 200.0), (572.5, 200.0), (575.5, 10.0), (635.5, 10.0), (575.5, 200.0), (635.5, 200.0), (638.5, 10.0), (698.5, 10.0), (638.5, 200.0), (698.5, 200.0), (701.0, 10.0), (761.0, 10.0), (701.0, 200.0), (761.0, 200.0), (764.0, 10.0), (824.0, 10.0), (764.0, 200.0), (824.0, 200.0), (10.0, 390.0), (70.0, 390.0), (73.0, 390.0), (133.0, 390.0), (135.5, 390.0), (195.5, 390.0), (198.5, 390.0), (258.5, 390.0), (261.5, 390.0), (321.5, 390.0), (324.0, 390.0), (384.0, 390.0), (387.0, 390.0), (447.0, 390.0), (450.0, 390.0), (510.0, 390.0), (512.5, 390.0), (572.5, 390.0), (575.5, 390.0), (635.5, 390.0), (638.5, 390.0), (698.5, 390.0), (701.0, 390.0), (761.0, 390.0), (764.0, 390.0), (824.0, 390.0), (10.0, 580.0), (70.0, 580.0), (73.0, 580.0), (133.0, 580.0), (135.5, 580.0), (195.5, 580.0), (198.5, 580.0), (258.5, 580.0)]

let startPoint = CGPoint(x: 80, y: 20)
let endPoint = CGPoint(x: 170, y: 440)

let validPoints = extractValidPoints()

private func extractValidPoints() -> [CGPoint]
{
    var validPoints: [CGPoint] = []
    
    for point in pointsArray
    {
        let coordinate = CGPoint(x: point.0, y: point.1)
        
        if coordinate.doesExistInRegion(regionStart: startPoint, regionEnd: endPoint)
        {
            validPoints.append(coordinate)
        }
    }
    
    return validPoints
}

2。求对之间的最短距离

从上面的数组中，我得到了区域内的 4 个有效坐标，它们存储在 validPoints 数组中：

(133.0, 200.0)
(135.5, 200.0)
(133.0, 390.0)
(135.5, 390.0)

现在我们可以遍历这些点来得到距离。首先我创建了一个方便的结构来更好地组织事情

struct PointPair: Comparable, Hashable
{
    private(set) var startPoint = CGPoint.zero
    private(set) var endPoint = CGPoint.zero
    private(set) var distance = CGFloat.zero
    
    init(withStartPoint start: CGPoint, andEndPoint end: CGPoint)
    {
        startPoint = start
        endPoint = end
        distance = startPoint.distance(to: endPoint)
        
        // Just for convenience
        display()
    }
    
    func display()
    {
        print("Distance (\(startPoint.x), \(startPoint.y)) and (\(endPoint.x), \(endPoint.y)): \(distance)")
    }
    
    // Needed to implement this so that we conform to Comparable and
    // can compare 2 points
    static func < (lhs: PointPair, rhs: PointPair) -> Bool
    {
        return lhs.distance < rhs.distance
    }
    
    // Need to implement this to conform to Hashable so we can insert a PointPair
    // into dictionaries and data strcutures that work with Hashable types
    func hash(into hasher: inout Hasher)
    {
        hasher.combine(startPoint.x)
        hasher.combine(startPoint.y)
        hasher.combine(endPoint.x)
        hasher.combine(endPoint.y)
    }
}

现在我可以遍历 validPoints 数组并像这样检查对：

if let nearestPoint = retrieveClosestPairUsingSort(fromPoints: validPoints)
{
    print("The nearest pair using sort O(n log n) is")
    print(nearestPoint.display())
}

private func retrieveClosestPairUsingSort(fromPoints points: [CGPoint]) -> PointPair?
{
    var pairs: [PointPair] = []
    
    // Loop through all the points
    for index in 0 ..< points.count
    {
        for secondIndex in index + 1 ..< points.count
        {
            let pointPair = PointPair(withStartPoint: points[index],
                                      andEndPoint: points[secondIndex])
            
            pairs.append(pointPair)
        }
    }
    
    return pairs.sorted().first
}

输出如下：

Distance (133.0, 200.0) and (135.5, 200.0): 2.5
Distance (133.0, 200.0) and (133.0, 390.0): 190.0
Distance (133.0, 200.0) and (135.5, 390.0): 190.01644665659865
Distance (135.5, 200.0) and (133.0, 390.0): 190.01644665659865
Distance (135.5, 200.0) and (135.5, 390.0): 190.0
Distance (133.0, 390.0) and (135.5, 390.0): 2.5
The nearest pair using sort O(n log n) is
Distance (133.0, 200.0) and (135.5, 200.0): 2.5

3。更进一步

如果你有大量的过滤点，你可以考虑将坐标放入最小堆中以在 O(log n) - I have an implementation of a heap here

中检索最近的对

if let nearestPoint = retrieveClosestPairUsingHeap(fromPoints: validPoints)
{
    print("The nearest pair using heap O(n) is")
    print(nearestPoint.display())
}

private func retrieveClosestPairUsingHeap(fromPoints points: [CGPoint]) -> PointPair?
{
    // Instantiate a min heap so the root will be the closest pair
    var heap = Heap<PointPair>(withProperty: .min)
    
    // Loop through all the points
    for index in 0 ..< points.count
    {
        for secondIndex in index + 1 ..< points.count
        {
            let pointPair = PointPair(withStartPoint: points[index],
                                      andEndPoint: points[secondIndex])
            
            heap.insert(pointPair)
        }
    }
    
    return heap.peek()
}

这也给出相同的输出：

Distance (133.0, 200.0) and (135.5, 200.0): 2.5
Distance (133.0, 200.0) and (133.0, 390.0): 190.0
Distance (133.0, 200.0) and (135.5, 390.0): 190.01644665659865
Distance (135.5, 200.0) and (133.0, 390.0): 190.01644665659865
Distance (135.5, 200.0) and (135.5, 390.0): 190.0
Distance (133.0, 390.0) and (135.5, 390.0): 2.5
The nearest pair using heap O(n) is
Distance (133.0, 390.0) and (135.5, 390.0): 2.5

我创建了一个示例，其中所有这些代码作为一个简单的控制台应用程序协同工作以进行测试 - you can grab that from here.

我希望这能回答你的问题。

查找两个 CGPoint 之间的点

Find points between two CGPoints

cgpoint

ios

swift