我有一個(gè)帶有 x、y、寬度和高度的矩形對象。我有一個(gè)顯示在屏幕上的這些矩形的列表。保證它們都不重疊。給定用戶的點(diǎn)擊位置（x 和 y 坐標(biāo)），我想查看哪些矩形被點(diǎn)擊（因?yàn)樗鼈儾恢丿B，最多可以點(diǎn)擊一個(gè)矩形）。我顯然可以瀏覽所有這些并檢查每個(gè)用戶是否單擊它，但這非常慢，因?yàn)槠聊簧嫌泻芏?。?dāng)我在列表中插入一個(gè)新的矩形時(shí)，我可以使用某種比較來保持矩形的排序。是否有某種方法可以使用類似于二分搜索的方法來減少查找單擊哪個(gè) rect 所需的時(shí)間？注意：矩形可以是任何大小。謝謝：）編輯：要了解我在做什么，請?jiān)L問koalastothemax.com
3 回答
GCT1015
TA貢獻(xiàn)1827條經(jīng)驗(yàn) 獲得超4個(gè)贊
我能想出的最快方法絕對不是最有效的內(nèi)存方法。這是通過利用攤銷哈希表具有恒定查找時(shí)間這一事實(shí)來實(shí)現(xiàn)的。它會(huì)將矩形所具有的每個(gè)點(diǎn)映射到該矩形。這僅在您使用整數(shù)時(shí)才真正有效。如果您使用一點(diǎn)舍入，您也許可以讓它與浮點(diǎn)數(shù)一起使用。
確保Point該類具有哈希碼和等于函數(shù)。
public class PointCheck
{
public Map<Point, Rect> pointMap;
public PointCheck()
{
pointMap = new HashMap<>();
}
/**
* Map all points that contain the rectangle
* to the rectangle.
*/
public void addRect(Rect rect)
{
for(int i = rect.x; i < rect.x + rect.width; ++i)
{
for(int j = rect.y; j < rect.y + rect.height; ++i)
{
pointMap.put(new Point(i, j), rect);
}
}
}
/**
* Returns the rectangle clicked, null
* if there is no rectangle.
*/
public Rect checkClick(Point click)
{
return pointMap.get(click);
}
}
編輯： 只是想我應(yīng)該提到這一點(diǎn)：哈希映射值中保存的所有矩形都是對原始矩形的引用，它們不是克隆。
慕沐林林
TA貢獻(xiàn)2016條經(jīng)驗(yàn) 獲得超9個(gè)贊
這在很大程度上取決于您的應(yīng)用程序和細(xì)節(jié)，我們還不太清楚最佳解決方案是什么。但是，據(jù)我所知，我想說您可以制作一個(gè)指向矩形的二維數(shù)組。該二維數(shù)組將直接映射到屏幕上的像素。因此，如果您將數(shù)組設(shè)為 10x20，那么坐標(biāo) x 除以屏幕寬度乘以 10（轉(zhuǎn)換為 int）將是第一個(gè)索引，而 y 劃分的屏幕高度乘以 20 將是您的 y 索引。使用 x 和 y 索引，您可以直接映射到它指向的矩形。有些索引可能是空的，有些索引如果布局不完美，可能指向多個(gè)矩形，但這對我來說似乎是最簡單的方法，我對應(yīng)用程序不太了解。
添加回答
舉報(bào)
0/150
提交
取消