Попробуйте сделать широта-первых поиск вашего изображения, (или в качестве альтернативы перебирать в списке точек) и отметьте каждый пиксель, который соседствует с другим пикселем, который не из той же группы.
Мне непонятно, нужен ли по периметру каждый пиксель на внешнем краю запрашиваемого объекта или каждый пиксель, который граничит с объектом. На данный момент я возьмусь на первое место.
Настройка изображения:
Вот как вы бы идти об этом. Во-первых, создать изображение в виде массива в 2-D, с каждым пикселем, помеченный номером группы:
[ 0 0 0 0 1 1 0 ]
[ 0 0 2 0 0 0 0 ]
[ 0 2 2 0 3 3 0 ]
[ 0 2 2 0 0 3 0 ]
[ 0 2 2 0 0 0 0 ]
[ 0 2 0 0 4 4 0 ]
[ 0 0 0 0 4 4 0 ]
хороший способ, чтобы загрузить это было бы использовать Scanner
объект, чтобы получить каждую точку, по одному :
List<Point> points = new ArrayList<>();
Scanner scanner = new Scanner(/* whatever your input source is */);
String pointRegex = "\\(\\d,\\d\\)"; //looks for something like "(#,#)"
while(!scanner.hasNext(pointRegex)){
String pointText = scanner.next(pointRegex); //For example, "(5,4)"
Point point = getPointFromText(pointText); //turns a string into a point
points.add(point);
}
Обратите внимание на использование Scanner.next(String pattern)
. Это метод, который возвращает следующий String
, который выглядит как этот шаблон. (Читайте на регулярных выражениях, если вы хотите узнать больше о том, как это работает.)
Теперь на наполнении сетки:
boolean[][] binaryImage = new boolean[width][height];
for(Point p : points){ //Iterate through each Point inside our List of Point objects
binaryImage[p.getX()][p.getY()] = true;
}
Это помещает объект, представленный нашей коллекции Point
объектов "points
", в сетку boolean
s. Нам нужно только беспокоиться об этом одном объекте, поэтому нам не нужно загружать ни один из других. Теперь выясним, какие точки находятся по периметру.
Рекурсивный метод:
boolean[][] visitedBefore = new boolean[width][height];
boolean[][] isOnPerimeter = new boolean[width][height];
int[] deltaX = {-1, 0, 1, -1, 1, -1, 0, 1},
deltaY = {-1, -1, -1, 0, 0, 1, 1, 1};
Queue<Point> searchNext = new LinkedList<>();
searchNext.add(points.get(0)); //Just need one point to get going
while(!searchNext.isEmpty()){
Point p = searchNext.remove(); //take what's waiting at the front of the queue
if(visitedBefore[p.getX()][p.getY()]){
continue; //already check this spot!
}
//mark that we've been here
visited[p.getX()][p.getY()] = true;
//look at all of this Point's neighbors
for(int i = 0 ; i < deltaX.length ; i++){
int newX = p.getX() + deltaX[i];
int newY = p.getY() + deltaY[i];
//make sure this isn't out of bounds
if(newX < 0 || newX >= width || newY<0 || newY>=height){
isOnPerimeter[p.getX()][p.getY()] = true; //if you decide bordering the edge of the image counts as being on the perimeter
continue;
}
//check if this new point we're considering isn't part of the image
if(binaryImage[p.getX()][p.getY()] != binaryImage[newX][newY]){
//if it isn't, then this Point p must be on the perimeter
isOnPerimeter[p.getX()][p.getY()] = true;
} else {
/* otherwise, this new point we're considering is part of the
* same object, and could be part of the perimeter. */
searchNext.add(new Point(newX, newY));
}
}
}
Теперь у вас есть сетка с каждой точки по периметру отмечен как true
.Если вам нужны эти как список, выбирая те пункты легко:
List<Point> perimeter = new ArrayList<Point>();
for(int x = 0 ; x < isOnPerimeter.length ; x++)
for(int y = 0 ; y < isOnPerimeter[x].length ; y++)
perimeter.add(new Point(x,y));
Итерационный метод:
Это очень похоже на выше, но прыгает прямо поставив точки периметра в списке.
int[] deltaX = {-1, 0, 1, -1, 1, -1, 0, 1},
deltaY = {-1, -1, -1, 0, 0, 1, 1, 1};
outer: for(Point p : points){
inner: for(int i = 0 ; i < deltaX.length ; i++){
int newX = p.getX() + deltaX[i];
int newY = p.getY() + deltaY[i];
//check if this new point we're considering is outside the image
if(newX < 0 || newX >= width || newY<0 || newY>=height){
perimeter.add(p); //if you decide bordering the edge of the image counts as being on the perimeter
continue outer;
}
//check if this new point we're considering isn't part of the image
if(binaryImage[p.getX()][p.getY()] != binaryImage[newX][newY]){
//if it isn't, then this Point p must be on the perimeter
perimeter.add(p);
continue outer;
}
}
}
Обратите внимание на этикетки outer:
и inner:
. Это позволяет нам выбрать, что для цикла пропустить, когда мы скажем continue outer;
.
Там вы идете! Это должно помочь вам получить периметр любого объекта в виде двоичного изображения или в виде списка.