Forum Mjukvara Programmering och digitalt skapande Tråd

Avstånd linje-cirkelsegment

1
Skriv svar
Permalänk
Medlem
●

Avstånd linje-cirkelsegment

Tja!

Har sökt förgäves på nätet samt klurat själv på hur man gör följande:

Ta fram det kortaste avståndet mellan ett cirkelsegment och en linje!

Hur linjen eller arcen är definerade är egentligen irrelevant även vilket språk ni eventuellt löser det i. Jag letar efter nån som kan peka mig i rätt rikning mot en lösning eller om någon redan sitter på den. Och nej, detta är inte en skoluppgift, jag jobbar som programmerare, är ingen hejare på geometri dock. Och ja, förresten, att approximera arcen med linjer och sedan testa mot dessa är inte en acceptabel lösning, det har jag redan gjort, men av prestandaskäl vill jag ha något bättre. Det borde finnas tycker jag! Det är i 3 dimensioner vi pratar om också, även om det inte borde vara någon större skillnad!

Så kom igen nu alla spelkodare, ni borde vara hejare på sånt här!

Tacksam för svar..

EDIT: Såg att jag var lite otydlig med begreppen, men arc och cirkelsegment är förstås samma sak!

Visa signatur

5D MkII

Redigera
Citera flera Citera
Permalänk
Medlem
●

Avståndet (t.ex. 3.42 meter) eller de två punkterna på sfären resp. linjen?

Visa signatur

Min hemsida: http://www.srekel.net
Pocket Task Force: http://ptf.srekel.net
Kaka e gott! http://kaka.srekel.net

Redigera
Citera flera Citera
Permalänk
Medlem
●

Avståndet, inget annat. Och det är ingen sfär vi pratar om, en cirkelbåge, cirkelsegment, arc eller vad du/ni/jag vill kalla det....

EDIT: Kanske var otydligt att säga att det är 3D, cirkelsegmentet kan försås bara ligga i ett plan, vad jag menade var att planet inte nödvändigtvis behöver vara x-y planet...

Visa signatur

5D MkII

Redigera
Citera flera Citera
Permalänk
Glömsk
●

Öhm, lite förtydliganden.

Menar du kortaste avståndet från _någon_ av punkterna i linjen eller enbart ändpunkterna?

Vad menar du med cirkelsegment? Det här är ett cirkelsegment:

En bild skulle vara trevligt.

Visa signatur

...man is not free unless government is limited. There's a clear cause and effect here that is as neat and predictable as a law of physics: As government expands, liberty contracts.

Redigera
Citera flera Citera
Permalänk
Medlem
●

Hur beskriver du linjen och framförallt cirkelsegmentet rent matematiskt i ditt problem?

Metoden du får använda är att skriva avståndet från två godtyckliga punker, en på linjen och en på cirkelsegmentet, derivera och försöka finna nollställen, om sådant ej finns så är minimi i någon av kombinationerna av hörnen på de två.

(alternativt helt numeriskt, dela upp cirkelsegmentet och linje till ett godtyckligt antal punkter och testa alla kombinationer)

Redigera
Citera flera Citera
Permalänk
Medlem
●

Jag menar s i din bild. Och naturligtvis någon av de oändligt antal punkter i linjen respektive cirkelsegmentet, inte bara ändpunkterna....

EDIT: Linjen är definerad av två ändpunkter (x,y,z). Arcen defineras av en centrumpunkt (x,y,z) samt en startvinkel och slutvinkel. Fan, är ju inte på jobbet nu så jag har inte koden framför mig, men jag får återkomma med mer fakta imorgon om det skulle behövas.

EDIT2: Cirkelbåge ser jag nu att den svenska definitionen heter.

Senast redigerat
Visa signatur

5D MkII

Redigera
Citera flera Citera
Permalänk
Medlem
●

Intressant problem.. extra lurigt av dig o göra en post om det precis innan läggdags, nu kommer det vara omöjligt o somna

Antar att arcen inte behöver ligga i samma plan som linjen?

btw, en linje har ingen start- o slutpunkt, det har däremot ett linjesegment

Redigera
Citera flera Citera
Permalänk
Medlem
●

Om arcen ligger i samma plan som linjen så är det ju ett tvådimensionellt problem. Det är betydligt enklare att lösa.

Jag tror att det du söker är längden på en normal som är gemensam för både linjen och en tangent till cirkelbågen.

Redigera
Citera flera Citera
Permalänk
Medlem
●
Citat:

Ursprungligen inskrivet av vb
Intressant problem.. extra lurigt av dig o göra en post om det precis innan läggdags, nu kommer det vara omöjligt o somna

Antar att arcen inte behöver ligga i samma plan som linjen?

btw, en linje har ingen start- o slutpunkt, det har däremot ett linjesegment

Nåväl, kalla det vad du vill, linjesegment då!
Nej, jag skrev ju ovan att de inte behöver ligga i samma plan, faktum är att i mitt problem så gör de nästan aldrig det, och även om de gjorde det i detta fallet så vill jag ju ha en generell lösning.

Citat:

Ursprungligen inskrivet av Toett
Om arcen ligger i samma plan som linjen så är det ju ett tvådimensionellt problem. Det är betydligt enklare att lösa.

Jag tror att det du söker är längden på en normal som är gemensam för både linjen och en tangent till cirkelbågen.

Du får utveckla det sista du skrev lite mer, en normal till en linje, vad är det? Det kan man väl inte definera, inte i 3 dimensioner åtminstonde.

Visa signatur

5D MkII

Redigera
Citera flera Citera
Permalänk
Medlem
●

Du behöver komplettera med en radie för cirkeln för att definiera cirkelbågen entydigt...

En normal till en linje/sträcka är en linje som är vinkelrät mot den givna linjen/sträckan.

I tre dimensioner finns det ett oändligt antal normaler till en linje. Och det samma gäller för tangenten till cirkelbågen.

Problemet består i att hitta en normal som är gemensam för linjen och tangenten. När du hittat denna gemensamma normal så får du kontrollera så att punkten där normalen skär linjen respektive cirkeln ligger inom dina gränsvärden. Om så inte är fallet så finner du kortaste avståndet från någon av ändpunkterna.

Hmm... Snart förstår jag inte ens själv vad jag menar...

Senast redigerat
Redigera
Citera flera Citera
Permalänk
Medlem
●

Translatera/rotera så att cirkeln hamnar i xy-planet med centrum i origo. För en given punkt i rymden är det då lätt att hitta avståndet till cirkeln. Det är det röda på denna bild:

Parametrisera linjen och sätt in i formeln för avståndet. Finn minimum genom att derivera och hitta nollor.

Om minimum förekommer mellan punkter som inte ligger på linjesegmentet/cirkelbågen, kolla på kantpunkterna istället (start/slut för kurvorna).

Slavgörat får du göra själv eller med Maple eller liknande.

Visa signatur

:€

Redigera
Citera flera Citera
Permalänk
Medlem
●

http://www.geometrictools.com/Documentation/DistanceLine3Circ...

Redigera
Citera flera Citera
1
Skriv svar