Codechange: Make a merged k-d tree index of all viewport signs

17 files changed, 398 insertions, 91 deletions

diff --git a/projects/openttd_vs140.vcxproj b/projects/openttd_vs140.vcxproj
index c1a23497a..63aa57f56 100644
--- a/projects/openttd_vs140.vcxproj
+++ b/projects/openttd_vs140.vcxproj
@@ -698,6 +698,7 @@
     <ClInclude Include="..\src\vehicle_type.h" />
     <ClInclude Include="..\src\vehiclelist.h" />
     <ClInclude Include="..\src\viewport_func.h" />
+    <ClInclude Include="..\src\viewport_kdtree.h" />
     <ClInclude Include="..\src\viewport_sprite_sorter.h" />
     <ClInclude Include="..\src\viewport_type.h" />
     <ClInclude Include="..\src\water.h" />
diff --git a/projects/openttd_vs140.vcxproj.filters b/projects/openttd_vs140.vcxproj.filters
index 9bd33721a..3c4fc43d9 100644
--- a/projects/openttd_vs140.vcxproj.filters
+++ b/projects/openttd_vs140.vcxproj.filters
@@ -1182,6 +1182,9 @@
     <ClInclude Include="..\src\viewport_func.h">
       <Filter>Header Files</Filter>
     </ClInclude>
+    <ClInclude Include="..\src\viewport_kdtree.h">
+      <Filter>Header Files</Filter>
+    </ClInclude>
     <ClInclude Include="..\src\viewport_sprite_sorter.h">
       <Filter>Header Files</Filter>
     </ClInclude>
diff --git a/projects/openttd_vs141.vcxproj b/projects/openttd_vs141.vcxproj
index 2b6c5c178..c65269eab 100644
--- a/projects/openttd_vs141.vcxproj
+++ b/projects/openttd_vs141.vcxproj
@@ -698,6 +698,7 @@
     <ClInclude Include="..\src\vehicle_type.h" />
     <ClInclude Include="..\src\vehiclelist.h" />
     <ClInclude Include="..\src\viewport_func.h" />
+    <ClInclude Include="..\src\viewport_kdtree.h" />
     <ClInclude Include="..\src\viewport_sprite_sorter.h" />
     <ClInclude Include="..\src\viewport_type.h" />
     <ClInclude Include="..\src\water.h" />
diff --git a/projects/openttd_vs141.vcxproj.filters b/projects/openttd_vs141.vcxproj.filters
index 9bd33721a..3c4fc43d9 100644
--- a/projects/openttd_vs141.vcxproj.filters
+++ b/projects/openttd_vs141.vcxproj.filters
@@ -1182,6 +1182,9 @@
     <ClInclude Include="..\src\viewport_func.h">
       <Filter>Header Files</Filter>
     </ClInclude>
+    <ClInclude Include="..\src\viewport_kdtree.h">
+      <Filter>Header Files</Filter>
+    </ClInclude>
     <ClInclude Include="..\src\viewport_sprite_sorter.h">
       <Filter>Header Files</Filter>
     </ClInclude>
diff --git a/projects/openttd_vs142.vcxproj b/projects/openttd_vs142.vcxproj
index 66b07576a..0ffaf9f38 100644
--- a/projects/openttd_vs142.vcxproj
+++ b/projects/openttd_vs142.vcxproj
@@ -698,6 +698,7 @@
     <ClInclude Include="..\src\vehicle_type.h" />
     <ClInclude Include="..\src\vehiclelist.h" />
     <ClInclude Include="..\src\viewport_func.h" />
+    <ClInclude Include="..\src\viewport_kdtree.h" />
     <ClInclude Include="..\src\viewport_sprite_sorter.h" />
     <ClInclude Include="..\src\viewport_type.h" />
     <ClInclude Include="..\src\water.h" />
diff --git a/projects/openttd_vs142.vcxproj.filters b/projects/openttd_vs142.vcxproj.filters
index 9bd33721a..3c4fc43d9 100644
--- a/projects/openttd_vs142.vcxproj.filters
+++ b/projects/openttd_vs142.vcxproj.filters
@@ -1182,6 +1182,9 @@
     <ClInclude Include="..\src\viewport_func.h">
       <Filter>Header Files</Filter>
     </ClInclude>
+    <ClInclude Include="..\src\viewport_kdtree.h">
+      <Filter>Header Files</Filter>
+    </ClInclude>
     <ClInclude Include="..\src\viewport_sprite_sorter.h">
       <Filter>Header Files</Filter>
     </ClInclude>
diff --git a/source.list b/source.list
index 74068d48d..d744101ea 100644
--- a/source.list
+++ b/source.list
@@ -385,6 +385,7 @@ vehicle_gui_base.h
 vehicle_type.h
 vehiclelist.h
 viewport_func.h
+viewport_kdtree.h
 viewport_sprite_sorter.h
 viewport_type.h
 water.h
diff --git a/src/misc.cpp b/src/misc.cpp
index b1d480d82..4e3086fce 100644
--- a/src/misc.cpp
+++ b/src/misc.cpp
@@ -30,6 +30,7 @@
 #include "linkgraph/linkgraphschedule.h"
 #include "station_kdtree.h"
 #include "town_kdtree.h"
+#include "viewport_kdtree.h"
 
 #include "safeguards.h"
 
@@ -79,6 +80,7 @@ void InitializeGame(uint size_x, uint size_y, bool reset_date, bool reset_settin
 
 	RebuildStationKdtree();
 	RebuildTownKdtree();
+	RebuildViewportKdtree();
 
 	ResetPersistentNewGRFData();
 
diff --git a/src/saveload/afterload.cpp b/src/saveload/afterload.cpp
index a80114f91..ea7882e89 100644
--- a/src/saveload/afterload.cpp
+++ b/src/saveload/afterload.cpp
@@ -19,6 +19,7 @@
 #include "../network/network_func.h"
 #include "../gfxinit.h"
 #include "../viewport_func.h"
+#include "../viewport_kdtree.h"
 #include "../industry.h"
 #include "../clear_map.h"
 #include "../vehicle_func.h"
@@ -221,6 +222,7 @@ void UpdateAllVirtCoords()
 	UpdateAllStationVirtCoords();
 	UpdateAllSignVirtCoords();
 	UpdateAllTownVirtCoords();
+	RebuildViewportKdtree();
 }
 
 /**
@@ -538,6 +540,9 @@ bool AfterLoadGame()
 
 	RebuildTownKdtree();
 	RebuildStationKdtree();
+	/* This needs to be done even before conversion, because some conversions will destroy objects
+	 * that otherwise won't exist in the tree. */
+	RebuildViewportKdtree();
 
 	if (IsSavegameVersionBefore(SLV_98)) GamelogGRFAddList(_grfconfig);
 
diff --git a/src/signs_cmd.cpp b/src/signs_cmd.cpp
index 4badd3605..69fde2559 100644
--- a/src/signs_cmd.cpp
+++ b/src/signs_cmd.cpp
@@ -16,6 +16,7 @@
 #include "signs_func.h"
 #include "command_func.h"
 #include "tilehighlight_func.h"
+#include "viewport_kdtree.h"
 #include "window_func.h"
 #include "string_func.h"
 
@@ -57,7 +58,7 @@ CommandCost CmdPlaceSign(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32
 		if (!StrEmpty(text)) {
 			si->name = stredup(text);
 		}
-		si->UpdateVirtCoord();
+		_viewport_sign_kdtree.Insert(ViewportSignKdtreeItem::MakeSign(si->index));
 		InvalidateWindowData(WC_SIGN_LIST, 0, 0);
 		_new_sign_id = si->index;
 	}
@@ -98,7 +99,7 @@ CommandCost CmdRenameSign(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32
 		}
 	} else { // Delete sign
 		if (flags & DC_EXEC) {
-			si->sign.MarkDirty();
+			_viewport_sign_kdtree.Remove(ViewportSignKdtreeItem::MakeSign(si->index));
 			delete si;
 
 			InvalidateWindowData(WC_SIGN_LIST, 0, 0);
diff --git a/src/station.cpp b/src/station.cpp
index 5722fcdcf..3c50ef94f 100644
--- a/src/station.cpp
+++ b/src/station.cpp
@@ -14,6 +14,7 @@
 #include "company_base.h"
 #include "roadveh.h"
 #include "viewport_func.h"
+#include "viewport_kdtree.h"
 #include "date_func.h"
 #include "command_func.h"
 #include "news_func.h"
@@ -163,6 +164,7 @@ Station::~Station()
 	CargoPacket::InvalidateAllFrom(this->index);
 
 	_station_kdtree.Remove(this->index);
+	_viewport_sign_kdtree.Remove(ViewportSignKdtreeItem::MakeStation(this->index));
 }
 
 
diff --git a/src/station_cmd.cpp b/src/station_cmd.cpp
index 67ea4daf5..f7eb353a0 100644
--- a/src/station_cmd.cpp
+++ b/src/station_cmd.cpp
@@ -14,6 +14,7 @@
 #include "bridge_map.h"
 #include "cmd_helper.h"
 #include "viewport_func.h"
+#include "viewport_kdtree.h"
 #include "command_func.h"
 #include "town.h"
 #include "news_func.h"
@@ -672,9 +673,11 @@ static void UpdateStationSignCoord(BaseStation *st)
 	/* clamp sign coord to be inside the station rect */
 	TileIndex new_xy = TileXY(ClampU(TileX(st->xy), r->left, r->right), ClampU(TileY(st->xy), r->top, r->bottom));
 	if (new_xy != st->xy) {
+		_viewport_sign_kdtree.Remove(ViewportSignKdtreeItem::MakeStation(st->index));
 		_station_kdtree.Remove(st->index);
 		st->xy = new_xy;
 		_station_kdtree.Insert(st->index);
+		_viewport_sign_kdtree.Insert(ViewportSignKdtreeItem::MakeStation(st->index));
 		st->UpdateVirtCoord();
 	}
 
@@ -715,6 +718,7 @@ static CommandCost BuildStationPart(Station **st, DoCommandFlag flags, bool reus
 		if (flags & DC_EXEC) {
 			*st = new Station(area.tile);
 			_station_kdtree.Insert((*st)->index);
+			_viewport_sign_kdtree.Insert(ViewportSignKdtreeItem::MakeStation((*st)->index));
 
 			(*st)->town = ClosestTownFromTile(area.tile, UINT_MAX);
 			(*st)->string_id = GenerateStationName(*st, area.tile, name_class);
@@ -3975,6 +3979,7 @@ void BuildOilRig(TileIndex tile)
 	st->rect.BeforeAddTile(tile, StationRect::ADD_FORCE);
 
 	st->UpdateVirtCoord();
+	_viewport_sign_kdtree.Insert(ViewportSignKdtreeItem::MakeStation(st->index));
 	st->RecomputeCatchment();
 	UpdateStationAcceptance(st, false);
 }
diff --git a/src/town_cmd.cpp b/src/town_cmd.cpp
index 0f1ccbba3..ee2f49d93 100644
--- a/src/town_cmd.cpp
+++ b/src/town_cmd.cpp
@@ -14,6 +14,7 @@
 #include "road_cmd.h"
 #include "landscape.h"
 #include "viewport_func.h"
+#include "viewport_kdtree.h"
 #include "cmd_helper.h"
 #include "command_func.h"
 #include "industry.h"
@@ -1713,6 +1714,7 @@ static void DoCreateTown(Town *t, TileIndex tile, uint32 townnameparts, TownSize
 	t->townnameparts = townnameparts;
 
 	t->UpdateVirtCoord();
+	_viewport_sign_kdtree.Insert(ViewportSignKdtreeItem::MakeTown(t->index));
 	InvalidateWindowData(WC_TOWN_DIRECTORY, 0, 0);
 
 	t->InitializeLayout(layout);
@@ -2869,6 +2871,7 @@ CommandCost CmdDeleteTown(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32
 	/* The town destructor will delete the other things related to the town. */
 	if (flags & DC_EXEC) {
 		_town_kdtree.Remove(t->index);
+		_viewport_sign_kdtree.Insert(ViewportSignKdtreeItem::MakeTown(t->index));
 		delete t;
 	}
 
diff --git a/src/viewport.cpp b/src/viewport.cpp
index 894595119..5e8297143 100644
--- a/src/viewport.cpp
+++ b/src/viewport.cpp
@@ -82,6 +82,7 @@
 #include "tilehighlight_func.h"
 #include "window_gui.h"
 #include "linkgraph/linkgraph_gui.h"
+#include "viewport_kdtree.h"
 #include "viewport_sprite_sorter.h"
 #include "bridge_map.h"
 #include "company_base.h"
@@ -99,6 +100,10 @@
 Point _tile_fract_coords;
 
 
+ViewportSignKdtree _viewport_sign_kdtree(&Kdtree_ViewportSignXYFunc);
+static int _viewport_sign_maxwidth = 0;
+
+
 static const int MAX_TILE_EXTENT_LEFT   = ZOOM_LVL_BASE * TILE_PIXELS;                     ///< Maximum left   extent of tile relative to north corner.
 static const int MAX_TILE_EXTENT_RIGHT  = ZOOM_LVL_BASE * TILE_PIXELS;                     ///< Maximum right  extent of tile relative to north corner.
 static const int MAX_TILE_EXTENT_TOP    = ZOOM_LVL_BASE * MAX_BUILDING_PIXELS;             ///< Maximum top    extent of tile relative to north corner (not considering bridges).
@@ -1214,62 +1219,117 @@ void ViewportAddString(const DrawPixelInfo *dpi, ZoomLevel small_from, const Vie
 	}
 }
 
-static void ViewportAddTownNames(DrawPixelInfo *dpi)
+static Rect ExpandRectWithViewportSignMargins(Rect r, ZoomLevel zoom)
 {
-	if (!HasBit(_display_opt, DO_SHOW_TOWN_NAMES) || _game_mode == GM_MENU) return;
+	/* Pessimistically always use normal font, but also assume small font is never larger in either dimension */
+	const int fh = FONT_HEIGHT_NORMAL;
+	const int max_tw = _viewport_sign_maxwidth / 2 + 1;
+	const int expand_y = ScaleByZoom(VPSM_TOP + fh + VPSM_BOTTOM, zoom);
+	const int expand_x = ScaleByZoom(VPSM_LEFT + max_tw + VPSM_RIGHT, zoom);
 
-	const Town *t;
-	FOR_ALL_TOWNS(t) {
-		ViewportAddString(dpi, ZOOM_LVL_OUT_16X, &t->cache.sign,
-				_settings_client.gui.population_in_label ? STR_VIEWPORT_TOWN_POP : STR_VIEWPORT_TOWN,
-				STR_VIEWPORT_TOWN_TINY_WHITE, STR_VIEWPORT_TOWN_TINY_BLACK,
-				t->index, t->cache.population);
-	}
-}
+	r.left -= expand_x;
+	r.right += expand_x;
+	r.top -= expand_y;
+	r.bottom += expand_y;
 
+	return r;
+}
 
-static void ViewportAddStationNames(DrawPixelInfo *dpi)
+static void ViewportAddKdtreeSigns(DrawPixelInfo *dpi)
 {
-	if (!(HasBit(_display_opt, DO_SHOW_STATION_NAMES) || HasBit(_display_opt, DO_SHOW_WAYPOINT_NAMES)) || _game_mode == GM_MENU) return;
+	Rect search_rect{ dpi->left, dpi->top, dpi->left + dpi->width, dpi->top + dpi->height };
+	search_rect = ExpandRectWithViewportSignMargins(search_rect, dpi->zoom);
+
+	bool show_stations = HasBit(_display_opt, DO_SHOW_STATION_NAMES) && _game_mode != GM_MENU;
+	bool show_waypoints = HasBit(_display_opt, DO_SHOW_WAYPOINT_NAMES) && _game_mode != GM_MENU;
+	bool show_towns = HasBit(_display_opt, DO_SHOW_TOWN_NAMES) && _game_mode != GM_MENU;
+	bool show_signs = HasBit(_display_opt, DO_SHOW_SIGNS) && !IsInvisibilitySet(TO_SIGNS);
+	bool show_competitors = HasBit(_display_opt, DO_SHOW_COMPETITOR_SIGNS);
 
 	const BaseStation *st;
-	FOR_ALL_BASE_STATIONS(st) {
-		/* Check whether the base station is a station or a waypoint */
-		bool is_station = Station::IsExpected(st);
+	const Sign *si;
 
-		/* Don't draw if the display options are disabled */
-		if (!HasBit(_display_opt, is_station ? DO_SHOW_STATION_NAMES : DO_SHOW_WAYPOINT_NAMES)) continue;
+	/* Collect all the items first and draw afterwards, to ensure layering */
+	std::vector<const BaseStation *> stations;
+	std::vector<const Town *> towns;
+	std::vector<const Sign *> signs;
 
-		/* Don't draw if station is owned by another company and competitor station names are hidden. Stations owned by none are never ignored. */
-		if (!HasBit(_display_opt, DO_SHOW_COMPETITOR_SIGNS) && _local_company != st->owner && st->owner != OWNER_NONE) continue;
+	_viewport_sign_kdtree.FindContained(search_rect.left, search_rect.top, search_rect.right, search_rect.bottom, [&](const ViewportSignKdtreeItem & item) {
+		switch (item.type) {
+			case ViewportSignKdtreeItem::VKI_STATION:
+				if (!show_stations) break;
+				st = BaseStation::Get(item.id.station);
 
-		ViewportAddString(dpi, ZOOM_LVL_OUT_16X, &st->sign,
-				is_station ? STR_VIEWPORT_STATION : STR_VIEWPORT_WAYPOINT,
-				(is_station ? STR_VIEWPORT_STATION : STR_VIEWPORT_WAYPOINT) + 1, STR_NULL,
-				st->index, st->facilities, (st->owner == OWNER_NONE || !st->IsInUse()) ? COLOUR_GREY : _company_colours[st->owner]);
-	}
-}
+				/* Don't draw if station is owned by another company and competitor station names are hidden. Stations owned by none are never ignored. */
+				if (!show_competitors && _local_company != st->owner && st->owner != OWNER_NONE) break;
 
+				stations.push_back(st);
+				break;
 
-static void ViewportAddSigns(DrawPixelInfo *dpi)
-{
-	/* Signs are turned off or are invisible */
-	if (!HasBit(_display_opt, DO_SHOW_SIGNS) || IsInvisibilitySet(TO_SIGNS)) return;
+			case ViewportSignKdtreeItem::VKI_WAYPOINT:
+				if (!show_waypoints) break;
+				st = BaseStation::Get(item.id.station);
 
-	const Sign *si;
-	FOR_ALL_SIGNS(si) {
-		/* Don't draw if sign is owned by another company and competitor signs should be hidden.
-		 * Note: It is intentional that also signs owned by OWNER_NONE are hidden. Bankrupt
-		 * companies can leave OWNER_NONE signs after them. */
-		if (!HasBit(_display_opt, DO_SHOW_COMPETITOR_SIGNS) && _local_company != si->owner && si->owner != OWNER_DEITY) continue;
+				/* Don't draw if station is owned by another company and competitor station names are hidden. Stations owned by none are never ignored. */
+				if (!show_competitors && _local_company != st->owner && st->owner != OWNER_NONE) break;
+
+				stations.push_back(st);
+				break;
+
+			case ViewportSignKdtreeItem::VKI_TOWN:
+				if (!show_towns) break;
+				towns.push_back(Town::Get(item.id.town));
+				break;
+
+			case ViewportSignKdtreeItem::VKI_SIGN:
+				if (!show_signs) break;
+				si = Sign::Get(item.id.sign);
+
+				/* Don't draw if sign is owned by another company and competitor signs should be hidden.
+				* Note: It is intentional that also signs owned by OWNER_NONE are hidden. Bankrupt
+				* companies can leave OWNER_NONE signs after them. */
+				if (!show_competitors && _local_company != si->owner && si->owner != OWNER_DEITY) break;
+
+				signs.push_back(si);
+				break;
+
+			default:
+				NOT_REACHED();
+		}
+	});
+
+	/* Layering order (bottom to top): Town names, signs, stations */
 
+	for (const auto *t : towns) {
+		ViewportAddString(dpi, ZOOM_LVL_OUT_16X, &t->cache.sign,
+			_settings_client.gui.population_in_label ? STR_VIEWPORT_TOWN_POP : STR_VIEWPORT_TOWN,
+			STR_VIEWPORT_TOWN_TINY_WHITE, STR_VIEWPORT_TOWN_TINY_BLACK,
+			t->index, t->cache.population);
+	}
+
+	for (const auto *si : signs) {
 		ViewportAddString(dpi, ZOOM_LVL_OUT_16X, &si->sign,
-				STR_WHITE_SIGN,
-				(IsTransparencySet(TO_SIGNS) || si->owner == OWNER_DEITY) ? STR_VIEWPORT_SIGN_SMALL_WHITE : STR_VIEWPORT_SIGN_SMALL_BLACK, STR_NULL,
-				si->index, 0, (si->owner == OWNER_NONE) ? COLOUR_GREY : (si->owner == OWNER_DEITY ? INVALID_COLOUR : _company_colours[si->owner]));
+			STR_WHITE_SIGN,
+			(IsTransparencySet(TO_SIGNS) || si->owner == OWNER_DEITY) ? STR_VIEWPORT_SIGN_SMALL_WHITE : STR_VIEWPORT_SIGN_SMALL_BLACK, STR_NULL,
+			si->index, 0, (si->owner == OWNER_NONE) ? COLOUR_GREY : (si->owner == OWNER_DEITY ? INVALID_COLOUR : _company_colours[si->owner]));
+	}
+
+	for (const auto *st : stations) {
+		if (Station::IsExpected(st)) {
+			/* Station */
+			ViewportAddString(dpi, ZOOM_LVL_OUT_16X, &st->sign,
+				STR_VIEWPORT_STATION, STR_VIEWPORT_STATION + 1, STR_NULL,
+				st->index, st->facilities, (st->owner == OWNER_NONE || !st->IsInUse()) ? COLOUR_GREY : _company_colours[st->owner]);
+		} else {
+			/* Waypoint */
+			ViewportAddString(dpi, ZOOM_LVL_OUT_16X, &st->sign,
+				STR_VIEWPORT_WAYPOINT, STR_VIEWPORT_WAYPOINT + 1, STR_NULL,
+				st->index, st->facilities, (st->owner == OWNER_NONE || !st->IsInUse()) ? COLOUR_GREY : _company_colours[st->owner]);
+		}
 	}
 }
 
+
 /**
  * Update the position of the viewport sign.
  * @param center the (preferred) center of the viewport sign
@@ -1520,9 +1580,7 @@ void ViewportDoDraw(const ViewPort *vp, int left, int top, int right, int bottom
 	ViewportAddLandscape();
 	ViewportAddVehicles(&_vd.dpi);
 
-	ViewportAddTownNames(&_vd.dpi);
-	ViewportAddStationNames(&_vd.dpi);
-	ViewportAddSigns(&_vd.dpi);
+	ViewportAddKdtreeSigns(&_vd.dpi);
 
 	DrawTextEffects(&_vd.dpi);
 
@@ -1930,75 +1988,202 @@ static bool CheckClickOnViewportSign(const ViewPort *vp, int x, int y, const Vie
 	int sign_half_width = ScaleByZoom((small ? sign->width_small : sign->width_normal) / 2, vp->zoom);
 	int sign_height = ScaleByZoom(VPSM_TOP + (small ? FONT_HEIGHT_SMALL : FONT_HEIGHT_NORMAL) + VPSM_BOTTOM, vp->zoom);
 
-	x = ScaleByZoom(x - vp->left, vp->zoom) + vp->virtual_left;
-	y = ScaleByZoom(y - vp->top, vp->zoom) + vp->virtual_top;
-
 	return y >= sign->top && y < sign->top + sign_height &&
 			x >= sign->center - sign_half_width && x < sign->center + sign_half_width;
 }
 
-static bool CheckClickOnTown(const ViewPort *vp, int x, int y)
+
+/**
+ * Check whether any viewport sign was clicked, and dispatch the click.
+ * @param vp the clicked viewport
+ * @param x X position of click
+ * @param y Y position of click
+ * @return true if the sign was hit
+ */
+static bool CheckClickOnViewportSign(const ViewPort *vp, int x, int y)
 {
-	if (!HasBit(_display_opt, DO_SHOW_TOWN_NAMES)) return false;
+	x = ScaleByZoom(x - vp->left, vp->zoom) + vp->virtual_left;
+	y = ScaleByZoom(y - vp->top, vp->zoom) + vp->virtual_top;
+
+	Rect search_rect{ x - 1, y - 1, x + 1, y + 1 };
+	search_rect = ExpandRectWithViewportSignMargins(search_rect, vp->zoom);
+
+	bool show_stations = HasBit(_display_opt, DO_SHOW_STATION_NAMES) && _game_mode != GM_MENU;
+	bool show_waypoints = HasBit(_display_opt, DO_SHOW_WAYPOINT_NAMES) && _game_mode != GM_MENU;
+	bool show_towns = HasBit(_display_opt, DO_SHOW_TOWN_NAMES) && _game_mode != GM_MENU;
+	bool show_signs = HasBit(_display_opt, DO_SHOW_SIGNS) && !IsInvisibilitySet(TO_SIGNS);
+	bool show_competitors = HasBit(_display_opt, DO_SHOW_COMPETITOR_SIGNS);
+
+	/* Topmost of each type that was hit */
+	BaseStation *st = NULL, *last_st = NULL;
+	Town *t = NULL, *last_t = NULL;
+	Sign *si = NULL, *last_si = NULL;
+
+	/* See ViewportAddKdtreeSigns() for details on the search logic */
+	_viewport_sign_kdtree.FindContained(search_rect.left, search_rect.top, search_rect.right, search_rect.bottom, [&](const ViewportSignKdtreeItem & item) {
+		switch (item.type) {
+			case ViewportSignKdtreeItem::VKI_STATION:
+				if (!show_stations) break;
+				st = BaseStation::Get(item.id.station);
+				if (!show_competitors && _local_company != st->owner && st->owner != OWNER_NONE) break;
+				if (CheckClickOnViewportSign(vp, x, y, &st->sign)) last_st = st;
+				break;
+
+			case ViewportSignKdtreeItem::VKI_WAYPOINT:
+				if (!show_waypoints) break;
+				st = BaseStation::Get(item.id.station);
+				if (!show_competitors && _local_company != st->owner && st->owner != OWNER_NONE) break;
+				if (CheckClickOnViewportSign(vp, x, y, &st->sign)) last_st = st;
+				break;
 
-	const Town *t;
-	FOR_ALL_TOWNS(t) {
-		if (CheckClickOnViewportSign(vp, x, y, &t->cache.sign)) {
-			ShowTownViewWindow(t->index);
-			return true;
+			case ViewportSignKdtreeItem::VKI_TOWN:
+				if (!show_towns) break;
+				t = Town::Get(item.id.town);
+				if (CheckClickOnViewportSign(vp, x, y, &t->cache.sign)) last_t = t;
+				break;
+
+			case ViewportSignKdtreeItem::VKI_SIGN:
+				if (!show_signs) break;
+				si = Sign::Get(item.id.sign);
+				if (!show_competitors && _local_company != si->owner && si->owner != OWNER_DEITY) break;
+				if (CheckClickOnViewportSign(vp, x, y, &si->sign)) last_si = si;
+				break;
+
+			default:
+				NOT_REACHED();
+		}
+	});
+
+	/* Select which hit to handle based on priority */
+	if (last_st != NULL) {
+		if (Station::IsExpected(last_st)) {
+			ShowStationViewWindow(last_st->index);
+		} else {
+			ShowWaypointWindow(Waypoint::From(last_st));
 		}
+		return true;
+	} else if (last_t != NULL) {
+		ShowTownViewWindow(last_t->index);
+		return true;
+	} else if (last_si != NULL) {
+		HandleClickOnSign(last_si);
+		return true;
+	} else {
+		return false;
 	}
+}
 
-	return false;
+
+ViewportSignKdtreeItem ViewportSignKdtreeItem::MakeStation(StationID id)
+{
+	ViewportSignKdtreeItem item;
+	item.type = VKI_STATION;
+	item.id.station = id;
+
+	const Station *st = Station::Get(id);
+	Point pt = RemapCoords2(TileX(st->xy) * TILE_SIZE, TileY(st->xy) * TILE_SIZE);
+
+	pt.y -= 32 * ZOOM_LVL_BASE;
+	if ((st->facilities & FACIL_AIRPORT) && st->airport.type == AT_OILRIG) pt.y -= 16 * ZOOM_LVL_BASE;
+
+	item.center = pt.x;
+	item.top = pt.y;
+
+	/* Assume the sign can be a candidate for drawing, so measure its width */
+	_viewport_sign_maxwidth = max<int>(_viewport_sign_maxwidth, st->sign.width_normal);
+
+	return item;
 }
 
-static bool CheckClickOnStation(const ViewPort *vp, int x, int y)
+ViewportSignKdtreeItem ViewportSignKdtreeItem::MakeWaypoint(StationID id)
 {
-	if (!(HasBit(_display_opt, DO_SHOW_STATION_NAMES) || HasBit(_display_opt, DO_SHOW_WAYPOINT_NAMES)) || IsInvisibilitySet(TO_SIGNS)) return false;
+	ViewportSignKdtreeItem item;
+	item.type = VKI_WAYPOINT;
+	item.id.station = id;
 
-	const BaseStation *st;
-	FOR_ALL_BASE_STATIONS(st) {
-		/* Check whether the base station is a station or a waypoint */
-		bool is_station = Station::IsExpected(st);
+	const Waypoint *st = Waypoint::Get(id);
+	Point pt = RemapCoords2(TileX(st->xy) * TILE_SIZE, TileY(st->xy) * TILE_SIZE);
 
-		/* Don't check if the display options are disabled */
-		if (!HasBit(_display_opt, is_station ? DO_SHOW_STATION_NAMES : DO_SHOW_WAYPOINT_NAMES)) continue;
+	pt.y -= 32 * ZOOM_LVL_BASE;
 
-		/* Don't check if competitor signs are not shown and the sign isn't owned by the local company */
-		if (!HasBit(_display_opt, DO_SHOW_COMPETITOR_SIGNS) && _local_company != st->owner && st->owner != OWNER_NONE) continue;
+	item.center = pt.x;
+	item.top = pt.y;
 
-		if (CheckClickOnViewportSign(vp, x, y, &st->sign)) {
-			if (is_station) {
-				ShowStationViewWindow(st->index);
-			} else {
-				ShowWaypointWindow(Waypoint::From(st));
-			}
-			return true;
-		}
-	}
+	/* Assume the sign can be a candidate for drawing, so measure its width */
+	_viewport_sign_maxwidth = max<int>(_viewport_sign_maxwidth, st->sign.width_normal);
 
-	return false;
+	return item;
 }
 
+ViewportSignKdtreeItem ViewportSignKdtreeItem::MakeTown(TownID id)
+{
+	ViewportSignKdtreeItem item;
+	item.type = VKI_TOWN;
+	item.id.town = id;
+
+	const Town *town = Town::Get(id);
+	Point pt = RemapCoords2(TileX(town->xy) * TILE_SIZE, TileY(town->xy) * TILE_SIZE);
+
+	pt.y -= 24 * ZOOM_LVL_BASE;
 
-static bool CheckClickOnSign(const ViewPort *vp, int x, int y)
+	item.center = pt.x;
+	item.top = pt.y;
+
+	/* Assume the sign can be a candidate for drawing, so measure its width */
+	_viewport_sign_maxwidth = max<int>(_viewport_sign_maxwidth, town->cache.sign.width_normal);
+
+	return item;
+}
+
+ViewportSignKdtreeItem ViewportSignKdtreeItem::MakeSign(SignID id)
 {
-	/* Signs are turned off, or they are transparent and invisibility is ON, or company is a spectator */
-	if (!HasBit(_display_opt, DO_SHOW_SIGNS) || IsInvisibilitySet(TO_SIGNS) || _local_company == COMPANY_SPECTATOR) return false;
+	ViewportSignKdtreeItem item;
+	item.type = VKI_SIGN;
+	item.id.sign = id;
 
-	const Sign *si;
-	FOR_ALL_SIGNS(si) {
-		/* If competitor signs are hidden, don't check signs that aren't owned by local company */
-		if (!HasBit(_display_opt, DO_SHOW_COMPETITOR_SIGNS) && _local_company != si->owner && si->owner != OWNER_DEITY) continue;
-		if (si->owner == OWNER_DEITY && _game_mode != GM_EDITOR) continue;
-
-		if (CheckClickOnViewportSign(vp, x, y, &si->sign)) {
-			HandleClickOnSign(si);
-			return true;
-		}
+	const Sign *sign = Sign::Get(id);
+	Point pt = RemapCoords(sign->x, sign->y, sign->z);
+
+	pt.y -= 6 * ZOOM_LVL_BASE;
+
+	item.center = pt.x;
+	item.top = pt.y;
+
+	/* Assume the sign can be a candidate for drawing, so measure its width */
+	_viewport_sign_maxwidth = max<int>(_viewport_sign_maxwidth, sign->sign.width_normal);
+
+	return item;
+}
+
+void RebuildViewportKdtree()
+{
+	/* Reset biggest size sign seen */
+	_viewport_sign_maxwidth = 0;
+
+	std::vector<ViewportSignKdtreeItem> items;
+	items.reserve(BaseStation::GetNumItems() + Town::GetNumItems() + Sign::GetNumItems());
+
+	const Station *st;
+	FOR_ALL_STATIONS(st) {
+		items.push_back(ViewportSignKdtreeItem::MakeStation(st->index));
 	}
 
-	return false;
+	const Waypoint *wp;
+	FOR_ALL_WAYPOINTS(wp) {
+		items.push_back(ViewportSignKdtreeItem::MakeWaypoint(wp->index));
+	}
+
+	const Town *town;
+	FOR_ALL_TOWNS(town) {
+		items.push_back(ViewportSignKdtreeItem::MakeTown(town->index));
+	}
+
+	const Sign *sign;
+	FOR_ALL_SIGNS(sign) {
+		items.push_back(ViewportSignKdtreeItem::MakeSign(sign->index));
+	}
+
+	_viewport_sign_kdtree.Build(items.begin(), items.end());
 }
 
 
@@ -2045,9 +2230,7 @@ bool HandleViewportClicked(const ViewPort *vp, int x, int y)
 		return true;
 	}
 
-	if (CheckClickOnTown(vp, x, y)) return true;
-	if (CheckClickOnStation(vp, x, y)) return true;
-	if (CheckClickOnSign(vp, x, y)) return true;
+	if (CheckClickOnViewportSign(vp, x, y)) return true;
 	bool result = CheckClickOnLandscape(vp, x, y);
 
 	if (v != NULL) {
diff --git a/src/viewport_kdtree.h b/src/viewport_kdtree.h
new file mode 100644
index 000000000..93344a5e6
--- /dev/null
+++ b/src/viewport_kdtree.h
@@ -0,0 +1,83 @@
+/*
+* This file is part of OpenTTD.
+* OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
+* OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+* See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
+*/
+
+/** @file town_kdtree.h Declarations for accessing the k-d tree of towns */
+
+#ifndef VIEWPORT_KDTREE_H
+#define VIEWPORT_KDTREE_H
+
+#include "core/kdtree.hpp"
+#include "viewport_type.h"
+#include "station_base.h"
+#include "town_type.h"
+#include "signs_base.h"
+
+struct ViewportSignKdtreeItem {
+	enum ItemType : uint16 {
+		VKI_STATION,
+		VKI_WAYPOINT,
+		VKI_TOWN,
+		VKI_SIGN,
+	};
+	ItemType type;
+	union {
+		StationID station;
+		TownID town;
+		SignID sign;
+	} id;
+	int32 center;
+	int32 top;
+
+	bool operator== (const ViewportSignKdtreeItem &other) const
+	{
+		if (this->type != other.type) return false;
+		switch (this->type) {
+			case VKI_STATION:
+			case VKI_WAYPOINT:
+				return this->id.station == other.id.station;
+			case VKI_TOWN:
+				return this->id.town == other.id.town;
+			case VKI_SIGN:
+				return this->id.sign == other.id.sign;
+			default:
+				NOT_REACHED();
+		}
+	}
+
+	bool operator< (const ViewportSignKdtreeItem &other) const
+	{
+		if (this->type != other.type) return this->type < other.type;
+		switch (this->type) {
+			case VKI_STATION:
+			case VKI_WAYPOINT:
+				return this->id.station < other.id.station;
+			case VKI_TOWN:
+				return this->id.town < other.id.town;
+			case VKI_SIGN:
+				return this->id.sign < other.id.sign;
+			default:
+				NOT_REACHED();
+		}
+	}
+
+	static ViewportSignKdtreeItem MakeStation(StationID id);
+	static ViewportSignKdtreeItem MakeWaypoint(StationID id);
+	static ViewportSignKdtreeItem MakeTown(TownID id);
+	static ViewportSignKdtreeItem MakeSign(SignID id);
+};
+
+inline int32 Kdtree_ViewportSignXYFunc(const ViewportSignKdtreeItem &item, int dim)
+{
+	return (dim == 0) ? item.center : item.top;
+}
+
+typedef Kdtree<ViewportSignKdtreeItem, decltype(&Kdtree_ViewportSignXYFunc), int32, int32> ViewportSignKdtree;
+extern ViewportSignKdtree _viewport_sign_kdtree;
+
+void RebuildViewportKdtree();
+
+#endif
diff --git a/src/waypoint.cpp b/src/waypoint.cpp
index 857f8ba87..8452ff618 100644
--- a/src/waypoint.cpp
+++ b/src/waypoint.cpp
@@ -15,6 +15,7 @@
 #include "window_func.h"
 #include "newgrf_station.h"
 #include "waypoint_base.h"
+#include "viewport_kdtree.h"
 
 #include "safeguards.h"
 
@@ -54,4 +55,5 @@ Waypoint::~Waypoint()
 	if (CleaningPool()) return;
 	DeleteWindowById(WC_WAYPOINT_VIEW, this->index);
 	RemoveOrderFromAllVehicles(OT_GOTO_WAYPOINT, this->index);
+	_viewport_sign_kdtree.Remove(ViewportSignKdtreeItem::MakeWaypoint(this->index));
 }
diff --git a/src/waypoint_cmd.cpp b/src/waypoint_cmd.cpp
index 639dce13b..0fd5942c0 100644
--- a/src/waypoint_cmd.cpp
+++ b/src/waypoint_cmd.cpp
@@ -20,6 +20,7 @@
 #include "pathfinder/yapf/yapf_cache.h"
 #include "strings_func.h"
 #include "viewport_func.h"
+#include "viewport_kdtree.h"
 #include "window_func.h"
 #include "date_func.h"
 #include "vehicle_func.h"
@@ -225,11 +226,15 @@ CommandCost CmdBuildRailWaypoint(TileIndex start_tile, DoCommandFlag flags, uint
 	}
 
 	if (flags & DC_EXEC) {
+		bool need_sign_update = false;
 		if (wp == NULL) {
 			wp = new Waypoint(start_tile);
+			need_sign_update = true;
 		} else if (!wp->IsInUse()) {
 			/* Move existing (recently deleted) waypoint to the new location */
+			_viewport_sign_kdtree.Remove(ViewportSignKdtreeItem::MakeWaypoint(wp->index));
 			wp->xy = start_tile;
+			need_sign_update = true;
 		}
 		wp->owner = GetTileOwner(start_tile);
 
@@ -244,6 +249,7 @@ CommandCost CmdBuildRailWaypoint(TileIndex start_tile, DoCommandFlag flags, uint
 		if (wp->town == NULL) MakeDefaultName(wp);
 
 		wp->UpdateVirtCoord();
+		if (need_sign_update) _viewport_sign_kdtree.Insert(ViewportSignKdtreeItem::MakeWaypoint(wp->index));
 
 		const StationSpec *spec = StationClass::Get(spec_class)->GetSpec(spec_index);
 		byte *layout_ptr = AllocaM(byte, count);
@@ -310,6 +316,7 @@ CommandCost CmdBuildBuoy(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32
 			wp = new Waypoint(tile);
 		} else {
 			/* Move existing (recently deleted) buoy to the new location */
+			_viewport_sign_kdtree.Remove(ViewportSignKdtreeItem::MakeWaypoint(wp->index));
 			wp->xy = tile;
 			InvalidateWindowData(WC_WAYPOINT_VIEW, wp->index);
 		}
@@ -328,6 +335,7 @@ CommandCost CmdBuildBuoy(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32
 		MarkTileDirtyByTile(tile);
 
 		wp->UpdateVirtCoord();
+		_viewport_sign_kdtree.Insert(ViewportSignKdtreeItem::MakeWaypoint(wp->index));
 		InvalidateWindowData(WC_WAYPOINT_VIEW, wp->index);
 	}