Object (Particle), N Position: s = (s.x, s.y) [(m,m)] (s = station) Velocity: v = (v.x, v.y) [(m/s, m/s)] Speed: s = v.r [m,s] (r = Radius in Polarkoord. = length) Acceleration: a = (a.x, a.y) [(m/s²m/s²)] Mass: m [kg], m≠0 Inverse Mass 1/m [1/kg], m=∞ => 1/m=0 Momentum: p=mv [(kg*m/s, kg*m/s)] (Impulse) Damping: damp (e.g. air drag) reduces speed, a little bit of drag may be needed to overcome numerical inaccuracy Newton: First Law When there are no forces acting on an object, the momentum p=mv of the object does not change. Consequently, if, as usual, the mass does not change, the velocity does not change as well. Newton: Second Law F = ma = mv' = ms'' = p' , s'' = F/m: A force acting on an object changes the acceleration of the object. Neither the position nor the velocity can be changed directly! S'Alambert's principle: f sum f_i Newton: Third Law When a first body exerts a force F1 on a second body, the second body simultaneously exerts a force F2 = −F1 on the first body. (http://en.wikipedia.org/wiki/Newton%27s_laws_of_motion) Gravity: f = G*m1*m2/r² m1, m2 are the masses of two objects, r is the distance of these objects, and G is the universal gravitational constant. Earth: G, m_earth are constant, r is also constant (due to the huge distance): g=G*m_earth/r² = 9.81 m/s² f=m*g, s'' = f/m = g Orientation2D ============= vgl. C. Ericson, Real-Time Collision Detection, p. 32 https://de.serlo.org/mathe/geometrie/analytische-geometrie/flaechen-volumenberechnung/flaechenberechnung-der-analytischen-geometrie/flaechenberechnung-der-analytischen-geometrie Es seien a, b und c drei 2D-Vektoren. Orientation2D berechnet vorzeichenbehaftet die doppelte Fläche des Dreickes abc (b-a ist eine Seite, c-a die zweite Seite, c-b die dritte). Das heißt, es wird (vorzeichenbehaftet) die Fläche des Paralellogramms a,b,c,d berechnet, wobei d = (b-a)+(c-a) = b-c-2a. Das Vorzeichen gibt die Anordnung der Punkte an: Orientation2D(a,b,c) > 0 => c liegt links von dem gerichteten Vektor [ab], die Punkte des Dreiecks [abc] sind gegen den Uhrzeigersinn angeordnet Orientation2D(a,b,c) < 0 => c liegt rechts von dem gerichteten Vektor [ab], die Punkte des Dreiecks [abc] sind im Uhrzeigersinn angeordnet Orientation2D(a,b,c) = 0 => c liegt auf der Geraden [ab] oder a=b |a_x a_y 1| Orientation2D(a,b,c) = |b_x b_y 1| |c_x c_y 1| = |a_x-c_x a_y-c_y| |b_x-c_x b_y-c_y| = (a_x-c_x)*(b_y-c_y)-(b_x-c_x)*(a_y-c_y) Prüfung: Orientation2D(a,b,c) = a_x*b_y*1 + a_y*1*c_x + 1*b_x*c_y - 1*b_y*c_x - a_y*b_x*1 - a_x*1*c_y = a_x*b_y + a_y*c_x + b_x*c_y - b_y*c_x - a_y*b_x - a_x*c_y = a_x*b_y - a_x*c_y + a_y*c_x - b_y*c_x + b_x*c_y - a_y*b_x = a_x*b_y - a_x*c_y + c_x*a_y - c_x*b_y + c_x*c_y - c_x*c_y - b_x*a_y + b_x*c_y = a_x*b_y - a_x*c_y - c_x*b_y + c_x*c_y + c_x*a_y - c_x*c_y - b_x*a_y + b_x*c_y = a_x*(b_y-c_y) - c_x*(b_y-c_y) - b_x*(a_y-c_y) + c_x*(a_y-c_y) = (a_x-c_x)*(b_y-c_y)-(b_x-c_x)*(a_y-c_y) Orientation2D(a,b,c) = -Orientation2D(a,c,b) Orientation2D(a,b,c) = Orientation2D(b,c,a) = Orientation2D(c,a,b) Orientation2D(a,c,b) = Orientation2D(c,b,a) = Orientation2D(b,a,c) Beweis: Die Orientierung der Punkte ändert sich im 1. Fall, in den beiden anderen nicht. 1. Fall explizit: Orientation2D(a,b,c) = (a_x-c_x)*(b_y-c_y)-(b_x-c_x)*(a_y-c_y) = a_x*(b_y-c_y) - c_x*(b_y-c_y) - b_x*(a_y-c_y) + c_x*(a_y-c_y) = a_x*b_y - a_x*c_y - c_x*b_y + c_x*c_y - b_x*a_y + b_x*c_y + c_x*a_y - c_x*c_y = a_x*b_y - a_x*c_y - c_x*b_y - b_x*a_y + b_x*c_y + c_x*a_y = - a_x*c_y + a_x*b_y + b_x*c_y + c_x*a_y - c_x*b_y - c_x*a_y = - a_x*c_y + a_x*b_y + b_x*c_y - b_x*b_y + c_x*a_y - c_x*b_y - b_x*a_y + b_x*b_y = - a_x*(c_y-b_y) + b_x*(c_y-b_y) + c_x*(a_y-b_y) - b_x*(a_y-b_y) = -(a_x-b_x)*(c_y-b_y)+(c_x-b_x)*(a_y-b_y) = -Orientation2D(a,c,b) Schnittpunkt zweier Geraden/Strecken ==================================== vgl. C. Ericson, Real-Time Collision Detection, p. 151 g1 = [ab], g2 = [cd], n = Normale von [cd], n = (d_y-c_y, c_x-d_x) Geradengleichungen: g1: a+t*(b-a) (Parameterform) g2: n*(x-c)=0 (Normalengleichung) Berechnung von t für den Schnittpunkt von g1, g2: n*((a+t*(b-a))-c) = 0 <=> n*(a-c) + t*n(b-a) = 0 <=> t*n(b-a) = n*(c-a) <=> t = n*(c-a)/n*(b-a) falls n*(b-a) != 0 <=> t = Orientation2D(cda)/(Orientation2D(cda)-Orientation2D(cdb)) falls Orientation2D(cda)-Orientation2D(cdb) != 0 (Beweis: nachfolgend) Schnittpunkt: p=a+t*(b-a), wobei t wie zuvor berechnet wird Die letzte Formel kann auch wie folgt bewiesen werden: Es seien h1 die Höhe des Punktes a über der Strekce [bc] sowie h2 die Höhe des Punktes a über der Strekce [bc] a | /| h1 | t / | h1 | / | c ------------------- d h2 | / |/ b Dann verhält sich gemäß dem Satz der zentrischen Streckung h1 zu (h1+h2) wie t zu Gesamtlänge l der Strecke [ab]: t/l = h1/(h1+h2) In der Parameterform ist l = 1. Das heißt: t = h1/(h1+h2) Fläche des Dreiecks cda: |[cd]|*h1/2 = +-Orientation(cda)/2 (+- = plus oder minus) Fläche des Dreiecks cdb: |[cd]|*h2/2 = -+Orientation(cdb)/2 (-+ = minus oder plus) Da sich a und b auf verschiedenen Seiten von [cd] befinden, unterscheiden sich die Vorzeichen von Orientation(cda) und Orientation(cdb). => h1 = Orientation(cda)/|[cd]| oder h1 = -Orientation(cda)/|[cd]| h2 = -Orientation(cdb)/|[cd]| h2 = Orientation(cdb)/|[cd]| kurz h1 = +-Orientation(cda)/|[cd]| h2 = -+Orientation(cdb)/|[cd]| => t = h1/(h1+h2) = (+-Orientation(cda)/|[cd]|)/(+-Orientation(cda)/|[cd] -+ Orientation(cdb)/|[cd]|) = +-Orientation(cda) / (+-Orientation(cda) -+ Orientation(cdb)) = Orientation(cda) / (Orientation(cda) - Orientation(cdb)) Direkter Beweis, dass (falls n*(b-a) != 0) t = n*(c-a)/n*(b-a) <=> t = Orientation2D(cda)/(Orientation2D(cda)-Orientation2D(cdb)) n*(c-a) = (d_y-c_y) * (c_x-a_x) (c_x-d_x) (c_y-a_y) = (d_y-c_y)*(c_x-a_x) + (c_x-d_x)*(c_y-a_y) = (d_y-c_y)*(c_x-a_x) - (d_x-c_x)*(c_y-a_y) = d_y*(c_x-a_x) - c_y*(c_x-a_x) - d_x*(c_y-a_y) + c_x*(c_y-a_y) = d_y*c_x - d_y*a_x - c_y*c_x + c_y*a_x - d_x*c_y + d_x*a_y + c_x*c_y - c_x*a_y = d_y*c_x - d_y*a_x + c_y*a_x - d_x*c_y + d_x*a_y - c_x*a_y = c_x*d_y - c_x*a_y - a_x*d_y - d_x*c_y + d_x*a_y + a_x*c_y = c_x*d_y - c_x*a_y - a_x*d_y + a_x*a_y - d_x*c_y + d_x*a_y + a_x*c_y - a_x*a_y = c_x*(d_y-a_y) - a_x*(d_y-a_y) - d_x*(c_y-a_y) + a_x*(c_y-a_y) = (c_x-a_x)*(d_y-a_y) - (d_x-a_x)*(c_y-a_y) = Orientation2D(cda) = (a_x-c_x)*(b_y-c_y)-(b_x-c_x)*(a_y-c_y) n*(b-a) = (d_y-c_y) * (b_x-a_x) (c_x-d_x) (b_y-a_y) = (d_y-c_y)*(b_x-a_x) + (c_x-d_x)*(b_y-a_y) = d_y*(b_x-a_x) - c_y*(b_x-a_x) + c_x*(b_y-a_y) - d_x*(b_y-a_y) = c_x*(b_y-a_y) + d_y*(b_x-a_x) - d_x*(b_y-a_y) - c_y*(b_x-a_x) = c_x*b_y - c_x*a_y + d_y*b_x - d_y*a_x + - d_x*b_y + d_x*a_y - c_y*b_x + c_y*a_x = - c_x*a_y - a_x*d_y + d_x*a_y + a_x*c_y + c_x*b_y + b_x*d_y - d_x*b_y - b_x*c_y = c_x*d_y - c_x*a_y - a_x*d_y + a_x*a_y - d_x*c_y + d_x*a_y + a_x*c_y - a_x*a_y - c_x*d_y + c_x*b_y + b_x*d_y - a_x*b_y + d_x*c_y - d_x*b_y - b_x*c_y + a_x*b_y = c_x*(d_y-a_y) - a_x*(d_y-a_y) - d_x*(c_y-a_y) + a_x*(c_y-a_y) - c_x*(d_y-b_y) + b_x*(d_y-b_y) + d_x*(c_y-b_y) - b_x*(c_y-b_y) = (c_x-a_x)*(d_y-a_y)-(d_x-a_x)*(c_y-a_y) - (c_x-b_x)*(d_y-b_y)+(d_x-b_x)*(c_y-b_y) = Orientation2D(cda)-Orientation2D(cdb) Spezialfall: Orientation2D(abc) = 0, a != b => c liegt auf [ab]. Berechnung von t, so dass c = a + t*(b-a), falls a, b, c kolinear sind, d.h., falls (c-a)=s*(b-a) t = |c-a|/|b-a| = sqrt(|c-a|²/|b-a|²) -- nur eine Wurzeloperation (c-a)(b-a) t = ---------- (b-a)(b-a) Beide Formeln stimmen überein, falls das Ergebnis positiv ist. Die erste Formel liefert immer nur ein positives Ergebnis, unabhängig davon, ob c von a aus gesehen auf derselben Seite wie b liegt oder nicht. Die zweite Formel unterscheidet beide Fälle: Komplizierter Beweis: sqrt(|c-a|²) t = ------------ sqrt(|b-a|²) sqrt((c-a)(c-a)) sqrt((b-a)(b-a)) = ----------------*---------------- sqrt((b-a)(b-a)) sqrt((b-a)(b-a)) sqrt((c-a)(c-a)*(b-a)(b-a)) = --------------------------- sqrt((b-a)(b-a)*(b-a)(b-a)) (*)sqrt((c-a)(b-a)*(c-a)(b-a)) Skalar- und reeles Produkt kommutieren nicht, = -------------------------- allerdings sind die beiden Zähler gleich, wenn sqrt((b-a)(b-a)*(b-a)(b-a)) (c-a) und (b-a) kolinear sind, d.h, wenn (c-a) = s*(b-a); das ist laut Voraussetzung der (c-a)(b-a) Fall = +- ---------- (b-a)(b-a) uu*vv = (ux*ux+uy*uy)*(vx*vx+vy*vy) = ux*ux*vx*vx + ux*ux*vy*vy + uy*uy*vx*vx + uy*uy*vy*vy = != != = = ux*vx*ux*vx + ux*vx*uy*vy + uy*vy*ux*vx + uy*vy*uy*uy uv*uv = (ux*vx+uy*vy)*(ux*vx+uy*vy)) ux*ux*vy*vy + uy*uy*vx*vx - ux*vx*uy*vy - uy*vy*ux*vx = ux*vy*(ux*vy-vx*uy) + uy*vx*(uy*vx-vy*ux) = ux*vy*(ux*vy-vx*uy) - uy*vx*(ux*vy-vx*uy) = (ux*vy-uy*vx)*(ux*vy-vx*uy) = (ux*vy-uy*vx)² = 0 genau dann, wenn ux*vy = uy*vx. (c-a) und (b-a) sind kolinear, es gilt also (c-a)=s*(b-a) (Es gilt sogar s=t, das ist hier aber unwichtig.) (cx-ax)(by-ay) = s*(bx-ax)(by-ay) = s*(by-ay)(bx-ax) = (cy-ay)(bx-ax) => Die Gleichung (*) ist erfüllt. Einfacherer Beweis: Es sei c-a = s*(b-a) sowie s > 0, dann gilt (und es gilt s = t): (c-a)(b-a) t = |c-a|/|b-a| = s = ---------- (b-a)(b-a) t = |c-a|/|b-a| = sqrt((c-a)(c-a))/sqrt((b-a)(b-a)) = sqrt(s*(b-a)*s*(b-a))/sqrt((b-a)(b-a)) = sqrt(s²)*sqrt((b-a)(b-a))/sqrt((b-a)(b-a)) = +-s D.h, wenn s > 0, gilt s = t. (c-a)(b-a) s(b-a)(b-s) t = ---------- = ---------- = s (b-a)(b-a) (b-a)(b-a) Die zweite Gleichung ist besser: t = s gilt immer. Die erste Gleichung erfüllt nur die Bedingung: t = +-s --------------------- function intersecSegments(a, b, c, d) { if (a.isEqualTo(b)) { if (a.isEqualTo(c) || a.isEqualTo(d)) return true; //{t: 0, p: a.clone()}; else return false; } if (c.isEqualTo(a)) return true; // {t: 0, p: c.clone()}; if (c.isEqualTo(b)) return true; // {t: 1, p: c.clone()}; if (d.isEqualTo(a)) return true; // {t: 0, p: d.clone()}; if (d.isEqualTo(b)) return true; // {t: 1, p: d.clone()}; if (c.isEqualTo(d)) return false; // Now: a!=b && c!=d const c_abc = orientation(a, b, c), c_abd = orientation(a, b, d); if (c_abc*c_abd < -EPSILON) // c and d are on different sides of [ab] { const c_cda = orientation(c, d, a), c_cdb = orientation(c, d, b); //c_cdb = c_cda - c_abd - c_abc; // as c_abd - c_abc = c_cda - c_cdb; if (c_cda*c_cdb < -EPSILON) // a and b are on different sides of [cd] { //const t = c_cda/c_abd; return true; // {t: t, p: a.add(b.subtract(a), t)}; } else if (Math.abs(c_cda) <= EPSILON) // a lies on bc return true; // {t: 0, p: a.clone()}; else if (Math.abs(c_cdb) <= EPSILON) // b lies on bc return true; // {t: 1, p: b.clone()}; } else if (Math.abs(c_abc) <= EPSILON) // c (and perhaps d, too) lies on ab { const b_sub_a = b.subtract(a); return true; // {t: b_sub_a.dot(c.subtract(a))/b_sub_a.rSqr, p: c.clone()} } else if (Math.abs(c_abd) <= EPSILON) // d lies on ab { const b_sub_a = b.subtract(a); return true; // {t: b_sub_a.dot(d.subtract(a))/b_sub_a.rSqr, p: d.clone()} } return false; }