Геометрия, блин

← →
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;

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