關於對象管理器

Question

我正在設計一個管理矩形集合的類。 每個矩形代表一個鍵，使包含以下屬性：

• x位置
• y位置
• 寬度
• 高度
• 爲被按壓時，它會發生什麼的回調函數。

這個概念本身非常簡單，通過命令行界面進行管理。尤其是。

如果我輸入「100，125」，它會查找是否有一個包含這個點（或多個）的矩形並執行它們的回調函數。

我的建議是遍歷此集合中的所有矩形，並執行包含此點的每個單獨矩形的回調，或停止匹配的第一個矩形（模擬z次序）。

但是我擔心這個解決方案是sl，的，因爲這個迭代變得越長，我的矩形就越長。 這對於控制檯應用程序來說很好，因爲它可以輕鬆地超過10,000個矩形，並找到哪些匹配，昂貴的計算，但時間明智，這不是特別的問題。

問題是，如果我要在每次移動鼠標（模擬鼠標移動效果）時都需要執行此檢查的GUI應用程序中實現此算法，請將移動鼠標10個像素移動到面板上的10,000個對象將需要檢查100,000個物體，甚至不超過1000個像素，否則人們會傾向於將鼠標移動到。

這個問題有沒有更優雅的解決方案，還是這樣的程序總是需要如此昂貴？

注意：我知道大多數GUI不必一次處理10,000個活動對象，但這不是我的目標。 我選擇用按鈕來解釋這個問題的原因是因爲它們更簡單。理想情況下，我希望能夠在GUI中工作的解決方案以及與鼠標交互的粒子系統以及其他要求嚴格的系統。

在GUI中，我可以很容易地使用間接方式來大幅減少檢查的數量，但這並不能減輕每次移動鼠標時都需要執行檢查的問題，即使存在25個按鈕，當移動超過400個像素時，有25個對象（在理想條件下）會與移動1個像素10000個對象一樣糟糕。

概括地說，這個問題是雙重的：

1. 我能做些什麼來減少檢查的10000量（授予有10,000個對象）。
2. 是否有可能減少這種GUI應用程序所需的檢查量，從每一次鼠標移動到更合理的事情。

任何幫助表示讚賞！

Answer 1

您可以應用任意數量的2D交叉加速結構。例如，您可以使用四叉樹（http://en.wikipedia.org/wiki/Quadtree）以遞歸方式將視口分爲象限。細分未完全落入每個矩形內或完全落在每個矩形外的每個象限，並將指針放置在每個葉子的頂部或矩形列表（如果沒有矩形落在那裏，則爲NULL）。結構不是微不足道的，但在概念上相當簡單。

Answer 2

有沒有更優雅的解決方案來解決這個問題，還是這樣的程序總是需要如此昂貴？

而不是通過所有對象做一個線性搜索，你可以使用一個數據結構就像一個四叉樹，可以讓你有效地找到最近的對象。或者，您可以根據算法的預期用途想出一組更爲現實的需求。一次可見10,000個按鈕的GUI是一個糟糕的設計，原因很多，主要原因是窮人用戶很難找到正確的按鈕。從性能的角度來看，通過大量用戶界面的典型矩形進行線性搜索，比如介於2到100之間。