首先，不知道確切地如何提出這個問題，甚至不知道在哪里問，所以請耐心等待。
在我們正在開發的軟體中，我們有描述場景的形狀……可以將其視為高度簡化的 svg。在我們的例子中，我們只有矩形（半打，給予或接受），由它們的高度、寬度、旋轉和中心位置定義。
我們需要以高頻率（大約每 10 毫秒）使用此場景的影像（150x100 像素）渲染一個矩陣（即二維陣列），但我找不到這樣做的演算法或庫；我能夠完成的最好的事情是使用自制演算法達到約 50 毫秒，但這還不夠好。
我自己的演算法大致是這樣的：
drawing = [[0 for i in width] for _ in height]
for shape in shapes:
__calculate_intersection(shape, 0, width, 0, height)
def __calculate_intersection(shape, x1, x2, y1, y2):
global drawing
if x1 == x2 or y1 == y2:
return
if x1 1 == x2 and y1 1 == y2:
# If we are in a single cell, it is just
# checking whether the center of the cell is inside the object
if drawing[x1][y1] == 0:
if shape.is_point_in_obj(x1, y1):
drawing[x1][y1] = 100
return
if shape.bounding_box() does not touch our drawing:
return
else:
# if the area intersects the object bbox,
# then we iterate the recursion by dividing
# the area along its longer side
if i2 - i1 > j2 - j1:
self.__calculate_intersection(o, i1, i1 (i2 - i1) // 2, j1, j2)
self.__calculate_intersection(o, i1 (i2 - i1) // 2, i2, j1, j2)
else:
self.__calculate_intersection(o, i1, i2, j1, j1 (j2 - j1) // 2)
self.__calculate_intersection(o, i1, i2, j1 (j2 - j1) // 2, j2)
return
顯然我需要一個更好的演算法。外面有這種東西嗎？或者更好的是，是否有任何 Python 庫可以實作這一目標？還是我必須進行一些 GPU 編程？為什么 Tkinter Canvas 可以在不到 1 毫秒的時間內以高清質量呈現它，而我卻在為如此簡單的要求而苦苦掙扎？
uj5u.com熱心網友回復：
解決方案的快速描述：
計算四個頂點的坐標，并通過增加 Y 進行排序（不需要完全排序，有 8 種可能的排序）；
用水平線將多邊形分成三個區域（你得到 2 個三角形和一個梯形）；
對于這三個區域，在與它們交叉的整數縱坐標處繪制所有水平線，并計算與斜邊的兩個交點；
填充交叉點之間的水平運行。
uj5u.com熱心網友回復：
有很多方法。一種適用于這種情況的簡單快捷的方法是：
- 用 0s 初始化矩陣
- 對于每個形狀：
- 對于形狀接觸的每條線：
- 將 1 添加到形狀左邊界上的像素。如果那會超出影像的左邊緣，則只需將 1 添加到行首。
- 將 -1 添加到形狀右邊界之后的像素。如果那會超出影像的右邊緣，則跳過它。（如果它會離開左邊緣，那么你不應該做這條線——形狀不接觸它）。
- 對于形狀接觸的每條線：
- 完成所有形狀后，對于每一行：
- 計算每行的運行總數，將像素更改為 100（黑色），其中總和 > 0，將像素更改為 0，其中總和 == 0。
這樣，任何被形狀覆寫的像素都將被著色為黑色。這非常快，因為您只處理單個形狀的邊緣，最后一次完成所有區域著色。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/383707.html
上一篇：從二值影像中提取白色區域