Алгоритм точки в многоугольнике

Последнее сообщение
Guzel 236 17
Дек 06

знаю, что это какой-то классический алгоритм, который многие знают, уж очень часто он встречается нефтегазовом софте

как проверить принадлежность точки к области внутри полигона, заданного набором точек ху? полигон естественно должен быть 1) замкнутым 2) любой, даже самой заковыристой формы, исключая, пожалуй, замкнутые полигоны внутри полигонов

Guzel 236 17
Дек 06 #2

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

третий алгоритм вроде подходит по быстродействию:

"Очень быстрый алгоритм
В основе алгоритма лежит идея подсчёта количества пересечений луча, исходящего из данной точки в направлении вертикальной оси, со сторонами многоугольника. Если оно чётное, точка не принадлежит многоугольнику.

Не требуя, как и предыдущий алгоритм, арифметических операций деления, он превосходит его по быстродействию.

Недостатком является непредсказуемость результата определения принадлежности многоугольнику точек его границ."

но кто скажет, что есть пересечение луча со стороной многоугольника? тем более, нет собственно стороны, а есть только точки. есть только идея перебирать все точки грида по рядам. в каждом ряду должно быть два ближайших соседа к точкам полигона (мин расстояния), но если точек пересечения в ряду 4 или больше? Тогда нужно чтобы в полигоне расстояние между ближайшими точками было не больше размерности грида (предварительно разбить)... отбор если растояние от точки грида до точки полигона меньше половины размепрности грида... до первой точки пересечения - вне полигона, потом внутри, потом вне, внутри, вне... и тд. что-то муторно. интересно, как долго будет считать

Guzel 236 17
Дек 06 #3

а если поиск решения - пересечение двух отрезков. но отрезков не два, а много. то есть один + много.

в любом случае количество операций большое.

TimTTT 153 17
Дек 06 #4

http://pasc.al.ru/www/exampl35.htm - код на Паскале, разобраться можно, написан хорошо

Поисковик nigma.ru - рекомендую.

karakurt2 94 14
Июн 11 #5


raycast_result ps_raycast(const ps_point* p, \
const ps_point* q, double x, double y)
{
switch (ps_classify(p->xcoord(), p->ycoord(), q->xcoord(), q->ycoord(), x, y))
{
case CLASSIFY_LEFT:
return (p->ycoord() < y && y <= q->ycoord()?
RAYCAST_CROSSING: RAYCAST_INESSENTIAL);
case CLASSIFY_RIGHT:
return (q->ycoord() < y && y <= p->ycoord()?
RAYCAST_CROSSING: RAYCAST_INESSENTIAL);
case CLASSIFY_BETWEEN:
case CLASSIFY_ORIGIN:
case CLASSIFY_DESTINATION:
return RAYCAST_TOUCHING;
}
return RAYCAST_INESSENTIAL;
}

inpoly_result ps_inpoly(double x, double y, const ps_contour* g)
{
bool parity = false;
while (g)
{
const ps_halfedge* e = g->edge;
assert(e->symm->next);
do
{
switch (ps_raycast(e->node, e->symm->node, x, y))
{
case RAYCAST_TOUCHING:
return INPOLY_BOUNDARY;
case RAYCAST_CROSSING:
parity = !parity;
}
e = e->next;
}
while (e != g->edge);
g = g->next;
}
return (parity? INPOLY_INSIDE: INPOLY_OUTSIDE);
}

к сожалению, на сайте не реализовано форматирование кода

но мысли идут в правильном направлении

Go to top