[Алгоритмы] Проверка на попадание точки в заданный участок

[Akopalipsis]

Меня словосочетание "Высшая математика" пугает.. По этому у меня самый простой вопрос - если n-угольники выпуклые, то так же стоит ли воспользоваться алгоритмом с хабра или он будет слишком тяжёлый и в конкретной задаче лучше будет использовать другой?

[Dukobpa3]

Да я думаю в реальных задачах проще будет в твой выпуклый многоугольник вписать несколько прямоугольников и вхождение в них искать.
Будет некоторая погрешность, но тут уже от требуемой точности зависит. По производительности думаю это самый простой вариант.

[Akopalipsis]

Dukobpa3 Спасибо! Сижу на листочке решаю

[Nooob]

О производительности http://tmonax.blogspot.ru/2012/08/blog-post.html
не смотря на результаты, кажется лучшим вариантом трассировка луча. просто и красиво

public static function hitTestCoord (x:int, y:int, hitAreaPoints:Vector.<int>):Boolean
{
	var n:int = hitAreaPoints.length - 2;
	if (n <= 0)
	{
		return false;
	}
	var bx1:int   = hitAreaPoints[0];
	var by1:int   = hitAreaPoints[1];
	var x2:int    = x + 1000;
	var y2:int    = y;
	var i:int     = 0;
	var count:int = 0;
	while (i < n)
	{
		var bx2:int = hitAreaPoints[i + 2];
		var by2:int = hitAreaPoints[i + 3];
		var dx1:int = bx2 - bx1;
		var dy2:int = by2 - by1;
		if ((dx1 * (y - by1) - dy2 * (x - bx1)) * (dx1 * (y2 - by1) - dy2 * (x2 - bx1)) < 0)
		{
			var dx3:int = x2 - x;
			var dy4:int = y2 - y;
			if ((dx3 * (by1 - y) - dy4 * (bx1 - x)) * (dx3 * (by2 - y) - dy4 * (bx2 - x)) < 0)
			{
				count++
			}
		}
		bx1 = bx2;
		by1 = by2;
		i += 2;
	}
	return count % 2 != 0;
}

[Akopalipsis]

Nooob Спасибо! Именно из-за этой ссылки у меня и возник вопрос о векторном методе.
В итоге я склонился к методу, точное название которого не знаю, но приблизительно так же, как и у Вас.

Добавлено через 3 минуты
И у меня вопрос оффтопного характера - y=kx+l, это что?
Или y=kx+l === y=kx+b ?

[vorodis2]

Как я понимаю Вашу задачу, что у Вас есть набор точек из которого получается многоугольник. Когда я делал нечто подобное то самое сложное было из из набора точек построить многоугольник и разбить его на треугольники. В первый раз когда я этим парился, я делал свой алгоритм (не один), а во второй раз я использовал nape, чего и вам всетки рекомендую.
Посмотрите хотя бы на
http://napephys.com/samples.html#swf...uctibleTerrain

Но если захотите городить свой велосипед, то поиск точки в треугольнике, это самое простое из вашей задачи.))

[silin]

в качестве предположения: может оказаться, что отрисовка в шейп этого многоугольника (без добавления в дисплейЛист) и hitTestPoint обгонят по производительности самописный матанализ
не проверял, но вдруг

[Akopalipsis]

Но если захотите городить свой велосипед, то поиск точки в треугольнике, это самое простое из вашей задачи.))

Да, это самое простое. Nape я, как уже писал, использовать не хочу, я учусь, у меня беда с геометрией и алгеброй, вот и приходится учить.

hitTestPoint обгонят по производительности самописный матанализ

я думаю об этом с того момента, как захотел от него отказаться. Проверю скорость, напишу. Всем Спасибо!

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

Но если захотите городить свой велосипед, то поиск точки в треугольнике, это самое простое из вашей задачи.))

У меня вообще нет многоугольников, у меня девять прямоугольников, которые меняют координаты при вращении и масштабе вместе с плоскостью.

[Dukobpa3]

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

[Akopalipsis]

У меня вот как получается - рамку нужно не только отрисовать, но и изменить цвет, чтобы на черном она была белая, а на сером немного серее.. И получается, что если рамку делать как ДО, то появляется несколько лишних отрисовок bmd, но по остальным операциям не чего не сокращается. Вот и получается, что лучше всего рамку иметь только математически, а рисовать её в bmd всего холста через set-getPixel, попутно изменяя цвет.