Процедура обработки точки, определяющая положение точки в области

Общие сведения

Наименование программы: PrgTopology.exe

Программное обеспечение: Windows 7

Среда разработки: Delphi 7

Язык программирования: Object Pascal

Функциональное назначение

Программа «PrgTopology» предназначена для определения топологического отношения двух плоских фигур, заданных координатами точек поворота.

Описание логической структуры

Метод

Задача: Определить топологическое расположение (наложение, примыкание, вложенность и не примыкают) двух плоских фигур по их координатам.

Как мы видим на картинке, наши многоугольники накладываются друг на друга. Для того, что определить факт наложения надо, чтобы хотя бы одно ребро пересекало другое. Но если ребра не пересекаются, как же определить положение фигур? На помощь нам придут вершины данных фигур. Рассмотрим фигуру №1 и вершины фигуры №2. Вершины могут лежать в области фигуры, на ребре и не принадлежать области фигуры. Если же все точки не принадлежат области фигуры, нет пересечений ребер, то окончательный ответ дать невозможно, так как при таких обстоятельствах фигуры могут не примыкать или быть вложенными. Для этого используется двойная проверка, смысл которой заключается в последовательной проверки вершин одной фигуры относительно ребер другой, а потом наоборот. Далее результаты обрабатываются процедурами, первая дает окончательный ответ относительно отношения вершин ребер первого и второго случая, а вторая обрабатывает два результата, и выводит окончательный результат положения многоугольников.

Метод вроде бы прост, но возникает проблема, которая может разрушить его. Допустим, мы зададим координатами прямоугольник, две противолежащие стороны которого находятся перпендикулярно оси ОХ. Тогда уравнение прямой задать невозможно, так как x=const – это не функция, а линия. Тем самым человек, который захочет посмотреть положение двух прямоугольников, получит отказ в этом, так как коэффициент прямой k вычисляется по формуле

Следовательно, получается деление на ноль, так как x₁=x₀. На помощь приходят аффинные преобразования координат. Плюсом этих преобразований считается то, что положение прямых относительно друг друга не изменяются, т.е, если прямые пересекались до преобразований, то они будут пересекаться после, если были параллельные, то они остаются параллельные. Таких преобразований очень много, но в нашем методе понадобится только формула, которая делает скос фигуры.

Формула для получения скоса:

После такого преобразования координат расчет положение прямоугольников и многоугольников с ребром, которое перпендикулярно оси ОХ возможно. Конечно, некоторые прямые после преобразования могут стать перпендикулярно ОХ, но коэффициент подбирается так, чтобы такие прямые не встречались.

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

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

Примыкание - есть точки на ребрах, не пересекаются ребра, нет точек в области, есть точки, не лежащие в области.

Вложена - нет точек, которые находятся не в области, есть точки на ребрах или точки в области, не пересечения ребер.

Не примыкают – нет точек в области, на ребрах, отсутствуют пересечения ребер, есть точки, не лежащие в области.

Вторая процедура, которая определяет окончательный ответ топологического отношения двух фигур.

НАЛОЖЕНИЕ = НАЛОЖЕНИЕ или НАЛОЖЕНИЕ

ПРИМЫКАЕТ = ПРИМЫКАЕТ и ПРИМЫКАЕТ

ВЛОЖЕНА = (ВЛОЖЕНА или ВЛОЖЕНА) и (ПРИМЫКАЕТ или ПРИМЫКАЕТ или НЕ ПРИМЫКАЕТ или НЕ ПРИМЫКАЕТ)

НЕ ПРИМЫКАЕТ = НЕ ПРИМЫКАЕТ и НЕ ПРИМЫКАЕТ

Итог:

1. Преобразование координат с помощью аффинного преобразования

2. Проверка, есть ли ребра, которые пересекаются или накладываются

3. Нахождение положения точек одной фигуры относительно другой

4. Повторная проверка для точек первой фигуры относительно второй

5. По данным, полученным в пунктах 2-4, выносим вердикт для двух фигур

6. По данным, полученным в пункте 5, получаем конечный ответ

Блок-схема алгоритма[1]

Процедура создания прямых

Процедура обработки точки, определяющая положение точки в области

Процедура обработки точки, определяющая положение точки на ребре

Определение положения фигуры относительно другой

Процедура окончательного положения фигур

Основная процедура