Share
In mijn vorige zelfstudie over botsingsdetectie tussen een cirkel en een lijn bedekte ik de projectie op een lijn met behulp van het puntproduct van een vector. In deze zelfstudie zullen we het product met de loodrechte punt bekijken en gebruiken om het snijpunt voor twee lijnen te voorspellen.
Laten we eens kijken naar het uiteindelijke resultaat waar we naartoe zullen werken. Gebruik de linker en rechter pijltjestoetsen om het schip te besturen (driehoek) en druk op om de snelheid tijdelijk te verhogen. Als het geprojecteerde toekomstige botspunt op de muur (de lijn) ligt, wordt er een rode stip op geschilderd. Voor een botsing die "al" gebeurde (dat wil zeggen in het verleden gebeurd zou zijn, gebaseerd op de huidige richting), zal een rode stip nog steeds worden geschilderd maar enigszins transparant.
Je kunt ook met de muis klikken en de zwarte stippen verslepen om de muur te verplaatsen. Merk op dat we niet alleen de locatie van de botsing voorspellen, maar ook de tijd.
Voordat we met het onderwerp aan de slag gaan, laten we het een beetje herzien. Dit is de vergelijking van puntproducten (hier eerder behandeld):
En hier is de productbeschrijving van de loodrechte punt zoals geëxtraheerd uit Wolfram:
Om ons te helpen een mentale foto te maken, heb ik de onderstaande afbeelding voorbereid. Ik heb er vertrouwen in dat je in staat bent om de verticale en horizontale componenten van een vector af te leiden, dus de componenten met betrekking tot sinus en cosinus zouden geen uitdaging moeten zijn.
Laten we beide componenten vervangen door hun equivalent. Ik heb A met een hoed gebruikt om de eenheidsvector van A weer te geven (dat wil zeggen, een vector die in dezelfde richting wijst als A, maar een grootte heeft van exact 1). Een ander detail is dat de loodlijn van B eigenlijk de juiste normaal van B is - meer over normaal volgende stap.
Uit het bovenstaande schema kunnen we zien dat de projectie van B on A zal produceren | B | * cos (theta). Maar waarom zou de projectie van de normale producten van B zijn | B | * sin (theta)?
Om dit beter te begrijpen, heb ik hieronder een Flash-demo opgenomen. Klik en sleep de zwarte pijlpunt. Terwijl u het zachtjes verplaatst, zult u merken dat ook de loodrechte as volgt. Terwijl ze draaien, worden de vetgedrukte rode lijnen ook geanimeerd. Merk op dat deze twee lengten hetzelfde zijn - vandaar de vergelijking van het loodrechte puntproduct.
Normalen liggen per definitie op een verticale lijn die uw interessegebied kruist. Laten we ons deze lijnen op een geometrisch vlak voorstellen.
Het cartesiaanse coördinatenstelsel wordt gebruikt in het bovenstaande schema. B is de linker normaal en C is de juiste normaal. We zien dat de x-component van B negatief is (omdat deze naar links wijst) en dat de y-component van C negatief is (omdat deze naar beneden wijst).
Maar kijk eens naar de overeenkomsten tussen B en C. Hun x- en y-componenten zijn hetzelfde als die van A, behalve swizzled. Het verschil is alleen de positie van het bord. Dus we komen tot een conclusie door de afbeelding hieronder.
Merk op dat we specifiek verwijzen naar de cartesiaanse coördinatensysteem in dit voorbeeld. De y-as van Flash's coördinaatruimte is een reflectie van die in Cartesian, resulterend in een wissel tussen de linker en rechter normaal.
Om het punt van botsing van vector k op vlak A te berekenen, zullen we de staart van k met een willekeurig punt op vlak A eerst. Voor het onderstaande geval is vector j de verbindingsvector; dan krijgen we de loodrechte projectie van k en j op vlak A.
De rode stip op de afbeelding hieronder is het botspunt. En ik hoop dat je de vergelijkbare driehoek in het onderstaande diagram kunt zien.
Dus gezien de drie bovenstaande componenten, kunnen we het begrip ratio gebruiken om de lengte tussen de rode en blauwe punten af te leiden. Ten slotte stellen we de grootte van vector k in op de genoemde lengte en hebben we ons aanvaringspunt!
Dus hier komt de ActionScript-implementatie. Ik heb hieronder een demo opgenomen. Probeer de pijlpunten te verplaatsen zodat beide lijnen elkaar kruisen. Een klein zwart puntje markeert het snijpunt van de lijnen. Merk op dat deze segmenten niet noodzakelijkerwijs elkaar snijden, maar de oneindige lijnen die ze vertegenwoordigen zijn.
Dit is het script dat de berekeningen uitvoert. Uitchecken Basic.as in de brondownload voor het volledige script.
hercalculatie van persoonlijke functies (): void reorient (); / * Leg uit: * v1 & v2 zijn vectoren die beide lijnsegmenten * v1 joins set1b (tail) tot set1a (head) voorstellen - analoog aan vector k in diagram * v2 joins set2b (tail) to set2a (head) * toV2b is vector analoog aan die van vector j in diagram * / var perp1: Number = v1.perpProduct (v2.normalise ()); var toV2b: Vector2D = nieuwe Vector2D (set2b.x - set1b.x, set2b.y - set1b.y); var perp2: Number = toV2b.perpProduct (v2.normalise ()); / * Leg uit: * de lengte wordt berekend aan de hand van de vergelijkbare driehoeksverhouding * deze wordt later gebruikt als magnitude voor een vector * die in de richting van v1 wijst * / var length: Number = perp2 / perp1 * v1.getMagnitude (); var length_v1: Vector2D = v1.clone (); length_v1.setMagnitude (lengte); / * Leg uit * uit om de exacte locatie van het botspunt te vinden * / intersec.x = set1b.x + length_v1.x; intersec.y = set1b.y + length_v1.y;
Dus ik hoop dat de eerste benadering die ik heb gepresenteerd gemakkelijk te begrijpen was. Ik begrijp dat prestaties bij het verkrijgen van het kruispunt belangrijk zijn, dus daarna zal ik alternatieve benaderingen bieden, hoewel dat enige wiskundige herzieningen vereist. Draag met me mee!
Laten we eerst praten over lijnvergelijkingen. Er zijn verschillende vormen van lijnvergelijking, maar we zullen er slechts twee in deze tutorial aanraken:
Ik heb de onderstaande afbeelding toegevoegd om je te helpen herinneren. Geïnteresseerden kunnen verwijzen naar dit bericht op Wikipedia.
Voordat we manipulaties op twee-lijnsvergelijkingen uitvoeren, moeten we eerst deze lijnvergelijkingen afleiden. Laten we het scenario bekijken waarin we coördinaten van twee punten krijgen p1 (a, b). en p2 (c, d). We kunnen een lijnvergelijking vormen die deze twee punten verbindt met de gradiënten:
Vervolgens kunnen we met behulp van deze vergelijking de constanten A, B en C voor de standaardvorm afleiden:
Vervolgens kunnen we overgaan tot het oplossen van simultane lijnvergelijkingen.
Nu we lijnvergelijkingen kunnen maken, kunnen we twee lijnvergelijkingen maken en ze simultaan oplossen. Gegeven deze twee-lijnsvergelijkingen:
Ik zal deze coëfficiënten indelen volgens de algemene vorm Ax + By = C.
| EEN | B | C |
| E | F | G |
| P | Q | R |
Om de waarde van y te verkrijgen, doen we het volgende:
| EEN | B | C | Vermenigvuldigen met |
| E | F | G | P |
| P | Q | R | E |
En we komen aan de volgende tafel.
| EEN | B | C |
| EP | FP | GP |
| PE | QE | OPNIEUW |
Nadat we twee vergelijkingen hebben afgetrokken, komen we aan bij:
Verder gaan om x te verkrijgen:
| EEN | B | C | Vermenigvuldigen met |
| E | F | G | Q |
| P | Q | R | F |
We komen aan de volgende tafel
| EEN | B | C |
| EQ | FQ | GQ |
| PF | QF | RF |
Nadat we de twee vergelijkingen hebben afgetrokken, komen we aan bij:
Laten we verder herschikken.
We komen dus op het kruispunt van x en y. We merken dat ze dezelfde noemer delen.
Nu we de wiskundige bewerkingen hebben uitgewerkt en het resultaat hebben gekregen, hoef je alleen waarden in te pikken en hebben we het snijpunt.
Dit is de Actionscript-implementatie. Alle vectorbewerkingen zijn dus teruggebracht tot eenvoudige rekenkundige bewerkingen, maar in eerste instantie zijn hiervoor enkele algebra-bewerkingen nodig.
hercalculatie van persoonlijke functies (): void reorient (); var E: Number = set1b.y - set1a.y; var F: Number = set1a.x - set1b.x; var G: Number = set1a.x * set1b.y - set1a.y * set1b.x; var P: Number = set2b.y - set2a.y; var Q: Number = set2a.x - set2b.x; var R: Number = set2a.x * set2b.y - set2a.y * set2b.x; var noemer: Number = (E * Q - P * F); intersec.x = (G * Q - R * F) / noemer; intersec.y = (R * E - G * P) / noemer;
Natuurlijk is het hetzelfde resultaat als vorige demo, alleen met minder wiskunde en zonder gebruik van de Vector2D klasse.
Een ander alternatief voor het oplossen van dit probleem is het gebruik van matrix-wiskunde. Nogmaals, ik nodig geïnteresseerde lezers uit om in de lezing van prof. Wildberger over vergelijkingen van lijnen te duiken. Hier gaan we snel door het concept heen.
Volgens Prof Wildberger zijn er twee raamwerken die we kunnen adopteren:
Laten we eerst door de Cartesiaanse gaan. Bekijk de afbeelding hieronder.
Merk op dat matrix T en S constante waarden bevatten. Wat onbekend is gebleven, is A. Dus het herschikken van de matrixvergelijking in termen van A geeft ons het resultaat. We moeten echter de inverse matrix van T krijgen.
Hier is de implementatie van het bovenstaande met ActionScript:
hercalculatie van persoonlijke functies (): void reorient (); var E: Number = set1b.y - set1a.y; var F: Number = set1a.x - set1b.x; var G: Number = set1a.x * set1b.y - set1a.y * set1b.x; var P: Number = set2b.y - set2a.y; var Q: Number = set2a.x - set2b.x; var R: Number = set2a.x * set2b.y - set2a.y * set2b.x; var T: Matrix = nieuwe matrix (E, P, F, Q); T.invert (); var S: Matrix = nieuwe matrix (); S.a = G; S.b = R; S.concat (T); // vermenigvuldiging van de matrix intersec.x = S.a; intersec.y = S.b;
Ten slotte is er de parametrische vorm van de lijnvergelijking en zullen we proberen deze opnieuw op te lossen door middel van matrix wiskunde.
We willen graag het snijpunt krijgen. Gegeven alle informatie behalve voor u en v die we proberen te vinden, zullen we beide vergelijkingen in matrixvorm herschrijven en oplossen.
Dus nogmaals, we voeren matrixmanipulaties uit om tot ons resultaat te komen.
Dus hier is de implementatie van het matrixformulier:
rivate functie herberekening (): void reorient (); / * Leg uit: * r, s verwijzen eigenlijk naar componenten van v2 genormaliseerd * p, q verwijzen eigenlijk naar componenten van v1 genormaliseerd * / var norm_v2: Vector2D = v2.normalise (); var norm_v1: Vector2D = v1.normalise (); var a_c: Number = set1b.x - set2b.x; var b_d: Number = set1b.y - set2b.y; var R: Matrix = nieuwe matrix; R.a = norm_v2.x; R.c = norm_v1.x; R.b = norm_v2.y; R.d = norm_v1.y; R.invert (); var L: Matrix = nieuwe matrix; L.a = a_c; L.b = b_d; L.concat (R); intersec.x = set2b.x + L.a * norm_v2.x; intersec.y = set2b.y + L.a * norm_v2.y;
We hebben vier benaderingen behandeld om dit kleine probleem op te lossen. Dus hoe zit het met de prestaties? Nou ik denk dat ik dit probleem gewoon aan de lezers zal overlaten om te oordelen, hoewel ik geloof dat het verschil te verwaarlozen is. Gebruik dit harnas voor prestatietests van Grant Skinner.
Dus nu dat we dit begrip hebben gekregen, wat is de volgende stap? Het toepassen!
Stel dat een deeltje beweegt in een pad dat tegen een muur botst. We kunnen de impacttijd berekenen met de eenvoudige vergelijking van:
Velocity = verplaatsing / tijd
Stel je voor dat je in dit oranje ronde deeltje zit en voor elk voorbijgaand frame en aankondiging wordt gemaakt op de tijd om tegen de muur te botsen. Je hoort:
"Tijd om te beïnvloeden: 1,5 frames" - Frame 1
"Tijd om te beïnvloeden: 0,5 frames" - Frame 2
"Tijd om te beïnvloeden: -0,5 frames" - Frame 3
Wanneer we frame 3 bereiken, is botsing met de regel al gebeurd (zoals aangegeven door het negatieve teken). Je moet de tijd terugspoelen om het punt van botsing te bereiken. Uiteraard moet een botsing enige tijd tussen frames 2 en 3 plaatsvinden, maar Flash beweegt in stappen van één frame. Dus als een botsing halverwege frames gebeurt, geeft een omkering van het bord naar negatief aan dat de botsing al is gebeurd.
Om negatieve tijd te krijgen, gebruiken we het vectorpuntproduct. We weten dat wanneer we twee vectoren hebben en de richting van één niet binnen 90 graden aan weerszijden van de ander is, ze een negatief puntproduct zullen produceren. Ook is het stippenproduct een maat voor hoe parallelle twee vectoren zijn. Dus wanneer een botsing al is gebeurd, is de snelheid en richting van een vector naar een punt op de muur negatief - en omgekeerd.
Dus hier is het script (opgenomen in CollisionTime.as). Ik heb hier ook botsingsdetectie toegevoegd binnen het lijnsegment. Voor degenen die het niet kennen, verwijs ik naar mijn tutorial over botsingsdetectie tussen een cirkel en een lijnsegment, stap 6. En voor hulp bij het besturen van schepen, hier is nog een referentie.
Accentsconagua
// beslissen of binnen wandsegment var w2_collision: Vector2D = new Vector2D (collision.x - w2.x, collision.y - w2.y); collision.alpha = 0; // wanneer het schip naar links van de muur gaat als (w2_collision.dotProduct (v1) < 0) t.text = "Ship is heading to left of wall"; else //when ship is heading to right of wall if (w2_collision.getMagnitude() > v1.getMagnitude ()) t.text = "Het schip gaat naar rechts van de muur" // wanneer het schip naar het andere wandsegment gaat var ship_collision: Vector2D = new Vector2D (collision.x - ship.x, collision. y - ship.y); var verplaatsing: Number = ship_collision.getMagnitude (); if (ship_collision.dotProduct (velo) < 0) displacement *= -1; //showing text var time:Number = displacement / velo.getMagnitude(); t.text = "Frames to impact: " + time.toPrecision(3) + " frames.\n"; time /= stage.frameRate; t.appendText("Time to impact: " + time.toPrecision(3) + " seconds.\n"); //drop down alpha if collision had happened if (displacement > 0) collision.alpha = 1; else collision.alpha = 0.5; t.appendText ("Botsing was al gebeurd.") Dus hier is een demo van wat je zult bereiken. Gebruik de linker en rechter pijltjestoetsen om het schip (driehoek) te sturen en druk op Omhoog om de snelheid tijdelijk te verhogen. Als het voorspelde toekomstige botspunt op de muur (de lijn) ligt, wordt er een rode stip op geschilderd. Voor een botsing die "al" is gebeurd, zal een rode stip nog steeds worden geverfd maar enigszins transparant. Je kunt ook de zwarte stippen aan elke kant van de muur slepen om deze te verplaatsen.
Dus ik hoop dat deze tutorial informatief is geweest. Deel dit als je dit idee ergens anders hebt toegepast dan wat ik heb genoemd. Ik ben van plan een kort verslag te schrijven over de toepassing ervan om laserdoelen te verfijnen - wat denk je? Bedankt voor het lezen en laat het me weten als er fouten zijn.
