我在某个地方看到了一个关于线路交叉口的问题,我正试图解决这个问题。
有一个8位像素的64x64网格,上面有一堆1像素宽的不同颜色的垂直和水平线所有平行线之间至少有一个间距。问题是找出每一组彩色线的交叉口数量(例如,所有绿色线的交叉口都算作一个和)找出哪一组线路的交叉口最少。同样,一种颜色的所有垂直线都是相同的大小,而同一颜色的所有水平线都是相同的大小。
我有一些想法,但都显得效率很低这需要遍历网格中的每一个像素,如果遇到一种颜色,确定它是垂直线还是水平线,然后一直沿着线的方向走,同时检查相邻边是否有不同的颜色。
我正试图决定是否首先计算每种颜色的水平线和垂直线的长度会加快这个过程你们有什么好主意吗?
这里有两个例子请注意,平行线之间总是有一个空格。
最佳答案
在带有直线的网格上,查找两种类型的3x3正方形:
1).a. 2).a.
bab bbb
.a. .a.
“.”表示背景(总是黑色?)“A”和“B”代表两种不同的颜色(也不同于背景色)。如果找到,将a色线交点和b色线交点的计数增加1。
关于algorithm - 寻找直线相交的算法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/7629763/