|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Ezhguroff 2:5020/400 19 May 2001 06:29:56
To : Gleb Belyakov
Subject : Re: Точка внутри полигона.
--------------------------------------------------------------------------------
Привет! "Gleb Belyakov" <Gleb.Belyakov@f687.n5030.z2.fidonet.org> сообщил(а)
нам:
> Дан многоугольник заданый кооpдинатами вешин. О фоpме многоугольника и
> количестве веpшин заpание ничего не известно, кpоме того что его стоpоны
не
> пеpесекаются. Так вот, как максимально быстpо (с точки зpения
пpогpамиpования)
> найти любую точку внутpи этого многоугольника?
Максимально быстро - не знаю, но вариант такой:
1. Ищем 3 смежные вершины, A (предшествует B), B, C (следует за B), такие,
что B.y - абсолютный минимум (самая нижняя точка) и все три точки не лежат
на одной прямой.
2. Hаходим D - вторую снизу (после B) вершину, такую, что D.y<>B.y. D может
совпадать либо с A, либо с C. Т.е. для любой вершины Q: Q.y либо равно B.y,
либо больше D.y
3. Вычисляем точку E - средину отрезка [A, С]: E.x=(A.x+C.x)/2,
E.y=(A.y+C.y)/2
4. Проводим прямую (B, E) - медиану (если в терминах не ошибся) треугольника
ABC из вершины B к стороне AC: (x-E.x)/(y-E.y)=(B.x-E.x)/(B.y-E.y), т.е.
(2*x-(A.x+C.x))/(2*y-(A.y+C.y))=(2*B.x-(A.x+C.x))/(2*B.y-(A.y+C.y))
5. Вычисляем точку F, лежащую на прямой (B, E), такую, что F.y=(B.y+D.y)/2:
(2*F.x-(A.x+C.x))/((B.y+D.y)-(A.y+C.y))=(2*B.x-(A.x+C.x))/(2*B.y-(A.y+C.y)),
F.x=((A.x+C.x)+(B.y+D.y)*(2*B.x-(A.x+C.x))/(2*B.y-(A.y+C.y)))/2
Вроде бы точка F всегда лежит внутри многоугольника. Во всяком случае мне
контрпример придумать не удалось.
С уважением, Андрей.
--- ifmail v.2.15dev5
* Origin: COMSTAR Telecommunications (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
