Как найти полигоны на 2D карте, используя только маркер контура? - PullRequest
Новая
       43

Как найти полигоны на 2D карте, используя только маркер контура?

0 голосов
/ 06 мая 2019

Итак, учитывая двумерный массив точек, как найти все многоугольники, в которых каждая точка координаты многоугольника (по диагонали примыкает) к следующей?

Например, это изображение:

enter image description here

Я заинтересован в затоплении области, ограниченной замкнутой цепочкой точек (каждая координата примыкает к следующей, образующей замкнутую петлю), относительно ее формы.Я не заинтересован в идентификации отдельных полигонов, а только в заполнении полигона.Каждая точка имеет метку (1, 2, 3, + и т. Д.), Где 0 не установлено. Так, например:

  • Желтый - это квадрат, где центральная точка заполняется.
  • Оранжевый квадрат больше, но углы прилегают друг к другу только по диагонали.
  • Зеленый - это форма, в которой, если вы следуете цепочке точек, вы не всегда можете повернуть направо.
  • Красный не являетсядопустимая форма, поскольку ее точечная цепь не закрыта.
  • Синий не является допустимой формой, поскольку его точечная цепь не закрыта, ребро не закрывает ее.

Я смотрел навыпуклая оболочка, но это дает мне оболочку всех точек, которая меня не интересует.

Пара правил: - Каждая точка имеет значение от 1 до 10. - Область может быть заполнена, только если закрыто Pointchain имеет ту же самую метку.- Цепочки точек, которые не являются замкнутыми, не являются действительными регионами.- x / y координаты точек - целые числа.

Я реализую это в Java, и я попробовал это: https://github.com/Merowech/java-concave-hull/blob/master/ConcaveHull.java

Но с учетом карты, подобной этой: 

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 1, 0, 1, 0, 1, 0, 2, 2, 0, 0, 0, 0, 2, 0
0, 1, 0, 0, 0, 1, 2, 0, 0, 2, 0, 0, 0, 0, 0
0, 0, 1, 0, 1, 0, 2, 0, 0, 2, 0, 0, 0, 0, 0
0, 0, 0, 1, 0, 0, 0, 2, 2, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 3, 3, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 3, 3, 3, 0, 0, 3, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0

Это дает мне в качестве вывода: 

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 1, 0, 0, 0, 1, 0, 2, 2, 0, 0, 0, 0, 2, 0
0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0

Я также попробовал DBSCAN, который в итоге не смог игнорировать маленькие кластеры рядом с большим кластером с той же меткой

Обновление:

Простая заливка не будет работать, поскольку необходимо, чтобы все окружающие пиксели многоугольника имели одинаковое значение: 

    public static void floodFill(int[][] map, int fill, Point loc) {
        if (loc.x < 0 || loc.x >= map[0].length || loc.y < 0 || loc.y >= map.length) throw new IllegalArgumentException();

        int old = map[loc.y][loc.x];

        // Checks trivial case where loc is of the fill color
        if (fill == old) return;

        floodLoop(map, loc.x, loc.y, fill, old);
    }

    // Recursively fills surrounding pixels of the old color
    private static void floodLoop(int[][] map, int x, int y, int fill, int old) {

        int[] aux = {255, 255, 255, 255};

        // finds the left side, filling along the way
        int fillL = x;
        do {
            map[y][fillL] = fill;
            fillL--;
        } while (fillL >= 0 && map[y][fillL] == old);
        fillL++;

        // find the right right side, filling along the way
        int fillR = x;
        do {
            map[y][fillR] = fill;
            fillR++;
        } while (fillR <= map[0].length - 1 && map[y][fillR] == old);
        fillR--;

        // checks if applicable up or down
        for (int i = fillL; i <= fillR; i++) {
            if (y > 0 && map[y-1][i] == old) floodLoop(map, i, y - 1,
                    fill, old);
            if (y < map.length - 1 && map[y+1][i] == old) floodLoop(
                    map, i, y + 1, fill, old);
        }
    }

    public static int[][] map = new int[][]
    {
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 3, 0, 0, 0, 0, 0, 0},
            {0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 3, 0, 0, 0, 0, 0},
            {0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 3, 3, 0, 0, 0},
            {0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 2, 2, 2, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0},
            {0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 2, 0, 2, 0, 0, 3, 0, 0, 0, 0, 3, 0, 0, 3, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 0, 0, 3, 0, 0, 0, 3, 0, 3, 0, 3, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 3, 0, 0, 0, 3, 3, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 4, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 4, 0, 4, 0, 0, 0, 0, 5, 5, 5, 5, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},

    };

    public static int[][] expected_result = new int[][]
    {
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 3, 0, 0, 0, 0, 0, 0},
            {0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 0, 0, 0, 0, 0},
            {0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 3, 3, 3, 0, 0, 0},
            {0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 2, 2, 2, 0, 0, 3, 3, 3, 3, 3, 3, 3, 3, 3, 0, 0},
            {0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 2, 2, 2, 0, 0, 3, 3, 3, 3, 3, 3, 3, 3, 3, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 0, 0, 3, 3, 3, 3, 3, 0, 3, 3, 3, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 3, 0, 0, 0, 3, 3, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 4, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 4, 0, 4, 0, 0, 0, 0, 5, 5, 5, 5, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},

    };


    private static void printMap(int[][] map)
    {
        for (int y = 0; y < map.length; y++)
        {
            for (int x = 0; x < map[0].length; x++)
            {
                System.out.print(map[y][x] +  " ,");
            }
            System.out.println();
        }
    }
    public static void main(String[] args)
    {
        int[][] copy = map.clone();

        floodFill(copy, 1, new Point(0,0));

        printMap(copy);
    }

1 Ответ

1 голос
/ 07 мая 2019

Это не проблема кластеризации на основе плотности .Таким образом, DBSCAN просто не правильный алгоритм для этой задачи.

То, что вам нужно, - это довольно простой флуд заполнение подход.Определите снаружи, залейте его белым.Найдите пиксель, который не заполнен, но имеет соседа.Начните заливку цветом соседей.

За исключением некоторых угловых случаев (соприкасающихся фигур), это, вероятно, все, что вам нужно.Скорее всего, они могут быть обнаружены во время заливки пола и заполнены белым цветом.

...