Я хочу выполнить проверку точки в многоугольнике, но сначала нужно удалить лишние линии из многоугольника, чтобы я мог затем выполнить алгоритм наведения лучей.Многоугольник представляется в двумерном двоичном массиве (1 для заполненного, 0 для пустого).Считается, что избыточные линии имеют точку на обоих концах, которая не имеет заполненных по крайней мере 2 соседних ячеек (т. Е. Север, восток, юг и / или запад, но НЕ по диагонали).
Примеры линий со связанными точками(белый = пустой, синий = заполненный):
Примеры линий, заканчивающихся несвязанными точками (белый =пустой, синий = заполнен, зеленый = заполнен, но отключен):
Пример многоугольника (белый = пустой, синий = заполнено, зеленый = удалить):
Пример многоугольника после удаления избыточных точек(белый = пустой, синий = заполненный):
Простой, но крайне неэффективный алгоритм будет обнаруживать точки, которые имеют менее 2 смежных заполненных точеки удалите их и зациклите, пока не будут внесены изменения.Что может быть более эффективным способом решения этой проблемы?
Примечание: я знаю, что область заполненных точек размером 2x2 (или больше) будет считаться связанной друг с другом, поэтому не будет удалена - этонамеренноМне также известно, что в тесте на лучевое излучение необходимо учитывать горизонтальные и вертикальные линии, когда я добираюсь до алгоритма литья лучей.