|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Roman Ilyin 2:5020/400 28 Nov 2001 22:34:23
To : Nikita Golovachev
Subject : Re: Многоугольник и точка
--------------------------------------------------------------------------------
Доброе время суток, Nikita.
AM>>> Вообще-то эту задачу не каждый пpеп pешит. Мне на ухо шепнули, что
там
AM>>> чего-то куда-то кpутить надо, потом со значением 2pi сpавнивать...
RI>> Обходишь вектором из точки по контуру.
RI>> Если внутри, то вектор обойдет полный круг 2pi, если вне - то
RI>> неполный.
RI>> Хотя для сильно извратных частных случаев не работает.
NG> Hапример, как быть с самопересекающимися многоугольниками -
NG> 'восьмерка', 'звезда'?
NG> Если точка внутри многоугольника, то для 'восьмерки' вектор обойдет
NG> неполный круг - второе 'ухо' 'восьмерки' будет мешать.
NG> Для звезды вектор обойдет несколько кругов (можно проверить
NG> нарисовав ее неотрывая руки с самопересечением и обходя точки в
NG> порядке рисования).
Это и есть те самые частные случаи.
Их рассматриваешь как несколько (или один) многоугольников без
самопересечений. Оба твоих примера к такому виду приводятся
добавлением точек.
Я не говорил, что это удачный способ, просто пояснил в чем заключается
способ, про который человеку говорили.
А нафига тебе многоугольники с самопересечениями?
====================================================
Удачи!
Роман Ильин grisper@voronezh.net
--- ifmail v.2.15dev5
* Origin: Информсвязь-Черноземье (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
