Как доказать, что точка лежит внутри многоугольника?

[NikiToZz_]

И снова здравствуйте, господа... Начну с того, что несколько лет назад уже поднимались подобного рода темы (чтобы у модераторов вопросы отпали), но ответа в них я не нашел. Там пытаются рассматривать алгоритмы, к примеру, графический или лучевой. Кстати, последний весьма интересен.

Вернемся к задаче. Хочу на паскале после ввода с клавиатуры координат точки и координат вершин многоугольника получать "Точка принадлежит многоугольнику", либо "Точка не принадлежит многоугольника"..

Теперь самое интересное, что же сделал я.. Я пытался решить эту задачу, используя графический модуль. То есть я рисовал ребра фигуры по точкам, рисовал 2 диагонали, искал их пересечение, соединял точку пересечения с моей точкой. В итоге, если было бы пересечение получившегося отрезка с ребром фигуры, значит исходная точка вне фигуры. Else в фигуре.

З.Ы. Многоугольник всегда выпуклый.

Итог: Не очень-то мой метод заработал, ну или реализация неправильная.. Прошу помочь

Кому интересны мои каракули (Там я брал несколько фигур):

program dachniki;
  uses Graph;
  var i,k,x,y,x1,y1,x2,y2,x3,y3,x4,y4,xperint,yperint,N:integer;
    xper,yper:real;
begin
  i:=1; k:=0;
  readln(N);
  repeat
      readln(x,y,x1,y1,x2,y2,x3,y3,x4,y4);
      line(x1,y1,x2,y2);
      line(x2,y2,x3,y3);
      line(x3,y3,x4,y4);
      line(x4,y4,x1,y1);
      xper:=-((x1*y2-x2*y1)*(x4-x3)-(x3*x4-x4*y3)*(x2-x1))/((y1-y2)*(x4-x3)-(y3-y4)*(x2-x1));
      yper:=((y3-y4)*(-x)-(x3*y4-x4*y3))/(x4-x3);
      xperint:=round(xper);
      yperint:=round(yper);
      line(x,y,xperint,yperint);
      if not((xper>=x1)and(xper<=x2))or((xper>=x2)and(xper<=x1)) then
           write ('Внутри') 
           else write ('Снаружи');
      inc(i);
  until i<>N;
  readln;
end.

[min@y™]

Нет бы помог) Ты же знаешь алгоритм

да чо мелочиться? давай я сразу всю прогу тебе напишу, а? А то я целыми днями лысого теребонькаю от безделья.

200609.png

[NikiToZz_]

min@y™, слушай, уж лучше ничего не писать, чем так писать) Или кем ты возомнил себя на этом форуме?) Репутация большая? ;-) Вон у Smitt&Wesson в свое время больше была...

[min@y™]

уж лучше ничего не писать, чем так писать

твоё субъективное мнение меня не интересует. можешь думать, что твоя тема, состоящая из одного поста принесёт тебе больше пользы. Мне всё равно.

Или кем ты возомнил себя на этом форуме?

Не понял вопроса.

Репутация большая?

Это вот то число, что под аватаркой? Оно, разве, на что-то влияет? Или его можно обналичить?

Вон у Smitt&Wesson в свое время больше была...

И чо?


Я тебе ничего не должен. Чем ты недоволен?

[NikiToZz_]

Молодец ;-) Расфармил мою тему сообщениями, больше от тебя, собственно ничего не нужно теперь..

[min@y™]

Ну вот. И все довольны.
Инцидент исчерпан.

[GreyScall]

Если многоугольник строго выпуклый - достаточно проверить как изучаемая точка располагается относительно каждой его стороны: если обходить многоугольник по часовой стрелке, считая каждое как вы выразились ребро - вектором - с какой стороны от вектора будет эта точка?
Точка находящаяся внутри выпуклого многоугольника будет "правее" одновременно ко всем рёбрам. Кстати, аналогично проверяется а выпуклый ли многоугольник - вместо точки изучается следующая вершина.

Впрочем, нечто подобное и рассматривается по ссылке указанной (почему-то в виде скриншота) в сообщении #2, только для более общих случаев.

[NikiToZz_]

Та я уже посмотрел, спасибо..