3D-s szélessége bejárás C/C++ -ban

Címkék
3D-s szélessége bejárás C/C++ -ban
2012-02-20T13:48:22+01:00
2012-02-21T18:16:50+01:00
2022-11-24T19:05:38+01:00
szivar1
Hello!

Egy olyan kérdésem lenne, hogy ha van egy 3D-s bináris tömböm (ami egy kép vázát tartalmazza) akkor azt hogy tudom szélességi kereséssel bejárni?
/Egy tüdő egy pont vastagságú vázát tartalmazza a tömb és ezt a vázat szeretném felcímkézni az elágazásokban szélességi keresés alapján.Megvan a kezdőpont (9,85,26) ill. az elágazáspontok koordinátái is./
Tudna valaki segíteni!

Előre is kösz az infókat!
Mutasd a teljes hozzászólást!
Illetve bocs, ez nem szélességi, hanem mélységi bejárás, összekevertem. Kell egy lista a csúcsokról valóban, hiszen csak akkor szabad mélyebbre menned, ha már egy szinten megvan minden fia a gyökérnek.
Mutasd a teljes hozzászólást!

  • Nyilván ki lehet találni, hogy kell tömbben lépkedni ehhez, de valószínűleg bonyolult és biztosan felesleges. Építs belőle egy rendes fát és azon csinálj BFS-t.
    Mutasd a teljes hozzászólást!
  • És hogyan építsek belőle fát? Ahhoz tudnom kéne, hogy egy elágazáspont melyik részfához tartozik,nem?
    Pl: amit csatoltam képet ott a farokból kiinduló fát akarom "szintenként felcímkézni" (azaz szélességi keresést végezni).
    A int pontok [x][y][z] mondja meg, hogy vázpont-e vagy sem, a int szomszedok[x][y][z] pedig h hány szomszédja van (ha 2nél több akkor elágazás)
    Te hogy csinálnád meg?
    Mutasd a teljes hozzászólást!
    Csatolt állomány
  • Félreértettelek, azt hittem, hogy a tömböd elemei a gráf pontjai és nem egy bitmapről beszélünk. Így egy kicsit máshogy áll a dolog.

    Ennél a feladatnál elindulnék* a kezdőpontból úgy, hogy addig mennék a pontok tömbben, amíg a szomszedok tömbben azt nem látom, hogy 2-nél több szomszédja van, vagyis elágazás, vagyis a tényleges gráf egy pontja, és ezt tenném a fába, illetve címkézném fel. Innen rekurzívan tovább (a csúcspontban hasonló módszerrel meghatározod az elágazások irányait és folytatod), az újonnan felfedezett csúcsok az előző gyerekei lesznek.

    * elindulni = egy adott pontot "körbeszimatolsz" és amerre van szomszédos pont, mész tovább. A dolog természete miatt valószínűleg lehet úgy optimalizálni, hogy 27 elemű tömbben mindig a tetejére buborékoztatod az éppen nyerő irányt és ebben a sorrendben próbálod a következő lépést.

    Továbbá valószínűnek tartom, hogy a pontok tömb végigolvasását alaposan le lehet csökkenteni, de most késő van hozzá, hogy tovább optimalizáljam :)
    Mutasd a teljes hozzászólást!
  • Én is így gondoltam...
    A vázbejárás megvan, elmegy egy adott elágazásig (ill ha úgy állítom be akkor "végigfut az egyik szálon" de azzal volt bajom, hogy utána hogy talál vissza a korábbi ponthoz.
    Arra gondoltam, hogy esetleg egy Stack -vel meg lehetne oldani. (ki- be lehetne pakolni azokat a csúcsokat amik már nem kellenek és a sorrendet is megtartja)
    Szerinted ez nyerő lehet?
    Mutasd a teljes hozzászólást!
  • Ha magad nyilvántartasz egy stacket, az ugyanaz, mintha a rekurzív hívásokkal tennéd (ott is stack van, csak implicit módon). Valahogy így paraméterezném:

    bejár(gyökér, irány) {

    Amikor találsz egy csúcspontot, akkor:

    gyökér.hozzáfűz(csúcs); bejár(csúcs, irány1); bejár(csúcs, irány2); // ..stb. ha van több irányba elágazás }

    Hacsak ki nem fogysz a stackből (ami manapság nem jellemző), szerintem tisztább így csinálni, mint manuálisan. Ha óriási nagy az adathalmaz (nagyon mély lenne a rekurzió), csak akkor érdemes a heapen foglalni egy stacket és ott nyilvántartani a szülő csúcsokat kézileg, úgy, ahogy mondtad.
    Mutasd a teljes hozzászólást!
  • Illetve bocs, ez nem szélességi, hanem mélységi bejárás, összekevertem. Kell egy lista a csúcsokról valóban, hiszen csak akkor szabad mélyebbre menned, ha már egy szinten megvan minden fia a gyökérnek.
    Mutasd a teljes hozzászólást!
  • Akkor ezt megbeszéltük
    Kösz a segítséget!
    Mutasd a teljes hozzászólást!
Címkék
Tetszett amit olvastál? Szeretnél a jövőben is értesülni a hasonló érdekességekről?
abcd