Share to: share facebook share twitter share wa share telegram print page

Algoritmo flood fill

Niente fonti!
Questa voce o sezione sull'argomento programmazione non cita le fonti necessarie o quelle presenti sono insufficienti.
Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.
Flood-fill con 4 direzioni

L'algoritmo Flood fill individua un punto all'interno dell'area e, a partire da quel punto, colora tutto quello che ha intorno fermandosi solo quando incontra un confine, ovvero un pixel di colore differente (alcuni programmi di grafica permettono di definire quanto/come differente).

L'algoritmo richiede 3 parametri: il pixel iniziale, il colore da sostituire ed il colore di riempimento. La formulazione più semplice è ricorsiva. Si individua un pixel qualsiasi appartenente all'area da colorare, si controllano i vicini e se hanno un colore uguale lo si cambia con quello scelto, altrimenti si prosegue.

Immaginando i pixels come nodi, possiamo vedere l'algoritmo come una funzione ricorsiva che prende come parametri un nodo (il pixel all'interno dell'area), un colore_prima (il colore dell'area) ed infine colore_nuovo, ovvero il colore con cui vogliamo riempire l'area. 

Flood-fill (nodo, colore_prima, colore_nuovo):
 1. Se il colore di nodo è diverso da colore_prima, termina.
 2. Imposta il colore di nodo a colore_nuovo.
 3. Esegui Flood-fill (nodo ad ovest di nodo, colore_prima, colore_nuovo).
    Esegui Flood-fill (nodo a nord di nodo, colore_prima, colore_nuovo).
    Esegui Flood-fill (nodo ad est di nodo, colore_prima, colore_nuovo).
    Esegui Flood-fill (nodo a sud di nodo, colore_prima, colore_nuovo).
 4. Termina.

Il funzionamento può avvenire anche in modo non ricorsivo, inserendo i nodi da esaminare in un'apposita struttura dati ed esaminando i nodi uno per volta. Ecco un esempio di sviluppo non ricorsivo in Pascal, in questo caso è possibile usare una coda LIFO per mantenere le coordinate dei pixel ancora da processare. 

Procedure FloodFill(xStart, yStart:integer; ColorePrima, ColoreRiempimento:TColore);
Var
  x, y : integer;
  xEst, xWest : integer;
  yNord, ySud : integer;
begin
  QueueInit;
  QueuePush(xStart, yStart);
  while (QueueCount > 0) do begin
    QueuePop(x, y);
    xWest := x;
    xEst := x;
    if (y > 0) then
      yNord := y - 1
    else 
      yNord := -1;
    if (y < ImageHeight -1) then
      ySud := y + 1
    else 
      ySud := -1;
    while (xEst < ImageWidth -1) and (Pixel[xEst + 1, y] = ColorePrima) do Inc(xEst);
    while (xWest > 0) and (Pixel[xWest - 1, y] = ColorePrima) do Dec(xWest);
    for x := xWest to xEst do begin
      Pixel[x, y] := ColoreRiempimento;
      if (yNord >= 0) and (Pixel[x, yNord] = ColorePrima) then QueuePush(x, yNord);
      if (ySud >= 0) and (Pixel[x, ySud] = ColorePrima) then QueuePush(x, ySud);
    end;
  end;
end; //FloodFill

Questo algoritmo non serve direttamente per riempire poligoni, intendendo poligoni come oggetti descritti come oggetti vettoriali cioè non come semplici insiemi di pixel. Ad esempio come elenco delle coordinate dei vertici. In questo caso si ricorre prima all'algoritmo di rasterizzazione di poligono.

Altri progetti

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica

Read other articles:

Marcia su Washington per il lavoro e la libertà

Vista della marcia dal Lincoln Memorial verso il monumento a Washington La marcia su Washington per il lavoro e la libertà (o grande marcia su Washington, come ricordata in una registrazione sonora pubblicata dopo l'evento)[1][2] è stata una grande manifestazione politica a sostegno dei diritti civili ed economici per gli afroamericani che ebbe luogo mercoledì 28 agosto 1963 a Washington durante la presidenza di John Fitzgerald Kennedy. In quest'occasione, il leader afro-am...

 

Giải vô địch bóng đá nữ U-17 Bắc, Trung Mỹ và Caribe

Giải vô địch bóng đá nữ U-17 Bắc, Trung Mỹ và CaribeThành lập2008Khu vựcBắc, Trung Mỹ và Caribe (CONCACAF)Số đội8Đội vô địchhiện tại Hoa Kỳ (lần thứ 3)Đội bóngthành công nhất Hoa Kỳ (3 lần) 2016 Giải vô địch bóng đá nữ U-17 Bắc, Trung Mỹ và Caribe (tiếng Anh: CONCACAF Women's Under-17 Championship) là giải bóng đá nữ do Liên đoàn bóng đá Bắc, Trung Mỹ và Caribe (CONCACAF) tổ chức dà...

 

Mahkamah Eropa

Mahkamah EropaLogo Mahkamah EropaDidirikan1952YurisdiksiUni Eropa dan Irlandia Utara[1]LokasiKirchberg, Luxembourg City, LuxembourgCara penunjukkanDiangkat oleh perwakilan negara anggotaDisahkan olehPerjanjian Uni EropaBanding dariPengadilan Umum Uni EropaJumlah hakim27 hakim (1 per negara anggota)11 advokat jenderalSitus webcuria.europa.euPresidenSaat iniKoen LenaertsMulai menjabat08 Oktober 2015 (2015-10-08)Wakil PresidenSaat iniRosario Silva de LapuertaMulai menjabat09 Oktober...

Театр народного танцю «Заповіт»

Театр народного танцю «Заповіт» 49°59′38″ пн. ш. 36°13′44″ сх. д. / 49.9940063130670111° пн. ш. 36.22901461156941139° сх. д. / 49.9940063130670111; 36.22901461156941139Координати: 49°59′38″ пн. ш. 36°13′44″ сх. д. / 49.9940063130670111° пн. ш. 36.22901461156941139° сх. д. / 49.99400...

 

Jhanduta Assembly constituency

Legislative Assembly constituency in Himachal Pradesh State, India JhandutaConstituency for the Himachal Pradesh Legislative AssemblyConstituency detailsCountryIndiaRegionNorth IndiaStateHimachal PradeshDistrictBilaspurLS constituencyHamirpurTotal electors80,977[1]ReservationSCMember of Legislative Assembly14th Himachal Pradesh Legislative AssemblyIncumbent Jeet Ram Katwal PartyBharatiya Janata PartyElected year2022 Jhanduta Assembly constituency is one of the 68 assembly constituenci...

 

John of Gothia

You can help expand this article with text translated from the corresponding article in Alemannic. (October 2015) Click [show] for important translation instructions. Do not translate text that appears unreliable or low-quality. If possible, verify the text with references provided in the foreign-language article. You must provide copyright attribution in the edit summary accompanying your translation by providing an interlanguage link to the source of your translation. A model attributi...

Strategic dominance

Quality of a strategy in game theory For the business strategy, see Dominance (economics). This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (January 2016) (Learn how and when to remove this template message) In game theory, strategic dominance (commonly called simply dominance) occurs when one strategy is better than another strategy for one player, no matter h...

 

Makara

Hindu mythological creature For other uses, see Makara (disambiguation). MakaraMakara at the Konarak templeCountryIndia Makara as the Vahana (vehicle) of the goddess Ganga Makara (Sanskrit: मकर, romanized: Makara) is a legendary sea-creature in Hindu mythology.[1] In Hindu astrology, Makara is equivalent to the Zodiac sign Capricorn. Makara appears as the vahana (vehicle) of the river goddess Ganga, Narmada, and of the god of the ocean, Varuna.[2] Makara are conside...

 

Ramaiya Vastavaiya

2013 film by Prabhu Deva For the 2013 Telugu film, see Ramayya Vasthavayya. Ramaiya VastavaiyaTheatrical release posterDirected byPrabhu DevaWritten byAniket Shyamlal GuptaScreenplay byShiraz AhmedStory byVeeru PotlaBased onNuvvostanante Nenoddantana by PotlaProduced byKumar S. TauraniStarringGirish KumarShruti HaasanSonu SoodCinematographyKiran DeohansEdited byHemal KothariMusic bySongs:Sachin–JigarBackground Score:Sandeep ShirodkarProductioncompanyTips IndustriesDistributed byTips Industr...

The Autobiography of Supertramp

This article is about the album. For the book, see The Autobiography of a Super-Tramp. 1986 greatest hits album by SupertrampThe Autobiography of SupertrampGreatest hits album by SupertrampReleasedJuly 1986Recorded1974–1985GenreProgressive rock, pop rock, art rockLength47:10LabelA&MProducerKen Scott, Peter Henderson, David Kershenbaum, SupertrampSupertramp chronology Brother Where You Bound(1985) The Autobiography of Supertramp(1986) Free as a Bird(1987) Classics, Volume 9US cov...

 

Перепис населення США (1970)

Перепис населення США (1970) Печатка Бюро статистикиЗагальна інформаціяКраїна СШАДата 1970Населення 203 392 031Процентні зміни ▲ 13,4 %Найнаселеніший штат Каліфорнія19 953 134 Перепис населення США 1970 року — дев'ятнадцятий за рахунком перепис населення, що проводився на терито...

 

جون بودكن آدامز

جون بودكن آدامز معلومات شخصية الميلاد 21 يناير 1899  الوفاة 4 يوليو 1983 (84 سنة)   إيستبورن  سبب الوفاة قصور القلب  مواطنة المملكة المتحدة (12 أبريل 1927–) المملكة المتحدة لبريطانيا العظمى وأيرلندا (–12 أبريل 1927)  الحياة العملية المهنة طبيب،  وقاتل متسلسل  اللغات الإ...

Ministry of Parliamentary Affairs (Sri Lanka)

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Ministry of Parliamentary Affairs Sri Lanka – news · newspapers · books · scholar · JSTOR (January 2016) (Learn how and when to remove this template message) Ministry of Parliamentary AffairsMinistry overviewFormed1993JurisdictionDemocratic Socialist Repub...

 

The Magic Window

American TV series or program The Magic Windowpromotional photo of Betty Lou Varnum in The House with the Magic WindowStarringBetty Lou VarnumCountry of originUnited StatesProductionRunning time30 minutes per episodeOriginal releaseNetworkABC affiliate WOI-TV, Ames, IowaRelease1951 (1951) –1994 (1994) The Magic Window (also known as The House with the Magic Window) was an American children's television program broadcast on ABC affiliate WOI-TV in Ames, Iowa from 1951 to ...

 

Wuhan

Prefecture-level and sub-provincial city in Hubei, China Place in Hubei, ChinaWuhan 武汉市Clockwise from top: Skyline of Wuhan from the Wuhan Yangtze River Bridge, Tortoise Mountain TV Tower, causeway at East Lake, Guiyuan Temple, Yellow Crane TowerNicknames: 九省通衢[1][2] China's ThoroughfareThe Chicago of China[3][4][5]江城 (River City)Motto(s): 武汉，每天不一样！(Wuhan, Different Every Day!)Location of Wuhan City jurisdic...

Benjamin Fein

Jewish American gangster (c. 1889–1962) Benjamin FeinBornc. 1889New York CityDied1962New York City (uncertain) Benjamin Dopey Benny Fein (c. 1889–1962) was an early Jewish American gangster who dominated New York labor racketeering in the 1910s. With a criminal record dating back to 1900, Fein's arrest record included thirty charges from petty theft and assault to grand larceny and murder (of which he was acquitted twice due to lack of evidence). Fein was nicknamed Dopey Benny because of ...

 

1 Decembrie 1918 University, Alba Iulia

Research institution in Romania This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (June 2017) (Learn how and when to remove this template message) 1 Decembrie 1918 UniversityLatin: Universitas ApulensisOther nameUABEstablished1991; 32 years ago (1991)Academic affiliationsNIBSRectorValer-Daniel Breaz [ro]LocationAlba Iulia, Alba Cou...

 

2014 Toronto International Film Festival

Film festival 2014 Toronto International Film FestivalFestival posterOpening filmThe JudgeClosing filmA Little ChaosLocationToronto, Ontario, CanadaFounded1976AwardsThe Imitation Game (People's Choice Award)Hosted byToronto International Film Festival GroupNo. of films393 filmsFestival date4–14 September 2014Websitetiff.net The 39th annual Toronto International Film Festival, the 39th event in the Toronto International Film Festival series, was held in Canada from 4–14 September 2014.[...

Disco Bloodbath

Book by James St. James Disco Bloodbath AuthorJames St. JamesCountryUnited StatesLanguageEnglishGenreNon FictionPublisherSimon & SchusterPublication dateAugust 11, 1999Media typePrint (Hardback & Paperback)Pages288ISBN0-684-85764-2OCLC40990164Dewey Decimal364.15/23/097471 21LC ClassHV5805.S7 A3 199 Disco Bloodbath: A Fabulous but True Tale of Murder in Clubland is a 1999 memoir written by James St. James about his life as a Manhattan celebutante and club kid. The book specif...

 

Becoming Batman

Becoming Batman: The Possibility of a Superhero AuthorE. Paul ZehrCountryCanadaLanguageEnglishSubjectPhysiology and Superhero comicsGenreNon-fictionPublisherJohns Hopkins University PressPublication date2008Media typePrint (Hardcover)Pages300ISBN978-0-8018-9063-5OCLC213408580Dewey Decimal613.7 22LC ClassPN6728.B363 Z45 2008 Becoming Batman: The Possibility of a Superhero is a 2008 science book by neuroscience professor E. Paul Zehr.[1] The book was first published on Novembe...

 
Kembali kehalaman sebelumnya