intro.tex

\section{Введение}
\label{}

В работе описывается решение задачи преобразования многосвязных геометрических областей в односвязные в контексте кодирования географических карт. Полученный алгоритм работает в общем случае и может использоваться в других предметных областях.

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

По условию поставленной задачи имеются две геоинформационные системы, которые используют различные представления данных. Первая поддерживает в составе карты объекты любого размера и топологии. Вторая поддерживает только односвязные, а также имеет ограничение на количество точек в одном объекте. Понятно, что первая система автоматически поймет данные второй, но обратное неверно. Задача состоит в том, чтобы разработать алгоритм для преобразования данных из первой системы во вторую. Также на него накладываются дополнительные условия – создавать новые вершины запрещено, а вносимые разрезы должны быть минимальны.