Q

N矩形相交

2015-08-26 69 views 0 likes

0

考慮一組n軸平行矩形。蠻力算法是檢查一個矩形是否與其他矩形相交，複雜度是O（n^2）。是否有複雜度爲O（nlogn）的算法用於查找這些矩形集之間的所有交集？N矩形相交

第二個問題是如何找到複雜度爲O（nlogn）的給定矩形集合內矩形的其他矩形？

2015-08-26 Gumeni Pero

+1

使用掃描線。 –

+0

你想查找所有矩形之間的所有交點嗎？ – vish4071

+0

是的，我想找到所有的交點。 –

A

回答

2

查看四叉樹或軸對齊的邊界框寬相用於命中檢測。

這些是矩形命中檢測的典型遊戲使用/物理引擎系統。

2015-08-26 20:29:05 Diniden

相關問題