--- a/station_cmd.c	Wed Dec 27 18:29:34 2006 +0000
+++ b/station_cmd.c	Wed Dec 27 23:11:43 2006 +0000
@@ -34,6 +34,14 @@
 #include "yapf/yapf.h"
 #include "date.h"
 
+static void StationRect_Init(Station *st);
+static bool StationRect_IsEmpty(Station *st);
+static bool StationRect_BeforeAddTile(Station *st, TileIndex tile, bool exec);
+static bool StationRect_BeforeAddRect(Station *st, TileIndex tile, uint16 w, uint16 h, bool exec);
+static bool StationRect_AfterRemoveTile(Station *st, TileIndex tile);
+static bool StationRect_AfterRemoveRect(Station *st, TileIndex tile, uint16 w, uint16 h);
+
+
 /**
  * Called if a new block is added to the station-pool
  */
@@ -468,6 +476,7 @@
 	st->random_bits = Random();
 	st->waiting_triggers = 0;
 
+	StationRect_Init(st);
 }
 
 // Update the virtual coords needed to draw the station sign.
@@ -733,38 +742,14 @@
 	InvalidateWindowWidget(WC_STATION_VIEW, st->index, 4);
 }
 
-static bool CheckStationSpreadOut(Station *st, TileIndex tile, int w, int h)
-{
-	StationID station_index = st->index;
-	uint x1 = TileX(tile);
-	uint y1 = TileY(tile);
-	ottd_Rectangle r = {x1, y1, x1 + w - 1, y1 + h - 1};
-	// get station bounding rect
-	for (tile = 0; tile < MapSize(); tile++) {
-		if (IsTileType(tile, MP_STATION) && GetStationIndex(tile) == station_index) MergePoint(&r, tile);
-	}
-	// check if bounding rect doesn't exceed the maximum station spread
-	if (r.max_x - r.min_x >= _patches.station_spread || r.max_y - r.min_y >= _patches.station_spread) {
-		_error_message = STR_306C_STATION_TOO_SPREAD_OUT;
-		return false;
-	}
-	return true;
-}
-
 static void UpdateStationSignCoord(Station *st)
 {
-	ottd_Rectangle r = {MapSizeX(), MapSizeY(), 0, 0};
-	TileIndex tile;
-
-	// get station bounding rect
-	for (tile = 0; tile < MapSize(); tile++) {
-		if (IsTileType(tile, MP_STATION) && GetStationIndex(tile) == st->index) MergePoint(&r, tile);
-	}
-
-	if (r.max_x < r.min_x) return; // no tiles belong to this station
-
-	// clamp sign coord to be inside the rect
-	st->xy = TileXY(clampu(TileX(st->xy), r.min_x, r.max_x), clampu(TileY(st->xy), r.min_y, r.max_y));
+	StationRect *r = &st->rect;
+
+	if (StationRect_IsEmpty(st)) return; // no tiles belong to this station
+
+	// clamp sign coord to be inside the station rect
+	st->xy = TileXY(clampu(TileX(st->xy), r->left, r->right), clampu(TileY(st->xy), r->top, r->bottom));
 	UpdateStationVirtCoordDirty(st);
 }
 
@@ -1041,7 +1026,7 @@
 		}
 
 		//XXX can't we pack this in the "else" part of the if above?
-		if (!CheckStationSpreadOut(st, tile_org, w_org, h_org)) return CMD_ERROR;
+		if (!StationRect_BeforeAddRect(st, tile_org, w_org, h_org, false)) return CMD_ERROR;
 	} else {
 		// Create a new station
 		st = AllocateStation();
@@ -1100,6 +1085,8 @@
 
 		st->build_date = _date;
 
+		StationRect_BeforeAddRect(st, tile_org, w_org, h_org, true);
+
 		tile_delta = (axis == AXIS_X ? TileDiffXY(1, 0) : TileDiffXY(0, 1));
 		track = AxisToTrack(axis);
 
@@ -1220,6 +1207,7 @@
 		uint specindex = GetCustomStationSpecIndex(tile);
 		Track track = GetRailStationTrack(tile);
 		DoClearSquare(tile);
+		StationRect_AfterRemoveTile(st, tile);
 		SetSignalsOnBothDir(tile, track);
 		YapfNotifyTrackLayoutChange(tile, track);
 
@@ -1336,7 +1324,10 @@
 	} while (--h);
 
 	if (flags & DC_EXEC) {
+		StationRect_AfterRemoveRect(st, st->train_tile, st->trainst_w, st->trainst_h);
+
 		st->train_tile = 0;
+		st->trainst_w = st->trainst_h = 0;
 		st->facilities &= ~FACIL_TRAIN;
 
 		free(st->speclist);
@@ -1462,7 +1453,7 @@
 			return_cmd_error(STR_3009_TOO_CLOSE_TO_ANOTHER_STATION);
 		}
 
-		if (!CheckStationSpreadOut(st, tile, 1, 1)) return CMD_ERROR;
+		if (!StationRect_BeforeAddTile(st, tile, false)) return CMD_ERROR;
 
 		FindRoadStopSpot(type, st, &currstop, &prev);
 	} else {
@@ -1500,6 +1491,8 @@
 
 		st->build_date = _date;
 
+		StationRect_BeforeAddTile(st, tile, true);
+
 		MakeRoadStop(tile, st->owner, st->index, type, p1);
 
 		UpdateStationVirtCoordDirty(st);
@@ -1547,6 +1540,7 @@
 
 		DeleteRoadStop(cur_stop);
 		DoClearSquare(tile);
+		StationRect_AfterRemoveTile(st, tile);
 
 		UpdateStationVirtCoordDirty(st);
 		DeleteStationIfEmpty(st);
@@ -1708,8 +1702,7 @@
 		if (st->owner != OWNER_NONE && st->owner != _current_player)
 			return_cmd_error(STR_3009_TOO_CLOSE_TO_ANOTHER_STATION);
 
-		if (!CheckStationSpreadOut(st, tile, 1, 1))
-			return CMD_ERROR;
+		if (!StationRect_BeforeAddRect(st, tile, w, h, false)) return CMD_ERROR;
 
 		if (st->airport_tile != 0)
 			return_cmd_error(STR_300D_TOO_CLOSE_TO_ANOTHER_AIRPORT);
@@ -1746,6 +1739,8 @@
 
 		st->build_date = _date;
 
+		StationRect_BeforeAddRect(st, tile, w, h, true);
+
 		/* if airport was demolished while planes were en-route to it, the
 		 * positions can no longer be the same (v->u.air.pos), since different
 		 * airports have different indexes. So update all planes en-route to this
@@ -1808,6 +1803,8 @@
 			);
 		}
 
+		StationRect_AfterRemoveRect(st, tile, w, h);
+
 		st->airport_tile = 0;
 		st->facilities &= ~FACIL_AIRPORT;
 
@@ -1977,7 +1974,7 @@
 		if (st->owner != OWNER_NONE && st->owner != _current_player)
 			return_cmd_error(STR_3009_TOO_CLOSE_TO_ANOTHER_STATION);
 
-		if (!CheckStationSpreadOut(st, tile, 1, 1)) return CMD_ERROR;
+		if (!StationRect_BeforeAddRect(st, tile, _dock_w_chk[direction], _dock_h_chk[direction], false)) return CMD_ERROR;
 
 		if (st->dock_tile != 0) return_cmd_error(STR_304C_TOO_CLOSE_TO_ANOTHER_DOCK);
 	} else {
@@ -2006,6 +2003,8 @@
 
 		st->build_date = _date;
 
+		StationRect_BeforeAddRect(st, tile, _dock_w_chk[direction], _dock_h_chk[direction], true);
+
 		MakeDock(tile, st->owner, st->index, direction);
 
 		UpdateStationVirtCoordDirty(st);
@@ -2031,8 +2030,11 @@
 
 	if (flags & DC_EXEC) {
 		DoClearSquare(tile1);
-
 		MakeWater(tile2);
+
+		StationRect_AfterRemoveTile(st, tile1);
+		StationRect_AfterRemoveTile(st, tile2);
+
 		MarkTileDirtyByTile(tile2);
 
 		st->dock_tile = 0;
@@ -2899,6 +2901,7 @@
 {
 	Station *st;
 	uint i;
+	TileIndex tile;
 
 	/* Update the speclists of all stations to point to the currently loaded custom stations. */
 	FOR_ALL_STATIONS(st) {
@@ -2908,6 +2911,12 @@
 			st->speclist[i].spec = GetCustomStationSpecByGrf(st->speclist[i].grfid, st->speclist[i].localidx);
 		}
 	}
+
+	for (tile = 0; tile < MapSize(); tile++) {
+		if (GetTileType(tile) != MP_STATION) continue;
+		st = GetStationByTile(tile);
+		StationRect_BeforeAddTile(st, tile, true);
+	}
 }
 
 
@@ -3138,3 +3147,127 @@
 	{ 'STNS', Save_STNS,      Load_STNS,      CH_ARRAY },
 	{ 'ROAD', Save_ROADSTOP,  Load_ROADSTOP,  CH_ARRAY | CH_LAST},
 };
+
+
+#define my_min(a, b) (((a) < (b)) ? (a) : (b))
+#define my_max(a, b) (((a) > (b)) ? (a) : (b))
+#define my_value_in_range(v, a, b) ((a) <= (v) && (v) <= (b))
+#define my_pt_in_rect(r, x, y) (my_value_in_range(x, (r)->left, (r)->right) && my_value_in_range(y, (r)->top, (r)->bottom))
+
+static void StationRect_Init(Station *st)
+{
+	StationRect *r = &st->rect;
+	r->left = r->top = r->right = r->bottom = 0;
+}
+
+static bool StationRect_IsEmpty(Station *st)
+{
+	return (st->rect.left == 0 || st->rect.left > st->rect.right || st->rect.top > st->rect.bottom);
+}
+
+static bool StationRect_BeforeAddTile(Station *st, TileIndex tile, bool exec)
+{
+	StationRect *r = &st->rect;
+	uint16 x = TileX(tile);
+	uint16 y = TileY(tile);
+	if (StationRect_IsEmpty(st)) {
+		// we are adding the first station tile
+		r->left = r->right = x;
+		r->top = r->bottom = y;
+	} else if (!my_pt_in_rect(r, x, y)) {
+		// current rect is not empty and new point is outside this rect
+		// make new spread-out rectangle
+		StationRect new_rect = {my_min(x, r->left), my_min(y, r->top), my_max(x, r->right), my_max(y, r->bottom)};
+		// check new rect dimensions against preset max
+		uint16 w = new_rect.right - new_rect.left + 1;
+		uint16 h = new_rect.bottom - new_rect.top + 1;
+		if (w > _patches.station_spread || h > _patches.station_spread) {
+			assert(!exec);
+			_error_message = STR_306C_STATION_TOO_SPREAD_OUT;
+			return false;
+		}
+		// spread-out ok, return true
+		if (exec) {
+			// we should update the station rect
+			*r = new_rect;
+		}
+	} else {
+		; // new point is inside the rect, we don't need to do anything
+	}
+	return true;
+}
+
+static bool StationRect_BeforeAddRect(Station *st, TileIndex tile, uint16 w, uint16 h, bool exec)
+{
+	return StationRect_BeforeAddTile(st, tile, exec) && StationRect_BeforeAddTile(st, TILE_ADDXY(tile, w - 1, h - 1), exec);
+}
+
+static inline bool ScanRectForStationTiles(StationID st_id, uint16 left, uint16 top, uint16 right, uint16 bottom)
+{
+	TileIndex top_left = TileXY(left, top);
+	uint16 width = right - left + 1;
+	uint16 height = bottom - top + 1;
+	BEGIN_TILE_LOOP(tile, width, height, top_left)
+		if (IsTileType(tile, MP_STATION) && GetStationIndex(tile) == st_id) return true;
+	END_TILE_LOOP(tile, width, height, top_left);
+	return false;
+}
+
+static bool StationRect_AfterRemoveTile(Station *st, TileIndex tile)
+{
+	StationRect *r = &st->rect;
+	uint16 x = TileX(tile);
+	uint16 y = TileY(tile);
+	bool reduce_x, reduce_y;
+
+	// look if removed tile was on the bounding rect edge
+	// and try to reduce the rect by this edge
+	// do it until we have empty rect or nothing to do
+	for (;;) {
+		// check if removed tile is on rect edge
+		bool left_edge = (x == r->left);
+		bool right_edge = (x == r->right);
+		bool top_edge = (y == r->top);
+		bool bottom_edge = (y == r->bottom);
+		// can we reduce the rect in either direction?
+		reduce_x = ((left_edge || right_edge) && !ScanRectForStationTiles(st->index, x, r->top, x, r->bottom));
+		reduce_y = ((top_edge || bottom_edge) && !ScanRectForStationTiles(st->index, r->left, y, r->right, y));
+		if (!(reduce_x || reduce_y)) break; // nothing to do (can't reduce)
+		if (reduce_x) {
+			// reduce horizontally
+			if (left_edge) {
+				// move left edge right
+				r->left = x = x + 1;
+			} else {
+				// move right edge left
+				r->right = x = x - 1;
+			}
+		}
+		if (reduce_y) {
+			// reduce vertically
+			if (top_edge) {
+				// move top edge down
+				r->top = y = y + 1;
+			} else {
+				// move bottom edge up
+				r->bottom = y = y - 1;
+			}
+		}
+		if (r->left > r->right || r->top > r->bottom) {
+		// can't continue, if the remaining rectangle is empty
+			StationRect_Init(st);
+			return true; // empty remaining rect
+		}
+	}
+	return false; // non-empty remaining rect
+}
+
+static bool StationRect_AfterRemoveRect(Station *st, TileIndex tile, uint16 w, uint16 h)
+{
+	bool empty;
+	assert(my_pt_in_rect(&st->rect, TileX(tile), TileY(tile)));
+	assert(my_pt_in_rect(&st->rect, TileX(tile) + w - 1, TileY(tile) + h - 1));
+	empty = StationRect_AfterRemoveTile(st, tile);
+	if (w != 1 || h != 1) empty = empty || StationRect_AfterRemoveTile(st, TILE_ADDXY(tile, w - 1, h - 1));
+	return empty;
+}