Другие языки программирования и технологии
Как по координатам трех точек треугольника определить - начало координат находится внутри него или за его пределами?
Нарисовать не предлагать - треугольников миллион - надо описать алгоритм для компьютера
Алгоритм прост. Треугольник - выпуклая фигура. Значит, если обходить все ребра в одном направлении, например, по часовой стрелке, то все внутренние точки будут справа от ребра. Далее, вспоминаем про векторное произведение векторов и вот алгоритм:
1 отсортировать ребра по часовой стрелке (взять две первые точки - первое ребро. В зависимости от того, где третья - справа или слева - добваить оставшиеся ребра)
2. Для каждого ребра проверить векторное произведение (x1y2 -x2y1) Если знак его один и тот же - то точка внутри.
1 отсортировать ребра по часовой стрелке (взять две первые точки - первое ребро. В зависимости от того, где третья - справа или слева - добваить оставшиеся ребра)
2. Для каждого ребра проверить векторное произведение (x1y2 -x2y1) Если знак его один и тот же - то точка внутри.
Владимир, ты извини конечно, но вот интересная задача, а сам ты попробовал подумать?
Эх ты, а польза была бы будущему программисту!
=============================================
Функция, проверяющая принадлежность точки треугольнику, в языке Паскаль может иметь вид:
Function TRY(x,y:real;x1,y1:tarray{массив [1..3]}):integer;
Function PR(i,j:integer):boolean;
begin
PR:=((x-x1)*(y1[j]-y1))>((x1[j]-x1)*(y-y1));
end;
begin
if ((pr(1,2))=(pr(2,3))) and ((pr(1,2))=(pr(3,1)))
then TRY:=1 else TRY:=0
end;
Где:
* Х, У - координаты проверяемой точки;
* Х1 - массив, содержащий х-вые координаты точек треугольника;
* У1 - массив, содержащий у-вые координаты точек треугольника;
Функция возвращает:
* 1, если точка лежит внутри треугольника;
* 0, если точка лежит снаружи;
===========================================================
{ геометрические алгоритмы: Точка внутри треугольника? Вариант 2 }
{ ------------------------------------------------------------------------}
{ Идея: Пусть есть треугольник ABC и точка P. Если Площадь ABC равна сумме }
{ площадей треугольников ABP,BCP,CAP, то точка внутри треугольника. }
{ ------------------------------------------------------------------------}
(* функция вычисляет расстояние между точками *)
Function Distance(ax,ay,bx,by:real):real;
begin
Distance := sqrt(sqr(ax-bx)+sqr(ay-by));
end;
(* функция вычисляет площадь треугольника по формуле Герона *)
Function SqrGeron(ax,ay,bx,by,cx,cy:real):real;
var p,a,b,c :real;
Begin
a:=Distance(cx,cy,bx,by);
b:=Distance(ax,ay,cx,cy);
c:=Distance(ax,ay,bx,by);
p:=(a+b+c)/2;
SqrGeron:=sqrt(p*(p-a)*(p-b)*(p-c));
End;
(* функция определеяет относительное положение точки: внутри или нет *)
Function PointInsideTreangle(ax,ay,bx,by,cx,cy,px,py:real):boolean;
const error = 1.000001;
var s,s1,s2,s3 :real;
begin
PointInsideTreangle:=TRUE;
s :=SqrGeron(ax,ay,bx,by,cx,cy);
s1:=SqrGeron(ax,ay,bx,by,px,py);
s2:=SqrGeron(bx,by,cx,cy,px,py);
s3:=SqrGeron(cx,cy,ax,ay,px,py);
if s*error>s1+s2+s3 then PointInsideTreangle:=TRUE
else PointInsideTreangle:=FALSE;
end;
Begin (* Тело основной программы *)
writeln(PointInsideTreangle(1,1,8,1,1,8,2,2)); {TEST1, Inside}
writeln(PointInsideTreangle(1,1,8,1,1,8,6,6)); {TEST2, Outside}
End.
========================================
Можно подставлять 0,0 и будет универсально.
А хочешь - сам упрости.
Эх ты, а польза была бы будущему программисту!
=============================================
Функция, проверяющая принадлежность точки треугольнику, в языке Паскаль может иметь вид:
Function TRY(x,y:real;x1,y1:tarray{массив [1..3]}):integer;
Function PR(i,j:integer):boolean;
begin
PR:=((x-x1)*(y1[j]-y1))>((x1[j]-x1)*(y-y1));
end;
begin
if ((pr(1,2))=(pr(2,3))) and ((pr(1,2))=(pr(3,1)))
then TRY:=1 else TRY:=0
end;
Где:
* Х, У - координаты проверяемой точки;
* Х1 - массив, содержащий х-вые координаты точек треугольника;
* У1 - массив, содержащий у-вые координаты точек треугольника;
Функция возвращает:
* 1, если точка лежит внутри треугольника;
* 0, если точка лежит снаружи;
===========================================================
{ геометрические алгоритмы: Точка внутри треугольника? Вариант 2 }
{ ------------------------------------------------------------------------}
{ Идея: Пусть есть треугольник ABC и точка P. Если Площадь ABC равна сумме }
{ площадей треугольников ABP,BCP,CAP, то точка внутри треугольника. }
{ ------------------------------------------------------------------------}
(* функция вычисляет расстояние между точками *)
Function Distance(ax,ay,bx,by:real):real;
begin
Distance := sqrt(sqr(ax-bx)+sqr(ay-by));
end;
(* функция вычисляет площадь треугольника по формуле Герона *)
Function SqrGeron(ax,ay,bx,by,cx,cy:real):real;
var p,a,b,c :real;
Begin
a:=Distance(cx,cy,bx,by);
b:=Distance(ax,ay,cx,cy);
c:=Distance(ax,ay,bx,by);
p:=(a+b+c)/2;
SqrGeron:=sqrt(p*(p-a)*(p-b)*(p-c));
End;
(* функция определеяет относительное положение точки: внутри или нет *)
Function PointInsideTreangle(ax,ay,bx,by,cx,cy,px,py:real):boolean;
const error = 1.000001;
var s,s1,s2,s3 :real;
begin
PointInsideTreangle:=TRUE;
s :=SqrGeron(ax,ay,bx,by,cx,cy);
s1:=SqrGeron(ax,ay,bx,by,px,py);
s2:=SqrGeron(bx,by,cx,cy,px,py);
s3:=SqrGeron(cx,cy,ax,ay,px,py);
if s*error>s1+s2+s3 then PointInsideTreangle:=TRUE
else PointInsideTreangle:=FALSE;
end;
Begin (* Тело основной программы *)
writeln(PointInsideTreangle(1,1,8,1,1,8,2,2)); {TEST1, Inside}
writeln(PointInsideTreangle(1,1,8,1,1,8,6,6)); {TEST2, Outside}
End.
========================================
Можно подставлять 0,0 и будет универсально.
А хочешь - сам упрости.
Сергей Рудской
Как бы вам сказать. Я и сам программист и сисадмин уже как 5 лет :)
А про сравнение площадей я и сам алгоритм уже понял и применил - еще до того, как запостить вопрос. Хотелось другие варианты рассмотреть. Видел что-то про направление обхода и точки с одной стороны, но не понял :(
Это я: http://projecteuler.net/index.php?section=profile&profile=blueboar2
А про сравнение площадей я и сам алгоритм уже понял и применил - еще до того, как запостить вопрос. Хотелось другие варианты рассмотреть. Видел что-то про направление обхода и точки с одной стороны, но не понял :(
Это я: http://projecteuler.net/index.php?section=profile&profile=blueboar2
По такому алгоритму вычисляется местонахождение объекта на земле с помощью GPS
Каков вопрос - таков и ответ: понаблюдайте за знаком координат. Чтобы начало отсчёта было внутри треугольника, возможно лишь счётное количество вариантов перемен знака.. .
P.S.: Еси бы вы указывали пространство и размерность треугольника, тогда смог бы дать более развёрнутый ответ ;)
P.S.: Еси бы вы указывали пространство и размерность треугольника, тогда смог бы дать более развёрнутый ответ ;)
Сергей Рудской
Двумерный естественно случай. Если бы был трехмерный - был бы тетраэдр. Пространство Евклидово
Похожие вопросы
- C++ Вывести сообщение о том, какая из точек ближе к началу координат, и все соответствующие расстояния.
- Как можно решить такое задание : " Ввести из клавиатуры шестизначное число, определить цифры, которые находится рядом
- C++ весь код находится внутри int main(int argc, char* pszArgs[]) { }
- turbo pascal 7.0 Определить принадлежность к области точек с заданными координатами!!!
- Как определить точку внутри треугольника? Turbo Delphi
- Pascal. Даны координаты начала и конца отрезка. Определить координаты всех точек этого отрезка.
- не очень сложная прога на c++ не робит: Написать функцию, сравнивающую площадь двух треугольников, по координатам их вер
- Проверить, находится ли координата в квадрате/прямоугольнике
- Знатокам AutoCAD!!! Не могу ввести вторую координату точки отрезка.
- Треугольник задан координатами своих вершин. вычислить его площадь. На языке СИ!
(define pt:y (lambda (pt) (cdr pt)))
(define make-pt (lambda (x y) (cons x y)))
(define make-pt1 (lambda (x1 y1 x2 y2) (make-pt (- x2 x1) (- y2 y1))))
(define make-pt2 (lambda (p1 p2) (make-pt1 (pt:x p1)(pt:y p1)(pt:x p2)(pt:y p2))))
(define v-mul (lambda (p1 p2) (- (* (pt:x p1) (pt:y p2)) (* (pt:y p1)(pt:x p2)))))
(define is-right-triple (lambda (p1 p2 p3) (> 0 (v-mul (make-pt2 p1 p2) (make-pt2 p1 p3)))))
(display "Enter p1:" ) (define p1 (make-pt (read)(read)))
(display "Enter p2:" ) (define p2 (make-pt (read)(read)))
(display "Enter p3:" ) (define p3 (make-pt (read)(read)))
(display "Enter test point:" ) (define pt (make-pt (read)(read)))
(if (not (is-right-triple p1 p2 p3))
(let ((tmp p2)) (set! p2 p3) (set! p3 tmp)))
(if (and (is-right-triple p1 p2 pt) (is-right-triple p2 p3 pt) (is-right-triple p3 p1 pt))
(display "Point is inside of triangle\n")
(display "Point is outside of triangle\n"))