Как определить находися заданная точка внутри фигуры или вне ее?

Не хочу в очередной раз изобретать велосипед, а геометрию оочень давно изучал, может кто подскажет решение такой задачки:
Имеем замкунутую фигуру состоящую из отрезков прямой и точку на плоскости. Координаты вершин фигуры и самой точки известны, как по этим данным определить находися заданная точка внутри фигуры или вне ее.
Hаходим количество пересечений отрезков и любого луча с началом в точке. Если нечетное - то вне фигуры.
До этого я и сам додумался , но задача довольно распространенная в 2D графике, может быть кто-нибудь знает более эффктивные алгоритмы хотя бы для частных случаев... Да еще известна по крайней мере одна точка лежащая внутри фигуры (условный центр), и достаточно построить луч из заданной точки в ее "центр" фигуры... Но как находить пересечения если саму фигуру в памяти строить нельзя - большая она очень...
Поищи книги под названием "Алгоритмы машинной графики". Там всё и найдёшь. А алгоритмы будут отличаться в зависимости от ограничений для твоей фигуры. Например, самый простой для прямоугольника. Тут можно проверять где лежит точка относительно каждой стороны. Слева/Справа, Вверху/Внизу или на линии. В худшем случае четыре проверки плюс "контрольный выстрел".
А если скорость не очень существенна, и WinAPI не запрещено, можно вообще не изобретать:
Rgn := CreatePolygonRgn(Points, PointsCount,...);
Result := PtInRgn(Point,Rgn);
CloseHandle(Rgn);

Я точных названий и параметров не помню, но по хелпу найти легко будет...
А кто сказал, что фигуру строить надо? Надо действовать аналитически в той координатной сетке, в которой задана фигура и точка. Строим луч и простой перебор по рёбрам на предмет пересечения с лучом. Надеюсь, знаешь как найти точку пересечения 2х отрезков на плоскости с заданными координатами вершин?!
BOOL IsInArea(int areaX, int areaY, POINT* pt, int iCountPoint)
{
int iCount = 0;

for (int i = 0;i<iCountPoint;i++)
{
int j = (i+1)%iCountPoint;
int p1y = pt[i].y;
int p2y = pt[j].y;
int maxY,minY;

if (p1y == p2y) continue;
if (p1y > areaY && p2y >areaY) continue;
if (p1y < areaY && p2y < areaY) continue;
if (p1y > p2y)
{
maxY = p1y;
minY = p2y;
}
else
{
maxY = p2y;
minY = p1y;
}
if (maxY == areaY) iCount++;
else
if (minY == areaY) continue;
else
{
double t = (double)(areaY-p1y)/(double)(p2y-p1y);
if (pt[i].x+t*(pt[j].x-pt[i].x) >= areaX) iCount++;
}
}
return (iCount & 1);
}

Простой перебор меня не очень устраивает, как-то надо его оптимизировать, может сортировать вершины, нутром чуствую должен быть способ выделить 2-3 наиболее вероятных отрезка, а офорить это в алгоритм не получается, хотя пока не брался за этот вопрос серьезно - надеюсь найти готовое решение .
Тогда делай так - бери горизонтальный луч и проверяй пересечения только с теми рёбрами, вершины которых находятся по разные стороны луча. Больше пока ничего в голову не приходит... А решать придётся не одно линейное уравнение, а систему из 2х. Но это так, к слову...
Если надо проверять много точек (ну скажем, больше, чем квадрат числа сторон этого многоугольника), то есть мощные алгоритмы типа bsp (там затраты на построение дерева больше N ln N , N-число сторон многоугольника).
Точек намного больше, и они, подлые, еще и ползают по плоскости , а вот фигура не изменяется так что возможно использование "предрасчетных" талиц...
А кстати, регион тогда можно один раз создать а PtInRgn протрейсить/промерять тормознутость - может тормозить то и не будет... Мож там тоже оптимизация какая есть - MS ведь не везде идиоты сидят, а функция используется на каждый MouseMove и иногда не раз - тоесть, часто - может и с оптимизили ее не плохо...
Насколько я представляю для работы с регионами строится битовая маска, в моем случае плоскость ориентировочно имеет размер 16'000'000 x 16'000'000 точек...
BSP. Тут даже думать нечего. Но можно совместить с тайлами (разбить прямоугольной сеткой многоугольник).
В Win регионы сложной (точнее не прямоугольной) формы аппроксимируются набором прямоугольных регионов.
Насколько я помню, там можно комбинировать еще и элипсы, но в любом случае мне это не подходит... А вообще-то imho битовая маска оптимальное решение для регионов, если это не используется им же хуже.
Я имел в виду, что даже эллиптический регион на самом деле (т.е. внутри Win) реализуется как совокупность "маленьких прямоугольненьких" регионов. Битовые маски там не используются и я не уверен что им от этого хуже.
Для регионов не слишком сложной формы - прямоугольники лучше адназначна Со сложной формой тоже не все очевидно. Я тут как-то экспериментировал - строил регион по битмапу типа эллипс + "отъеденный снизу" кружок, всепрмерно 400х300. У меня число прямоугольников получилось примерно равным числу scanlines. Ну и что - подумаешь 300 четверок двухбайтовых чисел - 2.5К. Битмап больше тянет. А эти прямоугольнички идеально подходят для обработки в MMX и т.п. К тому же здесь нет проблемы масштабируемости - все координаты легко пересчитваются. Да и операции над такимим регионами удобны - всегда есть шанс придти к более компактной конструкции (после, например, объединения). А маска что с ней ни делай - всегда будет иметь размер bounding rect и требовать просчета ВСЕХ точек. Разумеется, мои высказывания тоже имеют слябые места. Удобство масок в некоторых случаях очевидно.

TopList Rambler's Top100