ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrey Tarasevich                    2:5020/400     01 Nov 2001  03:49:53
 To : Alexander Topolskiy
 Subject : Re: Пересечение многоугольников
 -------------------------------------------------------------------------------- 
 

 Alexander Topolskiy wrote:
 
 > 
 >  DG> Имеется плоскость и два многоугольника в ней. Как _быстро_ определить
 >  DG> факт их пересечения?
 > Как быстро точно не знаю, но эта задача сводится к определению лежит ли данная
 > точка на данном многоугольнике.
 > Делается это так:
 > Строится еще одна точка вне многоугольника - можно взять точку например
 > A(655535,65535). И достроить до нее отрезок.
 > Теперь в цикле проверять пересечение этого отрезка со сторонам многоугольника.
 > Если число пересечений - четное, то точка не лежит на многоугольнике, если
 > нечетное - то лежит. Пересечения решаются через систему уравнений.
 
 Для определения принадлежности точки внутренности многоугольника никакая
 вторая точка не нужна. Из тестовой точки проводят горизонтальный луч,
 например, вправо и счиают пересечения с ним.
 
 Есть и другие способы.
 
 > Как довести этот алгоритм до твоей задачи думаю знаешь.
 
 А я вот что-то никак не врублюсь. И как же?
 
 Best regards,
 Андрей.
 --- ifmail v.2.15dev5
  * Origin: good enough (2:5020/400)
 
 

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

Тема:    Автор:    Дата:    Re: Пересечение многоугольников   Andrey Tarasevich   01 Nov 2001 03:49:53   Пересечение многоугольников   Alexander Topolskiy   03 Nov 2001 17:18:10