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

Question

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

XЭто черные точки и точки ('.') - белые.

Второй массив точек содержит замкнутый многоугольник:

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

Как называется алгоритм, который позволяет мне различать два типа полигонов?

Обновление 1 (10.10.2015 10:05 MSK): Мне нужно различать закрытые и открытые полигоны, чтобы избежать ошибок при заливке.

Ошибки заливки, когда я применяю заливку к открытому многоугольнику, как

.....
..XXX
.X..X
X...X

и в итоге получается полностью заполненная сетка:

XXXXX
XXXXX
XXXXX
XXXXX

Моя оригинальная идея состояла в том, чтобы

1. взять многоугольник,
2. проверьте, открыт ли он или закрыт, и
3. если он закрыт, примените заливку.

Теперь я мог бы сделать это по-другому:

1. Наводнение залейте полигон.
2. Если вся сетка заполнена, то она является открытой, в противном случае (по крайней мере, одна точка в сетке после заливки заливкой белого цвета), это закрытая.

Если есть способ избежать заливки, чтобы определить, открыт ли полигон или нет, сообщите мне.

Answer 1

У меня нет никакого опыта с этим, но пока я изучал что-то еще, я нашел это и подумал, что это может быть полезно для вас:

http://www.cs.tufts.edu/~sarasu/courses/comp175-2009fa/pdf/comp175-05-region-filling.pdf

На слайдах упоминаются 3 разных алгоритма:

• Алгоритм массива X-пересечений
• Алгоритм краевого списка
• Алгоритм Пинеды