Постановка задачи

Необходимо написать программу, находящую выпуклую оболочку последовательно поступающих точек плоскости и вычисляющую её периметр, площадь. Необходимо также модифицировать проект, найдя площадь пересечения выпуклой оболочки с треугольником, координаты которого задаются заранее. Решение должно быть индуктивным, что означает определение выпуклой оболочки и вычисление её характеристик сразу после поступления очередной точки с использованием методов теории индуктивных функций.

Краткий комментарий к решению

• Ключевое понятие проекта: освещённость ребра из точки
• Вспомогательные классы:
  • R2Point — точка на плоскости
  • Deq — контейнер дек (double ended queue)
• Основные классы:
  • Figure — «абстрактная» фигура
  • Void — нульугольник
  • Point — одноугольник
  • Segment — двуугольник
  • Polygon — многоугольник
• Файлы проекта:
  • README.md — данный файл
  • README.html — полученный из файла README.md html-файл
  • r2point.py — реализация класса R2Point
  • deq.py — реализация класса Deq
  • convex.py — реализация основных классов
  • run_convex.py — файл запуска
  • tk_drawer.py — интерфейс к графической библиотеке
  • run_tk_convex.py — файл запуска с использованием графики
  • tests/test_r2point.py — тесты к классу R2Point
  • tests/test_convex.py — тесты к основным классам

Файлы run_tk_convex.py и run_tk_convex.py являются исполняемыми (они имеют бит x), в первой строке каждого из них используется шебанг и команда env с опцией (ключом) -S. Это обеспечивает передачу интерпретатору языка Python опции (ключа) -B, отменяющего генерацию pyc-файлов в директории __pycache__.

Комментарий к модификации

Для объектов классов Figure, Void, Point и Segment площадь пересечения всегда равна 0. Для определения этой площади с объектами класса Polygon создадим статический метод intersect в классе R2Point, в котором будем определять точку пересечения двух отрезков. Далее в классе Figure определим статический метод intersects, который ищет все точки пересечения двух треугольников, а также точки выпуклой оболочки, лежащие внутри заданного треугольника. По этим точкам создается выпуклая оболочка и вычисляется ее площадь. Когда выпуклая оболочка еще треугольник достаточно вызвать метод intersects. При добавлении новой точки перерасчет площади пересечения сводится к добавлению к исходной величине результатов метода intersects для новых треугольников, получившихся в результате соединения точек выпуклой оболочки с новой точкой. Таким образом, модификация выполнена индуктивно.

Соблюдение соглашений о стиле программного кода

Для языка Python существуют соглашения о стиле кода. Они являются лишь рекомендациями (интерпретатор игнорирует их нарушение), но основную их часть при написании программ целесообразно соблюдать. Существует простой способ проверить соблюдение считающегося правильным стиля записи кода с помощью утилиты (программы) pycodestyle. Утилита yapf позволяет даже изменить код в соответствии с этими соглашениями.

Команда

pycodestyle r2point.py

позволяет, например, проверить соблюдение стиля для файла r2point.py. С помощью очень мощной и часто используемой утилиты find проверить корректность стиля всех файлов проекта можно так:

find . -name '*.py' -exec pycodestyle {} \;

Эта команда находит все файлы с расширением py и запускает программу pycodestyle последовательно для каждого из них.

Запуск тестов

Уже известная нам команда (см. материал, посвящённый тестированию программ)

python3 -B -m pytest -p no:cacheprovider tests

запускает pytest, выполняя все начинающиеся с test методы классов, имена которых начинаются с Test, содержащиеся во всех файлах test_*.py директории tests.

Запуск программы

./run_convex.py

Запуск программы с графическим интерфейсом

./run_tk_convex.py