Добрый день. Нужно определить, попадает ли  точка в выпуклый многоугольник вершины должны быть в массиве.среда программирования Си++

Добрый день.
Не знаю как реализовать алгоритм в 

Цитата(Marathon @  2.12.2015,  08:18 )

среда программирования Си++

Но вот полное описание алгоритма и его реализация на яызке программирования Си++

Цитата(Marathon @  2.12.2015,  08:18 )

среда программирования Си++

Спасибо, это я нашел, но так выскакивают некоторые проблемки. Да и код уже есть, но хоть убей не могу понять почему не работает для 5 и 6 угольников.
#include <iostream>
 
typedef struct {
    int x, y;
} point;
 
/* принадлежность точки многоугольнику(для выпуклых)
   обход вершин по часовой стрелки */
bool PtInPolygon(const point& p, const point* d, int n){
    int r;
    --n;
    for(int i = 0; i < n; ++i) {
        r = (p.x - d[i].x)*(d[i].y - d[i + 1].y) - 
            (p.y - d[i].y)*(d[i].x - d[i + 1].x);
        if(r < 0)
            return false;
    }
    r = (p.x - d[n].x)*(d[n].y - d[0].y) - 
        (p.y - d[n].y)*(d[n].x - d[0].x);
    return (r >= 0);
}
 
int main(void){
    const int n = 4;
    point  d[n] = {
        { 200, 10  },
        { 250, 60  },
        { 200, 130 },
        { 150, 60  }
    };
    point p = { 190, 100 };
 
    if(PtInPolygon(p, d, n))
        std::cout << "Yes." << std::endl;
    else
        std::cout << "No!" << std::endl;
    return 0;
}

Ваше заполнение данными массива d[] не соответствует порядку обхода многоугольника (четырёхугольника) по часовой стрелке. Должно быть, к примеру, так:
{ 150, 60  },
{ 200, 130 },
{ 250, 60  },
{ 200, 10  }


Этот ответ добавлен с нового Винграда - http://vingrad.com

можно опрелелять автоматически. Все r должны быть одного знака. r == 0 значает, что точка лежит на стороне полигона, но проверять дальше всё равно надо - она может быть на продолжении стороны.

Код

bool PtInPolygon(const point& p, const point* d, int n){     double r0 = 0;     for(int i = 0; i < n; ++i) {        int j = (i+1) % n;        double r = // double чтобы избежать переполнения             (double)(p.x - d[i].x)*(d[i].y - d[j].y) -             (double)(p.y - d[i].y)*(d[i].x - d[j].x);         if(r*r0 < 0)             return false;         if (r0 == 0)             r0 = r;     }     return true; }

Код

bool PtInPolygon(const point& p, const point* d, int n){     double r0 = 0;     for(int i = 0; i < n; ++i) {        int j = (i+1) % n;        double r = // double чтобы избежать переполнения             (double)(p.x - d[i].x)*(d[i].y - d[j].y) -             (double)(p.y - d[i].y)*(d[i].x - d[j].x);         if(r*r0 < 0)             return false;         if (r0 == 0)             r0 = r;     }     return true; }

math64, Спасибо, то есть и по часовой и против?

ИгорьПереверзев, Там все правильно и для 5 и 6 угольников все работает, я перепутал, против часовой стрелки. Оказывается, сказали, чтобы интерфейс был " для   рядового пользователя" , исправил на ввод с клавиатуры вершин многоугольника и точки, но опять проблема, я не должен ставить рамки этому пользователю, точки вводит, да, по порядку, но не только против часовой, но и по, а вот тут уже прлблемы

Цитата(Marathon @  4.12.2015,  12:33 )

но не только против часовой, но и по, а вот тут уже прлблемы

А мой код, что не работает?

Цитата(Marathon @  4.12.2015,  12:33 )

но не только против часовой, но и по, а вот тут уже прлблемы

math64, Точка на самом деле лежит в многоугольнике, а вот программа выдает, что нет

math64, идей никаких, все пробую и не получается по часовой стрелке определять

Я в твоем коде заменил PtInPolygon на свой - выдает YES.

math64, Да,  выдает, я взял 5-угольник    const int n = 5;
    point  d[n] = {
        { 0, 5  },
        { 10, 8  },
        { 10, 25 },
        { -15, 25  },
        {-15, 9 }
    };
    point p = { 0, 100 };
Точки внутри - да, на пересечении - да, ну и в этой точке  0, 100 тоже да

Проверил с Вашим новым полигоном - выдаёт No - как и должно быть, точка намного выше полигона (верхняя сторона y=25)

math64, так, интересно

#include <iostream>
 
typedef struct {
    int x, y;
} point;
 
bool PtInPolygon(const point& p, const point* d, int n)
{
     double r0=0;
    for(int i = 0; i < n; ++i)
 {
         int j=(I+1)% n;
     double   r = 
    (double) (p.x - d[i].x)*(d[i].y - d[j].y) - 
        (double)(p.y - d[i].y)*(d[i].x - d[j].x);
        if(r* r0 <0)
            return false; 
         if (r0==0)
              r0=r ;
    return true;
        }
}
 
int main(void){
    const int n = 5;
    point  d[n] = {
        { 0, 5  },
        { 10, 8  },
        { 10, 25 },
        {- 15, 25},
        {-15, 9}
    };
    point p = { 0, 6 };
 
    if(PtInPolygon(p, d, n))
        std::cout << "Yes." << std::endl;
    else
        std::cout << "No!" << std::endl;
    return 0;
} 

Так ведь?

С точкой {0, 6} выдает Yes. И пользуйтесь тегом [code] (кнопка Код) для оформления кода программы в сообщении.