我有很多 2D 矩形（或有很多 3D 框）。
矩形可以用坐??標 ( xD,yD,xB,yB) 來描述。
A-----B
| |
| |
D-----C
我想獲得這些矩形/框的交點鄰接圖。
我現在使用 O(n^2) 的方式來實作。
AdjacencyGraph graph(n);
for (int i=0;i<n;i )
{
for (int j=i 1;j<n;j )
{
if (isItersection(boxes[i],box[j]))
{
graph.flagEdge(i,j);
graph.flagEdge(j,i);
}
}
}
但是這種方式非常慢。有沒有可以加速這個程序的快速演算法？
uj5u.com熱心網友回復：
1)如果盒子大小不相等：
- 在 X 軸上排序框
- 為每個框生成一維鄰接串列，通過僅在范圍內進行比較（因為它是一維且已排序，您只比較范圍內的框），如 [(1,2),(1,3),(1,5),。 ...] 用于第一個框，[(2,1),(2,6),..] 用于第二個框，等等。（而不是從 index=0 開始，從 index=current 開始并雙向進行直到它超出范圍）
- 迭代一維鄰接串列并洗掉重復項，或者只是不向后執行最后一步（僅與更大的索引框比較以避免重復）
- 對每個框索引的鄰接進行分組，例如 [(1,a),(1,b),..(2,c),(2,d)...]
- 在每對的第二個框的 Y 軸上對每組內的鄰接進行排序
- 在每個組中，創建 2D 鄰接串列，如 [(1,f),(1,g),..]
- 洗掉重復項
- 再次按第一個框索引分組
- 每組中每對第二個盒子的排序（Z）
- 創建 3D 鄰接串列
- 洗掉重復項
- 按第一個索引成對分組
- 結果=當前鄰接串列（它是一個稀疏矩陣，因此不是完整的 O(N*N) 記憶體消耗，除非所有框都接觸所有其他框）
所以總的來說，有：
- 1 次全排序 (O(N*logN))
- 2 部分排序，長度取決于碰撞次數
- 3對集中在一起（每個O（N））
- 洗掉重復項（或者只是不與較小的索引進行比較）：O(N)
這應該比 O(N^2) 快。
2）如果矩形大小相同，那么你可以這樣做：
分散：將框索引值放入網格的虛擬單元格中（即將計算量劃分為虛構的靜態單元格并將您的框放入包含所選框中心的單元格中。O（N）
收集：每個盒子只有一次，使用選定盒子周圍的網格單元格，使用單元格內的索引串列檢查碰撞。O(N) x 碰撞范圍內的平均鄰居框
3) If rectangles are not equal sized, then you can still "build" them by multiple smaller square boxes and apply the second (2) method. This increases total computation time complexity by multiplication of k=number of square boxes per original box. This only requires an extra "parent" box pointer in each smaller square box to update original box condition.
This method and the (2) method are easily parallizable to get even more performance but I guess first(1) method should use less and less memory after each axis-scanning so you can go 4-dimension 5-dimension easily while the 2-3 methods need more data to scan due to increased number of cell-collisions. Both algorithms can become too slow if all boxes touch all boxes.
4) If there is "teapot in stadium" problem (all boxes in single cell of grid and still not touching or just few cells close to each other)
- build octree from box centers (or any nested structure)
- compute collisions on octree traversal, visiting only closest nodes by going up/down on the tree
1-revisited) If boxes are moving slowly (so you need to rebuild the adjacency list again in each new frame), then the method (1) gets a bit more tricky. With too small buffer zone, it needs re-computing on each frame, heavy computation. With too big buffer zone, it needs to maintain bigger collision lists with extra filtering to get real collisions.
2-revisited) If environment is infinitely periodic (like simulating Neo trapped in train station in the Matrix), then you can use grid of cells again, but this time using the wrapped-around borders as extra checking for collisions.
For all of methods (except first) above, you can accelerate the collision checking by first doing a spherical collision check (broad-collision-checking) to evade unnecessary box-collision-checks. (Spherical collision doesn't need square root since both sides have same computation, just squared sum of differences enough). This should give only linear speedup.
For method (2) with capped number of boxes per cell, you can use vectorization (SIMD) to further accelerate the checking. Again, this should give a linear speedup.
For all methods again, you can use multiple threads to accelerate some of their steps, for another a linear speedup.
Even without any methods above, the two for loops in the question could be modified to do tiled-computing, to stay in L1 cache for extra linear performance, then a second tiling but in registers (SSE/AVX) to have peak computing performance during the brute force time complexity. For low number of boxes, this can run faster than those acceleration structures and its simple:
select a group of boxes n=multiple of 8
select another group of boxes n=multiple of 8
iterate first group 8 by 8
iterate second group 8 by 8
Only rotate the vector to scan all 8 elements (64 collision checks for each 2 vectors)
write results for 8 boxes in first group
Are coordinates only 16bit integers? Then you can cache each collision result using hash(distanceX,distanceY,distanceZ,sizeXYZ) as keys and true/false as values.
因此，解決方案取決于您的問題。什么是N？盒子重疊很多嗎？他們是在一個大環境中聚集在一起還是保持稀疏？系統有多少個核心？多少記憶體？盒子在移動嗎？移動速度有多快？您對多少個盒子的運行時期望是什么？
uj5u.com熱心網友回復：
對于第一個簡單的解決方案，您可以將框存盤為三元組對（Y、Xleft、Xright），并帶有一個標志來區分頂部和底部 Y。[由于 X 是重復的，您可以保留一些特殊值來使區別。]
然后按 Y 排序并通過增加 Y 進行掃描，同時保持“活動串列”。當您遇到頂部三元組時，將其插入活動串列，對于底部，將其洗掉。現在你有一個一維區間重疊問題。
與上面類似，您可以將活動串列中的間隔作為兩個不同的條目輸入，Xleft 和 Xright 加上一個標志。從左到右排序后，您掃描活動串列以通過輔助活動串列獲取重疊間隔。您可以顯式排序，也可以使用有序集維護已排序的串列。
3D 案例類似，但多了一個階段。您首先對 Z 進行排序，活動串列將由 2D 矩形組成，然后您使用上述程序。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/442329.html
標籤：算法
上一篇：將Scratch轉換為演算法