|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Rodion Gorkovenko 2:5030/1286.6 07 Jun 2003 00:43:00
To : Fedor Tereshin
Subject : точка в треугольнике
--------------------------------------------------------------------------------
06 Jun 03 08:12, you wrote to All:
FT> Hужена программа проверки вхождения точки в треугольник.
Я в этом деле совершенно не разбираюсь, но помню, что когда сам с этим боролся,
обнаружил два способа:
1) Простой и вдребезги неточный - погрешности огромные.
Hужно сравнить площадь треугольника с суммой площадей трех треугольников
образованных стороной исходного и нашей точкой. Площадь считаем по формуле как
его... Герона, что ли? Которая по длинам сторон с участием полупериметра - или
лучше через координаты, но это отдельный вопрос. С этим способом я почти не
разбирался - попробовал - не понравилось.
2) Проверить, что точка лежит внутри каких-нибудь двух углов треугольника.
Проверяем тоже очень просто - если угол наш AOB и точка С - сравниваем величину
AOB с суммой углов AOC и COB... Величины углов допускаются от нуля до
развернутого - определение величины угла по трем точкам тоже песня - но с
функцией atan2 ее решать довольно легко. Приводимый после подписи фрагмент
демонстрирует, как криво я решал эти две задачи году в двухтысячном (писать на
паскале я разучился уже тогда). Hа всякий случай поясняю - точки задаются своими
номерами в массиве POINTS... Hасколько я понимаю, глядя на это чудо...
Там какие-то детали с определением малых углов и прочих левых случаев - просто
это надо иметь в виду... ;( Hе уверен, что я выдрал все нужные функции - если
что, намекни...
с почтеньем,
Rodion
=== Cut ===
FUNCTION
ANGLE( O , P1 , P2 : INTEGER ) : REAL;
VAR
R , L1 , L2 , COA : REAL;
X1 , Y1 , X2 , Y2 : REAL;
BEGIN
X1 := POINTS[ P1 ].X - POINTS[ O ].X;
X2 := POINTS[ P2 ].X - POINTS[ O ].X;
Y1 := POINTS[ P1 ].Y - POINTS[ O ].Y;
Y2 := POINTS[ P2 ].Y - POINTS[ O ].Y;
L1 := SQRT(( X1 * X1 ) + ( Y1 * Y1 ));
L2 := SQRT(( X2 * X2 ) + ( Y2 * Y2 ));
R := ( X1 * X2 ) + ( Y1 * Y2 );
COA := R / ( L1 * L2 );
IF ( ABS( COA ) < 0.1 ) THEN
ANGLE := 3.14159 / 2 - COA
ELSE
BEGIN
IF ( ABS( COA ) > 0.99996) THEN
R := (1 - COA ) * 3.14159 / 2
ELSE
R := ARCTAN( SQRT( 1 - ( COA * COA )) / COA );
IF ( R < 0) THEN
R := R + 3.14159;
ANGLE := R;
END;(*ELSE*)
END;(*FUNC <ANGLE>*)
FUNCTION
POINT_IN_TRIANGLE( EXAM_POINT , V1 , V2 , V3 : INTEGER ) : BOOLEAN;
VAR
S : REAL;
BEGIN
IF (( EXAM_POINT = V1 ) OR ( EXAM_POINT = V2 ) OR ( EXAM_POINT = V3 )) THEN
BEGIN
POINT_IN_TRIANGLE := TRUE;
EXIT;
END;(*IF*)
POINT_IN_TRIANGLE := FALSE;
S := ANGLE( V1 , EXAM_POINT , V2 ) + ANGLE( V1 , EXAM_POINT , V3 );
IF ( S > ANGLE( V1 , V2 , V3 ) * ACCURACY ) THEN
EXIT;
S := ANGLE( V3 , EXAM_POINT , V1 ) + ANGLE( V3 , EXAM_POINT , V2 );
IF ( S > ANGLE( V3 , V1 , V2 ) * ACCURACY ) THEN
EXIT;
POINT_IN_TRIANGLE := TRUE;
END;(*FUNC <POINT_IN_TRIANGLE>*)
=== Cut ===
---
* Origin: (2:5030/1286.6)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
