[Algo] Blokken vinden in raster?

[TheBlasphemer]

Ik zoek een simpel algoritme om een raster (zie het maar als een plaatje) op te delen in blokken van hetzelfde type (kleur).
Ik heb tot nu toe een simpel ding dat elke pixel afgaat en vervolgens kijkt hoeveel pixels daaronder hetzelfde zijn, en daarna gaat ie dat ook nog eens in de breedte doen. Dat slaat ie dan op, en hij zet die pixels naar 0.
Dit werkt op zich prima, maar ik heb het idee dat dit niet optimaal is.
Het doel is om zo weinig mogelijk blokken te hebben...

Kent iemand hier wat voor?

Alvast bedankt,
TB

[Verwijderd]

Moeten die blokken vierkant of rechthoekig zijn? Of zoek je de grootste cluster van aaneengesloten blokjes van dezelfde kleur?

[Woy]

Ik denk dat je eens moet zoeken op Segmentation algoritmes. Of als het echt precies egaal gekleurde vlakken zijn kan je natuurlijk ook gewoon een flood-fill algoritme gebruiken.

[TheBlasphemer]

Verwijderd schreef op dinsdag 27 december 2005 @ 23:10:
Moeten die blokken vierkant of rechthoekig zijn? Of zoek je de grootste cluster van aaneengesloten blokjes van dezelfde kleur?

Rechthoeken

rwb schreef op dinsdag 27 december 2005 @ 23:32:
Ik denk dat je eens moet zoeken op Segmentation algoritmes. Of als het echt precies egaal gekleurde vlakken zijn kan je natuurlijk ook gewoon een flood-fill algoritme gebruiken.

Het zijn precies egaal gekleurde vlakken, maar flood-fill maakt geen rechthoeken

[Woy]

Geef eens een plaatje als voorbeeld? Ik snap denk niet helemaal meer wat je wilt.

[MTWZZ]

Kijk eens of je dit boek ergens kunt bemachtigen:

Digital Image Processing
Rafael C. Gonzalez and Richard E. Woods.
Published by Addison Wesley in 1993

[TheBlasphemer]

rwb schreef op woensdag 28 december 2005 @ 11:30:
Geef eens een plaatje als voorbeeld? Ik snap denk niet helemaal meer wat je wilt.

Voorbeeld:
Spel-level ziet er zo uit (elk blokje is 16x16 pixels, types hier zijn muur, ijs, rubber, player1, player2, shield,info,retry,forceup):


Ik zou het graag verdeeld zijn als:

(Dit is naar mijn idee de beste oplossing, maarja ben menselijk, dus kan me flink vergissen)

Zo iets duidelijker ?

[.oisyn]

Waarom moet het aantal blokken zo klein mogelijk zijn? Waarom wil je eigenlijk überhaupt die blokken weten?

[TheBlasphemer]

Spelletje gaat collision detection doen, om per tile te doen is vrij intensief (hij moet langs elk object loopen).
Als ik het aantal rechthoeken dus zo klein mogelijk houd issie (ietwat) sneller

[Soultaker]

Als al je invoer er precies zo uitziet als dat voorbeeld, dan lijkt het me vrij simpel. Je deelt het veld op in tegels van 16x16 en dan zoek je bij elke tegel het juiste plaatje; die tegels komen al voor 99% overeen met de plaatjes zo te zien.

edit:
Oh, je wil die tegels ook indelen in rechthoekige blokken, waarvan je het aantal dan weer wil minimaliseren.... nog maar even over nadenken dan.

[ Voor 26% gewijzigd door Soultaker op 28-12-2005 12:33 ]

[Verwijderd]

Voor collision detection zou ik het heel anders aanpakken (http://www.moock.org/webdesign/flash/actionscript/collision/)

maar als je het met rechthoeken wilt doen, dan zou ik beginnen met een rechthoek op te delen in twee driehoeken.

Kijk hier eens: http://www.math.ucdavis.edu/~latte/theory.html

[D4Skunk]

Niet optimaal, maar imho het eenvoudigste : je slicet gewoon alles verticaal, en dan gooi je alles tesamen wat naast elkaar ligt en hetzelfde aantal blokken in de diepte heeft. De meest optimale oplossing is niet altijd nodig hoor...

[.oisyn]

TheBlasphemer schreef op woensdag 28 december 2005 @ 12:30:
Spelletje gaat collision detection doen, om per tile te doen is vrij intensief (hij moet langs elk object loopen).
Als ik het aantal rechthoeken dus zo klein mogelijk houd issie (ietwat) sneller

Dus je wil van point location in een grid, wat O(1) kost, naar point location in een blok soup, wat minimaal O(log N) is? Hint hint

Verwijderd schreef op woensdag 28 december 2005 @ 12:40:
maar als je het met rechthoeken wilt doen, dan zou ik beginnen met een rechthoek op te delen in twee driehoeken.

Collision detection met axis aligned rectangles is een stuk makkelijker dan met arbitraire driehoeken hoor

[ Voor 29% gewijzigd door .oisyn op 28-12-2005 12:47 ]

[TheBlasphemer]

.oisyn schreef op woensdag 28 december 2005 @ 12:45:
[...]


Dus je wil van point location in een grid, wat O(1) kost, naar point location in een blok soup, wat minimaal O(log N) is? Hint hint

HELP!
Ik doe (helaas) nog maar VWO hoor... Volgend jaar mag je me doodgooien met dat soort dingen als ik Informatica studeer

[Woy]

Wat .oisyn bedoelt is denk dat je als je de goede datastructuur van je objecten gebruikt je in een grid heel makkelijk kan vinden of er op een locatie een object staat. Dat is veel makkelijker als voor alle objecten gaan kijken of er een collision is. Je weet tenslotte waar alle objecten heel willen bewegen. En waar objecten staan in het grid

[TheBlasphemer]

Mwja, tilemap was misschien wel makkelijker geweest,
maar dat vind IE nooit zo leuk, en daarbij geeft dit ook de mogelijkheid om halve blokjes enzo te doen...

EDIT: maar de level editor (waar dit probleem eigenlijk voor is ) werkt wel met blokjes van 16x16, simpelweg omdat dit makkelijker "designen" is

[ Voor 33% gewijzigd door TheBlasphemer op 28-12-2005 13:42 ]

[Woy]

maar dat IE het niet leuk vindt hoeft nog niet te maken dat je het intern niet zo opslaat! En ook met een grid kan je best met halve blokjes werken. Dan maak je je grid gewoon fijner