ru.algorithms

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

 Alexander Topolskiy wrote:
 
 > ...
 >  AT> Для определения принадлежности точки внутренности многоугольника
 >  AT> никакая вторая точка не нужна. Из тестовой точки проводят
 >  AT> горизонтальный луч, например, вправо и счиают пересечения с ним.
 > ...
 >  AT> Есть и другие способы.
 > Какие?
 
 Пусть n-угольник задан последовательностью вершин (v(0), v(1), ...,
 v(n-1)), а t - наша точка. Суммируем величины ориентированных углов
 v(0)-t-v(1), v(1)-t-v(2), v(2)-t-v(3), ..., v(n-2)-t-v(n-1), (v(n-1), t,
 v(0)). (Хм... как их там правильно зовут? "Ориентированные"? В общем,
 если абсолютное значение угла умножить на сигнум вектрного произведения
 сторон, то получим как раз то, что я имею в виду). Если точка t снаружи
 - сумма будет равна 0. Если же точка внутри, то сумма будет кратна 2 *
 PI.
 
 >  >> Как довести этот алгоритм до твоей задачи думаю знаешь.
 >  AT> А я вот что-то никак не врублюсь. И как же?
 > Ты прикалываешься или как? Ладно так и быть - сравниваем принадлежность не
 > одной точки, а всех точек многоульника B по отношению к многоугольнику A- если
 > хотя бы одна принадлежит - то пересекаются.
 > ...
 
 Ы?! Даже если предположить, что у тебя есть возможность перебрать "все
 точки многоугольника" (например, если задача машинной графики решается в
 пространстве изображения), практическая ценность такого алгоритма все
 равно будет нулевой.
 
 Best regards,
 Андрей.
 --- ifmail v.2.15dev5
  * Origin: good enough (2:5020/400)
 
 

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