Veckans problem nr2 - 1bit bitmap to vector

Jorå... Jag skall bara se till att generera ut resultatet med

Jag tar också och ger upp, min fastnar hela tiden efter ca 5-10 punkter.. och jag fattar verkligen inte varför :\

Kul med tävlingar, men vore det inte bättre att ha dem över lite längre tid?

oops

EDIT: Äsch... nu ändrades ju bilden... Trädet var på fel håll förut... Det var lite roligare

Kom precis hem och ska duscha, äta, och fixa ett par saker.

Skulle verkligen uppskatta om vi sköt upp det till 21:00. Det är en mycket finare och jämnare tid än 20:00, tycker ni inte det?

Edit: Jag tar tillbaka det. Får satsa lite hårdare till nästa gång. Har iaf skickat min ofärdiga lösning till Matricks, så kanske någon Delphi-programmerare lär sig något.

Fråga till dom som kodar java:

Vad skall jag använda för kommando för att skriva ut resultatet. Just nu så använder jag mig bara av System.out.println(resultat); ?

0 @ 373

Nepp... Jag måste nog lägga ned... Hinner inte tyärr...

Bra uppgift. Hade man haft lite mer tid så... Men nåt blev det ju iaf

Hoppas detta kan blie en tradition. Man lär sig mycket av att tävla i programmering.

Ah, har lyckats med lite trixande och tweakande nu fått 865 @ 20. Tar endast 17 sekunder på min burk (P4, 2.4 GHz).

Med lite mer extrem bruteforcing har jag lyckats komma ner till 857 @ 20, men då stod programmet och tuggade i ~40 min...

Tänkte jag skulle nå ner under 700, men har inte riktigt en aning om hur det ska gå till. Är nog min metod som sätter gränsen. Råkade visst bli lite spaghettiröra av koden också så det blir nog inga mer större ändringar nu.

Det lägsta antalet punkter som man kan få 0 fel med?

Vet inte, men jag tror inte det.
Just nu har jag bara tagit bort raka linjer på 0, 45 samt 90 grader. Går nog att få ner mer än detta.

Posta gärna din kod ändå.

Det är intressant att se olika sätt att lösa ett problem på, även om de inte är kompletta.

Har haft mycket att göra i helgen, annars hade jag varit med. Ska försöka vara med nästa gång dock, och det ska bli kul att se hur ni har löst veckans.

Hm, okej, men det är en riktigt rutten lösning..

Blunda!

Här kommer ett riktigt fulhack

Han inte lägga till kommentarer på min innan jag skickade den.
Men skriver dem här istället:
Min algoritm letar först fram innerkonturen på bilden och lagrar dessa pkter.
Sen utifrån hur många maxlines är så väljer den var n:te pkt.
Simpelt och ineffektivt, men den löser uppgiften i alla fall.

Däremot har jag en version som tar fram lösning med 0fel (eller väldigt nära på extrema bilder).

Provade med en version som testar hur mycket fel det är och sedan flyttar pkterna lite slumpvis, dock var min testfunktion så långsam så jag la ner projektet.

Jag misstänker att jag har en lite udda lösning på problemet, det ger knappast bra resultat och den är inte så snabb heller skulle jag inte tro, men den är iaf lite annorlunda. Den går ut på att den skapar en cirkel med det antal punkter som man har angett som parameter när man kör programmet, och sedan flyttar den alla punkterna mot mitten tills den träffar något som är vitt. Som ni förstår så fungerar detta extremt dåligt på former som t ex gap.raw om ni har sett den, men den borde lämpa sig relativt bra på trädet om man jämför med andra former. Ändå så fick jag sämst resultat tror jag..
Här är koden om någon vill se: http://files.blinkenlights.se/independence_bitmaptovector.cpp

Hade också den principen först innan jag ändrade.

Min lösning hör garanterat till de simplaste. Bilden delas upp i många mindre områden, och varje sådant område söks av var för sig. Om området innehåller både svart och vitt (i mitt program är det dock rött och vitt, fråga in varför), betyder det att området innehåller en kantbit av bilden. Om det är så, placerar en punkt mitt i det lilla området.

Det är väldigt enkelt, men tar också väldigt lite tid på sig. Från att programmet har startats, till att bilden är laddad och analyserad, och punkterna är utsatta, går det mindre än 0.3 sekunder. Punkterna placerat ut relativt bra, tycker jag.

Felet i programmet är att punkterna skapas i fel ordning. De skapas från vänster till höger, uppifrån och ner, villket gör att Matricks testprogram connectar punkterna fel.
Postar bilden som förklarar felet igen;

Så här funkar mitt program:

Först letar den fram innerstrukturen, dvs tar fram en linje för varje pixel (så man får en bild med 0 fel). Den första vita pixeln letas upp, sedan trace:ar den enligt alltid-följa-vänster-vägg regeln tills den kommit till startpositionen igen.

Sedan så sker en avvägning, där den linje som har minsta vinkeldifferensen tas bort. På detta sätt tas linje för linje bort tills man har så många som önskats (t ex 20 linjer). När en linje tas bort så räknas vinkeldifferensen om för föregående/efterföljande linjer.

Förbättring 1: Avvägningen baseras också på linjens längd, kortare linjer har större chans att tas bort. Använde denna formel: A = vinkeldiff * längd.

Förbättring 2: Längdens betydelse kan varieras. Använde formeln A = vinkeldiff * (längd ^ p) , där p är ett värde som jag lät variera mellan 0.0625 upp till 8. Lägre värden visade sig vara bra på bilder med massor med korta "spröt" och högre för bilder med långa linjer.

För varje nytt värde på p så räknades hela bilden om med poängen, och den bästa poängen (med de bästa linjerna) sparades.

Förbättring 3: Bruteforce. Värdet för x,y på punkten för varje linje ändrades, och för varje ändring så räknades poängen för hela bilden om. Den bästa sparades hela tiden osv.

Jag lyckades dock aldrig få poängberäkningen att helt överensstämma med matricks, så min lösning är nog inte helt optimal.

Min tänkta lösning är väldigt lik madah:s ovan. Men jag hann bara koda så jag fick ut innerkonturen. Sen orkade jag inte längre så då fulade jag till det lite. Medans jag letade fram innerkonturen så sparade jag för varje vit kantpixel hur många svarta den angränsade emot. Sen tog jag de punkterna som hade mest angränsande svarta och plockade ut lika många punkter som det skulle vara linjer. Lösningen är inte särskillt bra men den är ganska snabb

EDIT: Medans ni ändå väntar på resultatet så kan ni ju ta och hjälpa mig lite http://forum.sweclockers.com/showthread.php?s=&threadid=34963...