Недавно возник вопрос, как можно определить входит ли точка в произвольный полигон. Различных решений в интернетах море, но, как ни странно, никто не реализовывал эту задачу под 1С. Многие решения были достаточно громоздки, использовали тригонометрические функции, что приводило к довольно длительным вычислениям на больших массивах данных. Я выбрал алгоритм из http://habrahabr.ru/post/125356/ как отрабатывающий за время кратное количеству вершин в полигоне и требующий на каждую вершину лишь: 2 сложения, 4 вычитания, 1 умножение, 1 деление и одну операция взятия знака числа. Конечно, интерпретатор 1С далёк от лаконичности, но стало интересно в какие сроки этот алгоритм будет работать на реальных данных. Расчет реализован с помощью функции, принимающей на входе 2 параметра: массив структур, содержащих координаты вершин полигона и структуру, содержащую координаты точек. На выходе функция возвращает "Истина" если точка входит в полигон и "Ложь" в ином случае.
С теорией по работе алгоритма можно ознакомиться по следующей ссылке: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.5498&rep=rep1&type=pdf или из pdf во вложенном файле.
Код функции следующий:
//Полигон - Массив структур{Х,У} //Точка - Структура{Х,У}
Функция ПроверитьТочку(Знач Полигон,Знач Точка) Экспорт
Перем Результат;
Если Полигон.Количество() < 3 Тогда
Возврат Ложь;
КонецЕсли;
Результат = 0;
Шаблон = Новый Массив;
Строка1 = Новый Массив;
Строка1.Добавить(0);
Строка1.Добавить(1);
Шаблон.Добавить(Строка1);
Строка2 = Новый Массив;
Строка2.Добавить(3);
Строка2.Добавить(2);
Шаблон.Добавить(Строка2);
Размер = Полигон.Количество()-1;
Конец = Полигон[Размер];
ПредыдущаяТочка = Новый Структура("Х,У",Полигон[Размер].Х,Полигон[Размер].У);
ПредыдущаяТочка.Х = ПредыдущаяТочка.Х - Точка.Х;
ПредыдущаяТочка.У = ПредыдущаяТочка.У - Точка.У;
Если ПредыдущаяТочка.У < 0 Тогда
Х = 1;
Иначе
Х = 0;
КонецЕсли;
Если ПредыдущаяТочка.Х < 0 Тогда
У = 1;
Иначе
У = 0;
КонецЕсли;
Пред_КУ = Шаблон[Х][У];
Для Сч = 0 По Размер Цикл
ТекТочка = Новый Структура("Х,У",Полигон[Сч].Х,Полигон[Сч].У);
ТекТочка.Х = ТекТочка.Х - Точка.Х;
ТекТочка.У = ТекТочка.У - Точка.У;
Если ТекТочка.У < 0 Тогда
Х = 1;
Иначе
Х = 0;
КонецЕсли;
Если ТекТочка.Х < 0 Тогда
У = 1;
Иначе
У = 0;
КонецЕсли;
Ку = Шаблон[Х][У];
ДельтаКу = Ку - Пред_Ку;
Если ДельтаКу = -3 Тогда
Результат = Результат + 1;
ИначеЕсли ДельтаКу = 3 Тогда
Результат = Результат - 1;
ИначеЕсли ДельтаКу = -2 Тогда
Если ПредыдущаяТочка.Х*ТекТочка.У >= ПредыдущаяТочка.У*ТекТочка.Х Тогда
Результат = Результат + 1;
КонецЕсли;
ИначеЕсли ДельтаКу = 2 Тогда
Если НЕ (ПредыдущаяТочка.Х*ТекТочка.У >= ПредыдущаяТочка.У*ТекТочка.Х) Тогда
Результат = Результат - 1;
КонецЕсли;
КонецЕсли;
ПредыдущаяТочка = ТекТочка;
Пред_КУ = Ку;
КонецЦикла;
Возврат НЕ(Результат = 0);
КонецФункции
