Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 72, средняя оценка - 4.69
Gepar
1177 / 533 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
#1

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

10.05.2012, 18:01. Просмотров 10469. Ответов 86
Метки нет (Все метки)

Нужен такой вот алгоритм (а ещё лучше функция ).Поиск по форуму не увенчался успехом (темы есть , но кода нет). Вершины многоугольника не пересекаются. Помогите пожалуйста.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.05.2012, 18:01
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Принадлежит ли точка многоугольнику (C++):

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

Дана точка М(x, y). Присвоить z = 1, если точка принадлежит окружности с радиусом R и центром в точке (a, b) и z = 0 в противном случае. - C++
Дана точка М(x, y). Присвоить z = 1, если точка принадлежит окружности с радиусом R и центром в точке (a, b) и z = 0 в противном случае.

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

Определить принадлежит точка точка координатам - C++
Такая задача даны действительные числа x y определить принадлежит точка координатам х у заштрихованной части площади или нет, программу...

Принадлежит ли точка области. - C++
Даны действительные числа x, y. Определить, принадлежит ли точка с координатами (x, y) заштрихованной части плоскости. Ответ выдаёт не...

Принадлежит ли точка фигуре - C++
Определить принадлежность точки областям, обозначенным прописными буквами A и B. Строчными буквами обозначены определяемые пользователем...

86
Toshkarik
1143 / 860 / 51
Регистрация: 03.08.2011
Сообщений: 2,390
Завершенные тесты: 1
10.05.2012, 23:01 #31
И так вот что нашел, и намыслил для случае невыпуклой фигуры. Пускаем луч в любом направлении, и решаем уравнения пересечения отрезков многоугольника и этого луча. Если количество пересечений нечетное, то точка принадлежит данной фигуре. Если же четное или равно 0, то соответственно нет. Вот по такому примеру можно попробовать.
0
Gepar
1177 / 533 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
10.05.2012, 23:08  [ТС] #32
Toshkarik, ну сейчас попробую с треугольниками. Так а здесь будет проверять треугольники из двух первых вершин + третья циклом из массива остальных, так? Или нужно перебрать все-все варианты трёх вершин?

Добавлено через 5 минут
Я ищу принадлежность треугольнику вот так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    virtual bool belong(int x, int y)
    {
        int k = (a.m_X - x) * (b.m_Y - a.m_Y) - (b.m_X - a.m_X) *  (a.m_Y - y);
        int l = (b.m_X - x) * (c.m_Y - b.m_Y) - (c.m_X - b.m_X ) * (b.m_Y - y);
        int m = (c.m_X - x) * (a.m_Y - c.m_Y) - (a.m_X - c.m_X) *  (c.m_Y - y);
        if ((k >= 0 && l >= 0 && m >= 0) || (k <= 0 && l <= 0 && m <= 0))//(k==l==m==0)
         return true;
 
        return false;
    }
 
private:
    CCoord a;//левая
    CCoord b;//средняя
    CCoord c;//правая
0
Toshkarik
1143 / 860 / 51
Регистрация: 03.08.2011
Сообщений: 2,390
Завершенные тесты: 1
10.05.2012, 23:08 #33
Нет, нужно проверять со сдвигом. Например:
6 вершин ABCDEF. Первый треугольник будет ABC, то есть в массиве вершин будут индексы 0, 1 и 2. Если точка не входит в него, то сдвигаем на единицу, получается следующий треугольник будет BCD, и так до конца. Последний, в худшем случае, будет EFA.
0
Gepar
1177 / 533 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
10.05.2012, 23:10  [ТС] #34
Toshkarik, блин, не знаю как это задать хитро. Для меня ведь и производительность важна так что рекурсивный вызов функций не пойдёт, а вот как организовать хитрый цикл я даже не знаю ...
0
HighPredator
5544 / 1857 / 346
Регистрация: 10.12.2010
Сообщений: 5,479
Записей в блоге: 2
10.05.2012, 23:12 #35
Gepar, а почему вы не хотите грамотно реализовать алгоритм трассировки луча?
0
Toshkarik
1143 / 860 / 51
Регистрация: 03.08.2011
Сообщений: 2,390
Завершенные тесты: 1
10.05.2012, 23:13 #36
Ну цикл на самом деле это мелочь реализации. А по поводу равенства нулю при проверке принадлежности треугольнику, так вроде это означает, что точка лежит на ребре. Вам это, вроде, и нужно было.
0
Gepar
1177 / 533 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
10.05.2012, 23:17  [ТС] #37
Toshkarik, так с треугольниками что-то не сходится. Смотрите (красным показываю треугольник, который получается если свести первые три точки, но который не принадлежит многоугольнику).
0
Миниатюры
Принадлежит ли точка многоугольнику  
Toshkarik
1143 / 860 / 51
Регистрация: 03.08.2011
Сообщений: 2,390
Завершенные тесты: 1
10.05.2012, 23:18 #38
Gepar, так ведь это на предыдущей странице и писали Данный метод подходит только для выпуклых фигур. Для не выпуклых я написал вариант чуть выше:

Цитата Сообщение от Toshkarik Посмотреть сообщение
И так вот что нашел, и намыслил для случае невыпуклой фигуры. Пускаем луч в любом направлении, и решаем уравнения пересечения отрезков многоугольника и этого луча. Если количество пересечений нечетное, то точка принадлежит данной фигуре. Если же четное или равно 0, то соответственно нет. Вот по такому примеру можно попробовать.
В данном варианте нужно будет в любом случае решить все n систем двух уравнений.
0
Gepar
1177 / 533 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
10.05.2012, 23:25  [ТС] #39
Цитата Сообщение от HighPredator Посмотреть сообщение
Gepar, а почему вы не хотите грамотно реализовать алгоритм трассировки луча?

Не по теме:

Звучит как "а почему вы не хотите зарабатывать 1000$ ?"


Я бы с радостью, но как? У меня и не грамотно то не получается определить принадлежит ли точка многоугольнику. Хотя я вижу это и правда не простая задача: гугл так и не дал мне ни одного чужого решения. Помогите пожалуйста решением, буду благодарен.

Добавлено через 3 минуты
Цитата Сообщение от Toshkarik Посмотреть сообщение
Для не выпуклых я написал вариант чуть выше:
Так у вас же уровень матана более прокачан, для меня пока не заработаю повышение уровня этот текст недоступен
Если серьёзно: не понял основную идею, как мы должны пускать луч в любом направлении и зачем мы это делаем. Нам то надо принадлежность точки найти, а тут луч в любом направлении ...

Добавлено через 2 минуты
Цитата Сообщение от Toshkarik Посмотреть сообщение
А по поводу равенства нулю при проверке принадлежности треугольнику, так вроде это означает, что точка лежит на ребре.
Так то оно так, но если проверять на равенство 0 то функция сразу же всё время true начинает возвращать. При этом если оставить проверки как сейчас и загнать треугольник
C++
1
2
    CTriangle tri( 3, CCoord ( 10, 20 ), CCoord ( 20, 10 ), CCoord ( 30, 20 ));
    cout<<tri.belong(11,20);
то функция возвращает 1, тоесть она правильно определяет что точка находится на линии соединяющей две вершины треугольника, тоесть и так вроде всё ок без проверок на ноль ...
0
HighPredator
5544 / 1857 / 346
Регистрация: 10.12.2010
Сообщений: 5,479
Записей в блоге: 2
10.05.2012, 23:25 #40
Цитата Сообщение от Gepar Посмотреть сообщение
У меня и не грамотно то не получается определить принадлежит ли точка многоугольнику.
Алгоритм трассировки луча как раз и решает задачу определения принадлежности точки многоугольнику. Почитайте про него. Рекомендую. Посмотрите на алголисте. Там и пример есть. Ссылку я вам в личку кинул.
0
Toshkarik
1143 / 860 / 51
Регистрация: 03.08.2011
Сообщений: 2,390
Завершенные тесты: 1
10.05.2012, 23:30 #41
Итак как это будет выглядеть на псевдокоде:

Код
Задать произвольное направление луча от заданной точки ( например параллельно оси x )
Инициализировать счетчик пересечений нулем

Инициализировать i единицей
Пока i < n
   Решить систему из двух уравнений: 1 уравнение луча, 2 уравнение отрезка из двух точек - первая точка arr[ i ], вторая - arr[ i - 1 ]
   Если отрезок и луч пересекаются
      Увеличить счетчик на пересечений 1

Решить систему из двух уравнений: 1 уравнение луча, 2 уравнение отрезка из двух точек - первая точка arr[ 0 ], вторая - arr[ n - 1 ]
Если отрезок и луч пересекаются
      Увеличить счетчик на пересечений 1

Если число пересечений нечетное
   Вернуть true
Иначе
   Вернуть false
1
OstapBender
584 / 523 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
10.05.2012, 23:32 #42
а ларчик то просто открывался :
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#undef min
#undef max
 
double max(double v1,double v2) {
    return v1 > v2 ? v1 : v2;
}
 
double min(double v1, double v2) {
    return v1 < v2 ? v1 : v2;
}
 
struct Vertex {
    double x,y,z;
};
 
struct Line {
    Vertex p1, p2;
};
 
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 = (int)((double)dy2*dx1-(double)dx2*dy1)) == 0) 
  return FALSE; // Линии параллельны...
if (div > 0) {
  if ((mul = (int)((double)dx1*dyy-(double)dy1*dxx)) < 0 || mul > div)
    return FALSE; // Первый отрезок пересекается за своими границами...
  if ((mul = (int)((double)dx2*dyy-(double)dy2*dxx)) < 0 || mul > div)
     return FALSE; // Второй отрезок пересекается за своими границами...
}
else {
if ((mul = -(int)((double)dx1*dyy-(double)dy1*dxx)) < 0 || mul > -div)
  return FALSE; // Первый отрезок пересекается за своими границами...
if ((mul = -(int)((double)dx2*dyy-(double)dy2*dxx)) < 0 || mul > -div)
  return FALSE; // Второй отрезок пересекается за своими границами...
}
return TRUE;
}
 
 
 
 
 
double getLineY(Vertex p1, Vertex p2, double x) {
    return ( ((x - p1.x) * (p2.y - p1.y)) / (p2.x - p1.x)) + p1.y;
}
 
 
 
 
int main() {
 
    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, 80, 0};
 
    Vertex line_p = {(figure[0].p1.x + figure[0].p2.x) / 2, 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);
 
    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();
    
}
в 1-м месте был пропущен else.
0
Gepar
1177 / 533 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
10.05.2012, 23:45  [ТС] #43
OstapBender, что-то я в вашем коде потерялся: почему 3х мерное пространство? почему LinesIntersect принимает 4 координаты? Что в main вообще происходит? Почему часть кода си, а часть с++ (printf,а рядом потоки cin/cout)? Похоже что в main часть каких-то вычислений ещё, но почему они в main, а не в функциях по вычислениях.

Добавлено через 3 минуты
Toshkarik, наверное всё же нужна функция. Помогите с её написанием пожалуйста. Я вижу я уже окончательно запутался со всеми этими методами обходов вершин многоугольников ...
0
ser4ega
27 / 27 / 3
Регистрация: 15.11.2009
Сообщений: 143
10.05.2012, 23:47 #44
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++)//луч направляем вдоль оси х
/*1*/  {if((dotx<x[i]||dotx<x[i+1])&&doty<y[i]&&doty>y[i+1]||(dotx<x[i]||dotx<x[i+1])&&doty>y[i]&&doty<y[i+1]) {b=!b;cout<<1<<endl;}//если пересечет многоуолник нечетное число раз - тру
/*2*/     if(dotx==x[i]&&doty==y[i]){cout<<2<<endl;return true;}//если точка в вершине
     /*3*/if(y[i]!=y[i+1]){cout<<3<<endl;
     /*4*/if(((dotx<x[i]&&dotx>x[i+1])||(dotx>x[i]&&dotx<x[i+1]))&&(dotx*(y[i]-y[i+1])/(x[i]-x[i+1])==doty)){cout<<4<<endl; return true;}}//если точка лежит на ребре
     /*5*/if((y[i]==y[i+1])&&(doty==y[i])&&((dotx<x[i]&&dotx>x[i+1])||(dotx>x[i]&&dotx<x[i+1]))) {cout<<5<<endl;return true;}//если точка лежит на ребре
    /*6*/ if((y[i]==y[i+1])&&(doty==y[i])){cout<<6<<endl; b=!b;}//если ребро принадлежит лучу, мы его как будто все таки пересекаем =)
   }
   /*7*/    if((dotx<x[0]||dotx<x[n-1])&&doty<y[0]&&doty>y[n-1]||(dotx<x[0]||dotx<x[n-1])&&doty>y[0]&&doty<y[n-1]){cout<<7<<endl; b=!b;}//пересечение с последним ребром
 /*8*/      if((y[0]==y[n-1])&&(y[0]==doty)){cout<<8<<endl;b=!b;}//если ребро принадлежит лучу, мы его как будто все таки пересекаем =)
 /*9*/      if(dotx==x[n-1]&&doty==y[n-1]){cout<<9<<endl;return true;}//если точка в вершине
  /*10*/   cout<<10<<endl;
     return b;
     }
0
Gepar
1177 / 533 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
10.05.2012, 23:57  [ТС] #45
Цитата Сообщение от ser4ega Посмотреть сообщение
Когда я писал, я думал, что координаты вершин в массиве хранятся последовательно.
Ну они последовательно хранятся. Только неизвестно в какую сторону они пойдут: слева-направо, или справа-налево. Тоесть тот же мой домик может рисоваться начиная как с нижних точек(20,10 или 30,10) так и с верхней (25,30).
0
10.05.2012, 23:57
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.05.2012, 23:57
Привет! Вот еще темы с ответами:

Принадлежит ли точка четырехугольнику. - C++
Надеюсь на помощь форумчан: Задача следующяя: задана коодинатами точек четырёхугольная фигура A(-2,-1) B(-1,1) C(0,0) D(1,0) С...

Принадлежит ли точка прямоугольнику? - C++
Составить программку для определения принадлежности точки в прямоугольной области(прямоугольнику).

Определить, принадлежит ли точка M(x,y) - C++
Помагите сделать Дана трапеция координатами вершин. Определить, принадлежит ли точка M(x,y) трапеции. нужно написать программу на с++ ....

Принадлежит ли точка прямоугольнику? - C++
Даны координаты (x1, y1), (x2, y2), (x3, y3), (x4, y4) - вершины прямоугольника, и (x,y) - координаты точки. Определить, принадлежит ли...


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

Или воспользуйтесь поиском по форуму:
45
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru