Дек 06
знаю, что это какой-то классический алгоритм, который многие знают, уж очень часто он встречается нефтегазовом софте
как проверить принадлежность точки к области внутри полигона, заданного набором точек ху? полигон естественно должен быть 1) замкнутым 2) любой, даже самой заковыристой формы, исключая, пожалуй, замкнутые полигоны внутри полигонов
Опубликовано
27 Дек 2006
Активность
5
ответов
4476
просмотров
3
участника
0
Рейтинг
мм
да.
первый алгоритм сразу не подходит
второй - треугольники, тоже скорее всего, будет долгим, тк мне нужно проверить очень большое кол-во точек (мелкий грид)...
в сущности, это даже задача бланкования, тысячу раз реализованная во всяких там серферах и тд
третий алгоритм вроде подходит по быстродействию:
"Очень быстрый алгоритм
В основе алгоритма лежит идея подсчёта количества пересечений луча, исходящего из данной точки в направлении вертикальной оси, со сторонами многоугольника. Если оно чётное, точка не принадлежит многоугольнику.
Не требуя, как и предыдущий алгоритм, арифметических операций деления, он превосходит его по быстродействию.
Недостатком является непредсказуемость результата определения принадлежности многоугольнику точек его границ."
но кто скажет, что есть пересечение луча со стороной многоугольника? тем более, нет собственно стороны, а есть только точки. есть только идея перебирать все точки грида по рядам. в каждом ряду должно быть два ближайших соседа к точкам полигона (мин расстояния), но если точек пересечения в ряду 4 или больше? Тогда нужно чтобы в полигоне расстояние между ближайшими точками было не больше размерности грида (предварительно разбить)... отбор если растояние от точки грида до точки полигона меньше половины размепрности грида... до первой точки пересечения - вне полигона, потом внутри, потом вне, внутри, вне... и тд. что-то муторно. интересно, как долго будет считать
а если поиск решения - пересечение двух отрезков. но отрезков не два, а много. то есть один + много.
в любом случае количество операций большое.
- код на Паскале, разобраться можно, написан хорошо
Поисковик nigma.ru - рекомендую.
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);
}
к сожалению, на сайте не реализовано форматирование кода
но мысли идут в правильном направлении