По часовой стрелке

← →
Dib@zol © (2007-07-07 17:36) [0]

Дан невыпуклый многоугольник. Его вершины записаны в массиве последовательно. Как определить направление векторов (текущая вершина - начало, след. - конец), образующих контур, те. по часовой стрелке или против?

← →
@!!ex © (2007-07-07 18:49) [1]

По стандарту - по часовой.

← →
Однокамушкин (2007-07-07 19:03) [2]

Представьте спичку, которая движется по сторонам многоугольника так, что спичка всегда параллельна той стороне, на которой находится её конец... Каждый раз, когда спичка достигает вершины, она поворачивается на угол, равный внешнему углу между сторонами... если спичка движется против часовой стрелки, то при полном обходе многоугольника она повернётся на угол -2*Pi, если против часовой, то на +2*Pi...

Дальше всё просто: проходите по своему массиву, для каждой стороны с помощью ArcTan2 вычисляете угол, который она образует с осью X, разность углов текущей и следующей сторон даёт угол поворота спички на соответствующем угле... суммируете все эти углы и сравниваете с +/-2*Pi... с учётом погрешности, конечно...

Есть другой способ - берёте любую точку O внутри многоугольника и проводите из неё луч в произвольном направлении... Так как многоугольник невыпуклый, этот луч может пересечь контур многоугольника несколько раз... берём самую удалённую от начала луча точку пересечения этого луча с контуром... Если оказалось, что эта точка совпадает с вершиной многоугольника, нам не повезло, надо выбирать другое направление для луча... В противном случае пусть начало стороны, которой принадлежит эта точка, обозначается A, конец - B... Если угол, который образует вектор OA с осью X, больше угла, который образует OB (с ычётом направлений углов), обходи идёт по часовой стрелке, если меньше - против...

← →
Dib@zol © (2007-07-07 19:15) [3]

> По стандарту - по часовой.

Харрошый телепатор :))) Но попадаюцца и шрифты в которых некоторые буквы непрально прописаны.

← →
Dib@zol © (2007-07-07 19:16) [4]

> Однокамушкин (07.07.07 19:03) [2]

Блн в натуре пашет!!!!!!! Гарамадный сенксь! ЗЫЖ Это в каком классе проходят?

← →
Однокамушкин (2007-07-07 19:39) [5]

> Dib@zol © (07.07.07 19:16) [4]
> Это в каком классе проходят?

В какой-то книге прочитал, уже не помню, в какой...

← →
Dib@zol © (2007-07-07 21:14) [6]

БЛН!! ЁМАЁНХ!!!!! теперь он все многоугольники определяет как против часовой!!! Однокамушкин, твой алгоритм не фурычетъ... :(
Вот смотри, походу я нашёл в нем ошибку:

http://webfile.ru/1462586 (gif 2 кб)

← →
Однокамушкин (2007-07-08 08:15) [7]

> Dib@zol © (07.07.07 21:14) [6]
> БЛН!! ЁМАЁНХ!!!!! теперь он все многоугольники определяет
> как против часовой!!! Однокамушкин, твой алгоритм не фурычетъ.
> .. :(
> Вот смотри, походу я нашёл в нем ошибку:

Всё там работает, только, во-первых, на рисунке у вас ошибка, потому что BС^oX равен -135, а не 135, а во-вторых, углы, на которые поворачивается спичка, надо приводить в диапазон -180..180... Например, у вас на вершине B спичка поворачивается на BC^oX-AB^oX=-135-135=-270, так вот, тут надо к итоговой сумме прибавлять не -270, а +90, если делать так, для вашей фигуры получается правильное значение 360...

Угу. Смысел понятен. Надо значт сравниватьY-коорд. начала с координатой конца. Если она больше - угол > 0, а если меньше - соотсно < 0. Ща алгоритм доделаю - отпишусь как работает :)

Уф. Воттерь сё пучком! Для тестирования предлагается архив:
http://webfile.ru/1462861
(в нем прога, шрифт и ИНИ файл, шрифт надо установить себе). Для сравнения пользуйте прогу с http://delphimaster.net/view/9-1183718609/

По часовой стрелке Найти похожие ветки