Форум программистов, компьютерный форум CyberForum.ru

Принадлежит ли точка многоугольнику - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 72, средняя оценка - 4.69
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,511
10.05.2012, 18:01     Принадлежит ли точка многоугольнику #1
Нужен такой вот алгоритм (а ещё лучше функция ).Поиск по форуму не увенчался успехом (темы есть , но кода нет). Вершины многоугольника не пересекаются. Помогите пожалуйста.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ser4ega
27 / 27 / 3
Регистрация: 15.11.2009
Сообщений: 143
10.05.2012, 18:36     Принадлежит ли точка многоугольнику #2
вот так написал
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream.h>
 
bool amafree(float x1, float x2, float x3, float x4, float y1, float y2, float y3, float y4, float dotx, float doty)
 
{float x[4],y[4],temp;
for(int i=0;i<4;i++)
for(int j=0;j<3;j++)
{
        if(x[j]<x[j+1])
        {
                     temp=x[j];
                     x[j]=x[j+1];
                     x[j+1]=temp;  
                     temp=y[j];
                     y[j]=y[j+1];
                     y[j+1]=temp;  
                       }
        }
 
if (y[2]<y[3]) {temp=x[2];
                     x[2]=x[3];
                     x[3]=temp;  
                     temp=y[2];
                     y[2]=y[3];
                     y[3]=temp;  }//теперь мы упорядочили точки прямоугольника, чтобы понимать его как у меня на рисунке
     x1=x[0];
     x2=x[1];
     x3=x[2];
     x4=x[3];
     y1=y[0];
     y2=y[1];
     y3=y[2];
     y4=y[3];//так мне удобнее, потому что часть условий уже написал без всяких массивов
     
     float k[10];
     k[0]=(x1-x2)/(y1-y2);
     k[1]=(x1-x3)/(y1-y3);
     k[2]=(x3-x4)/(y3-y4);
     k[3]=(x2-x4)/(y2-y4);//коэффициенты прямых, проходящих по сторонам прямоугольника
  //   if(k[0]!=k[2]||k[1]!=k[3]) {cout<<"Eto dazhe ne parallelogramm\n";return false;}//условие параллельности противолежащих сторон
   //   if(k[0]!=1/k[1]||k[2]!=1/k[3]) {cout<<"Eto dazhe ne pryamougolnik\n";return false;}//условие перпендикулярности смежных сторон
     if(dotx<x[1])&&(dotx<x[2])&&(dotx<x3)&&(dotx<x4)||(doty<y1)&&(doty<y2)&&(doty<x3)&&(doty<x4)||//лежит точно вне
     (dotx>1)&&(dotx>x2)&&(dotx>x3)&&(dotx>x4)||(doty>y1)&&(doty>y2)&&(doty>x3)&&(doty>x4)||//лежит точно вне
     (dotx>x1)&&(dotx<x2)&&(dotx<x3)&&(dotx<x4)&&(doty-k[0]*dotx<0)||//нижний левый треугольник
     (dotx>x1)&&(dotx<x2)&&(dotx<x3)&&(dotx<x4)&&(doty-k[1]*dotx>0)||//верхний левый
     (dotx>x1)&&(dotx<x2)&&(dotx<x3)&&(dotx<x4)&&(doty-k[2]*dotx>0)||//верхний праввый
     (dotx>x1)&&(dotx<x2)&&(dotx<x3)&&(dotx<x4)&&(doty-k[3]*dotx<0)//нижний правый
     return false;
     return true;
     }
OstapBender
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
10.05.2012, 18:47     Принадлежит ли точка многоугольнику #3
Gepar,
почитай
http://ru.wikipedia.org/wiki/%D0%97%...B8%D0%BA%D1%83

... там есть метод суммы углов.. но это как я понимаю тоже только для плоскости...

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

к пространству хз....

Добавлено через 17 секунд
ser4ega, лол втф
ser4ega
27 / 27 / 3
Регистрация: 15.11.2009
Сообщений: 143
10.05.2012, 19:22     Принадлежит ли точка многоугольнику #4
OstapBender, это мой топорный метод. Прямоугольник там задан 4мя точками, и большая проверка. Я по рисунку смотрел своему=)
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,511
10.05.2012, 19:23  [ТС]     Принадлежит ли точка многоугольнику #5
Забыл предупредить: у меня на плоскости, никаких 3д не надо. Только 2д координаты.

ser4ega, но у многоугольников же количество углов = n. Функция которая принимает фиксированное число углов не подходит. Мне необходима функция которая примет координаты точки (x,y), а потом количество точек (size) и массив точек многоугольника ну и ответит попадает ли точка в многоугольник или нет.
OstapBender, википедия не помогает, там слишком сложно всё: там какие-то хитрые 3д многоугльники с учётом количества оборотов ... Мне бы несколько попроще.
ser4ega
27 / 27 / 3
Регистрация: 15.11.2009
Сообщений: 143
10.05.2012, 19:25     Принадлежит ли точка многоугольнику #6
надо еще добавить защиту от деления на 0, на случай, если прямоугольник лежит горизонтально.
И проверки немного изменить, на этот же случай

Добавлено через 59 секунд
Сорь, я подумал почему-то про прямоугольник. СЕЙЧАС ПЕРЕПИШУ
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,511
10.05.2012, 19:25  [ТС]     Принадлежит ли точка многоугольнику #7
ser4ega, с вычислением попадания точки в прямоугольник у меня проблем не возникло, там всё просто
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    virtual bool belong(int px, int py)
    {
        if((px>=x1 && py>=1) && (px<=x2 && py<=2))
         return true;
        return false;
    }
 
private:
    //верхняя левая координата
    int x1;
    int y1;
 
    //нижняя правая коордианата
    int x2;
    int y2;
Так же просто с кругом и треугольником, а вот многоугольник ...
OstapBender
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
10.05.2012, 19:28     Принадлежит ли точка многоугольнику #8
Gepar, проще не выйдет.... со сложными фигурами только так ...
попробуй реализовать метод с бесконечным лучем, он же не сложный.
ser4ega
27 / 27 / 3
Регистрация: 15.11.2009
Сообщений: 143
10.05.2012, 19:33     Принадлежит ли точка многоугольнику #9
Gepar, как работает твой код? Я не понимат
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,511
10.05.2012, 19:52  [ТС]     Принадлежит ли точка многоугольнику #10
ser4ega, там где 1 и 2 должно быть y1 и y2.
OstapBender, так нету там такого на вики. Приведите пожалуйста пример
ser4ega
27 / 27 / 3
Регистрация: 15.11.2009
Сообщений: 143
10.05.2012, 19:54     Принадлежит ли точка многоугольнику #11
так вот?
C++
1
2
3
4
5
6
7
8
bool belong(float x[], float y[],float dotx,float doty, int n)
{//n - размерность массива, массивы x и y хранят координаты вершин многоугольника, dotx, doty - координаты точки
     bool b=false;
     for(int i=0;i<n-1;i++)//луч направляем вдоль оси х
     if(dotx<x[i]&&doty<y[i]&&doty>y[i+1]||dotx<x[i]&&doty>y[i]&&doty<y[i+1]) b=!b;//если пересечет многоуолник нечетное число раз - тру
     if(dotx<x[i]&&doty<y[0]&&doty>y[n-1]||dotx<x[i]&&doty>y[0]&&doty<y[n-1]) b=!b;//пересечение с последним ребром
     return b;
     }
Добавлено через 1 минуту
Gepar, у тебя прямоугольник получается всегда горизонтальный - не катит
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,511
10.05.2012, 20:18  [ТС]     Принадлежит ли точка многоугольнику #12
ser4ega, ну вообще надо как-то так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct CCoord
{
    int   m_X;
    int   m_Y;
};
 
    virtual bool belong(int x, int y)//x,y - точка для которой надо определить принадлежность
    {
    }
 
private:
    int size;//сколько координат
 
    //указатель на массив координат
    CCoord* coord;
}
Думаю два массива с координатамы x и координатамы y отдельно это не очень хорошее решение

Добавлено через 1 минуту
Цитата Сообщение от ser4ega Посмотреть сообщение
Gepar, у тебя прямоугольник получается всегда горизонтальный - не катит
Да я вот тоже засомневался, а не будет ли у меня какой другой прямоугольник .... Наверное надо разбивать его на два треугольника и смотреть на принадлежность им. Ну да сейчас бы проблему с многоугольником решить ...
HighPredator
 Аватар для HighPredator
5342 / 1725 / 320
Регистрация: 10.12.2010
Сообщений: 5,108
Записей в блоге: 3
10.05.2012, 20:33     Принадлежит ли точка многоугольнику #13
Gepar, у вас многоугольник выпуклый?
OstapBender
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
10.05.2012, 21:01     Принадлежит ли точка многоугольнику #14
Gepar, я ж тебе алгоритм написал...
короче начал я делать... имхо все должно работать. но есть 1 НО. нет нормальной функции пересечения отрезков, с этим дополнительно придется морочиться...
2 что я нашел в инете выдают неверный результат.
КОД ЕПТ

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#undef min
#undef max
 
int max(int v1, int v2) {
    return v1 > v2 ? v1 : v2;
}
 
int min(int v1, int v2) {
    return v1 < v2 ? v1 : v2;
}
 
struct Vertex {
    double x,y,z;
};
 
struct Line {
    Vertex p1, p2;
};
 
double getLineY(Vertex p1, Vertex p2, double x) {
    return (x - p1.x) * (p2.y - p1.y) / (p2.x - p1.x) + p1.y;
}
 
 
int main() {
 
    Vertex M1[2] = {
        {500,871,0},
        {-20,-20,0}
    };
 
    Vertex M2[2] = {
{0,100,0},{100,100,0}
    };
 
 
 
    std::cout << LinesIntersect(M1[0],M1[1],M2[0],M2[1]);
// тупо проверка. функция выдает неверный рез-тат. как и другая функция intersect1
// не уверен что тут фейлится именно, но я проверял на фигуре ...
 
    getchar();
 
 
///////////////////// реальное задание
 
    const int n = 5;
 
    Line figure[n] = {
 
        {{0,100,0},{100,100,0}},
        {{100,100,0},{50,50,0}},
        {{50,50,0},{100,0,0}},
        {{100,0,0},{0,0,0}},
        {{0,0,0},{0,100,0}}
 
    };
 
    Vertex point = {-20,-20, 0};
 
    Vertex line_p = {(figure[0].p1.x + figure[0].p2.x) / 2, 0, 0}; // типа середина 0-ой линии
 
    line_p.y = getLineY(figure[0].p1, figure[0].p2, line_p.x);
 
    Vertex far_point;
 
    if (point.x > line_p.x) // типа направили луч 
        far_point.x = -500;
    else
        far_point.x = 500;
 
    far_point.y = getLineY(point, line_p, far_point.x);
 
    std::cout << far_point.y;
    getchar();
 
 
    int count = 0;
 
    for (int i=0; i<n; i++) {
 
        if (LinesIntersect(figure[i].p1, figure[i].p2, point, far_point)) {
            printf("Intersected line %d\n",i+1);
            count++;
        }
 
    }
 
    std::cout << count;
 
    if (count & 1) {
        puts("Inside");
    }
    else {
        puts("Outside");
    }
 
    std::cin.get();
    
}


функции из инета:
...

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
bool LinesIntersect(Vertex p11, Vertex p12, Vertex p21, Vertex p22) {
 
double maxx1 = max(p11.x, p12.x), maxy1 = max(p11.y, p12.y);
double minx1 = min(p11.x, p12.x), miny1 = min(p11.y, p12.y);
double maxx2 = max(p21.x, p22.x), maxy2 = max(p21.y, p22.y);
double minx2 = min(p21.x, p22.x), miny2 = min(p21.y, p22.y);
 
if (minx1 > maxx2 || maxx1 < minx2 || miny1 > maxy2 || maxy1 < miny2)
  return FALSE;  // Момент, када линии имеют одну общую вершину...
 
 
double dx1 = p12.x-p11.x, dy1 = p12.y-p11.y; // Длина проекций первой линии на ось x и y
double dx2 = p22.x-p21.x, dy2 = p22.y-p21.y; // Длина проекций второй линии на ось x и y
double dxx = p11.x-p21.x, dyy = p11.y-p21.y;
double div, mul;
 
 
if ((div = (double)((double)dy2*dx1-(double)dx2*dy1)) == 0) 
  return FALSE; // Линии параллельны...
if (div > 0) {
  if ((mul = (double)((double)dx1*dyy-(double)dy1*dxx)) < 0 || mul > div)
    return FALSE; // Первый отрезок пересекается за своими границами...
  if ((mul = (double)((double)dx2*dyy-(double)dy2*dxx)) < 0 || mul > div)
     return FALSE; // Второй отрезок пересекается за своими границами...
}
 
if ((mul = -(double)((double)dx1*dyy-(double)dy1*dxx)) < 0 || mul > -div)
  return FALSE; // Первый отрезок пересекается за своими границами...
if ((mul = -(double)((double)dx2*dyy-(double)dy2*dxx)) < 0 || mul > -div)
  return FALSE; // Второй отрезок пересекается за своими границами...
 
return TRUE;
}
 
 
 
 
 
 
 
int area (Vertex a, Vertex b, Vertex c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
 
bool intersect_1 (int a, int b, int c, int d) {
    if (a > b)  std::swap (a, b);
    if (c > d)  std::swap (c, d);
    return max(a,c) <= min(b,d);
}
 
bool intersect1 (Vertex a, Vertex b, Vertex c, Vertex d) {
    return intersect_1 (a.x, b.x, c.x, d.x)
        && intersect_1 (a.y, b.y, c.y, d.y)
        && area(a,b,c) * area(a,b,d) <= 0
        && area(c,d,a) * area(c,d,b) <= 0;
}


в общем мне чесно говоря надоело, может через час вернусь к этому
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,511
10.05.2012, 21:18  [ТС]     Принадлежит ли точка многоугольнику #15
Нашёл алгоритм, непонятно только рабочий ли он
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
bool pointInPolygon() {
 
  int      i, j=polySides-1 ;
  boolean  oddNodes=NO      ;
 
  for (i=0; i<polySides; i++) {
    if ((polyY[i]< y && polyY[j]>=y
    ||   polyY[j]< y && polyY[i]>=y)
    &&  (polyX[i]<=x || polyX[j]<=x)) {
      oddNodes^=(polyX[i]+(y-polyY[i])/(polyY[j]-polyY[i])*(polyX[j]-polyX[i])<x); }
    j=i; }
 
  return oddNodes; }
Добавлено через 1 минуту
HighPredator, да неизвестно чего там тыкать за многоугольники будут. Наверное все подряд так что упростить задачу до определения только выпуклых нельзя.

Добавлено через 8 минут
Не работает тот алгоритм что нашёл
ser4ega
27 / 27 / 3
Регистрация: 15.11.2009
Сообщений: 143
10.05.2012, 21:20     Принадлежит ли точка многоугольнику #16
Gepar, а мой работает?
Должон работать, пусть я там и не использовал коорд, дела это не меняет, если работает - для двумерного пространства разобрались
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,511
10.05.2012, 21:20  [ТС]     Принадлежит ли точка многоугольнику #17
Цитата Сообщение от OstapBender Посмотреть сообщение
в общем мне чесно говоря надоело, может через час вернусь к этому
Самому уже надоело, бесить вот начинает, но сделать надо. Беда ещё в том что это не основная задача, основная задача хранить это дело как-то и искать оптимально быстро в какие фигуры точка попадает ... но этот вопрос я уже поставил в другой теме, жаль что там никто так и не отписался.
Помогите пожалуйста с этим алгоритмом попадания точки в многоугольник, я не сильно понял то описание что на вики, мне бы функцию ...
ser4ega
27 / 27 / 3
Регистрация: 15.11.2009
Сообщений: 143
10.05.2012, 21:31     Принадлежит ли точка многоугольнику #18
Gepar, подумай над случаем прохождения луча через вершину, и еще вероятностью нахождения луча на ребре или точки на ребре. Это тяжелее оказалось
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,511
10.05.2012, 21:37  [ТС]     Принадлежит ли точка многоугольнику #19
Цитата Сообщение от ser4ega Посмотреть сообщение
Gepar, а мой работает?
Эм, я удивлён, но работает Только мне непонятно вовсе как оно работает, но работает, но тут тоже не всё гладко: попадение на пересечение оно отбрасывает, тоесть для прямоугольника:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool belong(float x[], float y[],float dotx,float doty, int n)
{//n - размерность массива, массивы x и y хранят координаты вершин многоугольника, dotx, doty - координаты точки
     bool b=false;
     for(int i=0;i<n-1;i++)//луч направляем вдоль оси х
     if(dotx<x[i]&&doty<y[i]&&doty>y[i+1]||dotx<x[i]&&doty>y[i]&&doty<y[i+1]) b=!b;//если пересечет многоуолник нечетное число раз - тру
     if(dotx<x[i]&&doty<y[0]&&doty>y[n-1]||dotx<x[i]&&doty>y[0]&&doty<y[n-1]) b=!b;//пересечение с последним ребром
     return b;
};
 
int main()
{
    float x[4]={0,20,30,30};
    float y[4]={0,20,20,0};
 
    cout<<belong(x,y,1,1,4);//ок, 1
    cout<<belong(x,y,0,1,4);//не ок, 0, хотя точка на нижней линии 
}
Сейчас погоняю с многоугольниками посложнее...

Добавлено через 4 минуты
Погонял ещё - и правда пока справляется. В том числе и со всякими пятиугольниками вроде этого
C++
1
2
3
4
    float x[5]={20,10,25,40,30};
    float y[5]={10,20,30,20,10};
 
    cout<<belong(x,y,25,15,5);
Остался только вопрос: как научить алгоритм ещё учитывать то что точка на линии тоже принадлежит многоугольнику.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.05.2012, 22:01     Принадлежит ли точка многоугольнику
Еще ссылки по теме:

C++ Даны отрезки [a, b] и [c, d] и точка A с координатой х. Определить, принадлежит ли данная точка одному из этих отрезков, обоим или лежит вне их
C++ Определить, принадлежит ли точка M(x,y)
Принадлежит ли точка области C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
ser4ega
27 / 27 / 3
Регистрация: 15.11.2009
Сообщений: 143
10.05.2012, 22:01     Принадлежит ли точка многоугольнику #20
Вот. Что делать с вершиной не знаю. Думаю) Как ты там?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cstdlib>
#include <iostream.h>
 
bool belong(float x[], float y[],float dotx,float doty, int n)
{//n - размерность массива, массивы x и y хранят координаты вершин многоугольника, dotx, doty - координаты точки
     bool b=false;
     for(int i=0;i<n-1;i++)//луч направляем вдоль оси х
     {if(dotx<x[i]&&doty<y[i]&&doty>y[i+1]||dotx<x[i]&&doty>y[i]&&doty<y[i+1]) b=!b;//если пересечет многоуолник нечетное число раз - тру
     if(dotx==x[i]&&doty==y[i])return true;//если точка в вершине
    if(y[i]!=y[i+1]){
     if(
     (     (dotx<x[i]&&dotx>x[i+1])||(dotx>x[i]&&dotx<x[i+1])        )
     
     
     &&(dotx*(x[i]-x[i+1])/(y[i]-y[i+1])==doty))return true;}//если точка лежит на ребре
     
     if((y[i]==y[i+1])&&(doty==y[i])&&((dotx<x[i]&&dotx>x[i+1])||(dotx>x[i]&&dotx<x[i+1]))) return true;//если точка лежит на ребре
     
     if((y[i]==y[i+1])&&(doty==y[i]))b=!b;//если ребро принадлежит лучу, мы его как будто все таки пересекаем =)
     }
     if(dotx<x[0]&&doty<y[0]&&doty>y[n-1]||dotx<x[0]&&doty>y[0]&&doty<y[n-1]) b=!b;//пересечение с последним ребром
    if((y[0]==y[n-1])&&(y[0]==doty))b=!b;//если ребро принадлежит лучу, мы его как будто все таки пересекаем =)
     if(dotx==x[n-1]&&doty==y[n-1])return true;//если точка в вершине
     
     return b;
     
     }
 
 
int main()
{
    system("PAUSE");
    return 0;
}
Yandex
Объявления
10.05.2012, 22:01     Принадлежит ли точка многоугольнику
Ответ Создать тему
Опции темы

Текущее время: 04:39. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru