Рисование линий и закрашивание областей в табличном документе 1С. Техническая реализация

Недавно я разместил пример обработки, которую я написал для тестов и своего собственного развлечения: Рисование линий и закрашивание областей в табличном документе 1С. В комментариях спросили о технической реализации, рассказываю. 

Рисование линий

Первая задача - как выделить фоном ячейки в табличном документе 1С, так чтобы они образовали подобие прямой линии, вот так (сделаем ячейки примерно квадратной формы, для красоты):

Для этого существует старинный известный алгоритм Алгоритм Брезенхэма. Это один из старейших алгоритмов в машинной графике — он был разработан Джеком Элтоном Брезенхэмом в компании IBM в 1962 году. Все довольно просто, начнем с ситуации когда начальная точка прямой выше и левее конечной, в наших координатах табличного документа, и еще ширина по горизонтали больше чем высота линии по вертикали:

Уравнение прямой:

Y = X0 + K*X, где

K - это коэффициент наклона:

K = (Хкон - Хнач + 1) / (Yкон - Yнач + 1).

То есть, когда мы увеличиваем X на 1, переходим к следующей ячейке, мы увеличиваем Y на K. K < 1 в нашем случае. Как только накопленный шаг по Y превысит 1, мы увеличиваем Y на 1:

Процедура НарисоватьЛинию(Xнач, Yнач, Xкон, Yкон);
	
	// Алгоритм Брезенхэма на 1С
	
	ДельтаX = Xкон - Xнач + 1;
	ДельтаY = Yкон - Yнач + 1;
	
	КоэфНаклона = ДельтаY / ДельтаX;
	
	ШагПоX = 1;
	ТекущийШагПоY = 0;
	
	Yтек = Yнач;
	Xтек = Xнач;
	
	Пока Xтек <= Xкон Цикл 
		
		Холст.Область(Yтек, Xтек).ЦветФона = ЦветЛинии;
		
		ТекущийШагПоY = ТекущийШагПоY + КоэфНаклона;
		
		Если ТекущийШагПоY >= 1 Тогда
			Yтек = Yтек + 1;
			ТекущийШагПоY = ТекущийШагПоY - 1;
		КонецЕсли;
		
		Xтек = Xтек + 1;
		
	КонецЦикла; 

КонецПроцедуры

Все просто, но это еще не алгоритм Брезенхэма. В то время процессоры производили вычисления с плавающей точкой значительно медленнее, чем целочисленные. На самом деле и сейчас тоже, просто скорость обработки и тех и других выросла на несколько порядков. И чтобы избавиться от медленных вычислений, Брезенхэм придумал уножить все дроби на знаменатель ДельтаX:

Процедура НарисоватьЛинию(Xнач, Yнач, Xкон, Yкон);
	
	// Алгоритм Брезенхэма на 1С
	
	ДельтаX = Xкон - Xнач + 1;
	ДельтаY = Yкон - Yнач + 1;
	
	КоэфНаклона = ДельтаY; // (ДельтаY / ДельтаX) * ДельтаX
	
	ШагПоX = 1;
	ТекущийШагПоY = 0;
	
	Yтек = Yнач;
	Xтек = Xнач;
	
	Пока Xтек <= Xкон Цикл 
		
		Холст.Область(Yтек, Xтек).ЦветФона = ЦветЛинии;
		
		ТекущийШагПоY = ТекущийШагПоY + КоэфНаклона;
		
		Если ТекущийШагПоY >= ДельтаX Тогда // 1 * ДельтаX
			Yтек = Yтек + 1;
			ТекущийШагПоY = ТекущийШагПоY - ДельтаX; // 1 * ДельтаX
		КонецЕсли;
		
		Xтек = Xтек + 1;
		
	КонецЦикла; 

КонецПроцедуры

Получается то же самое, но оптимально по вычислениям.

Теперь надо избавится от начального ограничения, что начальная точка прямой выше и левее конечной и добавить поддержку произвольного начала и конца линии:

Процедура НарисоватьЛинию(Xнач,Yнач,Xкон,Yкон);
	
	// Алгоритм Брезенхэма на 1С
	
	Xt = Xнач;
	Yt = Yнач;
	
	ДельтаX = Xкон - Xнач;
	ДельтаY = Yкон - Yнач;
	
	Если ДельтаY < 0 Тогда
		
		ШагПоY = -1;
		ДельтаY = - ДельтаY;
		
	Иначе
		
		ШагПоY = 1;
	
	КонецЕсли;
	
	Если ДельтаX < 0 Тогда
		
		ШагПоX = -1;
		ДельтаX = - ДельтаX;
		
	Иначе
		
		ШагПоX = 1;
	
	КонецЕсли;
	
	ДельтаY = ДельтаY + 1;
	ДельтаX = ДельтаX + 1;
	
	ТекущийШаг = 0;
	
	Если ДельтаX > ДельтаY Тогда
		
		Пока Xt<>Xкон Цикл
			
			Холст.Область(Yt, Xt).ЦветФона = ЦветЛинии;
			
			Xt = Xt + ШагПоX;
			ТекущийШаг = ТекущийШаг + ДельтаY;
			
			Если ТекущийШаг >= ДельтаX Тогда
				
				Yt = Yt + ШагПоY;
				ТекущийШаг = ТекущийШаг - ДельтаX;
				
			КонецЕсли;
			
		КонецЦикла;

		Холст.Область(Yt, Xt).ЦветФона = ЦветЛинии;
		
	Иначе 
		
		Пока Yt<>Yкон Цикл
			
			Холст.Область(Yt, Xt).ЦветФона = ЦветЛинии;
			
			Yt = Yt + ШагПоY;
			ТекущийШаг = ТекущийШаг + ДельтаX;
			
			Если ТекущийШаг >= ДельтаY Тогда
				
				Xt = Xt + ШагПоX;
				ТекущийШаг = ТекущийШаг - ДельтаY;
				             
			КонецЕсли;
			
		КонецЦикла;

		Холст.Область(Yt, Xt).ЦветФона = ЦветЛинии;
		                                             
	КонецЕсли;
   
КонецПроцедуры

Заливка областей

Когда я хаотично линовал экран в ходе тестов, мне прямо захотелось закрасить получившиеяся замкнутые области. Как команда Fill в графических редакторах. На первый взгляд все просто - нам поможет рекурсия:

Процедура ЗакраситьРекурсивно(X, Y, ЦветДоПерекрашивания, НовыйЦветОбласти) 

	Если X > ШиринаПоля ИЛИ Y > ВысотаПоля ИЛИ X < 1 ИЛИ Y < 1 Тогда
		Возврат;
	КонецЕсли;

	Область = Холст.Область(Y, X);
	
	Если Не Область.ЦветФона = ЦветДоПерекрашивания Тогда
		Возврат;
	КонецЕсли;
		
	Область.ЦветФона = НовыйЦветОбласти;

	ЗакраситьРекурсивно(X,   Y-1, ЦветДоПерекрашивания, ЦветЛинии);
	ЗакраситьРекурсивно(X-1, Y, ЦветДоПерекрашивания, ЦветЛинии);
	ЗакраситьРекурсивно(X+1, Y, ЦветДоПерекрашивания, ЦветЛинии);
	ЗакраситьРекурсивно(X,   Y+1, ЦветДоПерекрашивания, ЦветЛинии);
	
КонецПроцедуры

Но не тут-то было. Каждая процедура рекурсивно вызовет саму себя 4 раза. Это очень много - стек очень быстро переполнится на больших областях и программа вылетит с ошибкой. А что самое обидное, эти вызовы по большей части будут ложными, некоторые точки мы будем пытыться раскрасить много раз. Надо как-то сократить количество вызовов и, по возможности, не проверять на перекрашиваемость точки, которые уже были проверены.

Я начал с простого. Можно легко начертить горизонтальную линию от точки клика до пересечения с границей области, например горизонтальная линия на рисунке:

Процедура ЗакраситьГоризонтальнуюЛиниюНачинаяСТочки(X, Y, ЦветДоПерекрашивания, ЦветПерекрашивания)
	
	Xтек = X;
	Пока Истина Цикл	
		
		Область = Холст.Область(Y, Xтек);
		
		Если Область.ЦветФона <> ЦветДоПерекрашивания Тогда
			Прервать;
		КонецЕсли;
		
		Область.ЦветФона = ЦветПерекрашивания;
		Xтек = Xтек + 1;
		
	КонецЦикла;
	
	Xтек = X - 1;
	Пока Истина Цикл	
		
		Область = Холст.Область(Y, Xтек);
		
		Если Область.ЦветФона <> ЦветДоПерекрашивания Тогда
			Прервать;
		КонецЕсли;
		
		Область.ЦветФона = ЦветПерекрашивания;
		Xтек = Xтек - 1;
		
	КонецЦикла;
	
КонецПроцедуры

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

&НаКлиенте
Функция СтруктураТочки(X, Y)

	Рез = Новый Структура;
	Рез.Вставить("X", X);
	Рез.Вставить("Y", Y);
	
	Возврат Рез;

КонецФункции

&НаКлиенте
Процедура ЗафиксироватьВертикальнуюЛиниюНачинаяСТочки(X, Y, ЦветДоПерекрашивания, ЦветПерекрашивания)
	
	Yтек = Y;
	Пока Истина Цикл	
		
		Область = Холст.Область(Yтек, X);
		
		Если Область.ЦветФона <> ЦветДоПерекрашивания Тогда
			Прервать;
		КонецЕсли;
		
		МассивКлючевыхТочек.Добавить(СтруктураТочки(X, Yтек));
		Yтек = Yтек + 1;
		
	КонецЦикла;
	
	Yтек = Y - 1;
	Пока Истина Цикл	
		
		Область = Холст.Область(Yтек, X);
		
		Если Область.ЦветФона <> ЦветДоПерекрашивания Тогда
			Прервать;
		КонецЕсли;
		
		МассивКлючевыхТочек.Добавить(СтруктураТочки(X, Yтек));
		Yтек = Yтек - 1;
		
	КонецЦикла;
	
КонецПроцедуры

А дальше для каждой ключевой точки нарисуем горизонталь:

&НаКлиенте
Процедура ЗакраситьОбластьНачинаяСТочки(X, Y, ЦветДоПерекрашивания, ЦветПерекрашивания)
	
	МассивКлючевыхТочек = Новый Массив;
	
	ЗафиксироватьВертикальнуюЛиниюНачинаяСТочки(X, Y, ЦветДоПерекрашивания, ЦветПерекрашивания, МассивКлючевыхТочек);
	
	Для каждого КлючеваяТочка Из МассивКлючевыхТочек Цикл
	
		ЗакраситьГоризонтальнуюЛиниюНачинаяСТочки(КлючеваяТочка.X, КлючеваяТочка.Y, ЦветДоПерекрашивания, ЦветПерекрашивания);
	
	КонецЦикла;

КонецПроцедуры

Уже начинает получаться:

Но закрашивает не все, что нужно.

Дальнейшее развитие - в момент, когда мы рисуем очередную горизонталь, проверяем, не проходит ли она вплотную к граничному элементу. Вот например, на рисунке, мы рисуем линию вправо от очередной узловой (ключевой) точки (синяя стрелка) и видим, что сверху к ней вплотную примыкает граница (красная стрелка):

И если она проходит рядом с границей, то вот эту новую точку, выше нашей линии (ярко-голубая точка и стрелка на рисунке) добавляем в массив ключевых точек.

Так же поступаем если граница проходит ниже рисуемой области и в тех случаях когда линию мы рисуем влево. Итого четыре случая получается.

А дальше обрабатываем весь этот массив узловых точек дальше, пока весь не обработаем и нечего в него будет добавлять. В этот момент вся наша область должан быть перекрашена

Как это сделать - предлагаю подумать самостоятельно, чтобы потренировать мозги ))
Либо подсмотреть в бесплатной обработке в статье Рисование линий и закрашивание областей в табличном документе 1С