Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Заказчик называет адрес … Как искусственный интеллект определит район, чтобы предложить интервалы доставки?
Математически задача определения района сводится к определению принадлежности точки к многоугольнику. Часто используется термин полигон – массив вершин замкнутого многоугольника. В сервисе Яндекс, например, можно прочертить многоугольник и получить полигон – координаты вершин.
На картах это может выглядеть так:
Массив координат может выглядеть так:
[
[55.5398240358901,86.06198408166499],
[55.53923998368585,86.18901350061027],
[55.498529562499215,86.23501874963371],
[55.47260090273308,86.2381086544189],
[55.48839408166666,86.14300825158683],
[55.500478393141144,86.05649091760245],
[55.5398240358901,86.06198408166499]
]
Географические координаты, соответствующие адресу, можно получить через соответствующие интернет-сервисы, например, dadata, и останется лишь определить, попадает ли данная точка в заданный многоугольник.
Принцип определения принадлежности точки полигону следующий:
Запускаем из данной точки бесконечный луч по любому направлению
Считаем, сколько раз луч пересек границу полигона
Если пересек нечетное количество раз, то точка находится внутри полигона, если четное, в том числе 0, то точка не находится внутри полигона
Рассматриваем совпадения точки с вершинами полигона и нахождение точки на границе полигона.
Алгоритм простой, доступно для любого языка программирования.
Рассмотрим данный алгоритм на js.
В нашем случае будем определять только нахождение точки внутри полигона, то есть не проверяем на совпадение точки с вершинами и на нахождение точки на границе полигона.
Зададим координаты точки, координаты полигона и установим счетчик пересечений в начальное нулевое значение.
var point = [7,6];
var polygon = [[5,5], [10,10], [15,10], [14,6], [5,5]];
var point_counter = 0;Будем поочередно перебирать вершины полигона и определять линии – границы полигона.
polygon.forEach(function(item_polygon, i_polygon) {
if ( i_polygon < (polygon.length-1) ) {
var polyline = [item_polygon, polygon[i_polygon + 1]];
}
});Для удобства направим бесконечный луч из точки вправо.
Очевидно, что если точка находится выше или ниже косой линии, то луч линию не пересекает. Также, если точка находится правее косой линии, то луч линию не пересекает.
Луч точно пересекает косую линию, если точка находится левее самой крайней слева вершины.
Если же точка находится между вершинами и по вертикали, и по горизонтали, то тут уже нужно смотреть, с какой стороны от линии она находится – слева/справа (выше/ниже). Так, если вертикальная координата точки больше, чем вертикальная координата точки на линии, соответствующей данной горизонтальной координате, то луч пересекает линию, если меньше – то не пересекает.
Проверить, находится ли точка между вершинами достаточно просто. Нужно перемножить разности координат, и если знак отрицательный, то точка находится между, если знак положительный, то точка будет находиться с одной стороны от вершин.
// косая линия
if ( polyline[0][0] != polyline[1][0] & polyline[0][1] != polyline[1][1] ) {
// проверка по горизонтали
var check1 = ( point[0] - polyline[0][0] ) * ( point[0] - polyline[1][0] );
// проверка по вертикали
var check2 = ( point[1] - polyline[0][1] ) * ( point[1] - polyline[1][1] );
// если попала слева по горизонтали и между по вертикали
if ( check2 < 0 & point[0] < polyline[0][0] & point[0] < polyline[1][0]) {
point_counter++;
}
// если попала между по горизонтали и между по вертикали
if ( check1 < 0 & check2 < 0) {
var delta0 = (point[0] - polyline[0][0])/(polyline[1][0]-polyline[0][0]);
var coord1 = (polyline[1][1]- polyline[0][1]) * delta0 + polyline[0][1];
// проверка нахождения с нужной стороны от косой линии
var check3 = ( coord1 - point[1]) * ( polyline[1][1] - polyline[0][1] );
// если попала с нужной стороны
if ( check3 < 0) {
point_counter++;
}
}
}Отдельно рассмотрим случай пересечения вертикальной линии. Очевидно, что луч пересекает вертикальную линию, если вертикальная координата точки лежит между вертикальными координатами вершин, а горизонтальная координата меньше горизонтальной координаты любой вершины (горизонтальные координаты вершин равны).
// перпендикулярная вертикальная линия
if ( polyline[0][0] == polyline[1][0] ) {
// проверка по вертикали
var check = ( point[1] - polyline[0][1] ) * ( point[1] - polyline[1][1] );
// если попала слева от линии по горизонтали и между по вертикали
if ( point[0] < polyline[0][0] & check < 0 ) {
point_counter++;
}
}Пересечение луча с горизонтальной границей не рассматриваем, так как в нашем случае это не влияет на нахождение точки внутри полигона.
Осталось рассмотреть пересечение луча с вершиной. Здесь нужно всего лишь определить, находится ли горизонтальная координата точки левее горизонтальной координаты вершины, и находится ли вертикальная координата точки между вертикальными координатами соседних вершин.
// проверяем пересечение с вершиной
// если точка левее вершины по горизонтали и на уровне по по горизонтали
if ( point[1] == item_polygon[1] && point[0] < item_polygon[0] ) {
//проверяем, точка внутри угла или снаружи
if ( i_polygon > 0) {
// произведение разниц вертикальных координат точки и соседених вершин
var check = (point[1] - polygon[i_polygon-1][1]) * (point[1] - polygon[i_polygon+1][1]);
}
if ( i_polygon == 0) {
// произведение разниц вертикальных координат точки и соседених вершин
var check = (point[1] - polygon[polygon.length-2][1]) * (point[1] - polygon[i_polygon+1][1]);
}
// если точка находится между по вертикали
if (check < 0) {
point_counter++;
}
}
Для удобства можно обернуть подсчет в единую функцию и остается только проверить на четность.
var polygon = [[5,5], [10,10], [15,10], [14,6], [5,5]];
var point = [7,6];
var point_counter = 0;
point_counter = Counter(point,polygon);
if ( point_counter % 2 == 0 ) {
// вывод или сохранение переменной
console.log('точка: ' + point + ' находится не внутри полигона');
}
else {
// вывод или сохранение переменной
console.log('точка: ' + point + ' находится внутри полигона');
}
function Counter(point,polygon) {
polygon.forEach(function(item_polygon, i_polygon) {
if ( i_polygon < (polygon.length-1) ) {
var polyline = [item_polygon, polygon[i_polygon + 1]];
if ( polyline[0][0] != polyline[1][0] & polyline[0][1] != polyline[1][1] ) {
var check1 = ( point[0] - polyline[0][0] ) * ( point[0] - polyline[1][0] );
var check2 = ( point[1] - polyline[0][1] ) * ( point[1] - polyline[1][1] );
if ( check2 < 0 & point[0] < polyline[0][0] & point[0] < polyline[1][0]) {
point_counter++;
}
if ( check1 < 0 & check2 < 0) {
var delta0 = (point[0] - polyline[0][0])/(polyline[1][0]-polyline[0][0]);
var coord1 = (polyline[1][1]- polyline[0][1]) * delta0 + polyline[0][1];
var check3 = ( coord1 - point[1]) * ( polyline[1][1] - polyline[0][1] );
if ( check3 < 0) {
point_counter++;
}
}
}
if ( polyline[0][0] == polyline[1][0] ) {
var check = ( point[1] - polyline[0][1] ) * ( point[1] - polyline[1][1] );
if ( point[0] < polyline[0][0] & check < 0 ) {
point_counter++;
}
}
if ( point[1] == item_polygon[1] && point[0] < item_polygon[0] ) {
if ( i_polygon > 0) {
var check = (point[1] - polygon[i_polygon-1][1]) * (point[1] - polygon[i_polygon+1][1]);
}
if ( i_polygon == 0) {
var check = (point[1] - polygon[polygon.length-2][1]) * (point[1] - polygon[i_polygon+1][1]);
}
if (check < 0) {
point_counter++;
}
}
}
});
return point_counter;
}
Конечно, код можно оптимизировать, объединив все сравнения в более сложное одновременное сравнение. Данный же код просто показывает алгоритм, упрощает понимание алгоритма и проверку ошибок.
