Megjegyzések a digitális topológiáról
Ez a szakasz egy adott S "elvékonyításának" módszereit tárgyalja ívek és görbék csoportjában. Feltételezzük, hogy S teljes egészében hosszúkás részekből áll, így a kapott ívek és görbék ésszerű közelítést jelentenek az S-hez (1.5c. Szakasz). Más típusú S-k esetében a súlycsökkenés eredménye nem lehet különösebben jelentős. (A nyúlás meghatározását lásd a 3.4b szakaszban). S elvesztésének eredményét S csontvázának nevezzük .
A bárhol elvékonyodott S MA-ja csontváznak tekinthető, de két hibája van. Azokban a helyeken, ahol S kiszélesedett, MA két pont vastag, mivel az MA az a distances távolság maximumainak halmaza, amint az a 2.1a. Szakaszban látható. Továbbá, amint azt ott megjegyeztük, az MA hajlamos megszakadni, és azt szeretnénk, ha az összekapcsolt S-darabok elvékonyodnának összekapcsolt ívekké vagy görbékké. Ebben a részben egy vékonyodási sémát írunk le, amely összekapcsolt és vékony csontvázakat állít elő.
Hígítási algoritmusunk egy speciális zsugorodási folyamat, amely minden iterációnál eltávolítja az S-ből azokat az élpontokat, amelyek eltávolításával lokálisan nem választják le a szomszédságukat; Megmutatható [54], hogy ez garantálja, hogy az S csatlakozási tulajdonságai nem változnak, még akkor sem, ha az ilyen pontokat egyszerre távolítják el. Annak megakadályozására, hogy egy már elvékonyodott ív a végén zsugorodjon, azt is előírjuk, hogy azokat a pontokat, amelyeknek csak egy szomszédja van S-ben, nem törlik.
Sajnos, ha eltávolítjuk az összes pontot S széléről, és S vastagsága csak két pont, pl.,
akkor S teljesen eltűnik. Ezt elkerülhetnénk olyan algoritmus használatával, amely nemcsak egy pont közvetlen szomszédját vizsgálja, de egy ilyen algoritmus túl bonyolult lenne. Ehelyett csak azokat a pontokat távolítjuk el az élen, amelyek az S adott oldalán vannak, azaz amelyeknek adott szomszédságuk van (észak, kelet, nyugat vagy dél) Љ-ben, adott iterációban. Annak biztosítása érdekében, hogy a csontváz a lehető legközelebb legyen S "középső részéhez", az ellenkező oldalakat használjuk felváltva, pl. Észak, dél, kelet, nyugat. (Lehetséges olyan algoritmusok kidolgozása, amelyek egyidejűleg eltávolítják az élpontokat két szomszédos oldalról, pl. Észak és kelet, majd nyugat és dél, de ez a megközelítés egy kicsit bonyolultabb, és itt nem írjuk le részletesen. két pont szomszédjainak ellenőrzése annak megállapításához, hogy azokat is eltávolítják-e, és ha igen, ne törölje az adott pontot).
Az algoritmus pontosabb bemutatásához meg kell adnunk azokat a pontos feltételeket, amelyek mellett egy élpont eltávolítható. S S élpontját egyszerűnek nevezzük, ha P 8 szomszédjának S-ben lévő halmazának pontosan egy olyan komponense van, amely szomszédos P-vel. Ez az utolsó mondat azt jelenti, hogy ha az S 4-összekapcsolhatóságát használjuk, akkor csak azok a komponensek foglalkoznak, amelyek 4-vel szomszédosak a P-vel. Ha 8-kapcsolatot használunk, az utolsó tagmondat elhagyható. Például P 4 egyszerű, ha a szomszédsága megegyezik
mivel ebben az esetben az 1-eknek csak egy 4-komponense van 4-szomszédos P-vel; de P nem 4-egyszerű, ha a szomszédsága az
Másrészt P a harmadik esetben 8-egyszerű, de az első két esetben nem.
Könnyen belátható, hogy egyetlen pont törlése az S-ből nem változtatja meg sem S, sem Љ kapcsolati tulajdonságait; S - < P >komponensei ugyanazok, mint az S, azzal a különbséggel, hogy egyikükből hiányzik a P pont, és Љ И < P >komponensei megegyeznek a Љ-vel, azzal a különbséggel, hogy most P az egyik. Vegye figyelembe, hogy egy elszigetelt pont (amelynek nincs szomszédja S-ben) nem egyszerű, és hogy egy végpont (amelynek pontosan egy szomszédja van S-ben) automatikusan egyszerű.
Hígítási algoritmusunk most a következőképpen állítható be: Töröljük az összes élpontot az S adott oldalán, amennyiben azok egyszerűek és nem végpontok. Ezt egymást követően északi, déli, keleti, nyugati, északi oldalról fogjuk megtenni. addig, amíg nincs több változás. Az algoritmus működésének egyszerű példáját a 14. ábra mutatja.
Az S adott oldalának széleiről a pontokat ki kell küszöbölni "párhuzamosan", azaz. bármely pont törlése előtt ellenőrizni kell a pont törlésének feltételeit. (Tegyük fel, hogy nem tesszük, és csak soronként végezzük a törlést. Az északi perempontok törlésével rétegenként eltávolítjuk az S tetejét, és az így kapott csontváz nem lesz szimmetrikus; pl., Ha S egy téglalap, az első művelet után az alsó során kívül semmi sem maradna). Ily módon az algoritmus minden iterációja elvégezhető a multiprocesszoros számítógép egyszerű párhuzamos műveleteként.
Az algoritmus megvalósítható egy hagyományos számítógépen, minden iterációhoz képkövetést alkalmazva. Minden sorban a pontok megjelölésre kerülnek a törléshez, de addig nem törlődnek, amíg a következő sorban lévő pontokat meg nem jelölik. Elkerülhetjük a teljes kép ismételt feltérképezését, ha az 1. sorrendben működtetjük a sorokat; huszonegy; 3, 2, 1; . mint a 2.1c szakaszban. K lépés után, ahol 2 k + 1 az S maximális szélessége, az első sorban nincs szükség további elvékonyításra, így elhagyható; így egyelőre csak k sornak kell rendelkezésre állnia.