Till att börja med vill jag säga att jag vet att detta inte är direkt relaterat till varken datorer eller IT, men detta tycktes ändå den mest passande forumdelen, då det trots allt är ett programmeringsproblem som jag söker hjälp med.
Jag behöver finna huruvida en cirkel kolliderar med en ändlig linje.
Jag har funnit en metod som ser ut att vara förhållandevis enkel, men jag har stött på problem vid implementationen.
http://mathworld.wolfram.com/Circle-LineIntersection.html
Om någon skulle kunna förklara denna metod (eller annan metod, om ni har någon som ni finner enklare) och/eller posta det implementerat i valfritt språk, så skulle jag bli ytterst tacksam. Jag ska ge mig på det imorgon igen, hade jag tänkt. Men tyvärr är jag ingen fantastisk matematiker, så jag har en känsla av att jag lär få kämpa.
EDIT: Fick hjälp av en god människa. Det fanns tydligen en förhållandevis enkel metod som kan avgöra huruvida en cirkel kolliderar med en oändlig linje (det var dock en tämligen enkel sak att modifiera för ändliga linjer).
Koden ser ut som följer (ignorera att allt råkar vara skrivet på en rad):
x1,y1,x2,y2 är linjens olika ändpunkter. circlex/circley är cirkelns mittpunkt och circler är cirkelns radie.
function lineCollide(x1,y1,x2,y2,circlex,circley,circler)
if ((circler^2) * (math.sqrt(((x2-circlex)-(x1-circlex))^2 + ((y2-circlex) - (y1-circlex))^2)) * ((x1-circlex)*(y2-circlex)-(x2-circlex)*(y1-circlex)) >= 0) then
if circlex+circler >= math.min(x1,x2) and circlex-circler <= math.max(x1,x2) and circley+circler >= math.min(y1,y2) and circley-circler <= math.max(y1,y2) then
return true
end
else
return false
end
end
Skrik gärna till om ni ser någonting fruktansvärt fel med denna metod.
Jag kan uppdatera med att ovanstående metod fungerar inte. Vissa kollisioner upptäcks, men andra inte.
Jag har hittat ett annat sätt att göra det, som ska fungera för ändliga linjer, men tyvärr finns ingen förklaring till metoden, och den är skriven i ett syntax jag ej är bekväm i:
bool IntersectCircleSegment(
const Vector2& c, // center
float r, // radius
const Vector2& p1, // segment start
const Vector2& p2) // segment end
{
Vector2 dir = p2 - p1;
Vector2 diff = c - p1;
float t = diff.Dot(dir) / dir.Dot(dir);
if (t < 0.0f)
t = 0.0f;
if (t > 1.0f)
t = 1.0f;
Vector2 closest = p1 + t * dir;
Vector2 d = c - closest;
float distsqr = d.Dot(d);
return distsqr <= r * r;
}
Raderna:
Vector2 dir = p2-p1;
Vector2 diff = c - p1;
float t = diff.Dot(dir) / dir.Dot(dir);
Ger mig speciellt mycket huvudbry. Jag önskar att människan kunde ange punkter som x1,y2 o.s.v. istället för att klumpa ihop dem i vektorer. Syntaxen när skalärprodukten räknas ut förvirrar mig också, eftersom jag inte vet hur diff och dot presenteras, samt vilken som är vilken.
Jag har skrivit en simpel funktion för att räkna ut skalärprodukten, som ser ut som följer:
function dot(x1,y1,x2,y2)
return (x1*x2 + y1*y2)
end
Jag känner att jag är ute på lite för djupt vatten, och mina mattekunskaper är tyvärr inte så stora. Hjälp! ![[cry]](/img/smilies/cry.gif)
uppenbarligen är inte um-are tillräckligt intelligenta för dethär</3
farbror gugge:
uppenbarligen är inte um-are tillräckligt intelligenta för dethär</3
Jodå, det finns några. Jag bara väntar på att Gentlernen ska komma och förlolämpa min intelligens. ![[cute]](/img/smilies/cute.gif)
Åtta:
Jodå, det finns några. Jag bara väntar på att Gentlernen ska komma och förlolämpa min intelligens.
ofta han kan matte ![[crazy]](/img/smilies/crazy.gif)
ennie:
ofta han kan matte
Han läser ju datavetenskap, så om inte annat får han läsa brutala mängder fysik. Precis det som jag håller på med borde han ha fått lära sig om, tycker jag.
Gentlernen:
Upp till bevis!
För varje punkt x på linjen, där f är linjens funktion, (cx, cy) är cirkelns position och r är cirkelns radie:
dx = abs(x - cx)
dy = abs(f(x) - cy)
d = sqrt(dx*dx + dy*dy)
pointIsInCircle = (d <= r)
Med andra ord behöver du bara lösa olikheten r >= sqrt(abs(cx-x)^2 + abs(cy-f(x))^2) med avseende på x.
Åtta:
så om inte annat får han läsa brutala mängder fysik
Varifrån har du fått den vanföreställningen? Det är datorteknikarna som får läsa sig så mycket irrelevant skit att de inte får någon tid över till programmering, algoritmer, etc., och blir riktigt pissiga på det de utbildar sig till (för att citera en civing-student på Chalmers: "vadå implementationsberoende? menar du typ 32 000?".) Det är viktigare att vara fin ingenjör än att faktiskt veta vad man håller på med.
Gentlernen:
Varifrån har du fått den vanföreställningen?
Genom att kika genom nyckelhålen på datavetenskapsföreläsningarna, samt bekanta som läser det.
Gentlernen:
För varje punkt x på linjen, där f är linjens funktion, (cx, cy) är cirkelns position och r är cirkelns radie:
dx = abs(x - cx)
dy = abs(f(x) - cy)
d = sqrt(dx*dx + dy*dy)
pointIsInCircle = (d <= r)Med andra ord behöver du bara lösa olikheten r >= sqrt(abs(cx-x)^2 + abs(cy-f(x))^2) med avseende på x.
Så om jag förstått det hela rätt så tittar man på varje punkt utefter linjen och ser huruvida avståndet mellan punkten och cirkeln är mindre än cirkelns radie?
Jag tror att jag har det mesta fixat, men (och jag känner mig aningen retarderad när jag säger detta) hur fan får man ut b i linjens ekvation (alltså y när x är 0)? Matematiskt kan jag och alla som läst matte a göra det, men hur gör jag det programmatiskt? ![[blush]](/img/smilies/blush.gif)
Man kan göra något i den här stilen:
(x-a)^2 + (y-b)^2 = r^2 (cirkelns ekvation där (a,b) är cirkelns centrum)
x = x0 + xd*t
y = y0 + yd*t
Substituera cirkelekvationens x och y med de parametriska ekvationerna ovan och skicka över radien till vänsterledet.
(x0 + xd*t - a)^2 + (y + yd*t - b)^2 - r^2 = 0
Denna ekvation ska lösas. De rötter man får ut på t avgör hur linjen korsar cirkeln.
A = xd^2 + yd^2 (andragradstermerna för t)
B = 2xd(x0-a) + 2xd(x0-b) (engradstermer för t)
C = (x0 - a)^2 + (y0 + b)^2 - r^2 (konstanttermer)
Så man ska kunna skriva om ekvationen till:
At^2 + Bt + C = 0
Denna ekvation kan man lösa i vanlig ordning med lösningsformeln från Matte B.
Beroende på vilka värden man får ut på t så är det en tangentlinje eller sekant. Det intressanta i vårat fall är väl dock om den saknar reella rötter, vilket innebär att den inte intersectar cirkeln på något sätt.
Åtta:
Han läser ju datavetenskap, så om inte annat får han läsa brutala mängder fysik.
Att datavetare läser fysik är för mig ganska okänt. Men de läser ju en del matematik.
Med hjälp av en god vän så kom vi fram till följande lösning:
function checkLineCollision(x1,y1,x2,y2, circlex, circley, circler)
for n=0,1,0.001 do
local x = x1 + ((x2 - x1) * n)
local y = y1 + ((y2 - y1) * n)
local dist = math.sqrt((x - circlex)^2 + (y - circley)^2)
if(dist <= circler) then return true end
end
end
Det är inte optimalt, eftersom linjen delas upp i 100 delar, oavsett linjens längd. Men det fungerar i alla fall.
Du bör definitivt INTE kolla för 100 olika punkter på linjen, det vore helt vansinnigt långsamt.
