ポイントの配列があり、各ポイントはマップ上の座標です。ポイントをマップに追加すると、最も近い2つのポイントの間にある配列に追加されるようにしたいと思います。
さらに、異なるポイント間にクロスオーバーがないように、ポイントをレンダリングしたいと思います。結果のポリゴンの外側の端に新しいポイントを追加し、最も近い 2 つに接続する必要があります。
これを行うアルゴリズムはありますか？
編集：
わかりやすくするために、次のスクリーンショットを用意しました。メソッド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;
}