Принадлежность точки неправильному многоугольнику

@UriahHeep · Регистрация: 24.09.2012

Студворк — интернет-сервис помощи студентам

Определяется область путём задания координат точек (количество точек может быть произвольным). Как определить принадлежит ли точка этой области? Область (многоугольник) может быть как выпуклая, так и нет. Интересует общий способ. Наведите на мысль. Спасибо.

Принадлежность точки неправильному многоугольнику

Байт · 11.03.2015, 13:43

Для выпуклой фигуры все просто... Для не выпуклой - как-то разбить на выпуклые и анализировать для них...

Добавлено через 3 минуты
Для выпуклой делается так. Пишется уравнение каждой стороны в виде Ax+By+C=0
И вот точка должна давать при подстановке ее координат в уравнение тот же знак, что и одна из вершин (других, не на этой стороне)

Добавлено через 18 минут
Критерий выпуклости - для уравнения любой стороны все остальные вершины лежат от нее по одну сторону (дают одинаковый знак).
Это подсказывает алгоритм разбиения фигуры на выпуклые. Если для одной сторон это не так (на рисунке 5-6) находим ее пересечение с ближайшей стороной (2-3) и получаем разбиение на 2 части. Для каждой из частей снова применяем критерий выпуклости, пока все части не станут "хорошими"

@VSI · 11.03.2015, 14:18

UriahHeep, как иллюстрация - программа на Mathcad'е...

Не по теме:

А Вы кто - Мик Бокс, Дэвид Байрон, Кен Хенсли, Гэри Тэйн или Ли Керслэйк? Или за всех сразу? :)

@UriahHeep · 11.03.2015, 14:52 **[ТС]**

Принцип ясен, спасибо.

Не по теме:

VSI, я за того, который у Диккенса.

@palva · 11.03.2015, 17:30

Вычисляем сумму ориентированных углов 1X2 2X3 ... NX1. Если получилось 2пи, значит точка внутри, если 0 - значит вне. Если многоугольник с самопересечениями, то возможны другие варианты. Но в таких случаях вы должны определиться, что значит точка лежит внутри.

Байт · 11.03.2015, 18:58

Сообщение от palva

Если получилось 2пи

Да, ваш метод теоретически очень хорош. Одно НО. Мы тут попадаем в зависимость от причуд машинной арифметики.

Добавлено через 44 минуты
Впрочем, скорее всего, мои опасения напрасны. Для внутренней и внешней точек сумма углов будет резко отличаться. И достаточно для сравнения с 2пи взять небольшой эпсилон ("машинный ноль")

@palva · 12.03.2015, 00:44

Минус 2пи тоже может быть, если точки в многоугольнике перечислены по часовой стрелке.
https://ru.wikipedia.org/wiki/... 0%BE%D0%B9

Новые блоги и статьи Все статьи Все блоги /
Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .
Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .

Принадлежность точки неправильному многоугольнику

Решение

Решение

Решение

@UriahHeep 224 / 219 / 77 Регистрация: 24.09.2012 Сообщений: 511 Записей в блоге: 2

	Принадлежность точки неправильному многоугольнику 11.03.2015, 13:01. Показов 1691. Ответов 6 Метки нет (Все метки) Определяется область путём задания координат точек (количество точек может быть произвольным). Как определить принадлежит ли точка этой области? Область (многоугольник) может быть как выпуклая, так и нет. Интересует общий способ. Наведите на мысль. Спасибо. 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	11.03.2015, 13:43
	Сообщение было отмечено UriahHeep как решение Решение Для выпуклой фигуры все просто... Для не выпуклой - как-то разбить на выпуклые и анализировать для них... Добавлено через 3 минуты Для выпуклой делается так. Пишется уравнение каждой стороны в виде Ax+By+C=0 И вот точка должна давать при подстановке ее координат в уравнение тот же знак, что и одна из вершин (других, не на этой стороне) Добавлено через 18 минут Критерий выпуклости - для уравнения любой стороны все остальные вершины лежат от нее по одну сторону (дают одинаковый знак). Это подсказывает алгоритм разбиения фигуры на выпуклые. Если для одной сторон это не так (на рисунке 5-6) находим ее пересечение с ближайшей стороной (2-3) и получаем разбиение на 2 части. Для каждой из частей снова применяем критерий выпуклости, пока все части не станут "хорошими" 1

@VSI Модератор $Эксперт по математике/физике$ 5293 / 4075 / 1392 Регистрация: 30.07.2012 Сообщений: 12,499
	11.03.2015, 14:18
	UriahHeep, как иллюстрация - программа на Mathcad'е... Не по теме: А Вы кто - Мик Бокс, Дэвид Байрон, Кен Хенсли, Гэри Тэйн или Ли Керслэйк? Или за всех сразу? :) Миниатюры 1

@UriahHeep 224 / 219 / 77 Регистрация: 24.09.2012 Сообщений: 511 Записей в блоге: 2
	11.03.2015, 14:52 [ТС]
	Принцип ясен, спасибо. Не по теме: VSI, я за того, который у Диккенса. 0

@palva 4278 / 2970 / 693 Регистрация: 08.06.2007 Сообщений: 9,930 Записей в блоге: 5
	11.03.2015, 17:30
	Сообщение было отмечено Байт как решение Решение Вычисляем сумму ориентированных углов 1X2 2X3 ... NX1. Если получилось 2пи, значит точка внутри, если 0 - значит вне. Если многоугольник с самопересечениями, то возможны другие варианты. Но в таких случаях вы должны определиться, что значит точка лежит внутри. 1

@palva 4278 / 2970 / 693 Регистрация: 08.06.2007 Сообщений: 9,930 Записей в блоге: 5
	12.03.2015, 00:44
	Сообщение было отмечено Байт как решение Решение Минус 2пи тоже может быть, если точки в многоугольнике перечислены по часовой стрелке. https://ru.wikipedia.org/wiki/... 0%BE%D0%B9 1