https://ru.wikipedia.org/wiki/Алгоритм_Брезенхэма
Ничего сложного, сделал, потестировал, действительно были кривые линии вместо прямых. Ошибку нашел быстро, неправильно компенсировал накапливающуюся погрешность.
Но суть не в этом. Когда я хаотично разлиновал экран в ходе тестов, мне прямо захотелось закрасить получившиеяся замкнутые области. Как команда Fill в графических редакторах. Раз захотелось - будем делать )))
Конечно, сразу напрашивается рекурсия:
1. Определяем исходный цвет точки.
2. Закрашиваем точку новым цветом.
3. Проверяем 8 соседних точек.
4. Если они исходного цвета, повторяем для них с п.2, иначе выход из рекурсии.
5. Конец.
Каждая процедура рекурсивно вызовет саму себя до 8 раз. Это очень много - стек очень быстро переполнится. А что самое обидное, эти вызовы по большей части будут ложными, некоторые точки мы будем пытыться раскрасить много раз. Надо как-то сократить количество вызовов и, по возможности, не проверять на перекрашиваемость точки, которые уже были проверены.
Я начал с простого. Можно легко начертить горизонтальную линию от точки клика до пересечения с границей области, например горизонтальная линия на рисунке.
Потом мы формируем набор ключевых точек вертикально от точки клика до границ (вертикальная сине-зеленая линия). А теперь от каждой ключевой точки тоже нарисуем горизонтальную линию.
Просто. Но этого мало. Это будет работать только с выпуклыми областями. Если область имеет вогнутости или какие-нибудь пилообразные грани, алгоритм их закрасит не полностью, он просто остановится на границах сине-зеленой линии, и будет считать свою работу законченной:
Тогда мы поступаем так. В тот момент, когда мы рисуем очередную горизонталь, проверяем, не проходит ли она вплотную к граничному элементу. Вот например, на рисунке, мы рисуем линию вправо от очередной узловой (ключевой) точки (синяя стрелка) и видим, что сверху к ней вплотную примыкает граница (красная стрелка):
В данном случае, мы формируем новый набор ключевых точек, расположенных вертикально. От которого в дальнейшем снова рисуем горизонтальные линии заливки. Так же, по аналогии, поступаем, когда рисуем линию влево, и когда граничная область у нас снизу.
Вроде все просто, но отлаживать пришлось долго.
Кстати, в детстве, я помню, пытался написать игру Xonix, и не смог - не справился как раз с заливкой.
Теперь можно вернуться к детским опытам.
Проверено на следующих конфигурациях и релизах:
- Бухгалтерия предприятия КОРП, редакция 3.0, релизы 3.0.171.20
