|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexey Kruglov 2:5015/70.5 15 Jun 2003 23:19:49
To : Anatoly Saveliev
Subject : вопрос1
--------------------------------------------------------------------------------
Пятница 13 Июня 2003 07:01, Anatoly Saveliev wrote to Kirill Timofeev:
>> GK> У меня была подобная задача - вхождение точки в выпуклый
>> GK> многоугольник. Тонкостей не томню, но суть способа такова - из
>> GK> точки
>> 1. Если луч пересекает вершину к счетчику прибавлять число два.
AS> ответ неверный - достаточно обходить контур, и на одном конце
AS> проверять <, а на другом <=. Работает для всех фигур, в том числе
AS> невыпуклых.
Оба ответа неверные. Примеры придумайте сами.
Hадо учитывать пересечения с верхним концом ребра, и не учитывать пересечения с
нижним концом. Горизонтальные рёбра не учитываем. Луч горизонтальный.
>> Луч рекомендуется выпускать горизонтальный, так как тогда формулки
>> попроще будут - и нагрузка на проц уменьшится.
AS> никакой разницы в формулах, очевидно, быть не может, (достаточно
AS> мысленно переставить в них X и Y местами), но для человека понятнее
Может быть, он имел в виду, что будет проще, чем для наклонного луча.
>> Сейчас не помню были ли ещё какие-нибудь условия, а придумать
>> пример не
>> могу,
>> когда это не пройдет. :(
AS> И не нужно вспоминать - пройдет всегда (см. Graphic Jem).
Hе знаю, что это такое, но либо у них ошибка, либо ты их неправильно понял. Ещё
полезно уметь самому доказывать алгоритмы.
nOkA. Alexey.
--- GoldED+/W32 1.1.5-021109
* Origin: 6DFA 1186 7576 DE60 6CCB EB39 AD81 1733 EEBB 970A (2:5015/70.5)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
