Как узнать принадлежность Опции

[kojan]

как узнать принадлежит ли точка к треугольнику (находится ли она в нем) или нет!
Зарание спасибо!!

[Ozzя]

http://algolist.manual.ru/maths/geom/belong/poly2d.php

[kojan]

Спасибо конечно, но мне там не все понятно, и тмболее как я понял там написанно на СИ, можно ли написать формулу, алгоритм на дэлфи.
Зарание спасибо!

[volvo]

Поиск: Принадлежность точки многоугольнику

[kojan]

к сожадению я не понимаю этот алгоритм, моет ест что-нибудь по проще?

[virt]

program point_in_treug;
const _eps = 1E-7;
type TPoint = record
                 x,y : real;
              end;

var a,b,c,p : TPoint;
    s,s1,s2,s3 : real;

function sq_treug(a,b,c : TPoint) : real;
begin
   sq_treug := (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)) / 2;
end;

begin
   read(a.x,a.y);
   read(b.x,b.y);
   read(c.x,c.y);
   read(p.x,p.y);
   s := abs (sq_treug(a,b,c));
   s1 := abs (sq_treug(a,b,p));
   s2 := abs (sq_treug(a,p,c));
   s3 := abs (sq_treug(p,b,c));
   if abs (s - s1 - s2 - s3) < _eps then writeln('point is inside the triangle')
      else writeln('point is outside the triangle');
end.

функция sq_treug вычисляет ориентированную площадь треугольника. Соответственно если точка p вне треугольника то сумма площадей треугольников abp ,apc ,pbc бедет больше площади abc ,иначе площади будут равны.

[volvo]

virt, уверен, что это будет работать ВСЕГДА? Я - нет... Доказать?

А тебе, kojan: попроще- попроси пользователя проверить на бумаге, и нажать на Y если точка внутри, и на N если точка - снаружи... Что значит "непонятно"? Есть алгоритм, и его нельзя сделать "проще" или "сложнее"... Не понимаешь - бери другое задание...

[virt]

уверен ,докажи..

[virt]

там могут быть ошибки только из-за нехватки точности.

[nd2]

А есть графическое решение сей же задачи?
Я знаю что оно есть, но не помню его

[volvo]

Если знаешь - чего спрашиваешь?

А теперь вопрос к тебе: Что значит "графическое решение"? Входные/выходные данные для него приведи...
"типа, на экране прямая, чуть ниже и левее точка, ..."

Все равно тебе придется решать аналитически.
Если ты про ВИЗУАЛИЗАЦИЮ - то по предложенному алгоритму ее и напишешь...


P.S. Насчет графического решения: ТЫ на бумаге сможешь решить эту задачу графически? Вот когда решишь, тогда и пытайся объяснить это компьютеру...

[nd2]

Если знаешь - чего спрашиваешь?

А теперь вопрос к тебе: Что значит "графическое решение"? Входные/выходные данные для него приведи...
"типа, на экране прямая, чуть ниже и левее точка, ..."

Все равно тебе придется решать аналитически.
Если ты про ВИЗУАЛИЗАЦИЮ - то по предложенному алгоритму ее и напишешь...
P.S. Насчет графического решения: ТЫ на бумаге сможешь решить эту задачу графически? Вот когда решишь, тогда и пытайся объяснить это компьютеру...

Я знаю, но не помню, вот премерный алгоритм:
Задача решалась методом заливки треугольника, и определением цвета точки, если цвет совпадал с цветом заливки, то точка соответственно лежит, если нет-то нет, только я вот не могу придумать из какой точки заливать треугольник, нужна формула для точки которая точно будет лежать в произвольном треугольнике, т е т пересечения бесиктрис, а как найти её координаты, если имеешь координаты вершин?
Вот в этом и весь вопрос!

[Гость]

program point_in_treug;
const _eps = 1E-7;
type TPoint = record
                 x,y : real;
              end;

var a,b,c,p : TPoint;
    s,s1,s2,s3 : real;

function sq_treug(a,b,c : TPoint) : real;
begin
   sq_treug := (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)) / 2;
end;

begin
   read(a.x,a.y);
   read(b.x,b.y);
   read(c.x,c.y);
   read(p.x,p.y);
   s := abs (sq_treug(a,b,c));
   s1 := abs (sq_treug(a,b,p));
   s2 := abs (sq_treug(a,p,c));
   s3 := abs (sq_treug(p,b,c));
   if abs (s - s1 - s2 - s3) < _eps then writeln('point is inside the triangle')
      else writeln('point is outside the triangle');
end.

Мона пояснение к сеёму, а то начинающим не особо понятно

[Гость]

Мона пояснение к сеёму, а то начинающим не особо понятно

а разве если просто сравнить с нулём модуль разности площадей, то это не точнее будет?

[Hunt666]

эта программа имеет недостаточную точность. попробуйте ввести A1(0,0),A2(1,1),A3(0,1) и координаты точки(1.00001;0) эта программа будет писать что точка внутри треугольника а на самом деле она вне его. КТО-НИБУДЬ исправте чтоб было ТОЧНЕЕ

[volvo]

Running
0
0
1
1
0
1
1.00001
0
point is outside the triangle

Какие проблемы?

[Hunt666]

теперь понял в чем у меня были проблемы не надо менять" if abs (s - s1 - s2 - s3)<_eps" на " if abs (s - s1 - s2 - s3)=0" тогда все будет в порядке спс всем очень хороший сайт