Hitta vektorn i ett point cloud via "Linear least squares"?

Hej,

Jag har ett 2d point cloud som jag försöker hitta en vektor igenom. Vektorn kan man hitta genom att lösa det så kallade "linear least squares" -problemet.

Bild
https://upload.wikimedia.org/wikiped...ession.svg.png

Mer info
http://mathworld.wolfram.com/LeastSquaresFitting.html
https://en.wikipedia.org/wiki/Linear...s_(mathematics)

Koden jag skriver är egentligen inte i Python utan i ett sämre skräpspråk (MEL), men jag är mer bekant med Python så jag tänkte skriva det där först och sen bara översätta.

Jag har hittat flera olika lösningar på detta ute på nätet, bland annat:
https://python4mpia.github.io/fittin...s-fitting.html

Problemet med detta är att ALLA verkar använda sig utav libs såsom numpy och scipy (exempelvis scipy.optimize.leastsq) - och jag har inte sådana här libbar i skräpspråket MEL så jag måste skriva denna funktionalitet för hand. Jag lyckas dock inte hitta något Python-exempel på detta där inte numpy och/eller scipy används

Notera att jag enbart är intresserad utav vektorn - jag har inget behov av att plotta och rita en graf.

Du vill minimera ∑ d^2 där ∑ är en summa över alla punkter och d är avståndet mellan en punkt och linjen. Skapa en metod som räknar ut den summan, ändra vinkel och startpunkt för linjen och välj den linje som ger minst ∑d^2.

Du kan välja d som det lodräta avståndet mellan punkten och linjen eller det minsta avståndet från punkten till linjen. Ofta är det uppenbart vilket som är bäst från hur frågan*är ställd.

Edit: yggdrasil har svaret.

Det låter ju som en brute-force lösning. Räkna ut summa, rotera vektor, räkna ut summa, rotera vektor - måste ju bli ganska tungt ändå?

Ja det är det minsta avståndet till linjen jag är intresserad utav och inte det lodrätta avståndet. Jag tror jag kommer få för stora fel om jag kör på det senare.

För att förtydliga: Jag är intresserad utav kodexempel där numpy/scipy ej används (vill undvika att uppfinna hjulet på nytt)

Jag struntar i hur man gör. Varför kan du inte kalla på python från MEL?

Skall detta var högpreseterande i ett jäkla skitpråk inuti nått 3d verktygs krafs?
Annars kan du ju faktiskt kalla på ett python script.

Skriv den i C som en plugin eller nått annars, om det är viktigt med prestanda.
Där kan du säkert hitta en vettig lib.

Läste fö på wikipedia.


TLDR gör vad du kan för att slippa uppfinna hjulet och producera en massa buggig kod som du får underhålla och som crashar med stack overflows eller returnerar null varje torsdag när det är fullmåne.

Är det inte det du håller på med då?

Finns många mindre bibliotek du kan titta på. T.ex. detta

Anledningen att du använder numpy är för att det är snabbare än att använda massa loopar och liknande. Är det en Maya-plugin du utvecklar? Kolla om du inte kan koda en egen modul i C för python för att få bra prestanda. Varför måste du använda MEL?

Edit: vafan måste kolla trådarna jag svarar i så jag ser om någon annan hinner före

Funderade lite mer på detta och insåg att jag lika gärna kan göra en convex-hull -beräkning på punkterna, och sedan loopa över dom för att hitta de två punkter som har störst avstånd mellan varandra (om fler än 2: selecta ett random par). Vektorn kan jag sedan skapa utifrån dessa två punkter. Monotone chain borde vara tillräkligt snabbt?
Visst punkternas avstånd till vektorn blir inte helt optimerad men det blir en ok approximation.


Mr. Rage: Japp, det ska det. Och ja, jag är medveten om MEL-funktionen python(). Saken är den att scriptet ska fungera i Maya LT som ej har någon Python-tolk! (krav från beställaren jag jobbar åt).

Och ja, Maya LT är en jävla handikapp-version utav Maya men pengar är pengar och beställaren får det som den ber om.

Berätta gärna hur du löste det sen.

Jag googlade lite på detta igår, och hittade dethär:

http://stackoverflow.com/questions/2...ear-regression

En sak som ts kanske kommer att få problem med är det som nämns i lösningen (som inte är exakt det TS vill göra, men nära. I kommentarerna förklaras hur man gör om man har f(x,y) = z).


Jag antar att MEL har stöd för att transponera matriser, annars kan detta blir jobbigt att bygga själv.

Ett alternativ är att projicera punkterna på ett 2D plan som man anpassat till punkterna i rummet och sedan använda 2d least mean square, men när man gör den projektionen så tror jag att man får ett fel. Någon som är mer matematiskt kunnig kanske kan kommentera hur vida det är en bra eller dålig ide. Det kanske är lika jobbigt att ta fram ett plan, jag har dock sett några sådana algorimer runt om på nätet.

Själv skulle jag nog helst försöka anropa python eller ett annat program från MEL i stället för att bygga detta från grunden.