Find points between two CGPoints

Question

Trying to find nearest points between start and end point.

Points Array :

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)

Here I am trying to find points between start and end points from the existing points array.

using this below extension distance from specific point am getting but I am unable to get only specific points between startPoint and Endpoint

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

Answer 1

This is by no means the only solution, but here is one approach I would take.

1. Retrieve valid points from the array

We want to get only the valid points from the array which falls between the start and end points. So to visualize it, I assumed this:

A region is defined as follows in the iOS coordinate system with the top left being 0,0 but this should also work in other coordinate systems where the bottom left is 0,0 for example:

So to define a valid region, here are the rules:

• the start x and start y will be <= end x and end y.
• Start and end can be a straight line
• Start and end can be the same point
• But end cannot be below or to the left of start

I assume that

• the start x and start y will be <= end x and end y.
• Start and end can be a straight line
• Start and end can be the same point
• But end cannot be below or to the left of start

So in order to support that, I added to your CGPoint extension to check if the point exists in the region

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
    }
}

Then I extract only the valid points using the extension like this:

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. Find shortest distance between pairs

From your above array, I got 4 valid coordinates within the region and they are stored in the validPoints array:

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

Now we can loop through these points to get the distance. First I created a convenience struct to organize things better

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

Now I can loop through the validPoints array and check pairs like this:

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
}

The output for this is as follows:

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. Taking it one step further

If you have huge array of filtered points, you can consider putting the coordinates into a min heap to retrieve the closest pair in 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()
}

This also gives the same output:

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

I have created a sample with all of this code working together as a simple console application to test out - you can grab that from here.

I hope this answers your question.