Где проведён отрезок: внутри или снаружи многоугольника

@Ryder95 · Регистрация: 24.10.2013

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

Здравствуйте!

Есть многоугольник, заданный последовательностью точек его контура, которые идут в порядке против часовой стрелки. Две любые точки контура соединяются отрезком. Как можно определить, где проведён отрезок: внутри многоугольника, снаружи или пересекает (проблему пересечения решил, но, в основном, это просто перебор всех линий контура с проведённой линией)?

Заранее благодарю

@Igor3D · 21.02.2016, 12:54

Сводится к базовой задаче "точка внутри/снаружи". Для этого часто используют odd/even - подсчет числа пересечений луча (напр по x) из точки. Классический код (с учетом проблем точности) был в джемсах. Дальше разгуглите

Добавлено через 10 минут
Наверное в данном случае проще найти все пересечения контура с прямой заданной отрезком. А дальше посчитать odd/even. Там правда есть одна бяка: прямая может пересекать точку(и) контура

@Ryder95 · 21.02.2016, 16:18 **[ТС]**

Простите, забыл уточнить. Точки всегда находятся на контуре, то есть это и есть точки, которые задают контур. И между ними проводится отрезок. Вот как бы узнать, как он находится относительно полигона?

@Igor3D · 21.02.2016, 16:46

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

Точки всегда находятся на контуре, то есть это и есть точки, которые задают контур. И между ними проводится отрезок. Вот как бы узнать, как он находится относительно полигона?

Тогда совсем другое дело.

Пусть есть 3 точки контура в порядке p0, p1, p2. И есть отрезок из точки p1 в pn. Тогда

C++
1
2
3
4
5
6
7
8
9
10
11
12
Vec3 v01 = (p1 - p0).normalized();
Vec3 v12 = (p2 - p1).normalized();
Vec3 v1n = (pn - p1).normalized();
 
// углы 2 напр-й относительно вектора v01, dot = скалярное произведение
float angle1 = acos(dot(v01, v12));
float angle2 = acos(dot(v01, v1n));
 
// уточняем знаки углов, cross = векторное произведение
// положительный угол против часовой
if (cross(v01, v12) < 0)) angle1 = -angle1;
if (cross(v01, v1n) < 0)) angle2 = -angle2;

Если (angle1 > angle2) значит снаружи, иначе внутри.

@Ryder95 · 23.02.2016, 01:19 **[ТС]**

Да, спасибо большое))) Конечно, чутка громоздко, да и хотелось бы избежать мат.функций, но всё же работает. Кстати, как мне кажется, взять арккосинус от скалярного произведения не получится, так как оно может быть много больше единицы. Скорее всего, верный вариант:

C++ (Qt)
1
2
float angle1 = acos(dot(v01, v12)/(len(v01)*len(v02));
float angle2 = acos(dot(v01, v1n)/(len(v01)*len(v1n)));

@Fulcrum_013 · 23.02.2016, 03:11

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

Вот как бы узнать, как он находится относительно полигона?

Есть тест на взаимное пересечение отрезков. Находишь уравнения как всех отрезков полигона так и отрезка с которым ищется пересечение. Если пересечение возможно то при подстановке концов первого отрезка в уравнение второго получаешь разные знаки. Если определил что возможно подставляешь концы второго в уравнение первого. Если знаки тоже разные то пересечение есть. Вот таким образом проверяешь отрезок на пересечение с каждым ребром многоугольника. Но таким способом определяется только наличие пересечений. Если пересечений нет то он либо полностью внутри либо полностью снаружи.
Для того чтобы определить где именно: Если многоугольник выпуклый, то просто необходимо выбрать при построении нормали так чтобы они все смотрели внутрь. если концы отрезка при подстановке в выпуклый многоугольник имеют все знаки + то отрезок полностью внутри. Если - то снаружи.
В общем случае - многоугольник не выпуклый - строится логическая формула контура, из пересечений и сумм отсекаемых ребрами полуплоскостей, и расчиитывается для точек отрезка. Дальше тоже самое - плюс внутри, минус - снаружи. Подобнее про построение контура - гугли на тему "метод R-функций". Для данной задачи опреаторы R-функций(которые в результате дают не просто факт вхождения а расстояние до ближайшей границы) можно упростить заменив булевыми операторами над знаком (имеется в виду + true - false, 0- в зависимости от того считается ли линия ребра входящей в многоугольник или нет)

@Ryder95 · 23.02.2016, 03:22 **[ТС]**

По поводу пересечений есть функция, уже написал. Про R-функции слышал и гуглил, но что-то это сложно довольно мне даётся, так что пока я их просто тихонечко читаю

Добавлено через 2 минуты
Да уж, проверка линии тогда будет намного проще)) и это будет одно из наиудобнейших решений. Надо только научится строить эти r-функции

@Fulcrum_013 · 23.02.2016, 03:43

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

Кстати, как мне кажется, взять арккосинус от скалярного произведения не получится, так как оно может быть много больше единицы. Скорее всего, верный вариант:

Правильно кажется. Потому что скалярное произведение равно произведению модулей векторов на косинус угла между ними. Для того чтобы выдрать из скалярного произведения само значение косинуса, надо его разделить на произведение модулей векторов (6 или 7 класс насколько помню). Ну или в исходе работать с нормализованными векторами (2 курс, оптимизация графических алгоритмов, насколько помню).

Добавлено через 8 минут

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

Про R-функции слышал и гуглил

По большому счету там ничего сложного. Насколько помню на программу построения уравнения области, которая могла состоять из любого количества вложенных контуров (ну типа вырез, а внути выреза еще область) ушло в свое время часа 2 в сонном состоянии (делалось на один из 6 дипломов сделанных за месяц). Давно это правда было,году в 2000-ом, код не сохранился. Но смысл примерно такой обходишь внешний контур по часовой, когда его конец попадает в положительную область предыдущего ребра просто домножаешь на него, когда в минусовую приплюсовываешь. потом точно так же следующий внутренний, только его формулу от результирующего уравнения минусуешь.

Добавлено через 6 минут

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

Надо только научится строить эти r-функции

По большому счету сами R-функции это типа функции-операторы, которые позволяют вычислить расстояние до границы области при комбинации двух областей +, -, * и унарный -. Для определения просто факта попадания в область (знака) * соответствует булевскому & над знаком аргументов, + булевскому |, унарный - булевскому !, а - соответсвенно |!

Добавлено через 6 минут

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

Надо только научится строить эти r-функции

Если многоугольник выпуклый то его логическая функция будет & всех его ребер. Невыпуклый - сумма нескольких выпуклых.

@Igor3D · 23.02.2016, 06:24

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

Скорее всего, верный вариант:
float angle1 = acos(dot(v01, v12)/(len(v01)*len(v02));
float angle2 = acos(dot(v01, v1n)/(len(v01)*len(v1n)));

Так у меня то же самое только выше (normalized)

Да, и без acos можно обойтись, т.к. косинус убывает монотонно. Тогда инвертировать <>

@ichs · 26.02.2016, 17:47

Ryder95
Эту задачу можно решить иначе без всяких функций.
Многоугольник разбивается на треугольники. И для
каждого треугольника проверяется: лежат ли концы
отрезка в треугольнике или нет? Проверка простая.
Если точка лежит в треугольнике, то в этом случае
Сумма площадей трех маленьких треугольников равна
площади данного треугольника. В противном случае
точка лежит вне треугольника. Площадь треугольников
находится по формуле:
S = 0,5|(x2 - x1)(y3 - y1) - (x3 - x1)(y2 - y1)|
Где x1, y1, x2, y2, x3, y3 - координаты вершин треугольника

@Fulcrum_013 · 27.02.2016, 03:15

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

Эту задачу можно решить иначе без всяких функций.
Многоугольник разбивается на треугольники.

Если он не выпуклый то разбивать его на треугольники та еще задачка. Кстати есть много методов решения этой задачи (разбиения на треугольники) есть много, некоторые базируются на оптимизации логической формулы контура. А с выпуклыми и так проблем нет без разбиения.

Добавлено через 1 час 7 минут
простенький способ на основе r-функций
http://oaji.net/articles/2014/1126-1407819638.pdf

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@Ryder95 9 / 9 / 8 Регистрация: 24.10.2013 Сообщений: 215

	Где проведён отрезок: внутри или снаружи многоугольника 20.02.2016, 23:13. Показов 2346. Ответов 10 Метки нет (Все метки) Здравствуйте! Есть многоугольник, заданный последовательностью точек его контура, которые идут в порядке против часовой стрелки. Две любые точки контура соединяются отрезком. Как можно определить, где проведён отрезок: внутри многоугольника, снаружи или пересекает (проблему пересечения решил, но, в основном, это просто перебор всех линий контура с проведённой линией)? Заранее благодарю 0

@Igor3D 1968 / 824 / 115 Регистрация: 01.10.2012 Сообщений: 4,870 Записей в блоге: 2
	21.02.2016, 12:54
	Сводится к базовой задаче "точка внутри/снаружи". Для этого часто используют odd/even - подсчет числа пересечений луча (напр по x) из точки. Классический код (с учетом проблем точности) был в джемсах. Дальше разгуглите Добавлено через 10 минут Наверное в данном случае проще найти все пересечения контура с прямой заданной отрезком. А дальше посчитать odd/even. Там правда есть одна бяка: прямая может пересекать точку(и) контура 1

@Ryder95 9 / 9 / 8 Регистрация: 24.10.2013 Сообщений: 215
	21.02.2016, 16:18 [ТС]
	Простите, забыл уточнить. Точки всегда находятся на контуре, то есть это и есть точки, которые задают контур. И между ними проводится отрезок. Вот как бы узнать, как он находится относительно полигона? 0

@Ryder95 9 / 9 / 8 Регистрация: 24.10.2013 Сообщений: 215
	23.02.2016, 03:22 [ТС]
	По поводу пересечений есть функция, уже написал. Про R-функции слышал и гуглил, но что-то это сложно довольно мне даётся, так что пока я их просто тихонечко читаю Добавлено через 2 минуты Да уж, проверка линии тогда будет намного проще)) и это будет одно из наиудобнейших решений. Надо только научится строить эти r-функции 0

@ichs Заблокирован
	26.02.2016, 17:47
	Ryder95 Эту задачу можно решить иначе без всяких функций. Многоугольник разбивается на треугольники. И для каждого треугольника проверяется: лежат ли концы отрезка в треугольнике или нет? Проверка простая. Если точка лежит в треугольнике, то в этом случае Сумма площадей трех маленьких треугольников равна площади данного треугольника. В противном случае точка лежит вне треугольника. Площадь треугольников находится по формуле: S = 0,5\|(x2 - x1)(y3 - y1) - (x3 - x1)(y2 - y1)\| Где x1, y1, x2, y2, x3, y3 - координаты вершин треугольника 0