Town *AirportGetNearestTownKdTree(const AirportSpec *as, const TileIterator &it)
{
Town *nearest = NULL;
if (Town::GetNumItems() == 0) return nearest;
// uint add = as->size_x + as->size_y - 2; // CalcClosestTownFromTile can differ from DistanceManhattan by this much
uint mindist = UINT_MAX - 1; // prevent overflow
TileIterator *copy = it.Clone();
for (TileIndex cur_tile = *copy; cur_tile != INVALID_TILE; cur_tile = ++*copy) {
Town *t = CalcClosestTownFromTile(cur_tile, mindist + 1);
if (t == NULL) continue;
uint dist = DistanceManhattan(t->xy, cur_tile);
if (dist == mindist && t->index < nearest->index) nearest = t;
if (dist < mindist) {
nearest = t;
mindist = dist;
}
}
delete copy;
return nearest;
}
Town *AirportGetNearestTownForAllTowns(const AirportSpec *as, const TileIterator &it)
{
Town *t, *nearest = NULL;
uint add = as->size_x + as->size_y - 2; // GetMinimalAirportDistanceToTile can differ from DistanceManhattan by this much
uint mindist = UINT_MAX - add; // prevent overflow
FOR_ALL_TOWNS(t) {
if (DistanceManhattan(t->xy, it) < mindist + add) { // avoid calling GetMinimalAirportDistanceToTile too often
TileIterator *copy = it.Clone();
uint dist = GetMinimalAirportDistanceToTile(*copy, t->xy);
delete copy;
if (dist < mindist) {
nearest = t;
mindist = dist;
}
}
}
return nearest;
}
/**
* Finds the town nearest to given airport. Based on minimal manhattan distance to any airport's tile.
* If two towns have the same distance, town with lower index is returned.
* @param as airport's description
* @param it An iterator over all airport tiles
* @return nearest town to airport
*/
Town *AirportGetNearestTown(const AirportSpec *as, const TileIterator &it)
{
assert(AirportGetNearestTownForAllTowns(as, it) == AirportGetNearestTownKdTree(as, it));
return AirportGetNearestTownKdTree(as, it);
}