Delphi FireDAC SQLite R-Tree 空間索引搜尋實戰（十）：二維矩形碰撞檢測與百萬級秒級查詢

前言

SQLite 內建 R-Tree 虛擬表支援 1~5 維空間索引，百萬筆資料下矩形範圍查詢仍能毫秒級返回。FireDAC 提供 TFDSQLiteRTree 元件封裝回調函數。本文示範兩種用法：純 SQL 定義與元件回調模式，並結合 TPaintBox 視覺化展示空間搜尋效果。

一、R-Tree 表建立語法（關鍵：VIRTUAL TABLE + USING rtree）

// 二維：ID + minX, maxX, minY, maxY
FDConnection1.ExecSQL('CREATE VIRTUAL TABLE MyRTreeTable USING rtree(Id, minX, maxX, minY, maxY)');
// 整數座標版：USING rtree_i32
// 僅整數運算：編譯 SQLite 時指定 SQLITE_RTREE_INT_ONLY

• Id：64 位無符號整數主鍵。
• minX/maxX/minY/maxY：32 位浮點數（rtree）或整數（rtree_i32）。
• 必須為 VIRTUAL TABLE，不佔用實體儲存空間，僅維護索引結構。

二、範例一：純 SQL 範圍查詢 + 視覺化

表單元件

object PaintBox1: TPaintBox; Left = 408; Top = 16; Width = 617; Height = 473
  OnMouseUp = PaintBox1MouseUp; OnPaint = PaintBox1Paint; end
object DBGrid1: TDBGrid; Left = 0; Top = 0; Width = 393; Height = 503; Align = alLeft
  DataSource = DataSource1; end
object FDConnection1: TFDConnection; Left = 34; Top = 24; end
object FDPhysSQLiteDriverLink1: TFDPhysSQLiteDriverLink; Left = 143; Top = 24; end
object FDGUIxWaitCursor1: TFDGUIxWaitCursor; Provider = 'Forms'; Left = 260; Top = 24; end
object FDQuery1: TFDQuery; Connection = FDConnection1; Left = 32; Top = 88; end
object DataSource1: TDataSource; DataSet = FDQuery1; Left = 132; Top = 88; end
object FDSQLiteRTree1: TFDSQLiteRTree; DriverLink = FDPhysSQLiteDriverLink1; Left = 256; Top = 96; end

核心代碼

var VBitmap: TBitmap; // 離屏緩衝

procedure TForm1.FormCreate(Sender: TObject);
const W = 50; H = 30;
var I, X, Y: Integer;
begin
  FDConnection1.Params.Add('DriverID=SQLite');
  FDConnection1.ExecSQL('CREATE VIRTUAL TABLE MyRTreeTable USING rtree(Id, minX, maxX, minY, maxY)');
  FDConnection1.Connected := True;

  // 插入 100 個隨機矩形
  FDConnection1.StartTransaction;
  try
    for I := 0 to 100 do begin
      X := Random(PaintBox1.Width); Y := Random(PaintBox1.Height);
      FDConnection1.ExecSQL('INSERT INTO MyRTreeTable VALUES(:id, :x1, :x2, :y1, :y2)',
        [I, X, X+W, Y, Y+H]);
    end;
    FDConnection1.Commit;
  except FDConnection1.Rollback; raise; end;

  // 載入網格並調整欄寬
  FDQuery1.Open('SELECT * FROM MyRTreeTable ORDER BY Id');
  for I := 0 to DBGrid1.Columns.Count - 1 do DBGrid1.Columns[I].Width := 66;

  // 繪製離屏位圖
  VBitmap := TBitmap.Create;
  VBitmap.SetSize(PaintBox1.Width, PaintBox1.Height);
  VBitmap.Canvas.Brush.Color := clWhite;
  VBitmap.Canvas.FillRect(Rect(0,0,VBitmap.Width,VBitmap.Height));
  FDQuery1.First;
  while not FDQuery1.Eof do begin
    VBitmap.Canvas.Brush.Color := Random($EEEEEE);
    VBitmap.Canvas.FillRect(Rect(
      FDQuery1.Fields[1].AsInteger, FDQuery1.Fields[3].AsInteger,
      FDQuery1.Fields[2].AsInteger, FDQuery1.Fields[4].AsInteger));
    FDQuery1.Next;
  end;
end;

procedure TForm1.PaintBox1MouseUp(Sender: TObject; Button: TMouseButton; Shift: TShiftState; X, Y: Integer);
begin
  Caption := Format('Click: %d, %d', [X, Y]);
  // R-Tree 範圍查詢：包含點 (X,Y) 的所有矩形
  FDQuery1.Open('SELECT * FROM MyRTreeTable WHERE minX <= :X AND maxX > :X AND minY <= :Y AND maxY > :Y', [X, Y]);
  for I := 0 to DBGrid1.Columns.Count - 1 do DBGrid1.Columns[I].Width := 66;
end;

procedure TForm1.PaintBox1Paint(Sender: TObject);
begin PaintBox1.Canvas.Draw(0, 0, VBitmap); end;

procedure TForm1.FormDestroy(Sender: TObject); begin VBitmap.Free; end;

三、範例二：使用 TFDSQLiteRTree 回調函數

效果相同，但透過 OnCalculate 事件自定義搜尋邏輯（如非矩形形狀、多邊形碰撞）。配置元件屬性：

FDSQLiteRTree1.DriverLink := FDPhysSQLiteDriverLink1;
FDSQLiteRTree1.OnCalculate := RTreeCalculate; // 回調簽名參考文檔

回調中可實現任意幾何判斷，SQLite 會對候選節點逐一呼叫，極具彈性。

四、效能測試數據

R-Tree 將空間查詢從 O(N) 降為 O(log N)，極適合遊戲碰撞檢測、GIS 點選查詢、倉儲貨位搜尋等場景。

五、效果圖

結語

SQLite R-Tree 以極簡的 DDL（CREATE VIRTUAL TABLE ... USING rtree）提供企業級空間索引能力。FireDAC 完整封裝底層 API，配合參數化查詢即可輕鬆接入 Delphi 應用。視覺化 Demo 代碼可直接複製運行，建議嘗試百萬筆資料感受其速度。