|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg Polubasoff 2:5020/400 19 May 2001 14:09:16
To : Oleg Tynianyi
Subject : Как определить направление обхода ?!?
--------------------------------------------------------------------------------
Привет, Oleg Tynianyi! Ты писал:
OT> Есть на плоскости набор точек (в виде массива), образующих замкнутый
OT> многоугольник.
OT> Hужно выяснить, следуют ли точки в массиве против часовой стрелки вокруг
OT> воображаемого центра
OT> многоугольника или по часовой, так как если ПО то нужно развернуть их
OT> ПРОТИВ.
OT> Так вот пытался решать эту проблему путем вычисления угла между прямыми,
OT> проведенными
OT> из центра к двум соседним точкам, накапливая последовательно эти углы и
OT> обращая внимание на
OT> знак результата, но как-то эта схема 100% надежности не дала.
OT> Подскажите способ решения проблемы ?!?!?
---------------------- Hачало цитаты ------------------------------------
From: Aleksey Smirnov
To: Viktor Lukovsky
Date: Saturday, November 13, 1999, 6:31:02 PM
Subject: clockwise or counterclockwise?
-------------------------------------------------------------------------
Hi, Viktor!
12 Nov 99 10:05, Viktor Lukovsky wrote to All:
VL> Есть последовательность координат вершин многоугольника.
VL> Последовательность описывает очередность рисования многоугольника,
VL> т.е. из первой координаты во вторую, из второй в третью, из последней
VL> в первую. Многоугольник не может быть самопересекающимся. Подскажите
VL> алгоритм, позволяющий определить, рисуется многоугольник по часовой
VL> стрелке или против часовой стрелки.
Hаходим самую левую точку. Если мы пришли в неё снизу или ушли из неё
наверх, то многоугольник обходится по часовой стрелке. Если мы пришли в неё
сверху или ушли вниз, то против. Реализация:
=== Cut ===
const MaxN = 100;
var buf : text;
x, y, x1, y1, px, py, n, i, minx : integer;
prev_min : boolean; { говорит, является ли предыдущая точка минимумом }
clockwise : boolean;
begin
assign(buf, '1113.in'); reset(buf);
readln(buf, n);
read(buf, px, py); minx := px; prev_min := true; x1 := px; y1 := py;
for i := 2 to n do
begin
read(buf, x, y);
if x <= minx then
begin
minx := x;
if py < y then clockwise := true else
if py > y then clockwise := false;
prev_min := true;
end else
if prev_min then
begin
if py < y then clockwise := true else
if py > y then clockwise := false;
prev_min := false;
end;
px := x; py := y;
end;
if x1 <= minx then
begin
if py < y1 then clockwise := true else
if py > y1 then clockwise := false;
end else
if prev_min then
begin
if py < y1 then clockwise := true else
if py > y1 then clockwise := false;
end;
if clockwise then writeln('clockwise') else
writeln('counterclockwise');
close(buf);
end.
=== Cut ===
Aleksey
----------------------- Конец цитаты ------------------------------------
--
Best regards,
Oleg mailto:pbas@spb.cityline.ru
--- ifmail v.2.15dev5
* Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
