Другие языки программирования и технологии

Как по координатам трех точек треугольника определить - начало координат находится внутри него или за его пределами?

Нарисовать не предлагать - треугольников миллион - надо описать алгоритм для компьютера
Алгоритм прост. Треугольник - выпуклая фигура. Значит, если обходить все ребра в одном направлении, например, по часовой стрелке, то все внутренние точки будут справа от ребра. Далее, вспоминаем про векторное произведение векторов и вот алгоритм:
1 отсортировать ребра по часовой стрелке (взять две первые точки - первое ребро. В зависимости от того, где третья - справа или слева - добваить оставшиеся ребра)
2. Для каждого ребра проверить векторное произведение (x1y2 -x2y1) Если знак его один и тот же - то точка внутри.
Алексей Л.
Алексей Л.
84 351
Лучший ответ
Алексей Л. (define pt:x (lambda (pt) (car pt)))
(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"))
Владимир, ты извини конечно, но вот интересная задача, а сам ты попробовал подумать?
Эх ты, а польза была бы будущему программисту!

=============================================

Функция, проверяющая принадлежность точки треугольнику, в языке Паскаль может иметь вид:

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 и будет универсально.
А хочешь - сам упрости.
Артём Клишин
Артём Клишин
7 165
Сергей Рудской Как бы вам сказать. Я и сам программист и сисадмин уже как 5 лет :)
А про сравнение площадей я и сам алгоритм уже понял и применил - еще до того, как запостить вопрос. Хотелось другие варианты рассмотреть. Видел что-то про направление обхода и точки с одной стороны, но не понял :(

Это я: http://projecteuler.net/index.php?section=profile&profile=blueboar2
По такому алгоритму вычисляется местонахождение объекта на земле с помощью GPS
Каков вопрос - таков и ответ: понаблюдайте за знаком координат. Чтобы начало отсчёта было внутри треугольника, возможно лишь счётное количество вариантов перемен знака.. .

P.S.: Еси бы вы указывали пространство и размерность треугольника, тогда смог бы дать более развёрнутый ответ ;)
Сергей Рудской Двумерный естественно случай. Если бы был трехмерный - был бы тетраэдр. Пространство Евклидово

Похожие вопросы