[c#] isobar maken

[mr_taipan]

Hoi,

Ik ben bezig met een programma die uit een verzameling punten een kaartje kan produceren zoals bij het weer.



De punten in de verzameling bestaan uit een x een y coordinaat en waarde tussen 30 en 90.

Van de lijst met punten wil ik graag een kaartje maken.

Weet iemand hoe ik dat aan moet pakken?

Alvast bedankt.

[TeeDee]

Misschien heb je hier iets aan?

[rml][ alg] kleur atlas shader[/rml]

[mr_taipan]

Ik heb op zich geen probleem met de kleuren.

Meer met het interpoleren tussen verschillende punten en het tekenen van een kaartje

[TeeDee]

A! Okay.

Je kan toch met een "pen" over de x/y coordinaat van een canvas heen gaan?

_{kwam er laatst wat over tegen, zal ff rondneuzen}

Je kan zowiezo met Mappoint aan de slag.

/edit: kan het zo snel ff niet vinden.

Verder nog een mooi artikel: http://www.15seconds.com/issue/030630.htm (svg)

[ Voor 38% gewijzigd door TeeDee op 22-04-2004 10:38 ]

[mr_taipan]

Het tekenen lukt wel in c#.

Het maken van isobaren lukt niet.

En ik kan ook nergens een algoritme vinden om isobaren te produceren

[12_0_13]

Een isobar is een lijn die punten met gelijke hoogte verbind. Helaas kan je niet zomaar lijnen gaan trekken.

Je kan eigenlijk alleen een isobar plaatje maken als je van ALLE punten de durk weet. Nu kan je gewoon de druk mappen op een kleur, bijv:

30-40 -> blauw
40-50 -> groen
50-60 -> geel etc.

Als je niet voor alle punten een druk hebt, zou je die kunnen interpoleren (bilinair, bicubic, whatever) vanuit punten waarvan de WEL de druk weet. Op die manier kun je dan een plaatje genereren.

[ Voor 13% gewijzigd door 12_0_13 op 22-04-2004 13:00 ]

[Janoz]

Je zult toch iets meer informatie moeten geven. Die punten, staan die random verspreid over het oppervlak of netjes in een rooster?

[mr_taipan]

De punten staan helemaal random op het oppervlak.

[Janoz]

Je zult ene algorimte moeten bedenken dat met behulp van die punten de waarde op elke positie op het veld bepaald. Dit kun je bijvoorbeeld doen door de waarde van een specifiek punt af te laten hangen van een gewogen gemiddelde van alle punten waarbij het geicht wordt bepaald door de afstand tussen de positie van het sample punt en elk van de waarde punten. Door vervolgens te kijken of deze waarde hoger of lager dan een bepaalde vooraf ingestelde band is kun je bepalen tot welke groep dat punt behoort.

Een voorbeeld van een gewicht zou kunnen zijn 1/afstand. 1/0 is oneindig dus daar ff op letten. Dat punt telt dan in zijn eentje mee .

[mr_taipan]

Als ik dus in 2 for loopjes door een raster heen loop en voor elk punt op het raster bepaal bij welke band het hoord heb ik en grote verzameling punten.

Op welke manier kan ik dan alle punten met elkaar verbinden die de zelfde waarde hebben. ?

[12_0_13]

Niet

Je kleur gewoon je bitmap in, en geeft de hoogtes met dezelfde waarden eenzelfde kleur. Dan krijg je vanzelf die lijnen

Als je perse lijnen wilt, moet je gaan kijken waar je punten overgaan van bijv. geel naar groen. Dan blijf je die rand volgen tot je weer uitkomt waar je was, of tot je aan een rand bent. Je kan nu een kromme maken die de punten die je hebt nagelopen redelijk benaderd.

MMmm hersenspinsel: maak een voronoi-diagram ervan, en laat de lijnen die langs gelijke punten lopen aan elkaar groeien.

[ Voor 66% gewijzigd door 12_0_13 op 22-04-2004 15:31 ]

[mOrPhie]

mr_taipan schreef op 22 april 2004 @ 15:02:

Op welke manier kan ik dan alle punten met elkaar verbinden die de zelfde waarde hebben. ?

Interpoleren.

Basic-erwijs houdt dit in: bedenk voor alle rasterpunten waar geen waarde van bekend is de waarde, aan de hand van de 3 meest in de buurt liggende punten.

Maar het ligt er ook maar net aan wat je wilt. Wil je een mooi vormgegeven model zoals het plaatje in de startpost, of een wetenschappelijk plaatje? Interpoleren is mooier, maar je krijgt dan wellicht hoekjes, maar wel meer detail-vormen, in plaats van verzonnen curven zoals op het plaatje.

[ Voor 29% gewijzigd door mOrPhie op 22-04-2004 15:30 ]

[.oisyn]

Maak eerst een delaunay triangulatie van je punten, dit verdeelt je vlak op in driehoekjes die je kunt gebuiken voor interpolatie (de waarde van een punt is dan gewoon een gewogen gemiddelde van de drie hoekpunten van de driehoek waar je punt in ligt).

Nu je de waarden vam elk willekeurig punt kunt bepalen, kun je met een sufrace construction algoritme de isobaren vinden. Dat kun je bijvoorbeeld doen door te gaan zoeken naar de juiste grenswaarde, en dan daaromheen gaan zoeken naar aansluitende punten die voldoen aan die grenswaarde.
Een andere methode is het zogenaamde marching cubes algoritme (of eigenlijk marching squares aangezien het 2d is ), waarbij je het gebied opdeelt in een homogeen 2d grid, waarbij je voor elk van de 4 hoekpunten van elk grid-element gaat kijken of het hoger of lager dan je grenswaarde is. Als de ene kant van een rand van zo'n grid-element erboven ligt, en de nadere kant eronder, dan ligt er dus ergens tussenin een verbindingspunt (die je zou kunnen bepalen dmv interpolatie tussen de hoekpunten). Zo krijg je per vierkantje een klein aantal verbindingspunten die je met elkaar kunt verbinden, en zo ontstaat een hele isobar

isobaren zijn trouwens lijnen met gelijke luchtdruk (vandaar de term bar). Ik zie in je kaartje dat je temperatuur gebruikt, dan zijn het dus ook geen isobaren "isolijnen" is de algemene benaming

[ Voor 11% gewijzigd door .oisyn op 22-04-2004 15:52 ]

[Janoz]

mr_taipan schreef op 22 april 2004 @ 15:02:
Als ik dus in 2 for loopjes door een raster heen loop en voor elk punt op het raster bepaal bij welke band het hoord heb ik en grote verzameling punten.

Op welke manier kan ik dan alle punten met elkaar verbinden die de zelfde waarde hebben. ?

Niet, gebeurt vanzelf. Als de ene groep punten in het rode bereik vallen en een andere groep punten in het gele bereik dan heb je automagisch er tussenin een overgang die vast vloeiend verloopt.

[.oisyn]

Oh, wil je het alleen maar kleuren? Waarom heb je het dan over isobaren?

Dit zijn isobaren, die witte lijnen dus:

[ Voor 49% gewijzigd door .oisyn op 22-04-2004 15:59 ]

[12_0_13]

TS, ik ben wel benieuwd naar het resultaat eignelijk, lukt het al een beetje?

[Zoijar]

Marching squares, de 2d variant van marching cubes (3d). Zit alleen helaas patent op het algoritme, dus je moet even uitkijken met commerciele implementaties. Goed voorbeeld van het nut van software patenten...

oh sorry, ik lees nu net dat dit boven al is gezegd...

[ Voor 13% gewijzigd door Zoijar op 23-04-2004 13:20 ]

[.oisyn]

Ik was een beetje dom, als je toch al een delaunay triangulatie hebt is het natuurlijk lomp als je met een marching squares algoritme het veld op gaat delen als een grid. Er wordt lineair geinterpoleerd tussen de driehoeken, dus dan kun je net zo goed een "marching triangle" oid implementeren

Valt dat trouwens ook onder dat patent? ()

[Soultaker]

Volgens mij is dat een patent in de Verenigde Staten, dus dat zou ik in Europa maar gewoon negeren. Bovendien heeft marching cubes specifiek te maken met 3D modelleren, dus ik betwijfel of het patent ook 'automatisch' de 2D variant zou bestrijken.

[ Voor 4% gewijzigd door Soultaker op 26-04-2004 18:43 ]

[mr_taipan]

Bedankt voor alle reacties.

Ik denk dat ik maar voor het raster ga met gemiddelde waardes.

Eigenlijk wil ik niet het hele plaatje inkleuren maar alleen het stuk binnen de meetpunten die het meest aan de buitenkan liggen.

Ik denk zelf dat het dan mischien handig is om de punten te sorteren over bijvoorbeeld de x as.

maar hoe krijg ik zo'n plaatje


in plaats van zo'n fout plaatje


en als ik dan de buitenste punten heb en ik leg er een raster overheen dan moet ik nog weten welke punten binnen het goeie gebied vallen en welke niet

[Jelmer]

Dat het een Convex Hull. Voor een algoritme:
http://www.icim.fnt.hvu.nl/vak/6NUAP1/ConvexeOmhulling.doc

[mr_taipan]

Dat is precies wat ik bedoelde.

Toevalig iemand die het al in c# heeft geimplementeerd

[.oisyn]

Kom op, zo moeilijk is dat niet

Sorteer de punten eerst op de x-as, van links naar rechts, en voeg vervolgens de eerste twee punten aan je lijst toe. Zoals je aan je eigen plaatje al kunt zien, mag er, als je de lijn volgt, alleen een bocht naar rechts gemaakt worden. Zodra er ergens een bocht naar links voorkomt is het fout, en moet je een aantal punten verwijderen.

Dus je hebt al de 2 punten. Ga nu elke keer een punt toevoegen, en kijk hoe de bocht is over de laatste 3 punten in je lijst. Zolang er een bocht naar links is bij die laatste drie punten, dan moet je het een-na-laatste punt in je lijst verwijderen, totdat er dus een bocht naar rechts is, of totdat je nog maar 2 punten over hebt. Ga dan weer verder met het toevoegen.

Je hebt nu de hele bovenste rand van de convexe omhulling. De onderste rand gaat natuurlijk op dezelfde manier, maar dan van rechts naar links (de bochten blijven wel hetzelfde overigens)

Bepalen of een bochts naar links of naar rechts gaat kan heel simpel met behulp uitwendig product tussen 2 vectoren. In 3D, een uitwendig product tussen 2 vectoren geeft altijd een vector dat loodrecht staat op die 2 vectoren. Aangezien je 2D coordinaten gebruikt, betekent dat dat je altijd een vector terugkrijgt die door je scherm heen gaat. Oftewel, we zijn dan ook alleen maar geïnteresseerd in de z-coordinaat van het resultaat. Als de vector naar je toe gaat, dus een negatieve z, dan is er een bocht naar links. Bij een positieve z is er een bocht naar rechts. Als z=0, dan liggen de 3 punten op één lijn. Aangezien het middelste punt in dat geval dan óók op de convexe omhulling ligt, noemen we dat voor het gemak ook even rechtsom

Een heel verhaal, maar uiteindelijk komt het hier op neer:

code:

bocht (p1, p2, p3)
{
    v1 = p2 - p1;
    v2 = p3 - p2;
    if ((v1.x * v2.y - v1.y * v2.x) >= 0)
        return RECHTSOM;
    else
        return LINKSOM;    
}

[mr_taipan]

Na veel zoek werk was ik er ook achter gekomen en ben ik tot dit resultaat gekomen.

[farlane]

.oisyn schreef op 22 april 2004 @ 15:50:
isobaren zijn trouwens lijnen met gelijke luchtdruk (vandaar de term bar). Ik zie in je kaartje dat je temperatuur gebruikt, dan zijn het dus ook geen isobaren "isolijnen" is de algemene benaming

En isothermen de speciefieke term voor temperatuur.

[mr_taipan]

Nou dit is dan het resultaat.




Dit is met vakjes van 1 bij 1 pixel. Dit duurt ongeveer 5 seconden om in te kleuren :-)


Dit komt omdat er voor elke pixel geken word of hij binnen de polygoon valt.
Als dat zo is word het array waar alle meetpunten in staan gesorteerd op afstand tot de pixel en dan word daar eengemiddelde van genomen en dat word als kleur gebruikt. Moet nog maar eens uizoeken of dat sneller kan

[.oisyn]

OMG
Dat kan makkelijk een factor 1000 (!!!) sneller

[mr_taipan]

Ik weet het.

Alleen weet niet hoe

[Janoz]

mr_taipan schreef op 28 april 2004 @ 14:47:
Nou dit is dan het resultaat.


[afbeelding]

Dit is met vakjes van 1 bij 1 pixel. Dit duurt ongeveer 5 seconden om in te kleuren :-)


Dit komt omdat er voor elke pixel geken word of hij binnen de polygoon valt.

Door telkens te kijken of een pixel rechts (of links) van alle edges ligt (als je van begin naar eind punt van een edge kijkt) kun je heel snel bepalen of een punt ergens binnen valt of niet. Die operatie zit ook al in de confex hull bepaling, dus die zou je zo kunnen gebruiken.

Als dat zo is word het array waar alle meetpunten in staan gesorteerd op afstand tot de pixel en dan word daar eengemiddelde van genomen en dat word als kleur gebruikt.

Je hoeft toch niet de array opnieuw te sorteren voor elk punt? Het bepalen van een gemiddelde is niet afhankelijk van de volgorde van de meetpunten. Ik ben trouwens benieuwd naar je wegings factoren. Ik zie enkele artifacten op je plaatje.

Moet nog maar eens uizoeken of dat sneller kan

Bij deze wat tips dus

[ Voor 4% gewijzigd door Janoz op 28-04-2004 15:50 ]

[Soultaker]

Bij het invullen zou ik werken met scanlines binnen je polygoon, dan hoef je nooit meer te testen of je punt binnen de polygoon licht, maar dan moet je wel even goed nadenken over je code.

Op zich zou een test echter ook wel moeten kunnen, maar ik vind de tijdsduur niet heel verwonderlijk. Met een polygoon van 7 punten zou het testen of een punt binnen een polygoon valt zomaar een slordige 100 instructies (om maar eens ruim te schatten) kunnen vergen; het berekenen van de gemiddelde waarde is nogal FPU heavy, maar met een stuk of 50 FPU instructies per pixel zou je d'r toch wel moeten zijn. Met een totaal van 200.000 pixels zit je dan rond de 1 miljard instructies van (laten we zeggen) gemiddeld 2,5 clockcycles. Een 500 MHz CPU doet er dan inderdaad 5 seconde over.

Neemt niet weg dat het met een beetje low-level optimalisatie aanzienlijk sneller zou moeten kunnen.

[mr_taipan]

Ik sorteer het array met meetpunten omdat ik de 3 meetpunten wil die het dichts bij het punt liggen wat ik aan het testen ben.

Voor elke pixel word voor elke meeting (nu nog maar 11) de afstand tot de pixel berekend en dat word gesorteerd.

Dit is de code die voor elke pixel die binnen de convex hull ligt word uitgevoerd

C#:

if(convex.PointPolygonAlgorithm(myPoints,new Point(x,y)))
{
    //je hebt een punt binnen de buitenste ring
    //sorteer al je meetpunten en pak de beste
    punt = new MeetPunt(x,y,1);
    puntenModel.Sort(new DistanceComparer(punt));

    int p0 = Math.Abs((int)((Meting)((MeetPunt)puntenModel[0]).getMetingen(mac)).getAverageSS());
    int p1 = Math.Abs((int)((Meting)((MeetPunt)puntenModel[1]).getMetingen(mac)).getAverageSS());
    int p2 = Math.Abs((int)((Meting)((MeetPunt)puntenModel[2]).getMetingen(mac)).getAverageSS());

    p0 = (int)((p0 - 40) * 255 / 80);
    p1 = (int)((p1 - 40) * 255 / 80);
    p2 = (int)((p2 - 40) * 255 / 80);

    int gem = (int)((p0 + p1 +p2)/3);
                        
    SolidBrush p = new SolidBrush(Color.FromArgb(255,gem, gem, gem));
                        
    g.FillRectangle(p,x-3,y-3,7,7);
}

class DistanceComparer : IComparer
    {
        MeetPunt p;
        public DistanceComparer(MeetPunt p)
        {
            this.p = p;
        }
        
        public float distanceBetweenPoints(MeetPunt x, MeetPunt y)
        {
            float zijde1 = 0;
            float zijde2 = 0;

            if (x.getX() > y.getX()){zijde1 = x.getX() - y.getX();}
            else { zijde1 = y.getX() - x.getX();}

            if (x.getY() > y.getY()){zijde2 = x.getY() - y.getY();}
            else { zijde2 = y.getY() - x.getY();}

            float result = (float)Math.Sqrt( ( (zijde1) * (zijde1) ) + ((zijde2) * (zijde2)));
            return result;
        }

        public int Compare (object o1, object o2)
        {
            float value1 = distanceBetweenPoints((MeetPunt)o1,this.p);
            float value2 = distanceBetweenPoints((MeetPunt)o2,this.p);

            return value1.CompareTo(value2);
        }
    }

Nu word nog het hele plaatje gescand dus daar kan ik nog wel wat optimaliseren. Alleen veranderd er nog niks met de snelheid van het kleuren.

Mischien dat ik dat sorteren zelf wat sneller kan maken door niet te sorteren maar alleen de 3 beste punten er uit te halen.

[Soultaker]

Een eerste tip is om te sorteren op afstand in het kwadraat; dat levert dezelfde ordening op als sorteren op afstand, maar scheelt je een heleboel worteltrekken. De gekwadrateerde afstand tussen twee punten is gewoon ((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y)). Je hoeft niet te controleren of je zijden positief of negatief zijn, want als je ze gaat kwadrateren wordt het toch allemaal positief. Verder doet de compiler de common subexpression elimination wel voor je, al is dat misschien een kwestie van smaak.

Verder is het nogal overbodig om elke keer dat je punten gaat vergelijken opnieuw die berekening te doen; je voert 'm dan O(N*log(N)) keer uit, in plaats van N keer. Je kunt dan beter een keer elk paar (bestaande uit punt en afstand tot je referentiepunt) een keer uitrekenen (en in een struct stoppen, bijvoorbeeld) en die sorteren op de opgeslagen afstand.

Tenslotte snap ik niet echt hoe je op de plaatjes uitkomt die je eerder gaf (die tot in detail zijn uitgewerkt) als je in plaats van pixels blokken van 7x7 pixels tekent.

[mr_taipan]

Ik had toen de blokjes ingesteld op 1 pixel om tot een mooi plaatje te komen.

Maar omdat dat te veel tijd kost heb ik er blokjes van 7 bij 7 van gemaakt. Omdat ik ook aan het uitvissen was hoe ik een zo'n groot mogelijk verloop in de kleur kan krijgen.

[12_0_13]

Ah okee.. Ik snap alleen niet dat het zo lang duurt...

Een groot kleurverloop kan je bereiken door bijvorobeeld de Hue te gebruiken in HSL ruimte (beter is een bepaalde Lab ruimte geloof ik) daar was laatst nog een topic over van Zoijar

[ Voor 136% gewijzigd door 12_0_13 op 29-04-2004 11:34 ]

[.oisyn]

Soultaker schreef op 29 april 2004 @ 10:28:
Een eerste tip is om te sorteren op afstand in het kwadraat; dat levert dezelfde ordening op als sorteren op afstand, maar scheelt je een heleboel worteltrekken. De gekwadrateerde afstand tussen twee punten is gewoon ((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y)). Je hoeft niet te controleren of je zijden positief of negatief zijn, want als je ze gaat kwadrateren wordt het toch allemaal positief. Verder doet de compiler de common subexpression elimination wel voor je, al is dat misschien een kwestie van smaak.

Sterker nog, met lineaire algebra kun je de kwadratische afstand per punt slechts met twee optellingen per pixel berekenen. Ook hoef je niet elke keer te sorteren, je bent immers niet geinteresseerd in een volgorde, maar geinteresseerd in de 3 dichtsbijzijnde punten. Dat kun je in constante tijd bepalen met enkele if-statements door gewoon slechts 3 punten bij te houden, en een punt in te voegen als ie onder het maximum valt. Bovendien is er ook nog zoiets als spatial coherence: de volgorde zal niet elke pixel drastisch veranderen, dus als je de volgorde van de vorige pixel meeneemt dan hoeft er slechts op de scheidingslijnen opnieuw "gesorteerd" te worden.

[mr_taipan]

.oisyn schreef op 29 april 2004 @ 12:49:
[...]

Bovendien is er ook nog zoiets als spatial coherence: de volgorde zal niet elke pixel drastisch veranderen, dus als je de volgorde van de vorige pixel meeneemt dan hoeft er slechts op de scheidingslijnen opnieuw "gesorteerd" te worden.

Hoe kan ik van te voren weten of er een verandering op gaat treden of niet? En tijdens het sorteren word de afstand berekend.

Hoe dat sorteren precies gaat weet ik niet omdat het door het systeem gedaan word. Zal wel een soort van quicksort zijn

[.oisyn]

mr_taipan schreef op 29 april 2004 @ 13:10:
[...]


Hoe kan ik van te voren weten of er een verandering op gaat treden of niet? En tijdens het sorteren word de afstand berekend.

Je hebt toch een maximale waarde van je 3 punten? Als dan tijdens het berekenen van de afstand een ander punt onder deze waarde blijkt te vallen, moet je dat nieuwe punt invoegen in de lijst van 3 punten.

Hoe dat sorteren precies gaat weet ik niet omdat het door het systeem gedaan word. Zal wel een soort van quicksort zijn

Dat doe je sowieso al fout, zoals Soultaker al zei gebeurt dat berekenen van afstand niet 1 keer. Elke keer als 2 punten met elkaar moeten worden vergeleken ga jij de afstand opnieuw berekenen. Dat moet je juist eerst doen, en daarna pas sorteren

[Soultaker]

Waarom trouwens alleen de drie dichtstbijzijnde punten meenemen? Ik kan me voorstellen dat dat gekke artifacts geeft.

[ Voor 30% gewijzigd door Soultaker op 29-04-2004 13:31 ]

[mr_taipan]

Soultaker schreef op 29 april 2004 @ 13:31:
Waarom trouwens alleen de drie dichtstbijzijnde punten meenemen? Ik kan me voorstellen dat dat gekke artifacts geeft.

Omdat het om signaal sterkte gaat van een draadloos netwerk. Punten die te ver weg liggen zeggen helemaal niks over de plek waar je het gemiddelde wilt weten


Ik heb het sorteren zelf gemaakt. Er word nu maar 1 keer per punt berekend wat de afstand is.

Oude methode duurde bijna 6 seconden
Nieuwe methode duurt net iets meer dan 3 :-)

Dit is de code van de nieuwe sorteer methode

code:

public MeetPunt[] getThreeBest(ArrayList punten, MeetPunt p)
        {
            MeetPunt[] tempPunten = new MeetPunt[3];
            float[] dist = new float[3];
            float max = 0;
            int maxindex = 0;
            for(int i = 0; i < 3; i++)
            {
                tempPunten[i] = (MeetPunt)punten[i];
                float dis = distanceBetweenPoints((MeetPunt)punten[i],p);
                if(dis > max)
                {
                    max = dis;
                    maxindex = i;
                }
                dist[i] = dis;
            }
            for(int i = 3; i < punten.Count; i++)
            {
                float dis = distanceBetweenPoints((MeetPunt)punten[i],p);
                if(dis < max)
                {
                    tempPunten[maxindex] = (MeetPunt)punten[i];
                    dist[maxindex] = dis;
                    max = dist[0];
                    maxindex = 0;
                    if(dist[1] > max)
                    {
                        max=dist[1];
                        maxindex = 1;
                    }
                    if(dist[2] > max)
                    {
                        max=dist[2];
                        maxindex = 2;
                    }
                }
            }

            return tempPunten;
        }

Zal nu ff proberen om eerst alle afstande te berekenen en dan het sorteren aan een comparer over te laten.

edit

heb het geprobeerd en dan duurt het weer een seconde langer. Ik laat daarom het sorteren er maar helemaal uit

[ Voor 10% gewijzigd door mr_taipan op 29-04-2004 14:55 . Reden: iets vergeten ]

[Swinnio]

Niet om het een of ander, maar ben je toevallig zoiets


aan het maken?

[ Voor 63% gewijzigd door Swinnio op 29-04-2004 16:10 ]

[mr_taipan]

Dat ziet er wel heel erg mooi uit.

Als die van mij er zo uit komt te zien ben ik wel heel