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))
}
}
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:
I assume that
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.