Тестове завдання. Перевірка входження точки в довільний полігон



Вступна

Відразу обмовлюся кому може бути цікава ця публікація. Це початківці 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:

  1. Масив координат полігону.
  2. Координати точки куди клікнув користувач.
Після одержання відповіді на його основі в точці кліка буде малюватися коло діаметром 5 пікс. зеленого (входить в полігон) або червоного (не входить) кольору.

Backend
Приймає запит від frontend-а, обчислює належність точки полігону та повертає результат у вигляді координат точки і boolean ознаки входження. Як бачимо багатокутник не зберігається на сервері і є потенційна можливість використання і backend-а у випадках, коли багатокутник змінюється.

Реалізація

Насамперед нам треба вивести наш полігон в браузері користувача. Створюємо головну (і єдину в нашому міні проекті) HTML сторінку.

mytest/start/templates/start/index.html:
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Тестове завдання</title>
{% load staticfiles %}
<script src="{% static 'js/jquery-1.12.0.min.js' %}"></script>
<script src="{% static 'js/main.js' %}"></script>
</head>
<body>
<style>
canvas#canvas-main {
border: 1px solid darkgray;
}
</style>
<canvas id="canvas-main"></canvas>
</body>
</html>

Як видно з коду на сторінці використовується бібліотека 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/. Повинна вийти картинка, аналогічна тій, що на початку посту.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.