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.
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);
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.
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.".
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?
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).
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/
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?
Ö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.
Ö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?
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.
Ö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.
Tråden låst på grund av inaktivitet
