1/*Package paint provides functions to edit a group of pixels on an image.*/
2package paint
3
4import (
5	"image"
6	"image/color"
7	"math"
8
9	"github.com/anthonynsimon/bild/clone"
10	"github.com/anthonynsimon/bild/util"
11)
12
13type fillPoint struct {
14	X, Y                  int
15	MarkedFromBelow       bool
16	MarkedFromAbove       bool
17	PreviousFillEdgeLeft  int
18	PreviousFillEdgeRight int
19}
20
21// FloodFill fills a area of the image with a provided color and returns the new image.
22// Parameter sp is the starting point of the fill.
23// Parameter c is the fill color.
24// Parameter t is the tolerance and is of the range 0 to 255. It represents the max amount of
25// difference between colors for them to be considered similar.
26func FloodFill(img image.Image, sp image.Point, c color.Color, t uint8) *image.RGBA {
27	var st util.Stack
28	var point fillPoint
29	visited := make(map[int]bool)
30	im := clone.AsRGBA(img)
31
32	maxX := im.Bounds().Dx() - 1
33	maxY := im.Bounds().Dy() - 1
34	if sp.X > maxX || sp.X < 0 || sp.Y > maxY || sp.Y < 0 {
35		return im
36	}
37
38	tSquared := math.Pow(float64(t), 2)
39	matchColor := color.NRGBAModel.Convert(im.At(sp.X, sp.Y)).(color.NRGBA)
40
41	st.Push(fillPoint{sp.X, sp.Y, true, true, 0, 0})
42
43	// loop until there are no more points remaining
44	for st.Len() > 0 {
45		point = st.Pop().(fillPoint)
46		pixOffset := im.PixOffset(point.X, point.Y)
47
48		if !visited[pixOffset] {
49			im.Set(point.X, point.Y, c)
50			visited[pixOffset] = true
51
52			// fill left side
53			xpos := point.X
54			for {
55				xpos--
56				if xpos < 0 {
57					xpos = 0
58					break
59				}
60				pixOffset = im.PixOffset(xpos, point.Y)
61				if isColorMatch(im, pixOffset, matchColor, tSquared) {
62					im.Set(xpos, point.Y, c)
63					visited[pixOffset] = true
64				} else {
65					break
66				}
67			}
68
69			leftFillEdge := xpos - 1
70			if leftFillEdge < 0 {
71				leftFillEdge = 0
72			}
73
74			// fill right side
75			xpos = point.X
76			for {
77				xpos++
78				if xpos > maxX {
79					break
80				}
81
82				pixOffset = im.PixOffset(xpos, point.Y)
83				if isColorMatch(im, pixOffset, matchColor, tSquared) {
84					im.Set(xpos, point.Y, c)
85					visited[pixOffset] = true
86				} else {
87					break
88				}
89			}
90			rightFillEdge := xpos + 1
91			if rightFillEdge > maxX {
92				rightFillEdge = maxX
93			}
94
95			// skip every second check for pixels above and below
96			skipCheckAbove := false
97			skipCheckBelow := false
98
99			// check pixels above/below the fill line
100			for x := leftFillEdge; x <= rightFillEdge; x++ {
101				outOfPreviousRange := x >= point.PreviousFillEdgeRight || x <= point.PreviousFillEdgeLeft
102
103				if skipCheckBelow {
104					skipCheckBelow = !skipCheckBelow
105				} else {
106					if point.MarkedFromBelow || outOfPreviousRange {
107						if point.Y > 0 {
108							pixOffset = im.PixOffset(x, point.Y-1)
109							if !visited[pixOffset] && isColorMatch(im, pixOffset, matchColor, tSquared) {
110								skipCheckBelow = true
111								st.Push(fillPoint{x, (point.Y - 1), true, false, leftFillEdge, rightFillEdge})
112							}
113						}
114					}
115				}
116
117				if skipCheckAbove {
118					skipCheckAbove = !skipCheckAbove
119				} else {
120					if point.MarkedFromAbove || outOfPreviousRange {
121						if point.Y < maxY {
122
123							pixOffset = im.PixOffset(x, point.Y+1)
124							if !visited[pixOffset] && isColorMatch(im, pixOffset, matchColor, tSquared) {
125								skipCheckAbove = true
126								st.Push(fillPoint{x, (point.Y + 1), false, true, leftFillEdge, rightFillEdge})
127							}
128						}
129					}
130				}
131			}
132		}
133	}
134
135	return im
136}
137
138func isColorMatch(im *image.RGBA, pos int, mc color.NRGBA, tSquared float64) bool {
139	rDiff := float64(mc.R) - float64(im.Pix[pos+0])
140	gDiff := float64(mc.G) - float64(im.Pix[pos+1])
141	bDiff := float64(mc.B) - float64(im.Pix[pos+2])
142	aDiff := float64(mc.A) - float64(im.Pix[pos+3])
143
144	distanceR := math.Max(rDiff*rDiff, math.Pow(rDiff-aDiff, 2))
145	distanceG := math.Max(gDiff*gDiff, math.Pow(gDiff-aDiff, 2))
146	distanceB := math.Max(bDiff*bDiff, math.Pow(bDiff-aDiff, 2))
147	distance := distanceR + distanceG + distanceB
148
149	return distance <= tSquared
150}
151