LINUX.ORG.RU

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

 ,


1

1

Я знаю, что задам тупой вопрос, но мне нужно простое решение проблемы, в интернете очень много сложных неправильных ответов.

Есть полигон, заданный в виде точек и отрезков (псевдокод):


class Vector2
    var x
    var y
    def __init__(x, y)
        self.x = x
        self.y = y

house = {
	"verts": [
		Vector2(-50.0, -50.0),
		Vector2(50.0, -50.0),
		Vector2(50.0, 50.0),
		Vector2(25.0, 50.0),
		Vector2(25.0, 25.0),
		Vector2(-50.0, 25.0),
	],
	"walls": [
		[0, 1],
		[1, 2],
		[2, 3],
		[3, 4],
		[4, 5],
		[5, 0],
	],
}

Задача для произвольного Vector2(x, y) проверить находится ли он внутри этого полигона. Скорость выполнения большая не нужна, нужен максимально простой и понятный код. Идеи?

★★★★★

Ну это же в любом учебнике по компьютерной графике есть. Берешь точку где-нибудь далеко. Например {100500; 0.1}. Вторая точка - та, которую ты проверяешь. Проводишь между ними прямую, назовем ее checkLine. Смотришь сколько сторон твоего многоугольника пересекаются с checkLine. Если кол-во пересечений нечетное - точка внутри. Если четное или 0, то снаружи.

Aswed ★★★★ ()

Алгоритм простой проверки отрезков на персечение сам найдешь?

Aswed ★★★★ ()

Лучше сразу взять OpenCV, там куча функций на любой вкус и цвет. http://docs.opencv.org/2.4/doc/tutorials/imgproc/shapedescriptors/point_polyg...

Либа сишная, так что и для питона есть биндинги. Опять же, для любого языка должна быть своя геометрическая либа, для того же питона — matplotlib, http://stackoverflow.com/questions/16625507/python-checking-if-point-is-insid...

anonymous ()

Есть идея, что тебе может хватить выпуклых, и тогда вместо ray casting хватит проверки векторного произведения [сторона x направление на точку].

t184256 ★★★★★ ()
Ответ на: комментарий от t184256

тогда вместо ray casting хватит проверки векторного произведения [сторона x направление на точку].

А можно отсюда поподробнее?

slapin ★★★★★ ()
Ответ на: комментарий от Aswed

Алгоритм простой проверки отрезков на персечение сам найдешь?

Но от ссылки не отказался бы

slapin ★★★★★ ()
Ответ на: комментарий от slapin

Даже и не знаю, как тут можно поподробнее, но постараюсь.

Вот у тебя на плоскости многоугольник ABCDEF и точка X. Считаешь векторное произведение [ABxAX]. Оно либо в одну сторону торчит, либо в другую. Фиксируем какое-либо из направлений, смотрим знак проекции на него. Пусть будет, допустим, +.

Теперь повторяем то же самое для [BCxBX], [CDxCX] ... [FA,FX]. Если все знаки одинаковые (все + или все -), то точка внутри.

Подвох прост: чтобы это работало, нужна выпуклость.

t184256 ★★★★★ ()
Последнее исправление: t184256 (всего исправлений: 1)
Ответ на: комментарий от t184256

Спасибо за объяснение. Но результат векторного произведения тоже вектор, как понять какой у него знак?

slapin ★★★★★ ()
Ответ на: комментарий от slapin

Этот вектор перпендикулярен интересующей тебя плоскости (назовем ее Oxy) => у него есть только z-компонента, т.е. скаляр. Вот ее знак тебе и нужен. Где плюс, а где минус — не суть.

Если забить на историю ее происхождения, то это — просто число a_y * b_x - b_y * a_x, где a_x, a_y, b_x, b_y — компоненты векторов-аргументов векторного произведения, перенормированных в начало координат. И то только с точностью до знака. И то только относительного.

Можно выключать режим чрезмерного объяснения или еще остались темные пятна в моем рассказе?

t184256 ★★★★★ ()
Последнее исправление: t184256 (всего исправлений: 1)
Ответ на: комментарий от slapin

Он имел в виду не векторное, а псевдовекторное/косое: x_1*y_2-x_2*y_1

vzzo ★★ ()
Ответ на: комментарий от slapin

Вот реализация на ocaml

(* it is ab^ac *)
value vecMull a b c =
	let (v1x,v1y) = (b.x -. a.x, b.y -. a.y) in
	let (v2x,v2y) = (c.x -. a.x, c.y -. a.y) in
	v1x *. v2y -. v1y *. v2x;
(* AB cross CD *)
value doesLinesCross a b c d =
	sign (vecMull c d a) <> sign (vecMull c d b) &&
	sign (vecMull a b c) <> sign (vecMull a b d);

Aswed ★★★★ ()
Ответ на: комментарий от Aswed

Смотришь сколько сторон твоего многоугольника пересекаются с checkLine.

Это для выпуклого многоугольника.

andreyu ★★★★★ ()
Ответ на: комментарий от Aswed

Похоже я был не прав. Посыпаю голову пеплом.

andreyu ★★★★★ ()

Самый простой способ — графический. Создаешь таблицу MxN пикселей и в ней рисуешь многоугольник. Каждую линию рисуешь "своим цветом", в точках, где проходит несколько линий, ставишь какой-то особый маркер. Всю внутренность заливаешь еще каким-то маркером, для заливки внутренней области алгоритмов дофига. Дальше рисуешь свой отрезок в этой таблице и проверяешь, что с пикселями. Если все соответствуют внутренним маркерам, то лежит внутри; если хоть один соответствует нулю — снаружи. А если же где-то натыкаешься на маркер вершин или номер грани, то проверяешь математически.

Для произвольного многоугольника проще, наверное, и не придумать. Другое дело — выпуклый многоугольник. У него тупо концы отрезка проверять надо, но все равно графически это проще.

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.