3
我有一個點陣列，其中每個點是地圖上的座標。我想這樣做是爲了當我向地圖添加一個點時，它會添加到我最近的兩個點之間的數組中。在地圖上排序點的算法？
另外，我想渲染點，以便在不同點之間不存在任何交叉點。新點應添加到生成的多邊形的外邊緣，並連接到最近的兩個邊。
有沒有這樣做的算法？
編輯：
爲了清楚起見，我有以下截圖。我想實現方法B：
編輯2：
這是我寫的，試圖解決這個問題的代碼一堆。假設MBCoordinates是正義的，座標：
//
// Detect which coordinate is the closest to the supplied coordinate
//
- (void) insertCoordinateBetweenClosestNeighbors:(MBCoordinate *)coordinate{
if (![self points] || [[self points] count] < 3) {
[[self points] addObject:coordinate];
return;
}
NSMutableSet *pointSet = [NSMutableSet setWithArray:[self points]];
MBCoordinate *closestCoordinate = [self closestCoordinateToCoordinate:coordinate inSet:pointSet];
[pointSet removeObject:closestCoordinate];
MBCoordinate *nextClosestCoordinate = [self closestCoordinateToCoordinate:coordinate inSet:pointSet];
NSUInteger indexOfClosestCoordinate, indexOfSecondClosestCoordinate, insertionIndex;
for (NSUInteger i=0; i < [[self points] count]; i++) {
if ([[self points][i] isEqual:closestCoordinate]) {
indexOfClosestCoordinate = i;
}
if ([[self points][i] isEqual:nextClosestCoordinate]) {
indexOfSecondClosestCoordinate = i;
}
}
if(indexOfSecondClosestCoordinate == indexOfClosestCoordinate-1){
insertionIndex = indexOfSecondClosestCoordinate+1;
}else{
insertionIndex = indexOfClosestCoordinate+1;
}
[[self points] insertObject:coordinate atIndex:insertionIndex];
/*
Not in use in my program, but an alternate attempt:
[[self points] addObject:coordinate];
[self sortPointsByDistance];
*/
}
- (void) sortPointsByDistance{
//
// Points that need sorting
//
NSMutableSet *unprocessedPoints = [NSMutableSet setWithArray:[self points]];
//
// All of the unsorted points
//
NSMutableSet *unsortedPoints = [NSMutableSet setWithArray:[self points]];
//
// The unsorted points minus the closest one
//
NSMutableSet *unsortedPointsExceptClosest = [NSMutableSet setWithArray:[self points]];
//
// We put the point into here in the correct order
//
NSMutableArray *sortedPoints = [@[] mutableCopy];
//
// Prime the pump
//
MBCoordinate *workingCoordinate = [self points][0];
[sortedPoints addObject:workingCoordinate];
[unprocessedPoints removeObject:workingCoordinate];
while([unprocessedPoints count] > 0){
MBCoordinate *closestCoordinate = [self closestCoordinateToCoordinate:workingCoordinate inSet:unsortedPoints];
MBCoordinate *secondClosestCoordinate = nil;
//
// The closest point might be sorted already!
//
// If it is, then we have to find the closest point.
//
if ([sortedPoints containsObject:closestCoordinate]) {
NSInteger indexOfClosest = [sortedPoints indexOfObject:closestCoordinate];
NSInteger indexOfSecondClosest = indexOfClosest;
NSInteger targetIndex = indexOfClosest+1;
if (!secondClosestCoordinate) {
[unsortedPoints removeObject:closestCoordinate];
secondClosestCoordinate = [self closestCoordinateToCoordinate:workingCoordinate inSet:unsortedPointsExceptClosest];
if ([sortedPoints containsObject:secondClosestCoordinate]) {
//
// Insert between the two points
//
indexOfSecondClosest = [sortedPoints indexOfObject:secondClosestCoordinate];
}
}
if (indexOfSecondClosest < indexOfClosest) {
targetIndex = indexOfSecondClosest + 1;
}
[sortedPoints insertObject:workingCoordinate atIndex:targetIndex];
workingCoordinate = [unprocessedPoints anyObject];
break;
}else{
workingCoordinate = closestCoordinate;
}
[sortedPoints addObject:workingCoordinate];
[unprocessedPoints removeObject:workingCoordinate];
unsortedPointsExceptClosest = [unsortedPoints copy];
secondClosestCoordinate = nil;
}
[self setPoints:sortedPoints];
}
- (MBCoordinate *) closestCoordinateToCoordinate:(MBCoordinate *)coordinate inSet:(NSSet *)aSet{
MBCoordinate *closest = nil;
CGFloat closestDistance;
for (MBCoordinate *coordinateInSet in aSet) {
if ([coordinateInSet isEqual:coordinate]) {
continue;
}
if (!closest) {
closest = coordinateInSet;
closestDistance = [self distanceBetweenCoordinate:coordinate andCoordinate:coordinateInSet];
}
CGFloat distanceBetweenPoints = [self distanceBetweenCoordinate:coordinate andCoordinate:coordinateInSet];
if (distanceBetweenPoints < closestDistance) {
closest = coordinateInSet;
closestDistance = distanceBetweenPoints;
}
}
return closest;
}
//
// Determines the distance between two coordinates
//
- (CGFloat) distanceBetweenCoordinate:(MBCoordinate *)coordinate andCoordinate:(MBCoordinate *)anotherCoordinate{
CGFloat xDistance, yDistance;
xDistance = coordinate.latitude-anotherCoordinate.latitude;
yDistance = coordinate.longitude-anotherCoordinate.longitude;
float distance = xDistance/yDistance;
//
// Absolute value of floats...
//
if (distance < 0) {
distance *= -1;
}
return distance;
}
你是否假設了凸性？另外，假設P是以C爲中心的正多邊形，並且在C處添加了一個點;應該發生什麼？ –
@ jwpat7我沒有考慮過這些事情。有沒有「優化」的方法？喜歡，假設一種方式或另一種取決於點？ – Moshe
如果您假定隨着點的添加，生成的多邊形總是凸的，那麼在O（n）時間內添加第n個點是很簡單的。如果您不假設凸面，例如允許星形，則問題可能無法解決。 Re凸包，其複雜度爲Ω（n log n），但如果假定船體內部沒有點，則可以獲得O（n）複雜度。 –