Aviseringar
Rensa alla

Kolla om två linjestycken korsar varandra eller inte


Ämnesstartare

Hur gör man för att kolla om två linjestycken korsar varandra eller inte?

Jag har två linjer, båda med egna ändpunkter, i två dimensioner.

Exempel: om linje 1 går från (0,0) till (1,1) och linje 2 går från (1,0) till (0,1) så korsar de varandra.

Jag försöker få ihop kollisionsmotorn till ett litet pythonprojekt.


   
Citera
Ämnesstartare

Det borde väl bara krävas en koll om x-positionen för linje A finns inom linje B och om y-positionen för linje A finns inom linje B.

function linecollision(A,B) =
return (A.x+A.w < B.x orelse x > B.x+B.w) orelse (A.y+A.h < B.y orelse A.y > B.y+B.h);


   
SvaraCitera
Ämnesstartare

sylar:

function linecollision(A,B) =
return (A.x+A.w < B.x orelse x > B.x+B.w) orelse (A.y+A.h < B.y orelse A.y > B.y+B.h);

Vart får du x ifrån, som i x > B.x+b.W? Den enda inputen är ju A och B och deras x- och y-värden. Jag gissar att du menar A.x.
Jag får hur som helst inte den där funktionen att fungera. Hur skulle den egentligen fungera? Den kollar ju bara bounding boxes för linjerna?

Om ens det, räcker ju att någon av de där fyra är sanna för att funktionen ska vara sann.


   
SvaraCitera
Ämnesstartare

Image
De där linjerna korsar inte varandra, även om de stämmer med "om x-positionen för linje A finns inom linje B och om y-positionen för linje A finns inom linje B.".


   
SvaraCitera
Ämnesstartare

k1337oris:

Vart får du x ifrån, som i x > B.x+b.W? Den enda inputen är ju A och B och deras x- och y-värden. Jag gissar att du menar A.x.

Jo, skrev fel.

k1337oris:

De där linjerna korsar inte varandra, även om de stämmer med "om x-positionen för linje A finns inom linje B och om y-positionen för linje A finns inom linje B.".

Sant, kunde inte föreställa mig det där fallet riktigt.
Vad sägs om Fortune's Algoritm?


   
SvaraCitera
Ämnesstartare

sylar:

Vad sägs om Fortune's Algoritm?

Den är väl mest för att kolla ett gäng linjer samtidigt? Den känns på tok för komplex för mitt projekt. Jag kommer behöva göra uppskattningsvis 100.000 kollar per sekund (om linje A kolliderar med linje B).


   
SvaraCitera
Ämnesstartare

Hittade http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
som verkade lösa problemet! Något mer kod än vad jag trodde var nödvändigt, men koden körs snabbt nog (277k ggr/sekund på min maskin, vilket är precis lagom mycket då jag behöver runt 100k/sekund vid <50% cpu).

Här är min pythonkod. Den är inte särskilt fin... Men den är PEP-8-compliant åtminstone. Tror jag.
http://paste.pocoo.org/show/133951/


   
SvaraCitera

Snyggt jobbat...men funkar scriptet så att du räknar ut endast om banorna korsar varandra eller om kulorna (eller vad det nu är) krockar? Banorna kan ju korsa varandra även utan att objekten krockar, menar jag... Vad är det du itererar i for-satsen längst ned?


   
SvaraCitera
Ämnesstartare

Ökänd:

Vad är det du itererar i for-satsen längst ned?

Ett väldigt fult prestandatest? Jag kör samma funktion om och om igen 100k gånger, kollar tiden mellan start och slut, och kör 1/x på det så har man en uppskattning av hur många gånger per sekund man kan köra funktionen.


   
SvaraCitera
Ämnesstartare

Ökänd:

Snyggt jobbat...men funkar scriptet så att du räknar ut endast om banorna korsar varandra eller om kulorna (eller vad det nu är) krockar? Banorna kan ju korsa varandra även utan att objekten krockar, menar jag...

Hur menar du?


   
SvaraCitera

k1337oris:

ur menar du?

Ja om objekten har olika utgångshastighet tex, är det inte säkert att de krockar med varandra även om deras banor korsas. De kan befinna sig i skärningen vid olika tidpunkter. Så menade jag.


   
SvaraCitera
Ämnesstartare

Ökänd:

Ja om objekten har olika utgångshastighet tex, är det inte säkert att de krockar med varandra även om deras banor korsas. De kan befinna sig i skärningen vid olika tidpunkter. Så menade jag.

Inte om linjerna jag kollar består av deras position respektive deras position plus deras vektor. De rör sig alltid lika långt som en vektor varje iteration.

Förövrigt så är det inte kulor i det här fallet: det är en boll (eller rättare sagt en punkt) som "studsar" mot en linje. Den ena linjen är alltså linjen jag vill se om den kommer att kollidera med, den andra linjen består av från punkten till punkten+punktens vektor.


   
SvaraCitera

Tråden låst på grund av inaktivitet


   
SvaraCitera