Gemiddelde hoek berekenen van een raster van punten

Wiskunde is niet alleen een vak op school. Kom je ergens in de praktijk (bijvoorbeeld tijdens je werk) een wiskundig probleem tegen dan kun je hier om hulp vragen.
Plaats reactie
Xian
Nieuw lid
Nieuw lid
Berichten: 3
Lid geworden op: 19 sep 2018, 17:21

Gemiddelde hoek berekenen van een raster van punten

Bericht door Xian » 19 sep 2018, 17:31

Gegeven: een puntenwolk van enkele duizenden (x,y)-coordinaten. Die coordinaten zijn de meetpunten van de posities van enkele duizenden rechthoekige objecten die verondersteld worden zij aan zij op een raster te liggen. Aangezien de objecten rechthoekig zijn, zijn de posities ongeveer equidistant in x en ongeveer equidistant in y. Helaas ligt het raster zelf niet evenwijdig met het xy-assenstelsel, maar is er een kleine (gemiddelde) hoek van het raster tov het assenstelsel (maximum een paar graden).

Gevraagd: hoe kan ik op een elegante manier die gemiddelde hoek van dat raster berekenen?

Xian
Nieuw lid
Nieuw lid
Berichten: 3
Lid geworden op: 19 sep 2018, 17:21

Re: Gemiddelde hoek berekenen van een raster van punten

Bericht door Xian » 19 sep 2018, 17:39

Oh ja, en de puntenwolk zelf is gewoon een 'platte' lijst van punten, bvb een 6973x2 matrix. Ik heb dus geen voorkennis van welke (x-y)-coordinaat bij welk punt van het 'ideale' raster zou kunnen horen...

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Gemiddelde hoek berekenen van een raster van punten

Bericht door arie » 20 sep 2018, 10:36

Afbeelding

Hierboven een plaatje met een puntenwolk:
- rood = de punten (hier ongeveer 250, bij jou duizenden)
- zwart = de rechthoek die elk punt representeert

De punten hebben een relatief kleine meetfout, waardoor de oorspronkelijke roosterstructuur nog vrij duidelijk zichtbaar is gebleven.
Bedoel je zoiets?

En heb je wellicht meer voorinformatie over je puntenwolk en het ideale rooster:
- de vorm: ligt de wolk in een vierkant of rechthoek of ovaal of in een nog andere vorm?
- zijn er veel en/of grote gaten in de puntenwolk?
- weet je vooraf hoeveel horizontale en/of verticale lijnen je puntenwolk in het ideale rooster omvat?
- weet je vooraf wat in het ideale rooster de afstanden tussen de punten in x- en/of y-richting zijn?

Xian
Nieuw lid
Nieuw lid
Berichten: 3
Lid geworden op: 19 sep 2018, 17:21

Re: Gemiddelde hoek berekenen van een raster van punten

Bericht door Xian » 24 sep 2018, 07:06

Ja, inderdaad zoiets.

- de vorm: de wolk ligt in een ovaal
- Er kunnen soms veel grote en kleine gaten in de puntenwolk zitten.
- Je weet niet op voorhand hoeveel horizontale en/of verticale lijnen je puntenwolk in het ideale rooster omvat.
- Je weet vooraf ongeveer (bij benadering) wat in het ideale rooster de afstanden tussen de punten in x- en/of y-richting zijn.

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Gemiddelde hoek berekenen van een raster van punten

Bericht door arie » 05 okt 2018, 11:16

[1] Verschuif eerst de hele puntenwolk zodat het zwaartepunt in de oorsprong komt te liggen:
- bepaal x_ave = het gemiddelde van de x-coördinaten van alle punten
- bepaal y_ave = het gemiddelde van de y-coördinaten van alle punten
Trek (x_ave, y_ave) van de coördinaten van alle punten af.


[2] Als de punten ongeveer in een ovaal (=ellips) liggen kunnen we eerst de afmetingen van die ellips benaderen.
De algemene formule van een ellips met middelpunt de oorsprong is:



waarbij
a = de helft van de lange as
b = de helft van de korte as
zie bijvoorbeeld https://nl.wikipedia.org/wiki/Ellips_(w ... rgelijking

Bepaal x_max en x_min, de maximum resp. minimum waarde van de x-coördinaten van de punten
Bepaal y_max en y_min, de maximum resp. minimum waarde van de y-coördinaten van de punten

Omdat de ellips hooguit slechts enkele graden gedraaid ligt, is:
a ~= (x_max - x_min) / 2
b ~= (y_max - y_min) / 2


[3] Nu kunnen we alle punten P = (px, py) om de oorsprong gaan roteren over rho graden.
(waarbij i loopt van 1 t/m het aantal punten)
Alle punten P worden dan afgebeeld op hun beeld Q = (qx, qy) waarbij:

qx = px*cos(rho) - py*sin(rho)
qy[i] = px[i]*sin(rho) + py[i]*cos(rho)

(zie bv. https://nl.wikipedia.org/wiki/Rotatie_( ... latte_vlak)

Definieer alpha = de hoek waaronder het raster gedraaid ligt.
Als het raster bijvoorbeeld maximaal 5 graden gedraaid kan liggen, geldt:



Als we rho dus stapsgewijs laten oplopen van -5 t/m 5 graden, dan moet het raster dus voor
rho = -alpha
recht komen te liggen.


[4] Om te bepalen voor welke rho het raster recht ligt kunnen we voor elke rho een histogram (zie bv. https://nl.wikipedia.org/wiki/Histogram) maken van de waarden van qx[i] (dwz: de x-coördinaten van alle punten Q indelen in categorieën).
Hier een drietal situaties (43 blauwe punten, worden geprojecteerd op 51 bins = bakjes = categorieën, weergegeven onder de punten):

Afbeelding

In de eerste situatie ligt het raster recht, er zijn dan veel bins zonder punten, en weinig bins met veel punten:
bins[] = [0,1,0,0,0,0,0,5,0,0,0,0,0,5,0,0,0,0,0,7,0,0,0,0,0,7,0,0,0,0,0,7,0,0,0,0,0,5,0,0,0,0,0,5,0,0,0,0,0,1,0]

In de tweede situatie ligt het raster scheef, er zijn dan veel bins met weinig of geen punten:
bins[] = [0,0,0,0,1,1,0,1,0,0,2,0,2,1,1,2,0,1,2,1,2,0,1,2,1,1,1,2,1,0,2,1,2,1,0,2,1,1,2,0,2,0,0,1,0,1,1,0,0,0,0]

Als maat voor "recht liggen van het raster" kunnen we dan als score nemen bijvoorbeeld:



ofwel: de score is de som (voor j = 1 t/m aantal bins) van binwaarde[j] tot de vierde macht.
De goed gevulde bins (met veel punten erin) dragen dan erg veel bij aan de score.

In het eerste geval is de score ,
in het tweede geval

Neem dan de rho met de hoogste score als eerste benadering van -alpha.


[5] De stapgrootte van rho:
In de derde situatie in bovenstaand plaatje is de ellips zodanig gedraaid (een hoek beta), dat de korte as (lengte 2b) precies geprojecteerd op de volledige afstand w (= de afstand van de punten in x-richting in het recht liggende raster).
Bij benadering is



Als je nu de stapgrootte van rho ongeveer beta/10 graden neemt, moet je ergens op een situatie met een groot aantal lege en een beperkt aantal zeer volle bins uitkomen.


[6] Als je de optimale rho gevonden hebt, kan je alle punten indelen in hun werkelijke raster x-coördinaat.
Voor deze optimale rho kan je tevens de y-waarden van de punten categoriseren in bins, en zo ook de werkelijke raster y-coördinaten bepalen.
Nu je voor elk punt P[i] de raster coördinaten weet, kan je op die punten eenvoudig een
regressie-analyse uitvoeren (https://nl.wikipedia.org/wiki/Regressie-analyse)
om zo de best passende lijn y = A + B*x door de punten van 1 of meerdere raster regels te vinden.
De hoek van het raster wordt dan benaderd door atan(B).

Plaats reactie