Существуют различные области применения, в которых основными объектами являются многоугольники. Например, среди этих областей есть алгоритмы для задач вычислительной геометрии, алгоритмы компьютерной графики, графические приложения, которые стремятся имитировать природные структуры: облака, земельные образования, биологические или гидрологические явления.
Генерация случайных многоугольников используется для проверки правильности и оценки потребления процессорного времени алгоритмов, работающих на многоугольниках. Данные могут быть заданы вручную или случайно. Главной сложностью генерации вручную является потребность предвидеть особенности задачи, чтобы за минимальное время протестировать исключительные случаи. Сгенерированные случайным образом данные позволяют увеличить объем и статистическую выборку работы алгоритма, также при большом количестве испытаний будут обнаружены все имеющиеся в алгоритме ошибки.
Данные для статистического тестирования должны быть разнообразны и достаточны по количеству, так как нет смысла проверять только на частных случаях многоугольников и на маленькой выборке. Часто практически невозможно получить достаточно большое количество разнообразных входных данных. Тогда наилучший вариант — запустить алгоритм для достаточно большого числа случайных входных данных. А так как в каждой задаче объекты могут быть своими, то хорошо бы задавать параметры, чтобы генерировать подходящие для этой задачи данные.
В данной работе рассматривается задача генерации случайных многоугольников с заданным количеством вершин и заданным классом (выпуклый, звездный). Описанные выше параметры являются обязательными и выбираются при построении многоугольника. Также есть и дополнительные: максимальная и минимальная длины ребра, диапазон изменения угла и дисперсия величины угла. Дополнительные параметры не являются необходимыми в поставленной задаче и учитываются при возможности разрабатываемых алгоритмов.
Работа состоит из двух глав. В первой главе рассматриваются основные известные алгоритмы и идеи на которых они основаны, анализируется применимость к поставленной задаче. Во второй главе описываются и сравниваются между собой алгоритмы, разработанные в рамках данной работы.
В рамках данной работы были разработаны два алгоритма репарации случайных выпуклых многоугольников и алгоритм генерации случайных звёздных многоугольников. Алгоритмы были реализованы объединены в одну общую программу. Программа позволяет кроме основных параметров выбирать частные дополнительные параметры и экспортировать полученный многоугольник в TjjX-файл. Также была протестирована, сравнена и проанализирована скорость работы алгоритмов, строящих многоугольники одних типов, на большом объеме экземпляров. Таким образом поставленная задача была выполнена.
В качестве развития темы возможна разработка алгоритмов генерации многоугольников других классов, а так же добавление других дополнительных параметров к разработанным алгоритмам.
