|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Zapadinsky Anatoly \(ZAB\) 2:5020/400 22 Feb 2002 07:16:51
To : Alexander Khristianovsky
Subject : Re: Anton Drokin : Hаправление обхода
--------------------------------------------------------------------------------
Hello, Alexander!
You wrote to Anton Drokin on Thu, 21 Feb 2002 07:06:00 +0000 (UTC):
AK> "Anton Drokin" <Anton.Drokin@p16.f156.n464.z2.fidonet.org> wrote in
AK> message news:1014243411@p16.f156.n464.z2.FidoNet.ftn...
AD>> Многоугольник (возможно, невыпуклый) задан последовательностью
AD>> вершин:
AD>> a(1),a(2),...,a(n) a(1)=a(n)
AD>> a(i)=(x(i),y(i))
AD>> Hеобходимо определить направление обхода: по часовой стрелке или
AD>> против.
AK> Для выпуклого полигона определяется так:
AK> Берется любая грань (вектор) [pt1, pt2] . Берется любой вектор [pt1,
AK> ptN]
AK> (из первой вершины грани в любую другую). Если он получается
AK> поворотом [pt1, pt2] по часовой стрелке, то таким будет и
AK> направление обхода полигона.
AK> Любой невыпуклый полигон можно свести к выпуклому (т.н. "Convex
AK> Hull")
AK> Hаправление обхода при этом не изменяется. Ссылка на алгоритм:
AK> http://geometryalgorithms.com/Archive/algorithm_0109/algorithm_0109.
AK> htm
А какая сложность у этого сведения? Может лучше всё же найти самую крайнюю
(по какой либо координате) вершину и рассмотреть произведение векторов с
началом в этой вершине и концами в соседних, получится линейная...
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Anton Drokin : Hаправление обхода 