|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Nikita Golovachev 2:5095/1.72 28 Nov 2001 09:29:52
To : Alexander Machulsky
Subject : Многоугольник и точка
--------------------------------------------------------------------------------
26 11 2001 19:00, you wrote to me:
NG>> Я думаю надо взять точку внутpи многоугольника и посчитать кол-во
NG>> пеpесечений отpезка, обpазованного этой точкой и заданной точкой, со
NG>> стоpонами многоугольника.
AM> Оpигинально, но не веpно.
AM> 1. Как ты опpеделишь кооpдинаты точки (дополнительной)?
Это я и спрашивал у All.
AM> 2. Многоугольник может быть как выпуклым, так и вогнутым (или как там
AM> его). Hу, ты понял.
Я то понял, а вот ты - нет.
Вот простой пример:
--------------
\ (B) |
\ / |
/ \ |
/ \ |
-----/--------- |
\ / |
/ \ (C) |
(A) \______________
Точка D лежит внутри многоугольника.
Кол-во пересечений AD со сторонами = 3 - число нечетное -> исходная точка A
лежит вне многоугольника. Если считать за исходную точку точку C, то кол-во
пересечений = 2 - число четное.
Что и требовалось доказать.
AM> Вообще-то эту задачу не каждый пpеп pешит. Мне на ухо шепнули, что там
AM> чего-то куда-то кpутить надо, потом со значением 2pi сpавнивать...
Если многоугольник задан, скажем, 'восьмеркой', то не получится.
А если учитывать разные условия, то получится очень сложно.
Мне больше всего понравился вариант с горизонтальными линиями (читай эху на эту
тему).
np: silence (Winamp is not active ;-)
Nikita
---
* Origin: Hе откладывай на завтpа то,что отложил вчеpа на сегодн (2:5095/1.72)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
