Описание приложения
Основная тема тестового задания - разбиение полигонов, предварительно созданных в программе при помощи мыши или клавиатуры. Так как это задание предполагает активное использование графических средств, то мной было принято решение для исполнения задания использовать подсистему Windows Presentation Foundation (WPF) в составе .NET Framework, использующую языки C# и XAML.Название приложения появилось на первом этапе его создания, когда поэтапно решались задачи по построению интерактивного полигона. Эти этапы оставлены в приложении в виде отдельных задач: 1.Построение интерактивной точки; 2.Построение интерактивной линии; 3.Построение интерактивной полилинии; 4.Построение интерактивного полигона. Получился своеобразный редактор для построения различных по степени сложности фигур.
Если возникнет необходимость, то список фигур обрабатывамых приложением можно будет расширить фигурами любой произвольной геометрии и сложности. Расширяемость обеспечивается созданной моделью представления параметров фигуры и форматом хранения этих параметров. В качестве формата хранения параметров фигуры выбран формат сохранения структурированых данных - Json.
Формат данных оказал существенное влияние на выбор СУБД для их хранения. MongoDB - документориентированная NoSQL СУБД, была выбрана для этой цели, так как позволяет удобно хранить данные любой структурной сложности и размера. MongoDB - серверная СУБД, поэтому в приложениии реализован доступ к удаленной демонстрационной Базе Данных, расположенной на VPS.
Так как при написании приложения использовалась система WPF,то этот выбор обусловил, при кодировании интерфейса пользователя, примененение паттерна программирования MVVM(Model-View-ViewModel) в тех местах, где это было целесообразно.
При оформлении кнопочного интерфейса были ипользованы иконки, переработанные из стандартных иконок или собственного дизайна.
При решении основной задачи - Разбиение Полигонов - чтобы "не изобретать велосипед", была изучена история решений этой задачи. Цепочка решений, которую мне удалось проследить, получилась примерно такая:
- Алгоритм Вейлера-Азертона(Уайлера-Атертона)(1977г) - только для многоугольников, неимеюших самопересечений.
- Алгоритм Ватти(1992г) - решает все варианты булевых операций(с любыми видами полигонов), но очень громоздкий(более 5000строк кода на С++).
- Алгоритм Гриннера-Хормана(1998) - проще и элегантнее, чем алгоритм Ватти, но не обрабатывает многоугольники с вырождениями.
- Алгоритм Мартинеса-Руэды 1-я вариант(2008г) - работает быстрее, чем алгоритмы Ватти и Гриннера-Хормана и работает со всеми видами полигонов.
- Алгоритм Мартинеса-Руэды 2-й вариант(2013г) - более быстрый, чем 1-й вариант.
Мне не удалось найти формальное описание алгоритма, который является последним пунктом в истории решений задачи - на данный момент это коммерческая информация. Но попался в свободном доступе на GitHub демонстрационный код, реализующий данный алгоритм на языке node-JS(~2000 строк кода). Чтобы разобраться с алгоритмом и использовать последнее и самое лучшее решение изучаемой задачи, я решил перевести этот код с node-JS на С# и реализовать этот блок программы в виде dll-библиотеки, что и было мной сделано. Таким образом, была выполнена основная задача: приложение получило возможность выполнять булевые операции с полигонами и их коллекциями любой конфигурации как c выпуклыми, так и нет, как без самопересеченй, так и с ними. Единственное ограничение демо-версии алгоритма - не обрабатываются полигоны с отверстиями: вместо отверстий создаются отдельные полигоны.
Прежде чем приступить к работе с программой PolygonEditor, ознакомьтесь с разделом Справки: "Особенности Интерфейса".