Přesné určení, zda/kdy/kde pohyblivá čára protíná pohyblivý bod

3 listopadu, 2021

Přesné určení, zda/kdy/kde pohyblivá čára protíná pohyblivý bod
Destinace
Intuice
Model
Řešení
Zobecnění
Souhrn
Diskutujte na Redditu
Archiv

vložil Craig Gidney 5. února 2013

Při publikování knihoven se snažím uvádět ukázkové projekty. V případě zkázonosných sbírek byla ukázkovým projektem vlastně jednoduchá hra založená na řezání čar ukazatelem myši:

V rámci psaní ukázky jsem musel vyřešit problém, jak určit, zda, kdy a kde ukazatel myši přejel přes čáru (nebo naopak). Můj obvyklý odkaz na geometrické algoritmy neobsahoval řešení, a tak jsem si ho vytvořil sám.

V tomto příspěvku budu vysvětlovat analytické řešení problému. Řešení je implementováno v malém množství zdrojového kódu (asi 150 řádků, počítám-li komentáře a podpůrné metody/typy), který je také k dispozici na githubu.

Destinace

Ukázalo se, že „přetnul ukazatel myši pohybující se čáru?“ je jeden z těch kouzelných matematických problémů, který začíná s relativně jednoduchými omezeními, pak se zdá, že se při řešení docela komplikuje, ale pak se v posledních několika krocích skoro všechno zruší nebo zkombinuje a nakonec dostanete něco absurdně jednoduchého. (Když se pak vrátíte a prohlédnete si řešení, ukáže se, že celou dobu existovala jednoduchá cesta.)

Pro referenci a motivaci sem hodím jádro implementace, než ji vysvětlím. Podtržená slova jsou odkazy na odpovídající kód na githubu.

public static IEnumerable<Sweep> WhenLineSweepsPoint(LineSegment pathOfLineStartPoint, LineSegment pathOfLineEndPoint, Point point) {var a = point - pathOfLineStartPoint.Start;var b = -pathOfLineStartPoint.Delta;var c = pathOfLineEndPoint.Start - pathOfLineStartPoint.Start;var d = pathOfLineEndPoint.Delta - pathOfLineStartPoint.Delta;return from t in QuadraticRoots(b.Cross(d), a.Cross(d) + b.Cross(c), a.Cross(c)) where t >= 0 && t <= 1 let start = pathOfLineStartPoint.LerpAcross(t) let end = pathOfLineEndPoint.LerpAcross(t) let s = point.LerpProjectOnto(new LineSegment(start, end)) where s >= 0 && s <= 1 orderby t select new Sweep(timeProportion: t, acrossProportion: s);}

Nevím jak vás, ale mě fakt, že výše uvedený kód řeší problém, udivuje. Zdá se to příliš jednoduché, a přesto příliš nesouvisející. Neměly by tam být třeba rohové případy? Navíc, kde se vzaly ty jednoduché křížové produkty? Jak pomůže jejich vložení do kvadratického polynomu? Tohle… bude potřeba vysvětlit.“

Intuice

Začněme tím, že se zamyslíme nad některými případy, se kterými se můžeme setkat, abychom získali intuitivní představu o problému. Následující animace ukazuje několik různých možných pohybů přímky:

Jednoduchý: oba koncové body se pohybují stejnou rychlostí, a to pouze podél normálového vektoru přímky.
Do strany: degenerovaný případ, kdy se přímka pohybuje po své vlastní délce.
Zvedání: jeden koncový bod se pohybuje vodorovně, zatímco druhý svisle („zvedání“ a spouštění přímky).
Potápění: jeden koncový bod se pohybuje diagonálně (‚potápí‘ se středem), zatímco druhý se pohybuje vertikálně.

Různé případy zametání

Všimněte si, že přímka může zametat bod 0, 1 nebo 2krát, protože její koncové body se pohybují konstantní rychlostí z jedné polohy do druhé. Případ „Vzestup“ příhodně obsahuje všechny tři možnosti. To je intuitivně důvod, proč řešení zahrnuje kvadratickou rovnici (která může mít 0, 1 nebo 2 různé reálné kořeny).

Dalším užitečným poznatkem je, že některým případům, jako je přímka pohybující se konstantní rychlostí nebo stojící na místě, budou odpovídat degenerované kvadratické rovnice, kde je koeficient nejvyššího řádu nulový (tj. nebo dokonce ). Tyto druhy případů musíme zahrnout do testů.

Model

Aby úsečka z do obsahovala bod , musí být splněny dvě podmínky. Za prvé, vektor „posunu“ z do musí být rovnoběžný s vektorem „delta“ z do . Matematicky to můžeme vyjádřit požadavkem, aby jejich křížový součin byl nulový: $(c-p) \krát (q-p) = 0$ . To zaručuje, že leží na přímce, kterou získáme prodloužením úsečky v obou směrech (nebo že máme degenerovanou jednobodovou úsečku). Za druhé, skalární projekce vektoru posunu na delta vektor musí být ve správném rozsahu: $0 \leq s = \frac{(c-p) \cdot (q-p)}{(q-p)^2} \leq 1$ . To zaručuje, že neprochází žádným z koncových bodů úsečky.

Pokud se čas pohybuje od do , bude naše úsečka procházet bodem tehdy a jen tehdy, pokud existuje čas , kdy aktuální úsečka obsahuje . Protože se koncové body naší úsečky pohybují konstantní rychlostí, je dráha, po které se pohybují, také úsečkou. Koncový bod pohybující se z do bude v čase v lineárně interpolovaném bodě $lerp(p_0, p_1, t) = p_0 + (p_1 - p_0) \cdot t$ . Všimněte si, že pro úsporu místa budu zkracovat jako . Dosazením našich pohybujících se bodů do vzorců ‚úsečka obsahuje bod‘ zjistíme, že musíme najít splňující $0 \leq t \leq 1$ a $(c - (p_0 + p_d \cdot t)). \krát ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t)) = 0$ a $0 \leq s = \frac{(c-(p_0 + p_d \cdot t)) \cdot ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))}{((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))^2} \leq 1$ .

Všimněte si, že „nějaký křížový součin se musí rovnat 0“ není jediný způsob, jak problém formulovat. Má také smysl uvažovat o něm jako o nalezení a , obou v rozsahu , tak, že je výsledkem lerpování obou koncových bodů přes jejich dráhu o a pak lerpování mezi koncovými body o . Matematicky to znamená . Proměnné a zhruba odpovídají tomu, „kdy“ a „kde“ dojde k průsečíku. V tomto tvaru je však řešení úlohy obtížnější, protože není zpočátku izolovaná, takže budu používat zarámování křížovým součinem (na rozdíl od toho, co jsem udělal poprvé…).

Řešení

Křížový a tečkový součin mají některé velmi pěkné vlastnosti, které usnadní izolaci . Za prvé rozdělují sčítání, což znamená, že $u \krát (v + w) = u \krát v + u \krát w$ a $u \cdot (v + w) = u \cdot v + u \cdot w$ . Za druhé, škálování může být provedeno před nebo za oběma produkty, což znamená $(c \cdot u) \times v = c \cdot (u \times v)$ a $(c \cdot u) \cdot v = c \cdot (u \cdot v)$ , kde je reálné číslo. Konečně, bodový součin je komutativní, což znamená $u \cdot v = v \cdot u$ , zatímco křížový součin je antikomutativní, což znamená $u \times v = -v \times u$ .

Při použití této znalosti součinu a při troše nadhledu, kdy víme, že s jednotlivými podvýrazy máme zacházet jako s jednotlivými proměnnými, můžeme naši rovnici s křížovým součinem, který je nulový, převést na kvadratickou rovnici:

$\begin{align*} 0 =(c - (p_0 + p_d \cdot t)) \times ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t)) \\= ((c - p_0) - p_d \cdot t) \times ((q_0 - p_0) - (q_d - p_d) \cdot t) \\= (a + b \cdot t) \times (c + d \cdot t) \\;\;\;\;\;\;\;\;kde\;\; a = c - p_0 \\;\;\;\;\;\;\;kde\;\; b = -p_d \\;\;\;\;\;\;\;\;kde\;\; c = q_0 - p_0 \\;\;\;\;\;\;\;kde\;\; d = -(q_d - p_d) \\= a \times c + a \times d \cdot t + b \times c \cdot t + b \times d \cdot t \cdot t \\= t^2 \cdot (b \times d) + t \cdot (a \times d + b \times c) + (a \times c) \end{align*}$

(Je to strašně jednodušší než cesta, kterou jsem zvolil poprvé.)

Aha, teď už je jasné, kde se vzal tvar řešení kódu. Začali jsme s křížovým součinem rovným nule (tvrdili jsme, že vektor z přímky do bodu je s přímkou rovnoběžný) a museli jsme součin rozdělit, abychom izolovali součty členů zahrnující různé mocniny . Tím přirozeně vznikla kvadratická rovnice s koeficienty zahrnujícími křížový součin. Pěkné!“

Všimněte si, že se jedná o velmi „robustní“ rovnici, protože jsme po cestě nikdy nic nepředpokládali o vektorech nebo skalárech. Například nikdy nedělíme (ani implicitně nerušíme) proměnnou, takže jsme nezavedli žádné číhající nenulové podmínky.

Při zjednodušené rovnici je určení možných hodnot jen standardní záležitostí „řešení kvadratického polynomu“. Musíme řešit rohové případy s nulami, což kód trochu komplikuje, ale je to jen nudná záležitost případ od případu, takže na ni jen odkážu.

Jakmile známe možnou hodnotu , můžeme přesně zjistit, kde ke kolizi došlo, pomocí vzorce plug-t-into-line-segment-point-containment zmíněného o kousek zpět: $s = \frac{(c-(p_0 + p_d \cdot t)) \cdot ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))}{((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))^2}$ . Tomuto vzorci říkám „lerpova projekce“ na přímku v čase , protože vrací podíl , o který je třeba lerpovat od počátečního bodu přímky do jejího koncového bodu, abychom získali zpět . Je to šikovná malá metoda pro extrakci:

public static double LerpProjectOnto(this Point point, LineSegment line) { var b = point - line.Start; var d = line.Delta; return (b * d) / (d * d); // when d == 0, result is +-infinity or NaN}

Nakonec, jakmile máme a , musíme zkontrolovat, zda jsou v rozsahu . Pokud je mimo rozsah, pak v aktuálním časovém kroku ke kolizi nedojde. Pokud je mimo rozsah, pak ke kolizi dojde na prodloužené přímce, ale ne na úsečce. Protože a popisují, jak moc se má lerpovat, aby se zjistilo, kdy/kde došlo ke kolizi, je to také užitečná informace, kterou je třeba vrátit volajícímu.

Zobecnění

Důležitý detail, který jsem ještě nezmínil, je, že pohybující se ukazatel myši samozřejmě neodpovídá bodu. Naštěstí můžeme pohyb ukazatele myši v posledním časovém kroku (za předpokladu, že je lineární) jednoduše zrušit odečtením od pohybu úsečky. Nejenže se tím soustava zredukuje na řešitelnou, ale výsledné hodnoty a jsou platné bez jakékoliv inverzní transformace. Použití vypadá takto:

// time goes from t0 to t1// line segment endpoint 1 moves from p0 to p1// line segment endpoint 2 moves from q0 to q1// point moves from c0 to c1var results = from hit in WhenLineSweepsPoint(new LineSegment(p0 - c0, p1 - c1), new LineSegment(q0 - c0, q1 - c1), new Point(0, 0)) let hitPos = new LineSegment(c0, c1).LerpAcross(hit.TimeProportion) let hitTime = t0 + (t1-t0)*hit.TimeProportion select new { p = hitPos, t = hitTime }foreach (var result in results) { System.Diagnostics.Debug.WriteLine(string.Format("Hit at p={0}, t={1}", result.p, result.t);}

Potenciální komplikací jsou degenerované úsečky, které nemají žádnou délku (kde jsou oba koncové body stejné). Kód tento případ explicitně neřeší, ale bude se chovat, jako by řezání úsečky, která je ve skutečnosti bodem, nebylo možné. Výpočet , pokud k němu dojde, se vydělí nulou. Výsledek (buď -nekonečno, +nekonečno, nebo NaN) neprojde kontrolou rozsahu.

Dalším aspektem, kterým jsem se nezabýval, je „úhel řezu“. V animaci, která ukazuje různé případy, jsou červené řezy orientovány lerpingem mezi rychlostmi dvou koncových bodů o (když je výsledná rychlost 0, je zvolen náhodný úhel). Použil jsem však i alternativní přístupy typu „úhel řezu je rychlost bodu“. V podstatě jde o to použít to, co vypadá dobře a je přirozené, místo abyste se snažili přijít na skutečný význam „úhlu řezu“.

Souhrn

Tento problém se stane triviálním, jakmile použijete některé znalosti z lineární algebry. To asi není příliš překvapivé, protože lineární algebra (a polynomy) se objevují všude, zejména v geometrii.

Přirozeným zobecněním tohoto problému je zahrnutí tlouštěk. Čáry nakreslené na obrazovkách přece nejsou nekonečně tenké. Mít tloušťku je také dobrý způsob, jak snížit vliv chyb s plovoucí desetinnou čárkou, které se zaokrouhlují v různých směrech během různých časových kroků. Další užitečnou změnou by byla možnost zpracovávat parabolické cesty, protože herní objekty často padají volným pádem. Na druhou stranu je asi jednodušší považovat „tlusté čáry“ za polygony s časovými kroky s konstantní rychlostí.

–

Diskutujte na Redditu

–

Twisted Oak Studios nabízí konzultace a vývoj špičkových interaktivních projektů. Podívejte se na naše portfolio nebo nám dejte vědět, pokud máte něco, s čím by vám měli pomoci nějací opravdu radikální inženýři.

Savage Rose

Přesné určení, zda/kdy/kde pohyblivá čára protíná pohyblivý bod | Twisted Oak Studios Blog