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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 72, средняя оценка - 4.69
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,511
10.05.2012, 18:01     Принадлежит ли точка многоугольнику #1
Нужен такой вот алгоритм (а ещё лучше функция ).Поиск по форуму не увенчался успехом (темы есть , но кода нет). Вершины многоугольника не пересекаются. Помогите пожалуйста.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,511
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
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
10.05.2012, 22:22     Принадлежит ли точка многоугольнику #23
Предлагаю разбить фигуру на простые треугольники. То есть берем первые три координаты, составляем из них треугольник, проверяем, принадлежит ли точка этому треугольнику. Если да, то выходим из цикла и возвращаем положительный ответ. Если нет, то сдвигаем на одну точку вперед, то есть если есть многоугольник с вершинами ABCDEF, то первый проверяемый треугольник будет ABC, второй BCD, третий CDE и так далее. Принадлежит ли точка прямоугольнику можно проверить вот так.
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,511
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
 Аватар для HighPredator
5346 / 1729 / 320
Регистрация: 10.12.2010
Сообщений: 5,112
Записей в блоге: 3
10.05.2012, 22:43     Принадлежит ли точка многоугольнику #26
Toshkarik, это будет работать для выпуклого многоугольника. Для невыпуклого может быть следующее (см. рисунок): заштрихованная зона не принадлежит многоугольнику.
Миниатюры
Принадлежит ли точка многоугольнику  
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
10.05.2012, 22:44     Принадлежит ли точка многоугольнику #27
HighPredator, да, я это знаю. Просто не уточнил. Можно попробовать искать такие вершины.
HighPredator
 Аватар для HighPredator
5346 / 1729 / 320
Регистрация: 10.12.2010
Сообщений: 5,112
Записей в блоге: 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
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,511
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
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
10.05.2012, 23:01     Принадлежит ли точка многоугольнику #31
И так вот что нашел, и намыслил для случае невыпуклой фигуры. Пускаем луч в любом направлении, и решаем уравнения пересечения отрезков многоугольника и этого луча. Если количество пересечений нечетное, то точка принадлежит данной фигуре. Если же четное или равно 0, то соответственно нет. Вот по такому примеру можно попробовать.
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,511
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
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
10.05.2012, 23:08     Принадлежит ли точка многоугольнику #33
Нет, нужно проверять со сдвигом. Например:
6 вершин ABCDEF. Первый треугольник будет ABC, то есть в массиве вершин будут индексы 0, 1 и 2. Если точка не входит в него, то сдвигаем на единицу, получается следующий треугольник будет BCD, и так до конца. Последний, в худшем случае, будет EFA.
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,511
10.05.2012, 23:10  [ТС]     Принадлежит ли точка многоугольнику #34
Toshkarik, блин, не знаю как это задать хитро. Для меня ведь и производительность важна так что рекурсивный вызов функций не пойдёт, а вот как организовать хитрый цикл я даже не знаю ...
HighPredator
 Аватар для HighPredator
5346 / 1729 / 320
Регистрация: 10.12.2010
Сообщений: 5,112
Записей в блоге: 3
10.05.2012, 23:12     Принадлежит ли точка многоугольнику #35
Gepar, а почему вы не хотите грамотно реализовать алгоритм трассировки луча?
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
10.05.2012, 23:13     Принадлежит ли точка многоугольнику #36
Ну цикл на самом деле это мелочь реализации. А по поводу равенства нулю при проверке принадлежности треугольнику, так вроде это означает, что точка лежит на ребре. Вам это, вроде, и нужно было.
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,511
10.05.2012, 23:17  [ТС]     Принадлежит ли точка многоугольнику #37
Toshkarik, так с треугольниками что-то не сходится. Смотрите (красным показываю треугольник, который получается если свести первые три точки, но который не принадлежит многоугольнику).
Миниатюры
Принадлежит ли точка многоугольнику  
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
10.05.2012, 23:18     Принадлежит ли точка многоугольнику #38
Gepar, так ведь это на предыдущей странице и писали Данный метод подходит только для выпуклых фигур. Для не выпуклых я написал вариант чуть выше:

Цитата Сообщение от Toshkarik Посмотреть сообщение
И так вот что нашел, и намыслил для случае невыпуклой фигуры. Пускаем луч в любом направлении, и решаем уравнения пересечения отрезков многоугольника и этого луча. Если количество пересечений нечетное, то точка принадлежит данной фигуре. Если же четное или равно 0, то соответственно нет. Вот по такому примеру можно попробовать.
В данном варианте нужно будет в любом случае решить все n систем двух уравнений.
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,511
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++ Даны отрезки [a, b] и [c, d] и точка A с координатой х. Определить, принадлежит ли данная точка одному из этих отрезков, обоим или лежит вне их
C++ Определить, принадлежит ли точка M(x,y)
Принадлежит ли точка области C++

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

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

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