![]() |
|
Принадлежность точки неправильному многоугольнику11.03.2015, 13:01. Показов 1589. Ответов 6
Метки нет Все метки)
(
Определяется область путём задания координат точек (количество точек может быть произвольным). Как определить принадлежит ли точка этой области? Область (многоугольник) может быть как выпуклая, так и нет. Интересует общий способ. Наведите на мысль. Спасибо.
0
|
11.03.2015, 13:01 | |
Ответы с готовыми решениями:
6
Напишите алгоритм, определяющий принадлежность точки выпуклому многоугольнику из N точек Разработать программу, которая решает задачу принадлежности точки многоугольнику с помощью метода "Учет числа оборотов" Принадлежность точки плоскости (ХУ). |
Диссидент
![]() ![]() 27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
11.03.2015, 13:43 | |
![]() Решение
Для выпуклой фигуры все просто... Для не выпуклой - как-то разбить на выпуклые и анализировать для них...
Добавлено через 3 минуты Для выпуклой делается так. Пишется уравнение каждой стороны в виде Ax+By+C=0 И вот точка должна давать при подстановке ее координат в уравнение тот же знак, что и одна из вершин (других, не на этой стороне) Добавлено через 18 минут Критерий выпуклости - для уравнения любой стороны все остальные вершины лежат от нее по одну сторону (дают одинаковый знак). Это подсказывает алгоритм разбиения фигуры на выпуклые. Если для одной сторон это не так (на рисунке 5-6) находим ее пересечение с ближайшей стороной (2-3) и получаем разбиение на 2 части. Для каждой из частей снова применяем критерий выпуклости, пока все части не станут "хорошими"
1
|
![]() |
|
11.03.2015, 14:52 [ТС] | |
Принцип ясен, спасибо.
Не по теме: VSI, я за того, который у Диккенса.
0
|
![]() |
|
11.03.2015, 17:30 | |
![]() Решение
Вычисляем сумму ориентированных углов 1X2 2X3 ... NX1. Если получилось 2пи, значит точка внутри, если 0 - значит вне. Если многоугольник с самопересечениями, то возможны другие варианты. Но в таких случаях вы должны определиться, что значит точка лежит внутри.
1
|
Диссидент
![]() ![]() 27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
11.03.2015, 18:58 | |
Да, ваш метод теоретически очень хорош. Одно НО. Мы тут попадаем в зависимость от причуд машинной арифметики.
![]() Добавлено через 44 минуты Впрочем, скорее всего, мои опасения напрасны. Для внутренней и внешней точек сумма углов будет резко отличаться. И достаточно для сравнения с 2пи взять небольшой эпсилон ("машинный ноль")
0
|
![]() |
|
12.03.2015, 00:44 | |
![]() Решение
Минус 2пи тоже может быть, если точки в многоугольнике перечислены по часовой стрелке.
https://ru.wikipedia.org/wiki/... 0%BE%D0%B9
1
|
12.03.2015, 00:44 | ||||||
Помогаю со студенческими работами здесь
7
Принадлежность точки отрезку
Определить принадлежность точки дуге
Искать еще темы с ответами Или воспользуйтесь поиском по форуму:
|
|
Опции темы | |
|
Новые блоги и статьи
![]() |
||||
std::vector в C++: от основ к оптимизации производительности
NullReferenced 06.04.2025
Для многих программистов знакомство с std::vector происходит на ранних этапах изучения языка, но между базовым пониманием и подлинным мастерством лежит огромная дистанция. Контейнер std::vector. . .
|
Реляционная модель и правила Кодда: фундамент современных баз данных
Codd 05.04.2025
Конец 1960-х — начало 1970-х годов был периодом глубоких трансформаций в области хранения и обработки данных. На фоне растущих потребностей бизнеса и правительственных структур существовавшие на тот. . .
|
Асинхронные операции в Django с Celery
py-thonny 05.04.2025
Разработчики Django часто сталкиваются с проблемой, когда пользователь нажимает кнопку отправки формы и. . . ждёт. Секунды растягиваются в минуты, терпение иссякает, а интерфейс приложения замирает. . . .
|
Использование кэшей CPU: Максимальная производительность в Go
golander 05.04.2025
Разработчикам хорошо известно, что эффективность кода зависит не только от алгоритмов и структур данных, но и от того, насколько удачно программа взаимодействует с железом. Среди множества факторов,. . .
|
Создаем Telegram бот на TypeScript с grammY
run.dev 05.04.2025
Одна из его самых сильных сторон Telegram — это интеграция ботов прямо в экосистему приложения. В отличие от многих других платформ, он предоставляет разработчикам мощный API, позволяющий создавать. . .
|
Паттерны распределённых транзакций в Event-Driven микросервисах
ArchitectMsa 05.04.2025
Современные программные системы всё чаще проектируются как совокупность взаимодействующих микросервисов. И хотя такой подход даёт множество преимуществ — масштабируемость, гибкость, устойчивость к. . .
|
Работа с объемным DOM в javascript
Htext 04.04.2025
Сегодня прочитал статью тут о расходах памяти в JS, ее утечках и т. п. И вот что вспомнил из своей недавней практики. Может, кому пригодится. Хотя, в той статье об этом тоже есть.
Дело в том, что я. . .
|
Оптимизация производительности Node.js с помощью кластеризации
run.dev 04.04.2025
Масштабирование приложений для обработки тысяч и миллионов запросов — обыденная задача для многих команд. Node. js, благодаря своей асинхронной событийно-ориентированной архитектуре, стал популярной. . .
|
Управление зависимостями в Python с Poetry
py-thonny 04.04.2025
Стандартный инструмент для установки пакетов в Python - pip - прекрасно справляется с базовыми сценариями: установил пакет командой pip install и используешь его. Но что произойдёт, когда разные. . .
|
Мониторинг с Prometheus в PHP
Jason-Webb 04.04.2025
Prometheus выделяется среди других систем мониторинга своим подходом к сбору и хранению метрик. В отличие от New Relic, который использует агентный подход и отправляет данные во внешнее хранилище,. . .
|