-3
Каков наилучший алгоритм для решения точки в многоугольнике в конкурсах программирования?Точка в полигоном Алгоритм в программировании Конкурсы
A
ответ
0
, если у вас есть выпуклый многоугольник можно использовать следующим образом:
1
Стреляй луч (в произвольном направлении) от точки и проверьте, сколько раз он пересек края многоугольника, если он даже тогда точка находится за пределами многоугольника, иначе точка находится внутри многоугольника.
Если вам нужно сделать это для множества точек запроса, вы можете триангулировать многоугольник (фактически триангулировать как внутри, так и область между многоугольником, выпуклым, содержащим его), чтобы вы могли снимать лучи в O (log n)
Смежные вопросы
- 1. Точка соединения с полигоном
- 2. Конкурсы Netflix
- 3. Точка в многоугольнике - ошибочный алгоритм
- 4. Как эта точка геометрии не пересекается с полигоном?
- 5. Конкурсы на программирование на С ++
- 6. Flex полигоном в реальном времени
- 7. Mutability в функциональном программировании
- 8. Как этот алгоритм может быть выражен в программировании для расчета?
- 9. Каков алгоритм обработки нескольких клиентов в программировании сокетов?
- 10. Векторизация в функциональном программировании
- 11. Самая изолированная точка на карте 2d - алгоритм
- 12. Алгоритм Средняя точка между различными GPoint
- 13. Как отрезать кирпич полигоном?
- 14. .. (точка точка) в URL-
- 15. Обнаружение столкновений многоугольника с полигоном
- 16. Проблемы с полигоном SVG
- 17. Самая изолированная точка на карте 2d - алгоритм
- 18. Конкурсы алгоритмов - Неизвестное количество тестовых случаев
- 19. Все конкурсы на Haskell онлайн или проблемы?
- 20. Как скопировать WorldMap с полигоном в R?
- 21. Различия между полигоном и полилинией в SVG
- 22. обрезание UIImage в соответствии с полигоном
- 23. Проблема с полигоном в книге PPP Stroustrup
- 24. Пересечение точки с полигоном в рубине
- 25. C# Установить прозрачность в область, определенную полигоном
- 26. bzero в программировании сокетов
- 27. Остановить пользователей, вступающих в мои конкурсы более одного раза
- 28. Метод бисекции в программировании c
- 29. Как превратить алгоритм Прима в алгоритм Крускаля?
- 30. Точка аргументов в основной функции
Существуют оптимизированные алгоритмы для большинства общих фигур (а именно треугольники и четырехугольники), но простой подход изложена в Википедии, которая должна работать для любого произвольного многоугольника, если вы правильно выбрали луч: http: // ru. wikipedia.org/wiki/Point_in_polygon – Blender
-1 Вы хотите ввести конкурс вычислительной геометрии, но попросите сообщество решить его для вас !? – cmannett85
Как вы пришли к такому выводу cmannett85 ?? !! – user1284064