Hjälp med formel för att plotta koordinater

C, C++, Pascal, Assembly, Raspberry, Java, Matlab, Python, BASIC, SQL, PHP, etc.
cjonash
Inlägg: 613
Blev medlem: 20 maj 2011, 08:53:58
Ort: Göteborg

Hjälp med formel för att plotta koordinater

Inlägg av cjonash »

Jag har ett programmeringsproblem, som jag inte lyckats hitta någon lösning på. Kanske för att jag inte hittat rätt söktermer. Matematiken som är involverad är tyvärr utanför mina egna kunskaper, så jag tänkte göra ett försök att posta det här.

Som utgångspunkt finns en yta som är definierad av 4 punkter (x1,y1 till x4,y4). Koordinatsystemet för dessa är odefinierat (flyttal, men ingen fördefinierad storlek). Ytan kan ha valfri rotering - det enda som är känt är att det är en rektangel, så alla vinklar är 90 grader. Inom denna yta så får jag koordinater (illustrerat som xP,xP). Illustrationen visar tre exempel på hur det kan se ut:
koordinater.jpg
Det jag behöver kunna göra är att mappa dessa koordinater (xP,xP) till en bild som inte är roterad, och med sitt eget koordinatsystem där 0,0 antingen är toppvänster eller center. Dvs jag behöver en funktion som tar fem koordinater (i samma koordnatsystem) och två värden för bredd och höjd (det nya koordinatsystemet) som indata, och som utdata ger X och Y värde i det nya koordinatsystemet.

Något i stil med detta (det är Delphi-kod, men principen bör vara begriplig):

Kod: Markera allt

Type
   TCoordinate = record
      X: Float;
      Y: Float;
   end;


function CalcPosition(c1, c2, c3, c4 : TCoordinate; aPos : TCoordinate; aWidth, aHeight : Float) : TCoordinate;
begin
   // Calculation
end;
Där c1, c2, c3 och c4 är de fyra hörnen, aPos är den koordinat som skall räknas ut, aWidth och aHeight definerar det nya koordinatsystemet och resultatet är positionen i det nya koordinatsystemet. Funktionen behöver alltså dels "rotera rätt", dels skala om värdena om proportionerna inte är desamma.

Funktionen behöver också kunna hantera att positionen ligger utanför den definerade rektangeln, men då givetvis också returna värden som ligger utanför den "nya" rektangeln.

Någon som antingen har eller kan skriva en formel för detta, eller har några tips att dela med sig av?
Du har inte behörighet att öppna de filer som bifogats till detta inlägg.
kodar-holger
EF Sponsor
Inlägg: 916
Blev medlem: 26 maj 2014, 12:54:35
Ort: Karlskoga

Re: Hjälp med formel för att plotta koordinater

Inlägg av kodar-holger »

Efter att ha läst några gånger tror jag att det fattas någon information, eller så övertänker jag.

Du säger att det fösta koordinatsystemet är okänt. I mitt huvud innebär det både i position och riktning. Men nån stans känns det som om du antar att det är lika orienterat som det du vill ha som output. Om det är så:

Rotationen är enkel att få ut. atan2(c2-c1) ger dig rotationsvinkeln.

Storleken på respektive axel är enkel att få ut. Pytagoras sats på sträckorna c1-c2 respektive c1-c3.

Sen måste du komma ihåg att flytta punkten aPos (translatera) innan du roterar med:

\(result.x:=x\cos\theta-y\sin\theta\\
result.t:=x\sin\theta+y\cos\theta.\)


Och så blir det väl nån skalning på slutet där du använder kvoten mellan aWidth och avståndet c1-c2 för att skala den roterade koordinaten.

Om det är mer än en punkt du skall transformera kan det löna sig att göra detta med rotationsmatriser och homogena koordinater.

Se:https://en.wikipedia.org/wiki/Transformation_matrix

Om det inte är så, d.v.s. koordinatsystemet du börjar med kan flyta fritt i output-systemet så undrar jag om det går att lösa. I alla fall utan att du lägger till ytterligare information.

(Det är för varmt för att skriva kod (snarare, jag är för tjock för den här värmen) så orkar inte förklara bättre just nu)
Användarvisningsbild
Krille Krokodil
Inlägg: 4062
Blev medlem: 9 december 2005, 22:33:11
Ort: Helsingborg

Re: Hjälp med formel för att plotta koordinater

Inlägg av Krille Krokodil »

Enklast är nog att tänka lite bakvänt, om låter två sidor på rektangeln vara axlarna i ett koordinatsystem R så kan transformen till världskoordinatsystemet W skrivas som en homogen matris:

\(\begin{bmatrix}
x_2-x_1 & x_4-x_1 & x_1\\
y_2-y_1 & y_4-y_1 & y_1\\
0 & 0 & 1 \\
\end{bmatrix}\)


(x1, y1) är i R (0,0,1), multiplicerat med matrisen får vi (x1,y1,1).

(x3, y3) är i R (1,1,1), multiplicerat med matrisen får vi (x2-x1+x4-x1+x1, y2-y1+y4-y1+y1,1). På den icke-roterade
matrisen i första bilden har vi x1=x4, y1=y2, x2=x3 och y3=y4 vilket ger (x2, y4, 1) = (x3, y3, 1).

Så nu har vi löst det bakvända problemet med var en punkt i rektangeln finns i världen, genom att invertera den homogena matrisen så kan vi räkna ut var en punkt i världen finns i rektangeln. Enklast gör man det med något bibliotek som har färdiga funktioner för matrisberäkningar och geometri. Vill man knacka koden själv så finns det ledning här bl a: https://mathematica.stackexchange.com/q ... ion-matrix
cjonash
Inlägg: 613
Blev medlem: 20 maj 2011, 08:53:58
Ort: Göteborg

Re: Hjälp med formel för att plotta koordinater

Inlägg av cjonash »

Tack för era svar!! Jag inser när jag läser dem att jag kanske kunde varit lite tydligare i min beskrivning...
Men kodar-holger är nog väldigt nära den lösning jag letade efter.

De tre bilderna visar tre olika exempel på hur indata kan se ut. I det här fallet skulle alla tre ge samma ut-resultat, eftersom min "punkt" är på samma ställe i alla tre figurerna, även om de är roterade olika mycket.
Så egentligen kan hela problemet beskrivas med att hitta hur mycket "punkten" skall flyttas för att motsvara att man har roterat ytan till så som den ser ut i den första figuren (alltså där x1y1 är uppe till vänster och y1=y2). Att därifrån "skala in den" i mitt nya koordinatsystem är inte ett problem, det gör jag redan på många andra ställen i min kod.

Möjligen är det samma sak som Krille skriver, men att jag inte riktigt hänger med i matris-matematiken. Första gången jag kom i kontakt med matriser var för några månader sedan (i samband med OpenGL programmering), så jag har en del kvar att lära där... :humm:

En liten fråga gällande att hitta roteringen. Du (kodar-holger) angav formeln så här: atan2(c2-c1)
Men vad är c2-c1? I min skiss är c2 och c1 två av hörnen, men det är ju två värden i varje (x och y).

Mvh
Jonas
kodar-holger
EF Sponsor
Inlägg: 916
Blev medlem: 26 maj 2014, 12:54:35
Ort: Karlskoga

Re: Hjälp med formel för att plotta koordinater

Inlägg av kodar-holger »

Ja det gick lite fort där kanske. Vad jag menade var väl ungefär

Vinkeln = arctan2 (differens i y-led mellan c1 och c2 , differens i x-led mellan c1 och c2);

Theta := arctan2(c2.y-c1.y , c2.x-c1.x);

Och så är det det här med tecken och rotationsriktning som jag alltid får debugga mig fram till rätt svar på.

I Hjälpen till min delphi-version står det att x a arctan2 inte får vara 0 men det måste vara fel. Tanken med arctan2 istället för vanlig arctan är just att den är definierad för alla vinklar utom när både x och y är 0.

Matriser är vacker matematik även om det för mig som bara gått gymnasiet är jobbigt och något jag tvingats lära mig just pga grafikprogrammering. Skönheten är att du kan slå ihop en hel serie transformationer (//:translation, rotation, skalning, projicering://) till en transformationsmatris som man sen kan tillämpa på en hel räcka punkter direkt. Utan att köra dyra operation som sinus och cosinus flera gånger. I det här fallet kan man kanske (se krille krokodils inlägg) få bort allihop eftersom tan(x) = sin(X)/cos(x) och inverserna har naturligtvis något med varandra att göra så att arctan + sin och cos i rotationen "tar ut varandra". Kan vara viktigt om du skall göra det miljoner gånger per sekund men mindre intuitivt för dom flesta när man ser koden.
Användarvisningsbild
Krille Krokodil
Inlägg: 4062
Blev medlem: 9 december 2005, 22:33:11
Ort: Helsingborg

Re: Hjälp med formel för att plotta koordinater

Inlägg av Krille Krokodil »

Man behöver inte kunna matrismatematiken, man kan använda ett färdigt bibliotek i stil med hur man gör med OpenGL där man har funktioner för skapa länkarna i kedjan, ex. flytta, rotera, skala. Detta problemet är ungefär detsamma som att flytta, vrida och zooma en kamera i OpenGL för få rektangeln där man vill ha den i bildfältet.

Kedjan kan se ut såhär:

1. Translatera (-x1, -y1) så att rektangelns första hörn blir rotationscentrum.
2. Rotera -Theta så att rektangelns sida ligger i x-axeln
3. Skala så att rektangelns sidor definerar 1 (eller den pixelskala man vill plotta punkten i sen).

Har man bara ett bibliotek med de här funktionerna så är det en lek med med enkla heltal och 90 graders vridningar för att förstå åt vilket håll saker flyttar, vrider och skalar sig.
cjonash
Inlägg: 613
Blev medlem: 20 maj 2011, 08:53:58
Ort: Göteborg

Re: Hjälp med formel för att plotta koordinater

Inlägg av cjonash »

Tack igen!
Jag skall prova formlerna i helgen, så får vi se om jag lyckas :)
Skriv svar