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



    Вводная


    Сразу оговорюсь кому может быть интересна данная публикация. Это начинающие 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/. Должна получиться картинка, аналогичная той, что в начале поста.
    Share post

    Similar posts

    Comments 51

      +1
      А какие ещё алгоритмы могут быть для решения этой задачи? Я от программирования человек далёкий, но первое, что пришло в голову — разбить полигон на непересекающиеся треугольники и последовательно перебирать, не принадлежит ли точка одному из них.
        +1
        А еще можно залить полигон цветом неуловимо для глаза отличающимся от цвета фона и по цвету пикселя в точке клика определять внутри она, снаружи или на границе
          0
          решение с цветом очень интересное… элегантно и просто. вероятно не для всех технологий подойдёт, но всё же.
          0
          С математической точки зрения правильнее так: https://habrahabr.ru/post/125356/
            0
            Кстати там же есть ветка, что задача решена не полностью и требует доп. проверок: habrahabr.ru/post/125356/#comment_4130015
              +1

              Там же в комментариях приводят решение этой проблемы: https://habrahabr.ru/post/125356/#comment_4125696
              Кстати, оно уже применено автором: "(yp <= y and y < yp_prev) or (yp_prev <= y and y < yp)". Все отрезки считаются открытыми сверху и закрытыми снизу. Поэтому пересечения с концами отрезков отрабатываются правильно — как 0, 1 или 2 пересечения с правильной четностью.

            +3
            Да, самый простой алгоритм — трассировка.
            Второй, который приходит в голову — сделать обход контура полигона против часовой и посмотреть, где находится точка от ближайшей стороны полигона, справа или слева. Если справа, то она снаружи, слева — внутри.
              0
              Это будет работать только с выпуклыми многоугольниками…
                0
                Можно разбить многоугольник на выпуклые.
                  +2
                  Это будет работать с любыми многоугольниками без самопересечений
                0
                Я считал количество пересечений отрезка (от нашей точки до любой точки за пределами канваса) с ребрами полигона. Если количество парное или равно 0 — точка не в полигоне; иначе, в полигоне.
                  0
                  Именно этот метод и описан в статье:
                  Последовательно проверяются все грани полигона на пересечение с лучом, идущим из точки, куда кликнул пользователь. Четное количество пересечений или нет пересечений вовсе — точка за пределами полигона. Количество пересечений нечетное — точки внутри.
                    0
                    понял, не сразу распознал эту часть)

                    if (...):
                    in_polygon = not in_polygon

                    прошу прощения.
                0
                Я бы использовал Алгоритм Грэхема или Джарвиса: habrahabr.ru/post/144921
                  0

                  Чем построение выпуклой оболочки поможет определить вхождение точки в многоугольник?

                  0
                  Я, к сожалению, python не знаю, поэтому ламерский вопрос: а что произойдет, если один или несколько сторон полигона окажутся строго горизонтальными и при этом точка окажется на прямой, к которой эта горизонтальная сторона принадлежит?

                  Другими словами что будет, если yp_prev == yp && y == yp?
                    0
                    В данной реализации попадание в вершину или на грань (даже если грань лежит на луче) будет считаться вхождением в полигон.
                      0
                      (xp_prev — xp) * (y — yp) / (yp_prev — yp) а деление на 0 нормально отработает в данной реализации?
                        0
                        Не могу точно сказать проверяет ли интерпретатор python все условия или прекращает дальнейшую проверку если одна часть and конструкции является False, но скорей всего прекращает. А это значит что ((yp <= y and y < yp_prev) or (yp_prev <= y and y < yp)) будет False и до деления на 0 не дойдет. Исключение — случай когда одна из граней имеет одинаковые координаты на обоих концах, то есть точка.
                          +1
                          Ну я правильно понимаю, что в этом случае вы пропускаете горизонтальные стороны?
                          Если ситуация будет как на картинке (извините за цвета, нарисовал быстро для примера), то ваша функция посчитает, что луч пересекает только зеленые грани, т.е. пересечений четное кол-во?
                          image
                            +1
                            Да, Вы правы, признаю, грань, лежащая на луче не будет засчитана, а прилегающие к ней грани посчитаются 2 раза, что выльется в результат «вне полигона». Такая ситуация требует отдельной проверки.
                              +1

                              Нет, не требует. Вы реализовали полностью правильный алгоритм. Грани соседствующие с горизонтальной на луче посчитаются 0, 1 или 2 раза в зависимости от из ориентации. У вас все отрезки закрыты снизу и открыты сверху, обратите внимание на строгие и нестрогие знаки: ((yp <= y and y < yp_prev) or (yp_prev <= y and y < yp)). Поэтому на картинке сверху будет одно пересечение, а если бы касание горизонтальной грани было сверху — то было бы 2 пересечения.

                                0
                                Поясните подробнее, пожалуйста. Не понял вашу мысль.
                                Сколько пересечений будет, если сложится ситуация как на моей картинке? По-хорошему должно быть 3 пересечения.
                                Но, судя по тому, что реализация автора проигнорирует горизонтальную грань (результат приведенных вами условий будет false), пересечений будет 2.
                                    0

                                    Будет 1 пересечение. Горизонтальная грань будет проигнорирована вообще. Верхняя грань зачтется за 1 пересечение по вершине. Нижняя грань (внешняя) не будет учтена за пересечение, потому что она лежит на луче верхней точкой. Условие в алгоритме всегда игнорирует верхнюю точку любого отрезка или горизонтальные отрезки целиком.


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

                                      0
                                      Да, действительно.
                                      Упустил из виду этот момент, акцентируя внимание на игнорировании горизонтальных линий.
                                      Забавно, что сам автор ввел в дополнительное заблуждение своим ответом.
                                        0
                                        Да, я сам запутался, wataru прав, я выполнял задание в январе — детали забываются, но достаточно посмотреть на код:

                                        ((yp <= y and y < yp_prev) or (yp_prev <= y and y < yp))
                                        

                                        как становится понятно что если один конец грани лежит на луче, а второй выше (визуально, учитывая что точка отсчета координат в левом верхнем углу) — такая грань не будет считаться пересечением.
                              +1
                              Прекращает проверку, это описано в стандарте: https://docs.python.org/3/library/stdtypes.html#boolean-operations-and-or-not
                        0
                        А что если перебирать все точки последовательно, обходя контур в каком либо направлении и суммировать углы поворота? Если суммарный угол в итоге будет равен 0, значит точка снаружи. Если 360 значит внутри.
                          0

                          Это тоже правильный метод. Надо только аккуратно обрабатывать точку на грани или совпадающую с вершиной многоугольника. Его недостаток — скорость. Медленные тригонометрические функции и невозможность сделать целиком в целых числах.


                          Метод пересечения с лучом можно реализовать без деления вообще в целых числах, если координаты всех вершин целые.

                        • UFO just landed and posted this here
                            +1
                            Может и микроскопом гвозди, я бы использовал https://pypi.python.org/pypi/Shapely сделать быстрее на порядок, вывод в json или svg.
                            0
                            Задача неплохая, но ее основная сложность, я бы сказал процентов 95, в самом алгоритме.
                              +1
                              Это начинающие Django + JQuery программисты, интересующиеся векторной графикой в браузере с использованием canvas

                              Вызывает то чувство, когда вводишь сложный вопрос в Гугл и получаешь 0 результатов.

                              В статье нет новизны. Обе темы рассматривались неоднократно. Кроме того, опубликованный код — не лучший пример для других. Во-первых, имя view.py намекает, что данный модуль отвечает за представление, а не логику. Во-вторых, алгоритм легко протестировать, но я не вижу тестов. И чтобы их написать, вам придётся разделить логику и код, который принимает запрос и отправляет ответ.
                              0
                              При пересекающихся ребрах есть особенности.

                              Бывает «even-odd winding rule» и «non-zero winding rule».
                              even-odd non-zero

                              В первом случае красная точка считается за пределами полигона (как у автора), во-втором — внутри.
                                0

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

                                  +1
                                  Вот еще один пример, из вики.
                                    0

                                    А почему левая четырехугольная область тут считается внутри многоугольника? Чем она принципиально отличается от правой треугольной, которая помечена как снаружи? По методу луча она тоже будет снаружи.

                                      0
                                      Она только по правилу non-zero winding rule считается внутри. А по правилу even-odd winding rule она бы считалась снаружи.

                                      Насчет отличия таких областей в вики есть удачная метафора:
                                      Если бы P была гвоздём, а C была бы завязанным в кольцо куском нитки, вытягивание какой-то части нитки прочь от гвоздя приведёт либо к вытягиванию всей нитки, либо нитка окажется накрученной несколько раз на гвоздь
                                  0
                                  Как-то я не уловил алгоритм:
                                  Последовательно проверяются все грани полигона на пересечение с лучом, идущим из точки, куда кликнул пользователь. Четное количество пересечений или нет пересечений вовсе — точка за пределами полигона. Количество пересечений нечетное — точка внутри.

                                  Треугольник дает 3 пересечения, прямоугольник — 4. В кого из них точка не входит?

                                     image
                                    0
                                    Луч уходит от точки влево (в реализации автора). Соответственно он пересекает только левые стороны ваших фигур. Кол-во пересечений в обоих случаях = 1.
                                      0
                                      То есть как и предполагал — алгоритм описан неправильно. )
                                      Надо добавить, что луч единственный и направлен влево.

                                      Тем не менее есть контр-пример:
                                         image

                                      Если считать, как написано в этом комменте, грани полуинтервалами, то левый прямоугольник даст 1 пересечение и точка будет засчитана внутри него. Если же считать грани отрезками, то правый прямоугольник даст 3 пересечения и точка «попадет» в него.
                                        0

                                        Смотрите код внимательно. Полуинтервалы, открытые сверху. Не с начала или с конца, а сверху всегда. В первом примере с касанием угла левая грань не будет считаться пересечением, потому что касание идет по верхней точке отрезка, которая исключена. Правая грань так же не зачтется, ибо эта точка верхняя и для второй грани. Если бы касание было нижней точки многоугольника то было бы зачтено 2 пересечения. Точно так же и со вторым примером, там еще есть горизонтальная грань, которая игнорируется всегда.

                                          0
                                          С такими дополнениями — да.
                                          Просто ничего этого в алгоритме не было указано.
                                            0

                                            Да, автор эту деталь не описал, хотя в коде она присутствует.

                                    0
                                    Скажу честно, меня заинтриговал питоновский цикл «for in range». Поскольку я абсолютно не специалист в этом языке, то подскажите пожалуйста, чему в Вашем цикле, где определяется вхождение точки в полигон, будет равно значение xp_prev (а также yp_prev) при первом шаге цикла, когда i=0, а [i-1], соответственно, равно -1?
                                      0
                                      Отрицательные индексы в питоне валидны и означают отсчет с конца массива, то есть [-1] — это последний элемент, [-2] — предпоследний и так далее.
                                        0
                                        Благодарю

                                    Only users with full accounts can post comments. Log in, please.