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

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

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

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

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

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

Принадлежит ли точка четырехугольнику. C++
Принадлежит ни точка кольцу (на C) C++
C++ Принадлежит ли точка фигуре
C++ Принадлежит ли точка области.
Дана точка М(x, y). Присвоить z = 1, если точка принадлежит окружности с радиусом R и центром в точке (a, b) и z = 0 в противном случае. C++
C++ Даны отрезки [a, b] и [c, d] и точка A с координатой х. Определить, принадлежит ли данная точка одному из этих отрезков, обоим или лежит вне их
Принадлежит ли точка окружности C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Gepar
1175 / 531 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
10.05.2012, 22:10  [ТС]     Принадлежит ли точка многоугольнику #21
Блин, что-то реально сложно оно определить находится ли точка на линии прохождения луча, когда неизвестна форма многоугольника ...
ser4ega
27 / 27 / 3
Регистрация: 15.11.2009
Сообщений: 143
10.05.2012, 22:14     Принадлежит ли точка многоугольнику #22
Вот такая симпатичная конструкция. если ее причесать. Она по-прежнему не знает, что ей делать, если луч проходит через вершину
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
     }
Добавлено через 1 минуту
Я не понял вопроса=) Зачем определять находится ли точка на линии луча?. Кстати могу написать, если нужно все-таки
Потести это, оно работает?
Я тут сам с собой войну правок устраивал =)
Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
10.05.2012, 22:22     Принадлежит ли точка многоугольнику #23
Предлагаю разбить фигуру на простые треугольники. То есть берем первые три координаты, составляем из них треугольник, проверяем, принадлежит ли точка этому треугольнику. Если да, то выходим из цикла и возвращаем положительный ответ. Если нет, то сдвигаем на одну точку вперед, то есть если есть многоугольник с вершинами ABCDEF, то первый проверяемый треугольник будет ABC, второй BCD, третий CDE и так далее. Принадлежит ли точка прямоугольнику можно проверить вот так.
Gepar
1175 / 531 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
10.05.2012, 22:35  [ТС]     Принадлежит ли точка многоугольнику #24
Цитата Сообщение от ser4ega Посмотреть сообщение
Я не понял вопроса=) Зачем определять находится ли точка на линии луча?. Кстати могу написать, если нужно все-таки
В чистом виде не нужно, по условию просто считается что точка находится в многоугольнике даже если она на линии что соединяет вершины. Сейчас потестирую ...
ser4ega
27 / 27 / 3
Регистрация: 15.11.2009
Сообщений: 143
10.05.2012, 22:43     Принадлежит ли точка многоугольнику #25
Toshkarik, вот так?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool belong(float x[], float y[],float dotx, float doty, int n)
{ 
     for(int i=1;i<n-1;i++)
    { if ((x[0]-dotx)*(y[i]-y[1])-(x[i]-x[0])*(y[0]-doty)>0&&
(x[i]-dotx)*(y[i+1]-y[i])-(x[i+1]-x[i])*(y[i]-doty)>0&&
(x[i+1]-dotx)*(y[0]-y[i+1])-(x[0]-x[i+1])*(y[i+1]-doty)>0) return true;
     if ((x[0]-dotx)*(y[i]-y[1])-(x[i]-x[0])*(y[0]-doty)<0&&
(x[i]-dotx)*(y[i+1]-y[i])-(x[i+1]-x[i])*(y[i]-doty)<0&&
(x[i+1]-dotx)*(y[0]-y[i+1])-(x[0]-x[i+1])*(y[i+1]-doty)<0) return true;
     
     if ((x[0]-dotx)*(y[i]-y[1])-(x[i]-x[0])*(y[0]-doty)==0||
(x[i]-dotx)*(y[i+1]-y[i])-(x[i+1]-x[i])*(y[i]-doty)==0||
(x[i+1]-dotx)*(y[0]-y[i+1])-(x[0]-x[i+1])*(y[i+1]-doty)==0) return true;
     }
     return false;
     }
HighPredator
5455 / 1821 / 335
Регистрация: 10.12.2010
Сообщений: 5,386
Записей в блоге: 3
10.05.2012, 22:43     Принадлежит ли точка многоугольнику #26
Toshkarik, это будет работать для выпуклого многоугольника. Для невыпуклого может быть следующее (см. рисунок): заштрихованная зона не принадлежит многоугольнику.
Миниатюры
Принадлежит ли точка многоугольнику  
Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
10.05.2012, 22:44     Принадлежит ли точка многоугольнику #27
HighPredator, да, я это знаю. Просто не уточнил. Можно попробовать искать такие вершины.
HighPredator
5455 / 1821 / 335
Регистрация: 10.12.2010
Сообщений: 5,386
Записей в блоге: 3
10.05.2012, 22:46     Принадлежит ли точка многоугольнику #28
Цитата Сообщение от Toshkarik Посмотреть сообщение
Можно попробовать искать такие вершины.
Вот пользователь звезду нарисует. Там каждый второй угол за 180.
_or_75
-1 / 0 / 0
Регистрация: 18.02.2012
Сообщений: 244
10.05.2012, 22:54     Принадлежит ли точка многоугольнику #29
Цитата Сообщение от ser4ega Посмотреть сообщение
вот так написал
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;
     }
если често я такие коды вообще непонимаю
Gepar
1175 / 531 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
10.05.2012, 22:59  [ТС]     Принадлежит ли точка многоугольнику #30
Эм, нашёл пару багов. Например для моих старых координат (домиком). Рисунок прилагается часть координат не определяется из тех что принадлежат, а часть из тех что не принадлежат определяются. При этом в первой версии кода ser4ega, эта же проблема присутсвовала (только что проверил). Чёрный цвет - сама фигура. Красным выделены "аномалии".
C++
1
2
3
4
5
6
7
    float x[5]={20,10,25,40,30};
    float y[5]={10,20,30,20,10};
 
    cout<<belong(x,y,24,21,5);//1, ок. Точка принадлежит
    cout<<belong(x,y,25,21,5);//0, не ок. Точка принадлежит
    cout<<belong(x,y,24,20,5);//0, не ок. Точка принадлежит
    cout<<belong(x,y,10,25,5);//0,не ок. Точка далеко сверху от многоугольника
Миниатюры
Принадлежит ли точка многоугольнику  
Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
10.05.2012, 23:01     Принадлежит ли точка многоугольнику #31
И так вот что нашел, и намыслил для случае невыпуклой фигуры. Пускаем луч в любом направлении, и решаем уравнения пересечения отрезков многоугольника и этого луча. Если количество пересечений нечетное, то точка принадлежит данной фигуре. Если же четное или равно 0, то соответственно нет. Вот по такому примеру можно попробовать.
Gepar
1175 / 531 / 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;//правая
Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
10.05.2012, 23:08     Принадлежит ли точка многоугольнику #33
Нет, нужно проверять со сдвигом. Например:
6 вершин ABCDEF. Первый треугольник будет ABC, то есть в массиве вершин будут индексы 0, 1 и 2. Если точка не входит в него, то сдвигаем на единицу, получается следующий треугольник будет BCD, и так до конца. Последний, в худшем случае, будет EFA.
Gepar
1175 / 531 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
10.05.2012, 23:10  [ТС]     Принадлежит ли точка многоугольнику #34
Toshkarik, блин, не знаю как это задать хитро. Для меня ведь и производительность важна так что рекурсивный вызов функций не пойдёт, а вот как организовать хитрый цикл я даже не знаю ...
HighPredator
5455 / 1821 / 335
Регистрация: 10.12.2010
Сообщений: 5,386
Записей в блоге: 3
10.05.2012, 23:12     Принадлежит ли точка многоугольнику #35
Gepar, а почему вы не хотите грамотно реализовать алгоритм трассировки луча?
Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
10.05.2012, 23:13     Принадлежит ли точка многоугольнику #36
Ну цикл на самом деле это мелочь реализации. А по поводу равенства нулю при проверке принадлежности треугольнику, так вроде это означает, что точка лежит на ребре. Вам это, вроде, и нужно было.
Gepar
1175 / 531 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
10.05.2012, 23:17  [ТС]     Принадлежит ли точка многоугольнику #37
Toshkarik, так с треугольниками что-то не сходится. Смотрите (красным показываю треугольник, который получается если свести первые три точки, но который не принадлежит многоугольнику).
Миниатюры
Принадлежит ли точка многоугольнику  
Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
10.05.2012, 23:18     Принадлежит ли точка многоугольнику #38
Gepar, так ведь это на предыдущей странице и писали Данный метод подходит только для выпуклых фигур. Для не выпуклых я написал вариант чуть выше:

Цитата Сообщение от Toshkarik Посмотреть сообщение
И так вот что нашел, и намыслил для случае невыпуклой фигуры. Пускаем луч в любом направлении, и решаем уравнения пересечения отрезков многоугольника и этого луча. Если количество пересечений нечетное, то точка принадлежит данной фигуре. Если же четное или равно 0, то соответственно нет. Вот по такому примеру можно попробовать.
В данном варианте нужно будет в любом случае решить все n систем двух уравнений.
Gepar
1175 / 531 / 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, тоесть она правильно определяет что точка находится на линии соединяющей две вершины треугольника, тоесть и так вроде всё ок без проверок на ноль ...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.05.2012, 23:25     Принадлежит ли точка многоугольнику
Еще ссылки по теме:

C++ Принадлежит ли точка четырехугольнику?
Принадлежит ли точка области C++
C++ Принадлежит ли точка прямоугольнику?
C++ Принадлежит ли точка выпуклому многоугольнику
C++ Определить принадлежит точка точка координатам

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

Или воспользуйтесь поиском по форуму:
HighPredator
5455 / 1821 / 335
Регистрация: 10.12.2010
Сообщений: 5,386
Записей в блоге: 3
10.05.2012, 23:25     Принадлежит ли точка многоугольнику #40
Цитата Сообщение от Gepar Посмотреть сообщение
У меня и не грамотно то не получается определить принадлежит ли точка многоугольнику.
Алгоритм трассировки луча как раз и решает задачу определения принадлежности точки многоугольнику. Почитайте про него. Рекомендую. Посмотрите на алголисте. Там и пример есть. Ссылку я вам в личку кинул.
Yandex
Объявления
10.05.2012, 23:25     Принадлежит ли точка многоугольнику
Ответ Создать тему
Опции темы

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