Forumet - Kolla om två linjestycken korsar varandra eller inte

Kolla om två linjestycken korsar varandra eller inte

1097 0 12
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.
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.

Spana också in:

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?
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/
Ö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.