試圖找到起點和終點之間最近的點。
點陣：
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)
在這里，我試圖從現有的點陣列中找到起點和終點之間的點。
使用以下從特定點開始的延伸距離，但我無法僅獲得 startPoint 和 Endpoint 之間的特定點
extension CGPoint {
func distance(to point: CGPoint) -> CGFloat {
return sqrt(pow(x - point.x, 2) pow(y - point.y, 2))
}
}
uj5u.com熱心網友回復：
這絕不是唯一的解決方案，但這是我會采取的一種方法。
1. 從陣列中檢索有效點
我們只想從位于起點和終點之間的陣列中獲取有效點。所以為了形象化它，我假設：
我假設
- 開始 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 bottom left of the region
/// - regionEnd: The top 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) 中最接近的對 -我在這里有一個堆的實作
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
我創建了一個示例，所有這些代碼作為一個簡單的控制臺應用程式一起作業以進行測驗 -你可以從這里獲取它。
我希望這回答了你的問題。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/421116.html
標籤：