一個(gè)簡(jiǎn)單的多矩形碰撞算法，有快于N^2的方法嗎？謝謝。我無(wú)法理解解決問(wèn)題時(shí)“碰撞”的含義。我把它理解為矩形覆蓋部分重疊時(shí)的碰撞。讓我們首先來(lái)看一個(gè)簡(jiǎn)單的一維情況：一條線(xiàn)由若干具有給定端點(diǎn)坐標(biāo)的線(xiàn)段分散

一個(gè)簡(jiǎn)單的多矩形碰撞算法，有快于N^2的方法嗎？

謝謝。

我無(wú)法理解解決問(wèn)題時(shí)“碰撞”的含義。我把它理解為矩形覆蓋部分重疊時(shí)的碰撞。

讓我們首先來(lái)看一個(gè)簡(jiǎn)單的一維情況：一條線(xiàn)由若干具有給定端點(diǎn)坐標(biāo)的線(xiàn)段分散而成。如何判斷線(xiàn)段是否相交？

n*logn的算法是標(biāo)記每個(gè)端點(diǎn)所在線(xiàn)段的左端點(diǎn)或右端點(diǎn)，然后按坐標(biāo)對(duì)所有端點(diǎn)進(jìn)行排序。如果線(xiàn)段a的左端點(diǎn)在線(xiàn)段B的左端點(diǎn)和右端點(diǎn)之間，并且線(xiàn)段a的右端點(diǎn)在線(xiàn)段B的左端點(diǎn)和右端點(diǎn)之外，則線(xiàn)段a和B相交。所以排序遍歷可以解決。

補(bǔ)充說(shuō)明：如果線(xiàn)段a及其左右端點(diǎn)位于線(xiàn)段B的左右端點(diǎn)之間，則線(xiàn)段a位于線(xiàn)段B內(nèi)部，即包含關(guān)系。計(jì)算包含關(guān)系的復(fù)雜性與計(jì)算交叉關(guān)系的復(fù)雜性相同。

因此，在二元平面上，所有矩形都可以首先投影到x軸上，并且可以一維方式判斷它們是否在x軸上相交。如果它們?cè)趚軸上相交，則可以判斷相應(yīng)矩形的投影線(xiàn)段是否在y軸上相交。如果X和Y軸相交，則可以確定兩個(gè)矩形的碰撞。

還可以計(jì)算正方形的完全覆蓋關(guān)系。

復(fù)雜性是排序n*logn、遍歷n和合成n*logn。

在蟲(chóng)島有更好的算法嗎。

一個(gè)簡(jiǎn)單的多矩形碰撞算法，有快于N^2的方法嗎？

一定有。一般來(lái)說(shuō)，這類(lèi)事情是根據(jù)具體情況來(lái)分析的。一般情況下，掃描線(xiàn)算法可以用來(lái)處理碰撞，即長(zhǎng)、寬、高的固定分辨率掃描。在這種情況下，最嚴(yán)重的復(fù)雜性取決于圖像的分辨率。如果用于數(shù)值處理（即僅判斷矩形是否相交），則可以先將矩形存儲(chǔ)為四個(gè)頂點(diǎn)的坐標(biāo)，然后對(duì)坐標(biāo)進(jìn)行離散化。之后，掃描線(xiàn)路。該算法的復(fù)雜度遠(yuǎn)高于n^2算法。特別是在處理非特定數(shù)據(jù)時(shí)，如果不退化，算法速度會(huì)更快。

qt怎么檢測(cè)碰撞？

1. qlabel的邊界是一個(gè)規(guī)則矩形，所以判斷兩個(gè)qlabel是否碰撞實(shí)際上就是判斷兩個(gè)矩形是否相交？矩形qrect類(lèi)有一個(gè)成員函數(shù)intersects，可以直接判斷它是否與另一個(gè)矩形相交。

2. 要通過(guò)鍵盤(pán)控制qlabel，需要獲取鍵盤(pán)事件，在鍵盤(pán)事件函數(shù)中移動(dòng)qlabel，判斷是否有碰撞。重寫(xiě)標(biāo)簽父窗口的keypressevent或keyreleaseevent函數(shù)。

3. 您可以使用圖形視圖框架來(lái)編寫(xiě)界面。使用這個(gè)框架來(lái)檢測(cè)碰撞要容易得多。直接調(diào)用函數(shù)即可。