Veckansproblem Nr.3 - "No turn point"

Okej.. Jag har en idé om hur man alltid kommer fram, men frågan är hur fan det skall optimeras.

Så här ser min algoritm ut på papper:

Nu är det bara att implementera

Blir nog en a* där jag söker på vinklar för min del...

Hur blir det med kanterna mellan svart och vitt??? Linjen mellan två punkter kommer ju inte att skära att täcka hela pixlar. Hur räknas det... Får man skära en svart pixel sålänge man bara skär den med mindre än halva arean... Eller får man inte ens nudda dom svarta... hur kommer isf valideringen gå till. Hur kommer det att avrundas för att approximera vilka pixlar som en linje "täcker "

Skickar med en bild med linjer ritade i paint... Så ser ni vad jag menar.

EDIT: Bilden blev lite liten... Men förstora den tyå 1000% så ser ni vad jag menar. Lägger till ytterligare en liten förklarande bild

00000000000000*00000
00**00000000000*0000
0000**000000000*0000
000000**00000000*000
00000000**0000000*00
000000000000000000*0
0000*0000000000000*0
00000*0000*****0000*
000000*00000000****0
0000000*000000000000
00000000*00000000000
00000000000000000000

Lite olika "linjer". dom blir ju inte linjer på pixelnivå, så hur skall vi avrunda för att få samma pixlar för samma linje på två olika implementeringar?

Jovisst... Men när man drar sina linjer mellan punkterna man fått fram... Hur avgörs det då om en linje skär kanten mellan vitt och svart och således är en otillåten väg? Hur nära kan man gå en svart pixel innan man anses ha varit på den? < halva?

Antas linjen vara oändligt tunn eller är den tjock som en pixel?

på bilden nedan har jag ritat in pixlar på två olika sätt för samma linje... Vilken går vi efter?

Man kan ju sätta upp såna här regler:

- En samling pixlar beskriver en linje.
- En pixel i samlingen måste omges av två andra pixlar i samlingen (även diagonalt räknas).
- Ändpixlarna får vardera bara gränsa till en annan pixel i mängden.
- Linjen skall från centrum till centrum på de två ändpixlarna.
- Varje pixel i mängden skall vara belägen så att om man drar ett oändligt tunt streck mellan start och slutpunkten skall pixeln skäras av linjen.
- De pixlar som beskriver linjen skall vara det minsta antalet pixlar som följer reglerna ovan

Då får man den linjen till vänster i min bild...

Nog för att jag med säkerhet kommer att komma sist, men jag skall nog ta och försöka på denna. Den förra verkade rolig, så jag hoppas på samma sak här (missa den andra). Bra att det är lång tid nu, kan behövas

Fuck.. Nu börjar jag komma på massa bra idéer.. Min algoritm ger inte den absolut snabbaste och bästa vägen, men en hyffsad väg iaf.. Tillräckligt för att vinna iaf

Fast det är inte snabbaste vägen vi vill ha, utan minst antal punkter (om jag förståt det rätt)

Jepp.. Helt korrekt... Det gör ju det hela lite mer intressant

Det jag menade

Eller rättare sagt. Den kortaste vägen avgör vid lika många punkter

Jag har en riktigt säker metod annars. Men då måste seti låna ut sin samlade datorkraft till dom som vill köra programmet.

Var ett tag sedan jag sysslade med C++ tyvär. Men det får väl visa sig... Jag får väl köra med en pixels säkerhetsavstånd helt enkelt.

Vi har ju viewern. Det blir ju inte speciellt svårt för oss att justera nån pixel om vi märker att den inte håller med

ERx: Läs bara in bilden ungefär som en fil, leta sedan efter ifyllda områden (1) och tomma områden (0).

Hur Cargo gör

EDIT: Det kanske är det där med Big/Little endian som du hänger upp dig på? Googla på det så fattar du... Det gjorde jag iaf.

Jag har lyckats framställa en algo nu, här kommer lite benchmarks:

(95, 90) --> (490, 490) på 11 turn points

(490, 100) --> (18, 498) på 2 turn points

(95, 90) --> (490, 234) på 8 turn points

Snyggt, din jävel Nu blev jag lite stressad.

Här får ni se min algo at work:

http://upl.silentwhisper.net/uplfolders/upload6/lalala.JPG

Den skrapar i lite i kanterna men det beror på skillnader i min linje algo och matricks linje algo.

Det tog ca: 5-6sek för mitt program att räkna ut detta.

Hmm... Din fungerar garanterat inte på samma sätt som min ser jag efter bilden..

Äsh.. Jag har en finfin ide... Men har inte hunnit börja implementera ännu... Grrr...

Om nån skall använda sig av .Net så har jag skrivit en RawBitmap klass i C# jag gärna skickar.

RawBitmap klassen läsen in en rawbitmap till en bool[][] för snabbhetens skull. Den kan även ritas ut till ett Graphics-objekt genom en GetBitmap metod som representerar en standard GDI+ bitmap.

Era jävlar som börjar få färdiga lösningar. Själv funderar jag fortfarande på hur det ska lösas teoretiskt...

Oj.. Fan vad snabbt ni har arbetat.. Jag har gjort basklasserna för inläsning etc och precis avslutat teorin bakom min algoritm. Skall implementera ikväll/imorgon.

Edit: Både don_tomaso och ookk får bättre resultat.. Dammit, bara att börja om

Lite mer bench på mitt program:

http://upl.silentwhisper.net/uplfolders/upload6/resultat.JPG
http://upl.silentwhisper.net/uplfolders/upload4/resultat3.JPG

Tog ca: 15s att generera.