Veckans problem nr2 - 1bit bitmap to vector

Jag gjorde en riktig fulkodning...
Programmet läser upp bilden i en 2D-array.
Där letar den reda på alla kanter och lägger dem som intresanta punkter. Den söker av bilden horizontalt.
Det var här det körde ihop sig för mig. Jag vill söka av bilden vertikalt neråt oxå och lägga ihop de båda listorna med intressanta punkter. Dock så var det FÖR mycket jobb för att hinna få klart det. Jag hade lite annat att göra i helgen som var oxå.
Där efter så loopar jag igenom koden och kan välja vilken frekven av intressanta punkter som jag ska rita linjer mellan.
Programmet tar bort punkter som är onödiga om t.ex. linjen går horizontalt eller vertikalt.

Hade jag vart smart ifrån början hade jag sökt efter 1 intressant punkt och sedan följt kanten, och räknat ut vinklar och skapat vektor punkt i de skarpaste vinklarna.

Resultat av källkoden med 1 scanning...

Min letar först reda på en startpunkt genom att leta efter två punkter so är olika, sen följer den utkanten på formen tills den inte kan följa mer.
Sen tar den helt enkelt bort var n:te punkt.
Jag hade tänkt att använda en formel för vinkel istället, men jag kunde inte komma på hur man räknar ut vinkel förrens lite väl sent. Så det är bara implementerat för att se till att man inte har två punkter på rad och för att sortera bort överflödiga punkter.
Och om man skickar kommandot gui till programmet (efter bildnamn och storlek) får man ett fönster där formen är uppmålad.

Koden är nog den fulaste jag srivit då jag inte hade tid till a koda vettigt...

Min kod är jävligt bra på att göra rätt former, fast på tok för jävla långsam. I och med att jag inte klarar 1min's gränsen med C# så bajsar jag på att skicka in.

Hade nog gått att optimera tillräckligt, ifall man hade haft lite mer tid. Var helt jävla suveränt problem. Hoppas på veckoproblem i fortsättningen.

Jag tracar runt trädet = 904 punkter.

Sen tar jag bort alla punkter som fortfarance ger 0 i score (Runt 200 punkter kvar)

Efter detta så testar jag att ta bort samtliga punkter, en åt gången. Den punkt som försämrar min score minst åker ut.

Sen upprepar jag detta, tar bort en punkt åt gången tills jag har 20 kvar. Resultatet blir skitbra, men jävlar vilken tid det tar. Använder GDI+ egna regions- och polygonfunktioner, och dom suger nåt så in i helvete.

Fuck, nu har Bizon säkert tid att jobba på de nya problemen på mathschallange, jag som hade tänkt bli första svensk att lösa de två nya.

Mycket bra tävling och hoppas på en ny lika bra nästa vecka.

Matrics:

Suverän tävlingsledning måste jag säga... Bra jobb med tävlingssidan.

Alla: Kul att så många var med och klurade. Hoppas det blir fler tävlingar även fall ribban inte ligger direkt lågt på arangemangsfronten just nu
Kul att se hur olika lösningar som folk kommer på för att lösa samma problem.

Japp det var ett lysande arrangemang. Jag ser fram emot nästkommande batalj!

Någon som har lust att förklara hur Bizons metod fungerar?

Detta är ju det ultimata sättet, vad fick du för bästa poäng på 20 linjer på trädet (och hur lång tid tog det)?

Har du skrivit hemsidan på ett sådant sätt att du slipper för mycket jobb för nästa problem? Och skall vi satsa på ett veckoproblem nu?

madah: 1200 när jag kollade var 4:e(!) pixel vid score-räkningen, vid punktborttagningen (detta för att snabba upp).. Hade jag checkat varje pixel hade jag väl fått vänta nån timma, men resultatet hade ju blivit perfekt. Nu blev det ju ganska skevt

När jag upptäckte att jag inte kunde komma ner ens under 5-10 minuter så gav jag upp..

Bizon....................................................................Independence

Hmm.. Undrar vem jag helst hade anställt som programmerare inom datorgrafik...

Närå. Bara skoj att jämföra algorimterna. Och klart som fan att jag inte har nått att säga till om när jag själv inte ställde upp.

Men jävligt skön tävling och dyker det upp ett lika trevligt problem igen så är jag lungt med! Tyvärr dök den här tävlingen upp mitt i tentaplugget.

Här kommer en kort förklaring på hur mitt program fungerar:

Uträkningen av punkterna görs i 3 olika steg:

Steg 1:
Programmet hittar den första raden uppifrån med en vit punkt och tar fram x,y för första punkten från vänster på den raden. Sedan följs kanten runt hela bilden ända tills man kommer tillbaka till startpunkten. Alla dessa kantpunkter lagras i en array.

Steg 2:
Varje kantpunkt beräknas hur mycke "felet" förändras om man skulle ta bort just den kantpunkten. Felet beräknas som en summan av avstånden från linjen till de punkter linjen ska approximera (vinkeln mellan närliggande punkter som approximeras vägs också in).
Sedan tas punkerna bort en efter en tills man nått det antal punkter som man vill ha. De punkter som ger minst fel-förändring tas bort först.

Steg 3:
Alla punkter ligger ju på kanten sedan steg 2, och det är inte alltid optimalt. Därför görs en sk "gradient descent" där punkterna flyttas lite för att se om det ger ett bättre värde. Blir värdet bättre så behålls den nya positionen osv. Detta görs några 100 ggr eller tills värdet inte förbättras längre. För att inte få konstiga resultat så får inte punkterna hamna för nära varandra under "gradient descent" algoritmen så det kollas också.

Fått några idéer om problem ännu?

Vi kanske skall försöka lägga ribban lite lägre på arrangemanget så att folk vågar hålla i det. der matricks gjorde var ju kanon med tävlingssida osv, Men man kan ju tänka sig att man bara kör det i en tråd direkt här på Swec. Så får de som är med och tävlar alla hjälpa till och göra det så smidigt som möjligt... Jag menar med att släppa kod som läser in etc... Den som håller i det presenterar uppgiften i en ny tråd och sedan ser han till att editera första posten med ny information rullande under helgen.

Jag kan inte hålla i det denna helg men kan tänka mig att hålla i en senare... Bara det inte gnälls för att det inte blir lika bra som matricks

Matrics: Jag tycker du gjorde ett bra jobb

Alla tycker att matricks gjorde ett suveränt jobb. Och tävlingen vad förbannat rolig.

Men i och med att det blev lite stressigt med problemet under endast en helg och det dessutom är snack nu om veckoproblem, så vad sägs om att du, matricks, bara släpper problemet på fredagen, så kan vi förbereda oss lite smått och så kan du fixa till sidan under veckan. Tror inte det blir av om inte du sätter igång nästa problem

Bra ide.. Då kan ju fler vara med även fall dom är upptagna lite då och då...

Vi kör fredag 18:00 -> Söndag 18:00 (9 dagar). Sen vilar vi i 5 dagar också kör vi igång nästa problem...

Låter bra, då kan ju även fler vara med som inte är så duktiga på programmering (jag exempelvis ;), visst jag kan PHP men det passar inte riktigt in här känns det som, lär mig dock C++).

Vi får ju sätta upp olika klasser bara... En för varje språk... Då kan man ju vinna om man löser problemet i ett skitknepigt språk... Skojjigt!

Usch, optimeringar verkar inte vara min grej Men men, jag ska försöka. Man lär väl sig något iallafall.