JavaScript/Recursive/FloodFill.js at master · sibalonecoding-code/JavaScript · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
/**
 * Flood fill.
 *
 * Flood fill, also called seed fill, is an algorithm that determines and alters the area connected to a given node in a
 * multi-dimensional array with some matching attribute. It is used in the "bucket" fill tool of paint programs to fill
 * connected, similarly-colored areas with a different color.
 *
 * (description adapted from https://en.wikipedia.org/wiki/Flood_fill)
 * @see https://www.techiedelight.com/flood-fill-algorithm/
 */

constneighborOffsets=[
[-1,-1],
[-1,0],
[-1,1],
[0,-1],
[0,1],
[1,-1],
[1,0],
[1,1]
]

functionisInside(rgbData,location){
constx=location[0]
consty=location[1]
returnx>=0&&x<rgbData.length&&y>=0&&y<rgbData[0].length
}

functioncheckLocation(rgbData,location){
if(!isInside(rgbData,location)){
thrownewError('location should point to a pixel within the rgbData')
}
}

function*neighbors(rgbData,location){
for(constoffsetofneighborOffsets){
constneighborLocation=[location[0]+offset[0],location[1]+offset[1]]
if(isInside(rgbData,neighborLocation)){
yieldneighborLocation
}
}
}

/**
 * Implements the flood fill algorithm through a breadth-first approach using a queue.
 *
 * @param rgbData The image to which the algorithm is applied.
 * @param location The start location on the image.
 * @param targetColor The old color to be replaced.
 * @param replacementColor The new color to replace the old one.
 */
exportfunctionbreadthFirstSearch(
rgbData,
location,
targetColor,
replacementColor
){
checkLocation(rgbData,location)

constqueue=[]
queue.push(location)

while(queue.length>0){
breadthFirstFill(rgbData,location,targetColor,replacementColor,queue)
}
}

/**
 * Implements the flood fill algorithm through a depth-first approach using recursion.
 *
 * @param rgbData The image to which the algorithm is applied.
 * @param location The start location on the image.
 * @param targetColor The old color to be replaced.
 * @param replacementColor The new color to replace the old one.
 */
exportfunctiondepthFirstSearch(
rgbData,
location,
targetColor,
replacementColor
){
checkLocation(rgbData,location)

depthFirstFill(rgbData,location,targetColor,replacementColor)
}

/**
 * Utility-function to implement the breadth-first loop.
 *
 * @param rgbData The image to which the algorithm is applied.
 * @param location The start location on the image.
 * @param targetColor The old color to be replaced.
 * @param replacementColor The new color to replace the old one.
 * @param queue The locations that still need to be visited.
 */
functionbreadthFirstFill(
rgbData,
location,
targetColor,
replacementColor,
queue
){
constcurrentLocation=queue[0]
queue.shift()

if(rgbData[currentLocation[0]][currentLocation[1]]===targetColor){
rgbData[currentLocation[0]][currentLocation[1]]=replacementColor
for(constneighborLocationofneighbors(rgbData,currentLocation)){
queue.push(neighborLocation)
}
}
}

/**
 * Utility-function to implement the depth-first loop.
 *
 * @param rgbData The image to which the algorithm is applied.
 * @param location The start location on the image.
 * @param targetColor The old color to be replaced.
 * @param replacementColor The new color to replace the old one.
 */
functiondepthFirstFill(rgbData,location,targetColor,replacementColor){
if(rgbData[location[0]][location[1]]===targetColor){
rgbData[location[0]][location[1]]=replacementColor
for(constneighborLocationofneighbors(rgbData,location)){
depthFirstFill(rgbData,neighborLocation,targetColor,replacementColor)
}
}
}