геометрия

← →
~Aid~ (2006-10-22 19:45) [0]

даны четыре точки типа TPoint
подскажите какой алгоритм использовать чтобы определить, является ли фигура построенная на этих 4 точках квадратом?

← →
Eraser © (2006-10-22 19:47) [1]

> [0] ~Aid~ (22.10.06 19:45)

длины всех линий должны быть равны, и хотя бы один угол должен равняться 90 гр.

← →
~Aid~ (2006-10-22 19:52) [2]

а можно готовым алгоритмом?описанным на Delphi

← →
Eraser © (2006-10-22 19:54) [3]

> [2] ~Aid~ (22.10.06 19:52)

у меня нету.
алгоритм я уже сказал, а как его реализовать - см. справочник математики, раздел про вектора.

← →
~Aid~ (2006-10-22 19:59) [4]

найдите в неем ошибку

function square(a,b,c,d:Tpoint):boolean;
begin
if ((rs(a,c)=rs(b,d)) and (rs(a,b)=rs(c,d)) and (rs(a,d)=rs(b,c)) and (abs(sl(a,b,c,d))<pogr))
or (abs(sl(a,d,b,c))<pogr) or (abs(sl(a,c,b,d))<pogr) then square:=true
else square:=false;
end;

где function rs(a,b:TPoint):double;
begin
rs:=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
end;

function sl(a,b,c,d:Tpoint):double;
begin
sl:=(b.x-a.x)*(c.x-d.x)+(b.y-a.y)*(c.y-d.y);
end;

← →
guav © (2006-10-22 19:59) [5]

Самый понятный - это без углов, четыре стороны равны и две диагонали равны.
Самое быстрое думаю будет если при повороте на 90* одного вектора стороны получаем другой и так для всех четырёх или то же самое для -90*.
Поворот на 90* newX := -Y; newY := X;

← →
~Aid~ (2006-10-22 20:06) [6]

guav
поподробнее с повоотом?

учти что вся геометрия решается с определенной точностью

← →
guav © (2006-10-22 20:09) [7]

Что-то вроде этого (не проверял, удивлюсь если работает).
function IsTurned90Degrees(const A, B, C: TPoint): Boolean; begin Result := ((B.X - C.X) = -(B.Y - A.Y)) and ((B.Y - C.Y) = (B.X - A.X)); end; function IsSquare(const A, B, C, D: TPoint): Boolean; begin Result := (IsTurned90Degrees(A, B, C) and IsTurned90Degrees(B, C, D)) or (IsTurned90Degrees(C, B, A) and IsTurned90Degrees(D, C, B)); end;

> учти что вся геометрия решается с определенной точностью

Т.е. приблизительно квадрат тоже должен быть квадратом ?

← →
~Aid~ (2006-10-22 20:11) [8]

Т.е. приблизительно квадрат тоже должен быть квадратом ?

да.. то есть сам понимаешь округление. расстояния могут не быть равными а вектора при повороте не давать нужных векторов

← →
Anatoly Podgoretsky © (2006-10-22 20:15) [9]

Математический сопроцессор имеет ограниченную точно, на что постоянно нарываются, как на садовые грабли. Поэтому квадрат в программирование всегда приблизителен, кроме редких случаев

← →
guav © (2006-10-22 20:16) [10]

> [8] ~Aid~ (22.10.06 20:11)

Тогда

> ((rs(a,c)=rs(b,d)) and (rs(a,b)=rs(c,d)) and (rs(a,d)=rs(b,
> c))

здесь тоже нужно сравнивать учитывая эпсилон.

кстати, такой код не годился бы даже если требовалось бы определять только точные квадраты.

← →
guav © (2006-10-22 20:18) [11]

> [9] Anatoly Podgoretsky © (22.10.06 20:15)

У меня точный, если конечно работает :-)

← →
~Aid~ (2006-10-22 20:21) [12]

я знаю что мой не годится....
вот и ищу...

проверь свой плиз

> [12] ~Aid~ (22.10.06 20:21)

Мой таки работает, но только для точных квадратов пиксель в пискель.
Ошибка у меня есть, что все вычитания в скобках должны быть наоборот, но она компенсирует сама себя.

У тя ошибка в том что ((rs(a,c)=rs(b,d))
надо ((rs(a,c)-rs(b,d)<pogr) . Может ещё где ошибки есть

Почитай http://www.delphikingdom.com/asp/viewitem.asp?catalogid=374 .

← →
~Aid~ (2006-10-22 20:40) [14]

guav да у тебя все работает все хорошо

спасибо большое что помог.

> Самый понятный - это без углов, четыре стороны равны и две
> диагонали равны.

Сне вот этот метод понравился. Нужна функция:
function LineLength(Point1, Point2: TPoint): Double;
она просто расчитывает длинну линии от точки до точки.

А потом в нее подставляй и сё.
Квадрат такой:
Point1 Point2 Point3 Point4

четыре стороны равны:
LineLength(Point1, Point2) - LineLength(Point3, Point4) = Inaccuracy LineLength(Point1, Point3) - LineLength(Point2, Point4) = Inaccuracy

Ну и так далее....

и вместо углов можно проверять равентсво диагоналей

В данной задаче для проверки равенства длин экономнее проверять равенство квадратов длин.
Интересно во сколько раз больше времени требуется сопроцессору для вычисления квадратного корня, чем для вычисления квадрата. Никто не в курсе? Может быть одно и то же время будет? Или сильно зависит от модели?

Я померял у меня получилось 6016 для извлечения квадратов и 3266 для возведения в квадрат, т. е. раза в два.

геометрия Найти похожие ветки