在二维坐标系中查找分隔线

Question

我目前正在寻找一个好的算法来在二维坐标中找到分隔线。

这是我所拥有的表示：

所以这里的算法应该 return 我有 3 条不同的分隔线，我希望稍后在执行过程中能够知道一个点属于哪条线。

有没有人有解决这个问题的想法？

注意：区域和线在内存中由二维布尔数组表示。颜色是数据的注释部分。

Answer 1

您需要的似乎是图形的连接组件，其中每个单元格都是一个顶点，如果顶点共享一条边，则这些顶点是相连的。有多种算法可用于查找连通分量，最著名的是广度优先搜索和深度优先搜索。

这些算法中的每一个都可以 return 组件的数量 ("lines") 并且还允许为每个单元格分配它所属的组件的数量。

Answer 2

这是我想出的一个例子：（在操场上用 Swift 2 Xcode 7 beta 2 测试过）

struct Point{
    var x, y: Int

    init(_ x: Int, _ y: Int) {
        self.x = x
        self.y = y
    }

    /**
    get points around it (Xs around P)
    if all {
        XXX
        XPX
        XXX
    } else {
        OXO
        XPX
        OXO
    }
    **/
    func pointsAround(all all: Bool = true) -> [Point] {
        if all {
            return Array(-1...1).flatMap{ x in
                (-1...1).flatMap{ y in
                    if x == 0 && y == 0 {
                        return nil
                    }
                    return Point(self.x + x, self.y + y)
                }
            }
        }
        return Array(-1...1).flatMap{ x in
            (-1...1).flatMap{ y in
                if abs(x) == abs(y) {
                    return nil
                }
                return Point(self.x + x, self.y + y)
            }
        }
    }
}

func distinguishAreas(var array: [[Bool]]) -> [[Point]] {
    // result
    var points = [[Point]]()

    let width = array.count
    let height = array[0].count
    // returns array[x][y] but with savety check (otherwise false)
    func getBool(x: Int, _ y: Int) -> Bool {
        guard 0..<width ~= x && 0..<height ~= y else { return false }
        return array[x][y]
    }

    // points where to check array
    var crawlers = [Point]()

    // loop through whole array
    for x in 0..<array.count {
        for y in 0..<array[0].count where array[x][y] {
            // if point (array[x][x]) is true

            // new point where to check
            crawlers = [Point(x, y)]

            // points to append (one area)
            var newPoints = [Point]()
            // loop as long as area is not "eaten" by crawlers
            while crawlers.count != 0 {

                // crawlers "eat" area and remove some of themselves
                crawlers = crawlers.filter{
                    let temp = array[[=10=].x][[=10=].y]
                    array[[=10=].x][[=10=].y] = false
                    return temp
                }

                newPoints += crawlers

                // make new crawlers around old crawlers and only where area is
                // passing false to p.pointsAround is mouch faster than true
                crawlers = crawlers.flatMap{ p in
                    p.pointsAround(all: false).filter{ getBool([=10=].x, [=10=].y) }
                }
            }
            points.append(newPoints)
        }
    }
    return points
}

编辑： 在评论 // crawlers "eat" area and remove some of themselves 下进行了更改，这使得算法在大面积时更有效

在二维坐标系中查找分隔线

Find separated lines in a 2D coordinate system

c#

algorithm

coordinates

graph-algorithm

swift