基於兩個維度範圍的快速檢索操作是否有效的.NET集合？

我正在尋找一個快速和高效的.NET集合（如果有的話）。我的目的是執行基於快速範圍的檢索操作，但在插入和刪除方面仍然不慢（我知道這通常是關於檢索效率和對集合的修改的折衷）。爲了簡短起見，假設檢索操作的效率仍然比修改操作更重要。基於兩個維度範圍的快速檢索操作是否有效的.NET集合？

背景是我設計使用的WinForms畫布，使之簡單說，我在它只是「畫」的形狀：

爲了使方法簡單一點，讓我們考慮一下，無論形狀如何或看起來如何，我們只會考慮用客戶機矩形定義的邊界框。

無論如何，現在我說我點擊了我的控件上的一個項目（如此顯示在畫布視圖中），它可能會顯示（相應於ZoomValue）所有項目包含在畫布中的部分集合，快速瞭解哪個項目已被點擊？

每個項目都有自己的BoundingBox屬性（所以X，Y，寬度&高度）和Z順序。但這裏有所不同，我們基本上把鼠標的座標轉換成Canvas視圖座標（相應的縮放因子），並基於它，我想知道如何避免查看項目中的完整和冗長的搜索（順便說一下這個問題還涉及視圖改變時項目的重新分配）。

在百件商品的情況下，它仍然很好，現在我正在考慮在屏幕上顯示數千個箭頭的情況（這是一個比窗口控件控件給出的數字更大的數字，這就是爲什麼我正在設計自己的畫布）。

我看了一些SPT策略，其中包括OmniTree數據結構，它可能是最適合我的情況的數據結構，但我仍然懷疑有些修改可能比較慢：http://www.codeproject.com/Articles/794171/Omni-Tree-Data-Structure-in-Csharp

任何人都會得到同樣的要求？

來源

2015-10-06 Ehouarn

一個簡單的'List '可能會做得很好。與實際渲染相比，迭代和命中測試（例如['Contains']（https://msdn.microsoft.com/en-us/library/22t27w02.aspx））將花費很少的時間。另一件事是分組，而不是繪製包含重疊基元的許多圖形，您可能需要先將該圖形處理成沒有重疊部分的簡化圖形。 – Sinatr

@Sinatr實際上，我現在的虛擬實現已經在使用列表，基本上整個畫布的一個列表以及另一個由View用於渲染/繪畫過程的列表。我認爲問題在於，當包含很多形狀時，「包含（...）」方法可能會有點慢（渲染過程結果可能被緩存（如位圖），所以這在這裏不是問題）。檢索操作可能很慢，因爲我們需要檢查測試點是否包含在多個矩形中，這可能需要一些時間。 – Ehouarn

@Sinatr這就是爲什麼我正在尋找一種執行檢索操作的替代方法。我更想到幕後的快速平衡樹，它允許在兩個維度上使用間隔：x和y。 – Ehouarn

不，沒有內置的集合允許按範圍/邊界矩形進行搜索。您需要編寫適合您需要的自己的/查找庫。

沒有通用算法適用於處理範圍數據搜索的大量應用程序。多維度也沒有幫助。

你可能想看看在遊戲中使用algoritms：

Binary space partitioning
Bin - 空間的定期/不定期散 - 每個矩形將映射到一個或多個細胞
您的分組可能成爲搜索的自然解決方案 - 找到根的矩形，從而限制下一級搜索。

來源

2015-10-06 14:45:14

好吧，那麼需要發明車輪:-) 對我來說似乎是合適的答案。感謝您的回答。 – Ehouarn

只是爲了讓人們知道我使用下面的東西也有不錯的表現： - 一個使用KD樹代替LinkedLists的bin - QuadTree – Ehouarn

R樹*以及=] – Ehouarn

爲了達到這個目的，您應該使用數據表，數據表允許您快速查找，刪除插入和更新。

來源

2015-10-06 14:58:33 Donald

基於兩個維度範圍的快速檢索操作是否有效的.NET集合？

回答

相關問題