ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Yurij Zabelyshynskij                 2:5020/400     22 Oct 2001  17:56:38
 To : Oleg Polubasoff
 Subject : Re: 2 Задачи по геометpии и соpтиpовка
 -------------------------------------------------------------------------------- 
 

 Hi, Oleg.
 Oleg Polubasoff wrote
 
 OP>     Hе хотелось бы, чтобы такой ответ попал в FAQ
 
 Рискую навлечь гнев модератора, но в этой эхе я видел FAQ только по
 мягким алгоритмам. А где же остальное?
 
 IK>>  Для определения принадлежности точки
 IK>>     треугольнику используется следующий алгоритм:
 IK>>     вся плоскость делится прямой, содержащей
 IK>>     сторону треугольника, на две полуплоскости.
 IK>>      Далее смотрим, если наша точка и
 IK>>     противоположная этой стороне вершина треугольника
 IK>>     лежат в разных полуплоскостях, то точка не
 IK>>     принадлежит треугольнику.
 IK>>  Такую проверку надо провести для всех 3-х сторон !!!!
 
 OP> /*  Если направление обхода треугольника abc - по часовой стрелке,
 OP> то точка p принадлежит внутренности треугольника abc тогда и
 
 только
 
 OP> тогда, когда направления обхода треугольников abp, bcp и cap тоже
 
 по
 
 OP> часовой стрелке.
 OP>     Если же направление обхода треугольника abc - против часовой
 OP> стрелки, то точка p принадлежит внутренности треугольника abc
 OP> тогда и только тогда,
 OP> когда направления обхода треугольников abp, bcp и cap тоже против
 OP> часовой стрелки.
 OP>     Такой подход годится и для любого _выпуклого_ многоугольника.
 OP> Для невыпуклых есть более другие методы. Они много раз здесь
 OP> обсуждались.
 
 Так это практически одно и то же, потому что для подсчета площади и
 определения полуплоскости надо использовать одни и те же формулы. И
 все равно лучше проверять четность пересечений с горизонтальным лучом.
 
 WBR, Yura.
 
 --- ifmail v.2.15dev5
  * Origin: Demos online service (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    2 Задачи по геометpии и соpтиpовка   Arsen Lyapin   20 Oct 2001 20:16:01   2 Задачи по геометpии и соpтиpовка   Stanislav Shwartsman   20 Oct 2001 21:53:23   Re: 2 Задачи по геометpии и соpтиpовка   Yurij Zabelyshynskij   21 Oct 2001 00:57:28   2 Задачи по геометpии и соpтиpовка   Egorov Pavel   22 Oct 2001 00:25:55   Re: 2 Задачи по геометpии и соpтиpовка   Yurij Zabelyshynskij   22 Oct 2001 01:59:05   Re: 2 Задачи по геометpии и соpтиpовка   Arsen Lyapin   23 Oct 2001 21:13:37   2 Задачи по геометpии и соpтиpовка   Egorov Pavel   26 Oct 2001 00:09:32   Re: 2 Задачи по геометpии и соpтиpовка   Arsen Lyapin   26 Oct 2001 18:29:48   Re: 2 Задачи по геометpии и соpтиpовка   Arsen Lyapin   23 Oct 2001 20:44:03   Re: 2 Задачи по геометpии и соpтиpовка   Artyom Petrov   21 Oct 2001 21:39:36   2 Задачи по геометpии и соpтиpовка   Ilia Kantor   22 Oct 2001 00:27:36   2 Задачи по геометpии и соpтиpовка   Oleg Polubasoff   22 Oct 2001 06:52:49   Re: 2 Задачи по геометpии и соpтиpовка   Yurij Zabelyshynskij   22 Oct 2001 17:56:38   S0rting Faq 1/3   Ilia Kantor   22 Oct 2001 21:50:12   2 Задачи по геометpии и соpтиpовка   Oleg Polubasoff   25 Oct 2001 15:29:07   Re: 2 Задачи по геометpии и соpтиpовка   Yurij Zabelyshynskij   28 Oct 2001 00:08:57   2 Задачи по геометpии и соpтиpовка   Oleg Polubasoff   29 Oct 2001 04:34:37   Re: 2 Задачи по геометpии и соpтиpовка   Yurij Zabelyshynskij   30 Oct 2001 00:35:36   2 Задачи по геометpии и соpтиpовка   Oleg Polubasoff   08 Nov 2001 21:01:56   Re: 2 Задачи по геометpии и соpтиpовка   Yurij Zabelyshynskij   08 Nov 2001 21:37:47   Re: 2 Задачи по геометpии и соpтиpовка   Arsen Lyapin   30 Oct 2001 00:18:17   Re: 2 Задачи по геометpии и соpтиpовка   Arsen Lyapin   23 Oct 2001 21:00:43   Re: 2 Задачи по геометpии и соpтиpовка   Artyom Petrov   21 Oct 2001 22:02:09   Re: 2 Задачи по геометpии и соpтиpовка   Arsen Lyapin   23 Oct 2001 22:02:53   Re: 2 Задачи по геометpии и соpтиpовка   Andrew Ezhguroff   24 Oct 2001 03:45:54   2 Задачи по геометpии и соpтиpовка   Andrew Simontsev   24 Oct 2001 14:05:13   Re: 2 Задачи по геометpии и соpтиpовка   Andrew Ezhguroff   25 Oct 2001 01:40:35   2 Задачи по геометpии и соpтиpовка   Egorov Pavel   26 Oct 2001 00:18:45   2 Задачи по геометpии и соpтиpовка   Andrew Simontsev   26 Oct 2001 13:47:07   2 Задачи по геометpии и соpтиpовка   Egorov Pavel   29 Oct 2001 00:45:12   Re: 2 Задачи по геометpии и соpтиpовка   Arsen Lyapin   30 Oct 2001 00:15:57   2 Задачи по геометpии и соpтиpовка   Andrew Simontsev   30 Oct 2001 13:57:59   2 Задачи по геометpии и соpтиpовка   Andrew Simontsev   30 Oct 2001 13:38:40   2 Задачи по геометpии и соpтиpовка   Andrew Simontsev   24 Oct 2001 14:01:08   Re^2: 2 Задачи по геометpии и соpтиpовка   Artyom Petrov   24 Oct 2001 13:30:53