Текущий архив: 2003.04.07;
Скачать: CL | DM;

Вниз

Геометрия, блин   Найти похожие ветки 

← →
Romkin ©   (2003-03-20 16:33) [40]

4. и 6. местами поменяй - если угол тупой, то и перпендикуляр считать не надо.
А вообще, вместо п. 2 Mbo уже сказал - гораздо проще

---

← →
nikkie ©   (2003-03-20 16:36) [41]

По поводу отрезков [A,B] и [С,D] - нужно проверить, что четырехугольник ACBD выпуклый. Проверяется знаком векторных произведений. Собственно явский алгоритм это и делает (CCW - counter clockwise).

---

← →
nikkie ©   (2003-03-20 16:41) [42]

>Romkin
Ну про то, что можно поменять местами я вроде написал. Согласен, что наиболее трудоемкие вычисления лучше в последнюю ветку засунуть.

Насчет решения Mbo - ведь придется корень считать. Не думаю, что это будет быстрее.

---

← →
nikkie ©   (2003-03-20 16:51) [43]

сорри, в формуле для h^2 потерялась 4 - делить надо на 4c^2

а вообще-то, с точки зрения количества умножений и упрощать не надо было
h^2 = a^2 - (a^2 - b^2 + c^2)^2 / 4c^2

---

← →
Merlin ©   (2003-03-20 19:44) [44]

> nikkie
Можно это записать на каком-нибудь языке программирования?

---

← →
nikkie ©   (2003-03-20 20:37) [45]

>Merlin
в стиле, принятом на этом форуме - "Можно." :))
на каком надо?

---

← →
ShaggyDoc   (2003-03-21 07:02) [46]

На всякий случай ссылка: Алгоритмы > Вычислительная геометрия

http://algolist.manual.ru/maths/geom/index.php

---

← →
Merlin ©   (2003-03-21 14:55) [47]

Всем спасибо. Особая благодарность Danilka и nikkie за присланные алгоритмы.

Тема закрыта.

P.S. Если кому пригодится, вот алгоритм пересечения окружности и отрезка от nikkie :


// function checks intersection of
// segment [A,B] and
// circle of radius R with center in (0,0)
function SegmentIntersectsCircle(Ax, Ay, Bx, By, R: Double): Boolean; overload;
var
a2, b2, c2, R2: Double;
begin
a2 := Ax * Ax + Ay * Ay;
b2 := Bx * Bx + By * By;
R2 := R * R;

if (a2 < R2) and (b2 < R2) then begin
Result := False;
end else if (a2 > R2) and (b2 > R2) then begin
if (Ax * (Ax - Bx) + Ay * (Ay - By) > 0) and
(Bx * (Bx - Ax) + By * (By - Ay) > 0) then
begin
c2 := (Ax - Bx) * (Ax - Bx) + (Ay - By) * (Ay - By);
if (4 * c2 * (a2 - R2) > (a2 - b2 + c2) * (a2 - b2 + c2)) then begin
Result := False;
end else begin
Result := True;
end;
end else begin
Result := False;
end;
end else begin
Result := True;
end;
end;

// function checks intersection of
// segment [A,B] and
// circle of radius R with center in O
function SegmentIntersectsCircle(Ax, Ay, Bx, By, Ox, Oy, R: Double): Boolean; overload;
begin
Result := SegmentIntersectsCircle(Ax - Ox, Ay - Oy, Bx - Ox, By - Oy, R);
end;


---

← →
Radionov Alexey ©   (2003-03-21 15:07) [48]

Если кому нужно, вот расстояние между отрезками (писал еще студентом, поэтому что к чему не помню. Да и пооптимизировать можно)



Function rs(x0, y0, x1, y1: extended): extended;
Begin
rs := sqrt(sqr(x0 - x1) + sqr(y0 - y1));
End;

Function StrikeToStrike(x0, y0, x1, y1, a0, b0, a1, b1: extended): extended;
Var
dx, dy, da, db, lxy, lab, t, x, y: extended;
Begin
dx := x0 - x1;
dy := y0 - y1;
da := a0 - a1;
db := b0 - b1;
lxy := sqr(dx) + sqr(dy);
lab := sqr(da) + sqr(db);
If (abs(lxy) < 1E-10) Or (abs(lab) < 1E-10) Then
Begin
result := -1;
exit;
End;
If ((a0 - x0) * dx + (b0 - y0) * dy >= 0) And ((a0 - x0) * da + (b0 - y0) * db
<= 0) Then
Begin
StrikeToStrike := rs(x0, y0, a0, b0);
Exit;
End;
If ((a1 - x1) * dx + (b1 - y1) * dy <= 0) And ((a1 - x1) * da + (b1 - y1) * db
>= 0) Then
Begin
StrikeToStrike := rs(x1, y1, a1, b1);
Exit;
End;
If ((a1 - x0) * dx + (b1 - y0) * dy >= 0) And ((a1 - x0) * da + (b1 - y0) * db
>= 0) Then
Begin
StrikeToStrike := rs(x0, y0, a1, b1);
Exit;
End;
If ((a0 - x1) * dx + (b0 - y1) * dy <= 0) And ((a0 - x1) * da + (b0 - y1) * db
<= 0) Then
Begin
StrikeToStrike := rs(x1, y1, a0, b0);
Exit;
End;

t := ((x0 - a0) * dx + (y0 - b0) * dy) / lxy;
If (t >= 0) And (t <= 1) Then
Begin
x := x0 + t * (x1 - x0);
y := y0 + t * (y1 - y0);
If (a0 - x) * da + (b0 - y) * db <= 0 Then
Begin
StrikeToStrike := rs(a0, b0, x, y);
Exit;
End;
End;
t := -((a1 - x0) * dx + (b1 - y0) * dy) / lxy;
If (t >= 0) And (t <= 1) Then
Begin
x := x0 + t * (x1 - x0);
y := y0 + t * (y1 - y0);
If (a1 - x) * da + (b1 - y) * db >= 0 Then
Begin
StrikeToStrike := rs(a1, b1, x, y);
Exit;
End;
End;

t := -((x0 - a0) * da + (y0 - b0) * db) / lab;
If (t >= 0) And (t <= 1) Then
Begin
x := a0 + t * (a1 - a0);
y := b0 + t * (b1 - b0);
If (x - x0) * dx + (y - y0) * dy >= 0 Then
Begin
StrikeToStrike := rs(x0, y0, x, y);
Exit;
End;
End;
t := -((x1 - a0) * da + (y1 - b0) * db) / lab;
If (t >= 0) And (t <= 1) Then
Begin
x := a0 + t * (a1 - a0);
y := b0 + t * (b1 - b0);
If (x - x1) * dx + (y - y1) * dy <= 0 Then
Begin
StrikeToStrike := rs(x1, y1, x, y);
Exit;
End;
End;
StrikeToStrike := 0;
End;


---

Страницы: 1 2 вся ветка

Текущий архив: 2003.04.07;
Скачать: CL | DM;

Наверх

Память: 0.55 MB
Время: 0.018 c