Условие: Номер 3

Задача 3. 1. Выпуклый многоугольник задается координатами вершин при его обходе по часовой или против часовой стрелки. Контур многоугольника не имеет самопересечений. Определить направление обхода. 2. Выполнить то же самое, но только в случае невыпуклого многоугольника.

  Решение задачи: Номер 3

Решение задачи 3. Найдем какую-нибудь внутреннюю точку A(x,y) выпуклого многоугольника, например, центр масс трех последовательных точек на контуре: A(x,y)=((x1+x2+x3)/3;(y1+y2+y3)/3). На контуре выберем произвольно две последовательные вершины L1 и L2 и вычислим углы, которые образуют отрезки (A,L1) и (A,L2) с осью OX. Если первый угол меньше второго, то обход против часовой стрелки, иначе - по часовой. Для вычисления углов можно использовать функцию arctan(x) в Pascal. Рассмотрим чуть другую задачу: Даны 2 точки A(x1,y1) и B(x2,y2). Определить, какой из отрезков,OA или OB, образует больший угол с осью OX. (Предыдущая задача очевидным образом сводится к этой задаче 1). Если в условии задачи многоугольник невыпуклый, то можно предложить следующий способ решения: находим точку с максимальной абсциссой, и, идя вдоль контура, смотрим: если первое невертикальное ребро отклоняется против часовой стрелки, то это обход против часовой стрелки, иначе - нет.

Назад