Поиск разделенных линий в 2D системе координат

Question

Я в настоящее время ищу хороший алгоритм для поиска отдельной линии в 2D-координате.

Вот представление о том, что у меня есть:

Так вот алгоритм должен вернуться, что у меня есть 3 Differents отделенные линии, и я хотел бы затем, чтобы иметь возможность позже во время выполнения, чтобы знать, чтобы к которой относится точка.

У кого-нибудь есть идея решить эту проблему?

Примечание. Площадь и линии представлены в памяти двумерным массивом булевых. Цвет - это часть данных.

Answer 1

Вот пример, который я придумал: (протестировано в Playground с Swift 2 Xcode 7 бета 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[$0.x][$0.y] 
        array[$0.x][$0.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($0.x, $0.y) } 
       } 
      } 
      points.append(newPoints) 
     } 
    } 
    return points 
} 

EDIT: сделал изменения под комментарием // crawlers "eat" area and remove some of themselves что делает алгоритм более эффективным с большими площадями

Answer 2

Что вам нужно, кажется, связаны компоненты графа, где каждая ячейка является вершиной, а вершины связаны, если они разделяют сторону. Существует несколько алгоритмов поиска подключенных компонентов, в первую очередь поиск по ширине и поиск по глубине.

Каждый из этих алгоритмов может возвращать количество компонентов («линии»), а также разрешать каждой ячейке присваивать номер компонента, которому он принадлежит.