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