Тестовое задание. Проверка вхождения точки в произвольный полигон
Вводная
Сразу оговорюсь кому может быть интересна данная публикация. Это начинающие Django + JQuery программисты, интересующиеся векторной графикой в браузере с использованием canvas. Или просто люди, получившие подобное задание.
Итак, находясь в постоянном сканировании рынка труда своего региона, наткнулся на весьма интересную вакансию web-разработчика в достаточно известной местной компании. В описании вакансии было сказано, что нужен python+django разработчик. После отправки резюме получил тестовое задание которое гласило:
Необходимо создать веб-приложение на Django, которое определяет факт вхождения точки в произвольный (не выпуклый) полигон. Клиентская часть должна отобразить в браузере (на канвасе или svg, или еще на чем-нибудь, в общем не принципиально) произвольный полигон, позволить пользователю указать точку на экране, отправить запрос на сервер, получить и отобразить ответ. Серверная часть, соответственно, должна принять запрос, определить, находится точка внутри контура, или нет, и вернуть ответ клиенту. Серверная часть на Python, клиентская — HTML + JavaScript либо CoffeeScript.
Потратив пару часов на выполнение задания и публикацию результата на тестовом сервере я уперся в полный игнор со стороны потенциального работодателя. Я не в обиде, бывает всякое, тем более задание было интересное и его выполнение принесло немало удовольствия. Чтобы добро не пропадало — публикую его здесь.
Поехали
Первым делом подготовим площадку, я использовал virtualenv:
scherbin@scherbin-pc ~$ cd WebDev/venvs
scherbin@scherbin-pc ~/WebDev/venvs/ $ virtualenv test
scherbin@scherbin-pc ~/WebDev/venvs/ $ cd test
scherbin@scherbin-pc ~/WebDev/venvs/test/ $ source bin/activate
Устанавливаем необходимый софт и прямо здесь создаем проект:
(test)scherbin@scherbin-pc ~/WebDev/venvs/test/ $ pip install django
(test)scherbin@scherbin-pc ~/WebDev/venvs/test/ $ django-admin startproject mytest
(test)scherbin@scherbin-pc ~/WebDev/venvs/test/ $ cd mytest
Наш проект будет состоять из двух приложений start и api. Первое будет отдавать браузеру пользователя HTML и JavaScript то есть наш frontend, второе будет обрабатывать AJAX запросы frontend-а, то есть будет нашим backend-ом. Создаем их:
(test)scherbin@scherbin-pc ~/WebDev/venvs/test/mytest/ $ django-admin startapp start
(test)scherbin@scherbin-pc ~/WebDev/venvs/test/mytest/ $ django-admin startapp api
Структура
Теперь, когда костяк проекта у нас есть, можно переходить непосредственно к творчеству. Для начала распишем структуру проекта. Как было указано выше, он будет состоять из двух частей, frontend и backend.Frontend
Будет выводить в браузере, с использованием canvas, произвольный полигон и обрабатывать клики пользователя по нему. При клике backend-у посредством AJAX запроса будут передаваться две вещи в формате JSON:
- Массив координат полигона.
- Координаты точки куда кликнул пользователь.
После получения ответа на его основе в точке клика будет рисоваться круг диаметром 5 пикс. зеленого (входит в полигон) или красного (не входит) цвета.Backend
Принимает запрос от frontend-а, вычисляет принадлежность точки полигону и возвращает результат в виде координат точки и boolean признака вхождения. Как видим многоугольник не хранится на сервере и есть потенциальная возможность использования и backend-а в случаях когда многоугольник меняется.
Реализация
Первым делом нам надо вывести наш полигон в браузере пользователя. Создаем главную (и единственную в нашем мини проекте) HTML страницу.
mytest/start/templates/start/index.html:
Тестовое задание
{% load staticfiles %}
Как видно из кода на странице используется библиотека JQuery версии 1.12.0 и наш main.js файл где содержится JavaScript код, реализующий всю рутину. А именно рисование полигона, обработку кликов и связь с backend-ом. По сути это главный файл нашего мини проекта.
mytest/start/static/js/main.js:
$(function() {
/**
* Координаты нашего полигона
*/
var polygon = [
[200, 50],
[415, 80],
[550, 200],
[700, 200],
[300, 400],
[750, 580],
[150, 530],
[100, 150],
[300, 250],
[200, 50]
];
/**
* Размеры холста
*/
var canvasWidth = 800;
var canvasHeight = 600;
/**
* Функция вывода нашего полигона на холсте с использованием массива координат
*/
var drawPolygon = function(id, coords) {
var canvas = $("#"+id);
if (canvas.length) {
var context = canvas[0].getContext("2d");
context.canvas.width = canvasWidth;
context.canvas.height = canvasHeight;
context.beginPath();
for (var i = 0; i < coords.length; i++) {
if (i == 0) context.moveTo(coords[i][0], coords[i][1]);
else context.lineTo(coords[i][0], coords[i][1]);
}
context.strokeStyle = '#0000';
context.stroke();
}
};
/**
* Обрабатываем нажатия мышкой на холст
*/
$(document).on("click", "#canvas-main", function(event){
// ФИксируем координаты клика
var x = event.pageX-$(this).offset().left;
var y = event.pageY-$(this).offset().top;
// Готовим запрос к серверу. Запрос содержит координаты полигона и точки куда был произведен клик
var query = {
"polygon": polygon,
"point": [x, y]
};
// Получаем доступ к холсту
var context = $(this)[0].getContext("2d");
// Выполняем POST запрос к серверу
$.ajax({
type: "POST",
url: '/api/in_polygon',
data: JSON.stringify(query),
success: function(data) {
// ОБрабатываем полученный ответ
p = data['point'];
// Рисуем круг в точке клика
context.beginPath();
context.arc(p[0], p[1], 5, 0, 2 * Math.PI, false);
// По результату запроса заливаем круг зеленым или красным цветом
if (data['in_polygon'])
context.fillStyle = "#73AD21";
else
context.fillStyle = "#FF0000";
context.fill();
}
});
});
/**
* Рисуем полигон сразу после загрузки страницы
*/
drawPolygon("canvas-main", polygon);
});
Теперь необходимо реализовать саму проверку вхождения точки в полигон. Алгоритм использован самый простейший — трассировка луча. Последовательно проверяются все грани полигона на пересечение с лучом, идущим из точки, куда кликнул пользователь. Четное количество пересечений или нет пересечений вовсе — точка за пределами полигона. Количество пересечений нечетное — точки внутри. Далее python реализация в backend приложении api.
mytest/api/views.py:
# -*- coding: utf-8 -*-
import json
from django.http import HttpResponse, JsonResponse
# Create your views here.
def in_polygon(request):
if request.method == 'POST':
data = json.loads(request.body)
in_polygon = False
# Main algorithms
x = data['point'][0]
y = data['point'][1]
for i in range(len(data['polygon'])):
xp = data['polygon'][i][0]
yp = data['polygon'][i][1]
xp_prev = data['polygon'][i-1][0]
yp_prev = data['polygon'][i-1][1]
if (((yp <= y and y < yp_prev) or (yp_prev <= y and y < yp)) and (x > (xp_prev - xp) * (y - yp) / (yp_prev - yp) + xp)):
in_polygon = not in_polygon
response = {u'in_polygon': in_polygon, u'point': [x, y]}
return JsonResponse(response)
else:
return HttpResponse(u'Запрос должен использовать метод POST');
Теперь основной функционал готов. Осталось заставить все это дело работать. Для этого правим три файла.
mytest/mytest/settings.py
# Application definition
INSTALLED_APPS = [
...
'start',
'api',
]
mytest/mytest/urls.py
from django.conf.urls import *
from django.contrib import admin
from start.views import *
urlpatterns = [
url(r'^admin/', admin.site.urls),
url(r'^api/', include('api.urls')),
url(r'^$', start_index),
]
mytest/api/urls.py
from django.conf.urls import *
from api.views import *
urlpatterns = [
url(r'^in_polygon$', in_polygon, name='in_polygon')
]
С этого момента можно запускать встроенный в Django тестовый web сервер:
(test)scherbin@scherbin-pc ~/WebDev/venvs/test/mytest/ $ ./manage.py runserver
И играть в зеленые и красные точки перейдя в браузере по адресу localhost:8000/. Должна получиться картинка, аналогичная той, что в начале поста.
