形狀拖動問題

Question

我需要設計一個軟件，用戶可以在窗口中拖動形狀。問題在於可能有成千上萬的形狀，並且可能存在一些限制，例如，一個形狀不能超過另一個形狀。

所以我實際上需要知道如何組織數據存儲和一些算法來快速確定一個形狀是否可以放置在某個特定位置。 我認爲這個問題已經解決了很多次，但我不知道如何正確地谷歌它。你能否給我提供一些關於這個話題的信息？ 謝謝！

Answer 1

四叉樹（2D，八叉樹，如果3D）經常用於碰撞檢測。想法是遞歸地將空間分成正方形/立方體，並將這些形狀放置到正確的正方形/立方體中。當您需要在給定的形狀上執行碰撞檢測時，您只能測試相同方塊/立方體中的形狀。

還有其他的結構，每個結構都有優點/缺點取決於你的限制。如果其他形狀是靜態的，BSP樹也可以是一個好的結構。