Здравствуйте, kkv79, Вы писали:

K>есть многоугольник
K>координаты его точек x1,y1.....xn,yn ..... x1,y1.
K>есть точка с координатами x,y
K>как определить лежит ли эта точка внутри или снаружи этого многоугольника?

Не читай википедий и алголистов — там в чаще всего ламеры публикуют свои лабораторные работы. Eric Haines, Point in Polygon Strategies — исчерпывающее раскрытие темы. http://www1.acm.org/pubs/tog/editors/erich/ptinpoly/

есть многоугольник
координаты его точек x1,y1.....xn,yn ..... x1,y1.
есть точка с координатами x,y
как определить лежит ли эта точка внутри или снаружи этого многоугольника?

Здравствуйте, kkv79, Вы писали:

K>есть многоугольник
K>координаты его точек x1,y1.....xn,yn ..... x1,y1.
K>есть точка с координатами x,y
K>как определить лежит ли эта точка внутри или снаружи этого многоугольника?

http://ru.wikipedia.org/wiki/Алгоритм_точки_в_многоугольнике

Здравствуйте, kkv79, Вы писали:

K>есть многоугольник
K>координаты его точек x1,y1.....xn,yn ..... x1,y1.
K>есть точка с координатами x,y
K>как определить лежит ли эта точка внутри или снаружи этого многоугольника?

Первое что в голову пришло: посчитайте сумму углов Pi-O-Pi+1, i = 1 .. n, Pi = (xi, yi), O — ваша точка. Если получился 0, то снаружи.

здесь

K>есть многоугольник
K>координаты его точек x1,y1.....xn,yn ..... x1,y1.
K>есть точка с координатами x,y
K>как определить лежит ли эта точка внутри или снаружи этого многоугольника?

Есть стандартная виндяшная функция PtInRegion делает именно то что тебе нужно. По точкам создай регион и проверь входит ли точка в него.

Здравствуйте, kkv79, Вы писали:

K>есть многоугольник
K>координаты его точек x1,y1.....xn,yn ..... x1,y1.
K>есть точка с координатами x,y
K>как определить лежит ли эта точка внутри или снаружи этого многоугольника?

/*
  Проверка принадлежности точки полигону по теореме Жордана -
  путем определения количества пересечений луча, выпущеного из нее, 
  с отрезками полигона. Луч выпускается вверх.

  Параметры:

  точки многоугольника; 
  число тоточек в нём; 
  точка, принаджежность которой многоугольнику нужно проверить;

  Возвращает:

  Перечисляемый тип - Inside, Outside, OnBorder.
*/
Belonging PointInPolygon(TPoint* Points,int Count, double x, double y){
    
    int next, Counter = 0; 
    double x1, y1, x2, y2, dx, dy, p;
    
    for (int i = 0; i < Count; i++){

        next = (i+1) % Count;

        x1 = Points[next].x; 
        y1 = Points[next].y;
        x2 = Points[i].x; 
        y2 = Points[i].y;

        if ((y1 < y) && (y2 < y)) 
            continue;

        if (x1 == x)
            if (y1 == y) return OnBorder;//Точка совпала с одним из узлов
            else 
            if (x2 == x)
                if ((y1 <= y) || (y2 <= y)) return OnBorder;//Точка на вертикальной границе 
                else 
                    continue;

                if (((x2 <=x ) && (x1<=x)) || ((x2 > x) && (x1 > x))) 
                    continue;

                if ((y1 > y) && (y2 > y)) 
                    Counter++;

                else{
                    dx = x2 - x1; 
                    dy = y2 - y1;
                    p = y1 + (x-x1) / dx * dy;

                    if (p > y) 
                        Counter++;

                    else if (p == y) 
                        return OnBorder;
                }
    }

    if (Counter % 2 == 0) 
        return Outside;
    else 
        return Inside;
}

Здравствуйте, sadomovalex, Вы писали:

S>http://ru.wikipedia.org/wiki/Алгоритм_точки_в_многоугольнике

Ужас-ужас! Если мозгов в голове нет, то давайте на треугольники порубаем, ага.

Здравствуйте, McSeem2, Вы писали:

MS>Не читай википедий и алголистов — там в чаще всего ламеры публикуют свои лабораторные работы. Eric Haines, Point in Polygon Strategies — исчерпывающее раскрытие темы. http://www1.acm.org/pubs/tog/editors/erich/ptinpoly/

Препарата Ф., Шеймос М. — Вычислительная геометрия: введение Глава 2. Геометрический поиск, параграф 2.2. Локализация точки — исчерпывающее раскрытие темы (просто печатным изданиям я склонен верить больше). Там предствален алгоритм, работающий за O(N) и использующий ту же идею что и в указанной мной ссылке в википедии в разделе Очень быстрый алгоритм, а именно число точек пересечения луча и сторон многоугольника

Здравствуйте, sadomovalex, Вы писали:

S>Препарата Ф., Шеймос М. — Вычислительная геометрия: введение Глава 2. Геометрический поиск, параграф 2.2. Локализация точки — исчерпывающее раскрытие темы (просто печатным изданиям я склонен верить больше). Там предствален алгоритм, работающий за O(N) и использующий ту же идею что и в указанной мной ссылке в википедии в разделе Очень быстрый алгоритм, а именно число точек пересечения луча и сторон многоугольника

Ну а зачем тогда ссылаться на какую-то лажу с разбиением на треугольники? Ведь именно этот алгоритм подробно описан и он вводит новичков в заблуждение — что яко-бы "это и есть нормальный метод". А поиск пересечений с лучем только лишь упомянут и упомянут как "очень быстрый". В действительности же он не очень быстрый, а нормальный. А с треугольниками и заведомым временем работы O(N^2) как раз является полной лажей. Поэтому я призываю думать, прежде чем давать на работы студентов-первокурсников как на яко-бы алгоритмы.

Что же касается "верить" или "не верить", то Эрик Хайнес как источник в общем и целом будет поглавней ископаемых Препараты и Шеймоса. Такие слова как SIGGRAPH, ACM ни о чем не говорят?

Здравствуйте, Мурлакотам!
Проверил экстремальные случаи "точки на границах". По-моему надо поменять местами проверки:

if (p > y) 
   Counter++;
else if (p == y) 
   return OnBorder;

if (approx_equal(p, y, eps)) 
   return OnBorder;
else if (p > y) 
   Counter++;
...
#define approx_equal(a,b,c) (fabs(a-b)<=c)

В "стандартных" случаях работает без ошибок.