Доброго времени суток.

Предположим, что у нас есть матрица:
0 0 0 0 0 0 0
0 1 1 1 1 0 0
0 1 0 0 1 1 1
0 1 1 1 1 1 1

Для каждого элемента матрицы я знаю координаты. Мне необходимо построить многоугольник, который бы отображал "единицы" из матрицы.
Известно, что такой многоугольник всегда можно построить (всегда есть замкнутая область единиц) и он единственный. Проблему представляют "пустоты" внутри этого многоугольника.

Подскажите нормальный алгоритм, неохото велосипед строить собственный...

Здравствуйте, DragonFire, Вы писали:

DF>Доброго времени суток.

DF>Предположим, что у нас есть матрица:
DF>0 0 0 0 0 0 0
DF>0 1 1 1 1 0 0
DF>0 1 0 0 1 1 1
DF>0 1 1 1 1 1 1

Что-то я ничего не понял. Нужно получить вот это?

0 0 0 0 0 0 0
0|1 1 1 1|0 0
0|1|0 0|1 1 1|
0|1 1 1 1 1 1|

DF>Для каждого элемента матрицы я знаю координаты. Мне необходимо построить многоугольник, который бы отображал "единицы" из матрицы.
DF>Известно, что такой многоугольник всегда можно построить (всегда есть замкнутая область единиц) и он единственный. Проблему представляют "пустоты" внутри этого многоугольника.

DF>Подскажите нормальный алгоритм, неохото велосипед строить собственный...

DF>Для каждого элемента матрицы я знаю координаты. Мне необходимо построить многоугольник, который бы отображал "единицы" из матрицы.
DF>Известно, что такой многоугольник всегда можно построить (всегда есть замкнутая область единиц) и он единственный. Проблему представляют "пустоты" внутри этого многоугольника.

Я так понял, надо соединить единицы чтобы получился многоугольник.
Если так, то по своей сути это задача поиска гамильтонова цикла, которая NP-полна.
В данном случае граф имеет свойство — степень вершин <= 4, но, похоже, это не меняет дело.

Думаю, что без перебора не обойтись. Простейший вариант — поиск в глубину.

Здравствуйте, _DAle_, Вы писали:

_DA>Здравствуйте, DragonFire, Вы писали:

DF>>Доброго времени суток.

DF>>Предположим, что у нас есть матрица:
DF>>0 0 0 0 0 0 0
DF>>0 1 1 1 1 0 0
DF>>0 1 0 0 1 1 1
DF>>0 1 1 1 1 1 1

_DA>Что-то я ничего не понял. Нужно получить вот это?
_DA>

_DA>0 0 0 0 0 0 0
_DA>0|1 1 1 1|0 0
_DA>0|1|0 0|1 1 1|
_DA>0|1 1 1 1 1 1|
_DA>

Ага, примерно такую фигуру =)

Здравствуйте, Буравчик, Вы писали:

DF>>Для каждого элемента матрицы я знаю координаты. Мне необходимо построить многоугольник, который бы отображал "единицы" из матрицы.
DF>>Известно, что такой многоугольник всегда можно построить (всегда есть замкнутая область единиц) и он единственный. Проблему представляют "пустоты" внутри этого многоугольника.

Б>Я так понял, надо соединить единицы чтобы получился многоугольник.
Б>Если так, то по своей сути это задача поиска гамильтонова цикла, которая NP-полна.
Б>В данном случае граф имеет свойство — степень вершин <= 4, но, похоже, это не меняет дело.

Б>Думаю, что без перебора не обойтись. Простейший вариант — поиск в глубину.

Не совсем согласен (или не совсем понял идею) использования гамильтоновой цепи — ведь у меня стоит задача не обойти все единицы в массиве, а как-бы "обвести вокруг них границу", чтобы получился многоугольник с полостями...

Здравствуйте, DragonFire, Вы писали:

DF>>>Предположим, что у нас есть матрица:
DF>>>0 0 0 0 0 0 0
DF>>>0 1 1 1 1 0 0
DF>>>0 1 0 0 1 1 1
DF>>>0 1 1 1 1 1 1

_DA>>Что-то я ничего не понял. Нужно получить вот это?
_DA>>

_DA>>0 0 0 0 0 0 0
_DA>>0|1 1 1 1|0 0
_DA>>0|1|0 0|1 1 1|
_DA>>0|1 1 1 1 1 1|
_DA>>

DF>Ага, примерно такую фигуру =)

Дык вроде всё просто — сначала сканируем по горизонтали: на переходе 01 ставим у единицы "левую стенку", на переходе 10 — ставим у единицы "правую стенку".
Потом аналогично сканируем по вертикали, расставляя единичкам верхние и нижние "стенки".
А потом ещё раз сканируем единички в поисках "углов" (точек, где сходятся стенки). В итоге получим набор вершин искомого многоугольника. Останется их как-то упорядочить.

Здравствуйте, andy1618, Вы писали:

A>Здравствуйте, DragonFire, Вы писали:

DF>>>>Предположим, что у нас есть матрица:
DF>>>>0 0 0 0 0 0 0
DF>>>>0 1 1 1 1 0 0
DF>>>>0 1 0 0 1 1 1
DF>>>>0 1 1 1 1 1 1

_DA>>>Что-то я ничего не понял. Нужно получить вот это?
_DA>>>

_DA>>>0 0 0 0 0 0 0
_DA>>>0|1 1 1 1|0 0
_DA>>>0|1|0 0|1 1 1|
_DA>>>0|1 1 1 1 1 1|
_DA>>>

DF>>Ага, примерно такую фигуру =)

A>Дык вроде всё просто — сначала сканируем по горизонтали: на переходе 01 ставим у единицы "левую стенку", на переходе 10 — ставим у единицы "правую стенку".
A>Потом аналогично сканируем по вертикали, расставляя единичкам верхние и нижние "стенки".
A>А потом ещё раз сканируем единички в поисках "углов" (точек, где сходятся стенки). В итоге получим набор вершин искомого многоугольника. Останется их как-то упорядочить.

Проблемы вызывают "пустоты" — области нулей внутри единиц. Такие области надо как-то обнаруживать и вырезать из искомого многоугольника.
Сами то границы многоугольника найти совсем не сложно, я согласен...

Здравствуйте, DragonFire, Вы писали:

A>>Дык вроде всё просто — сначала сканируем по горизонтали: на переходе 01 ставим у единицы "левую стенку", на переходе 10 — ставим у единицы "правую стенку".
A>>Потом аналогично сканируем по вертикали, расставляя единичкам верхние и нижние "стенки".
A>>А потом ещё раз сканируем единички в поисках "углов" (точек, где сходятся стенки). В итоге получим набор вершин искомого многоугольника. Останется их как-то упорядочить.

DF>Проблемы вызывают "пустоты" — области нулей внутри единиц. Такие области надо как-то обнаруживать и вырезать из искомого многоугольника.
DF>Сами то границы многоугольника найти совсем не сложно, я согласен...

Так ведь границы и внешние и внутренние — замкнутые ломаные.
Зная одно звено, легко найти продолжение.

Здравствуйте, DragonFire, Вы писали:

DF>Проблемы вызывают "пустоты" — области нулей внутри единиц. Такие области надо как-то обнаруживать и вырезать из искомого многоугольника.
DF>Сами то границы многоугольника найти совсем не сложно, я согласен...

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

Здравствуйте, andy1618, Вы писали:

A>Здравствуйте, DragonFire, Вы писали:

DF>>Проблемы вызывают "пустоты" — области нулей внутри единиц. Такие области надо как-то обнаруживать и вырезать из искомого многоугольника.
DF>>Сами то границы многоугольника найти совсем не сложно, я согласен...

A>Описанный алгоритм обнаружит и границы многоугольников с пустотами, а также, если внутри этих пустот в свою очередь есть изолированные блоки единиц — и их тоже, и т.д.

А можно ссылочку адекватную... =)

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, DragonFire, Вы писали:

A>>>Дык вроде всё просто — сначала сканируем по горизонтали: на переходе 01 ставим у единицы "левую стенку", на переходе 10 — ставим у единицы "правую стенку".
A>>>Потом аналогично сканируем по вертикали, расставляя единичкам верхние и нижние "стенки".
A>>>А потом ещё раз сканируем единички в поисках "углов" (точек, где сходятся стенки). В итоге получим набор вершин искомого многоугольника. Останется их как-то упорядочить.

DF>>Проблемы вызывают "пустоты" — области нулей внутри единиц. Такие области надо как-то обнаруживать и вырезать из искомого многоугольника.
DF>>Сами то границы многоугольника найти совсем не сложно, я согласен...

А>Так ведь границы и внешние и внутренние — замкнутые ломаные.
А>Зная одно звено, легко найти продолжение.

Ну нужно еще найти звенья — как определить что звено принадлежит именно внутренней границе, а не внешней...

Здравствуйте, DragonFire, Вы писали:

DF>Здравствуйте, Аноним, Вы писали:

А>>Здравствуйте, DragonFire, Вы писали:

A>>>>Дык вроде всё просто — сначала сканируем по горизонтали: на переходе 01 ставим у единицы "левую стенку", на переходе 10 — ставим у единицы "правую стенку".
A>>>>Потом аналогично сканируем по вертикали, расставляя единичкам верхние и нижние "стенки".
A>>>>А потом ещё раз сканируем единички в поисках "углов" (точек, где сходятся стенки). В итоге получим набор вершин искомого многоугольника. Останется их как-то упорядочить.

DF>>>Проблемы вызывают "пустоты" — области нулей внутри единиц. Такие области надо как-то обнаруживать и вырезать из искомого многоугольника.
DF>>>Сами то границы многоугольника найти совсем не сложно, я согласен...

А>>Так ведь границы и внешние и внутренние — замкнутые ломаные.
А>>Зная одно звено, легко найти продолжение.

DF>Ну нужно еще найти звенья — как определить что звено принадлежит именно внутренней границе, а не внешней...

Я бы решал так

1. Составляем множество S — множество всех найденных ребер.

2. Находим внешнюю границу:
2а. находим "левый верхний угол", т.е. левее и выше клетки только "0".
для клетки берем ребро р. Переносим ребро из S в P(ориентированный путь в порядке обхода).
2б. в S ищем следующее ребро р1 сопряженное с р.
Здесь есть единственная сложность — касающиеся клетки (например как в букве "Э")

0 1    или    1 0
1 0           0 1

но и здесь порядок обхода очевиден.
Переносим ребро из S в P.
р1=р

3в. повторяем (2б) пока не вернемся в начальную точку. (пока находятся ребра в S)
Внешняя граница найдена.

3 Для поиска "дырок" повторяем пункт 2 пока S не опустеет.(начальное ребро можно взять любое)
Сколько "дырок" — столько и повторов пункта 3.

Здравствуйте, DragonFire, Вы писали:

DF>А можно ссылочку адекватную... =)

Ссылочек не подскажу — задачка напоминает алгоритм штриховки произвольных (невыпуклых) полигонов.

DF>Подскажите нормальный алгоритм, неохото велосипед строить собственный...

В книжице http://www.careercup.com/book предлагается выполнить перебор. Только там квадрат и их может быть несколько разных. Но суть такая же.
Сложность получается O(n^6)

Но мне лично кажется все это можно очень сильно оптимизировать. Начать с построения списка горизонтальных и вертикальных отрезков — непрерывных последовательностей из 1. Эта задача займет O(n^4). Дальше уже сопоставлять отрезки (отсортировать по длине, сделать хэш по координатам) — тут надо подумать как можно заоптимизировать перебор. Отрезки единичной длины можно сразу отбрасывать.

В случае если заполнение площади единичками небольшое — мы получим значительный выигрыш.

Правда в таком варианте требования по памяти уже будут выше.

Здравствуйте, mazurkin, Вы писали:


M> Начать с построения списка горизонтальных и вертикальных отрезков — непрерывных последовательностей из 1. Эта задача займет O(n^4).

Я ошибся, не O(n^4), а O(2n^2) то есть O(n^2) — овчинка явно стоит выделки!

Convex Hull может помочь