|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Tarasevich 2:5020/400 27 Apr 2002 06:09:31
To : Andrey Tarasevich
Subject : Re: Hа: Писал yже кто-то, но пpопyстил
--------------------------------------------------------------------------------
Andrey Tarasevich wrote:
> ...
> > > Пpинадлежит ли точка замкнyтомy многоyгольникy?
> > > Оный тоже задан по вектоpам и обязательно замкнyт.
> > > Подскажите, плз.
> >
> > Я б еще предложил 3-й, часто используемый способ:
> > 1. Вычисляется площадь заданого замкнутого многоугольника.
> > 2. Вычисляются площади всех треугольников, которые образуются
> > заданой точкой и вершинами многоугольника: с вершиной 1 и 2,
> > с вершиной 2 и 3, с вершиной 3 и 4 и т. д. Затем все площади
> > треугольников суммируются.
> > Если сумма площадей треугольников больше площади
> > многоугольника - точка вне многоугольника, иначе она либо внутри,
> > либо на одной из сторон.
> > ...
>
> Такой алгоритм будет работать только для выпуклого многоугольника. В
> условии же задачи не сказано, что многоугольник выпуклый.
> ...
Можно, конечно, вычислять и суммировать _ориентированные_ (знаковые)
площади треугольников. Тогда и такой алгоритм будет работать.
Best regards,
Андрей.
--- ifmail v.2.15dev5
* Origin: good enough (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
