掃描線種子填充算法基本步驟:
- 初始化一個(gè)空棧用于存放種子點(diǎn)忍级，將種子點(diǎn)（x,y）入棧
- 判斷棧是否為空断序，如果棧為空則算法結(jié)束呵俏，否則取出棧頂元素作為當(dāng)前掃描線的種子點(diǎn)（x,y）,y是當(dāng)前的掃描線
- 從種子點(diǎn)（x,y）出發(fā)吻商，沿當(dāng)前掃描線向左向右兩個(gè)方向填充利职，直到邊界趣效。分別標(biāo)記區(qū)段的左右端點(diǎn)為xLeft，xRight
- 分別檢查與當(dāng)前掃描線相鄰的y-1和y+1兩條掃描線在區(qū)間[xLeft,xRight]中的像素猪贪，從xLeft開始xRight方向搜索跷敬，若存在非邊界且未填充的像素點(diǎn)，則找出這些相鄰像素點(diǎn)中最右邊的一個(gè)热押，并將其作為種子點(diǎn)入棧西傀，然后返回第2步（注：一條掃描線上可能存在多個(gè)種子點(diǎn)）
涂鴉效果
未命名.gif
iOS中如何實(shí)現(xiàn)掃描線種子填充算法
-
掃描的是什么東東？
掃描的是圖片上所有的像素點(diǎn)的集合桶癣，而常用的png拥褂，jpg是壓縮過的位圖，所以首先要把png鬼廓，jpg圖片進(jìn)行解壓縮
-
在iOS中如何把UIImage轉(zhuǎn)成像素點(diǎn)的集合肿仑？
主要利用CGContext的下面三個(gè)API
//初始化 CGContext public init?(data: UnsafeMutableRawPointer?, width: Int, height: Int, bitsPerComponent: Int, bytesPerRow: Int, space: CGColorSpace, bitmapInfo: UInt32) //將位圖也就是像素點(diǎn)的集合繪制到上下文中 public func draw(_ image: CGImage, in rect: CGRect) //得到上下文中的位圖 public func makeImage() -> CGImage?主要解釋一下第一個(gè)方法的各個(gè)參數(shù)的含義
data：存放像素點(diǎn)的指針
width,height:位圖的寬高
bitsPerComponent：顏色空間中每個(gè)通道占用的bit；（注碎税，此單位是bit）
bytesPerRow：位圖的每一行使用的字節(jié)數(shù)（注尤慰，此單位是byte，1byte=8bit）大小等于width*height*每個(gè)像素占用的大小雷蹂，在iOS里顏色空間是RGB時(shí)伟端，每個(gè)像素占用的大小是32
space:像素點(diǎn)的顏色空間
bitmapInfo：位圖的布局信息，主要包含了alpha 的信息匪煌；顏色分量是否為浮點(diǎn)數(shù)责蝠；像素格式的字節(jié)順序let image = UIImage(named: "test") if let imageRef = image?.cgImage { let width = imageRef.width let height = imageRef.height var pixels = Array<UInt32>(repeating: 0, count: width * height) let colorSpace = CGColorSpaceCreateDeviceRGB() //像素點(diǎn)的顏色空間 let bitsPerComponent = 8 //顏色空間每個(gè)通道占用的bit let bytesPerRow = width * 4 //位圖的每一行使用的字節(jié)數(shù) let bitmapInfo = CGImageAlphaInfo.premultipliedLast.rawValue if let context = CGContext(data: &(pixels), width: width, height: height, bitsPerComponent: bitsPerComponent, bytesPerRow: bytesPerRow, space: colorSpace, bitmapInfo: bitmapInfo) { context.draw(imageRef, in: CGRect(x: 0, y: 0, width: width, height: height)) } } -
如何把觸摸在imageView上的坐標(biāo)轉(zhuǎn)換為UIImage上的種子點(diǎn)
由于UIImageView的大小也UIImage得大小是不一樣的党巾，所以當(dāng)我們獲取手勢在ImageView上的坐標(biāo)的時(shí)候，要經(jīng)過變換得到UIImage上的坐標(biāo)霜医，把此點(diǎn)作為種子點(diǎn)入棧
//注齿拂，self是UIImageView的子類
override func touchesBegan(_ touches: Set<UITouch>, with event: UIEvent?) {
if touches.count == 1 , let touch = touches.first , let imageRef = self.image?.cgImage{
let point = touch.location(in: self)
let width = imageRef.width
let height = imageRef.height
let widthScale = CGFloat(width) / bounds.width
let heightScale = CGFloat(height) / bounds.height
//把相對于view的touch point 轉(zhuǎn)換成image的像素點(diǎn)的坐標(biāo)點(diǎn)
let realPoint = CGPoint(x: point.x * widthScale, y: point.y * heightScale)
}
}
-
實(shí)現(xiàn)掃描線種子填充算法
核心代碼如下，以下代碼是寫在自定義的UIImageView的子類中
//MARK: private method
/// 填充顏色
///
/// - Parameters:
/// - point: 種子點(diǎn)
/// - color: 填充顏色
private func floodFill(from point:CGPoint) {
if let imageRef = image?.cgImage {
let width = imageRef.width
let height = imageRef.height
let widthScale = CGFloat(width) / bounds.width
let heightScale = CGFloat(height) / bounds.height
//把相對于view的touch point 轉(zhuǎn)換成image的像素點(diǎn)的坐標(biāo)點(diǎn)
let realPoint = CGPoint(x: point.x * widthScale, y: point.y * heightScale)
scanedLines = [:]
imageSize = CGSize(width: width, height: height)
pixels = Array<UInt32>(repeating: 0, count: width * height)
let colorSpace = CGColorSpaceCreateDeviceRGB() //像素點(diǎn)的顏色空間
let bitsPerComponent = 8 //顏色空間每個(gè)通道占用的bit
let bytesPerRow = width * 4 //image每一行所占用的byte
let bitmapInfo = CGImageAlphaInfo.premultipliedLast.rawValue
if let context = CGContext(data: &(pixels), width: width, height: height, bitsPerComponent: bitsPerComponent,
bytesPerRow: bytesPerRow, space: colorSpace, bitmapInfo: bitmapInfo) {
context.draw(imageRef, in: CGRect(x: 0, y: 0, width: width, height: height))
let pixelIndex = lrintf(Float(realPoint.y)) * width + lrintf(Float(realPoint.x))
let newColorRgbaValue = newColor.rgbaValue
let colorRgbaValue = pixels[pixelIndex]
//如果點(diǎn)擊的黑色邊框肴敛，直接退出
if isBlackColor(color: colorRgbaValue) {
return
}
//如果點(diǎn)擊的顏色和新顏色一樣署海，退出
if compareColor(color: colorRgbaValue, otherColor: newColorRgbaValue, tolorance: colorTolorance) {
return
}
//存放種子點(diǎn)的棧
seedPointList.push(realPoint)
while !seedPointList.isEmpty {
if let point = seedPointList.pop() {
let (xLeft,xRight) = fillLine(seedPoint: point, newColorRgbaValue: newColorRgbaValue,
originalColorRgbaValue: colorRgbaValue)
scanLine(lineNumer: Int(point.y) + 1, xLeft: xLeft, xRight: xRight, originalColorRgbaValue: colorRgbaValue)
scanLine(lineNumer: Int(point.y) - 1, xLeft: xLeft, xRight: xRight, originalColorRgbaValue: colorRgbaValue)
}
}
if let cgImage = context.makeImage() {
image = UIImage(cgImage: cgImage, scale: image?.scale ?? 2, orientation: .up)
}
}
}
}
/// 通過種子點(diǎn)向左向右填充
///
/// - Parameters:
/// - seedPoint: 種子點(diǎn)
/// - newColorRgbaValue: 填充的新顏色的值
/// - originalColorRgbaValue: 觸摸點(diǎn)顏色的值
/// - Returns: 種子點(diǎn)填充的左右區(qū)間 都是閉區(qū)間
private func fillLine(seedPoint:CGPoint,newColorRgbaValue:UInt32,originalColorRgbaValue:UInt32) -> (Int,Int) {
let imageW = Int(imageSize.width)
let currntLineMinIndex = Int(seedPoint.y) * imageW
let currntLineMaxIndex = currntLineMinIndex + imageW
let currentPixelIndex = currntLineMinIndex + Int(seedPoint.x)
var xleft = Int(seedPoint.x)
var xright = xleft
if pixels.count >= currntLineMaxIndex {
var tmpIndex = currentPixelIndex
while tmpIndex >= currntLineMinIndex &&
compareColor(color: originalColorRgbaValue, otherColor: pixels[tmpIndex], tolorance: colorTolorance){
pixels[tmpIndex] = newColorRgbaValue
tmpIndex -= 1
xleft -= 1
}
tmpIndex = currentPixelIndex + 1
while tmpIndex < currntLineMaxIndex &&
compareColor(color: originalColorRgbaValue, otherColor: pixels[tmpIndex], tolorance: colorTolorance){
pixels[tmpIndex] = newColorRgbaValue
tmpIndex += 1
xright += 1
}
}
return (xleft + 1,xright)
}
/// 從xLeft到xRight的掃描第lineNumer行
///
/// - Parameters:
/// - lineNumer: 行數(shù)
/// - xLeft: 掃描線的最左側(cè)
/// - xRight: 掃描線的最右側(cè)
/// - originalColorRgbaValue: 觸摸點(diǎn)顏色的值
private func scanLine(lineNumer:Int,xLeft:Int,xRight:Int,originalColorRgbaValue:UInt32) {
if lineNumer < 0 || CGFloat(lineNumer) > imageSize.height - 1{
return
}
var xCurrent = xLeft //當(dāng)前被掃描的點(diǎn)的x位置
let currentLineOriginalIndex = lineNumer * Int(imageSize.width)
var currentPixelIndex = currentLineOriginalIndex + xLeft //當(dāng)前被掃描的點(diǎn)的所在像素點(diǎn)的位置
var currntLineMaxIndex = currentLineOriginalIndex + xRight //當(dāng)前掃描線需要掃描的最后一個(gè)點(diǎn)的位置
//此處是對種子掃描線算法的一點(diǎn)小優(yōu)化
var leftSpiltIndex:Int?
if var scanLine = scanedLines[lineNumer] {
if scanLine.xLeft >= xRight || scanLine.xRight <= xLeft {//沒有相交，什么也不做
}else if scanLine.xLeft <= xLeft && scanLine.xRight >= xRight { //舊掃描與新掃描的范圍關(guān)系是包含
return
}else if scanLine.xLeft <= xLeft && scanLine.xRight <= xRight {//舊掃描與新掃描的范圍關(guān)系是左包含右被包含
xCurrent = scanLine.xRight + 1
currentPixelIndex = currentLineOriginalIndex + scanLine.xRight + 1
scanLine.xRight = xRight
scanedLines[lineNumer] = scanLine
}else if scanLine.xLeft >= xLeft && scanLine.xRight >= xRight {//舊掃描與新掃描的范圍關(guān)系是左被包含右包含
currntLineMaxIndex = currentLineOriginalIndex + scanLine.xLeft - 1
leftSpiltIndex = currentLineOriginalIndex + scanLine.xLeft
scanLine.xLeft = xLeft
scanedLines[lineNumer] = scanLine
}else if scanLine.xLeft >= xLeft && scanLine.xRight <= xRight {//舊掃描與新掃描的范圍關(guān)系是被包含
scanLine.xLeft = xLeft
scanLine.xRight = xRight
scanedLines[lineNumer] = scanLine
}
}else {
scanedLines[lineNumer] = FillLineInfo(lineNumber: lineNumer, xLeft: xLeft, xRight: xRight)
}
while currentPixelIndex <= currntLineMaxIndex {
var isFindSeed = false
//找到此區(qū)間的種子點(diǎn)医男，種子點(diǎn)是存在非邊界且未填充的像素點(diǎn)砸狞，這些相鄰的像素點(diǎn)中最右邊的一個(gè)
while currentPixelIndex < currntLineMaxIndex &&
compareColor(color: originalColorRgbaValue, otherColor: pixels[currentPixelIndex], tolorance: colorTolorance) {
isFindSeed = true
currentPixelIndex += 1
xCurrent += 1
}
if isFindSeed {
//如果找到種子點(diǎn)，需要判斷while循環(huán)的退出條件是什么
//如果是到區(qū)間最右邊的倒數(shù)第二個(gè)點(diǎn)镀梭，則需要判斷最右邊的點(diǎn)是否和originalColorRgbaValue顏色一樣刀森，如果一樣，則最右邊的入棧报账，否則把上一個(gè)點(diǎn)入棧
//如果是碰到了邊界點(diǎn)退出的研底，則把當(dāng)前點(diǎn)的上一個(gè)點(diǎn)入棧
if compareColor(color: originalColorRgbaValue, otherColor: pixels[currentPixelIndex], tolorance: colorTolorance) &&
currentPixelIndex == currntLineMaxIndex {
//若當(dāng)舊掃描與新掃描的范圍關(guān)系是左被包含右包含，需要掃描的范圍應(yīng)該是新掃描范圍的左點(diǎn)到舊掃描范圍的左點(diǎn)的上一個(gè)點(diǎn)
//此時(shí)若掃描范圍內(nèi)的最右點(diǎn)顏色與originalColorRgbaValue一樣透罢，并且舊掃描范圍的左點(diǎn)的顏色也與originalColorRgbaValue一樣飘哨，則不需要入棧
if leftSpiltIndex == nil ||
!compareColor(color: originalColorRgbaValue, otherColor: pixels[leftSpiltIndex!], tolorance: colorTolorance){
seedPointList.push(CGPoint(x: xCurrent, y: lineNumer))
}
}else {
seedPointList.push(CGPoint(x: xCurrent - 1, y: lineNumer))
}
}
currentPixelIndex += 1
xCurrent += 1
}
}
/// 判斷顏色是否是黑色
///
/// - Returns: true 是 or false 不是
private func isBlackColor(color:UInt32) -> Bool {
let colorRed = Int((color >> 0) & 0xff)
let colorGreen = Int((color >> 8) & 0xff)
let colorBlue = Int((color >> 16) & 0xff)
let colorAlpha = Int((color >> 24) & 0xff)
if colorRed < colorTolorance &&
colorGreen < colorTolorance &&
colorBlue < colorTolorance &&
colorAlpha > 255 - colorTolorance{
return true
}
return false
}
/// 是否是相似的顏色
///
/// - Returns: true 相似 or false 不相似
private func compareColor(color:UInt32, otherColor:UInt32, tolorance:Int) -> Bool {
if color == otherColor {
return true
}
let colorRed = Int((color >> 0) & 0xff)
let colorGreen = Int((color >> 8) & 0x00ff)
let colorBlue = Int((color >> 16) & 0xff)
let colorAlpha = Int((color >> 24) & 0xff)
let otherColorRed = Int((otherColor >> 0) & 0xff)
let otherColorGreen = Int((otherColor >> 8) & 0xff)
let otherColorBlue = Int((otherColor >> 16) & 0xff)
let otherColorAlpha = Int((otherColor >> 24) & 0xff)
if abs(colorRed - otherColorRed) > tolorance ||
abs(colorGreen - otherColorGreen) > tolorance ||
abs(colorBlue - otherColorBlue) > tolorance ||
abs(colorAlpha - otherColorAlpha) > tolorance {
return false
}
return true
}
extension UIColor {
/// 獲取顏色的UInt32表示形式
fileprivate var rgbaValue:UInt32 {
var red:CGFloat = 0
var green:CGFloat = 0
var blue:CGFloat = 0
var alpha:CGFloat = 0
getRed(&red, green: &green, blue: &blue, alpha: &alpha)
return UInt32(red * 255) << 0 | UInt32(green * 255) << 8 | UInt32(blue * 255) << 16 | UInt32(alpha * 255) << 24
}
}
-
做此功能的一些其他收獲
-
UIScrollView很容易實(shí)現(xiàn)視圖的縮放功能，只要在代理方法中返回需要縮放的視圖即可琐凭，UIScrollView是如何實(shí)現(xiàn)子視圖的縮放的？
UIScrollView是通過改變子視圖的transform來實(shí)現(xiàn)縮放的
-
當(dāng)使用transform把視圖縮放后浊服，frame和bounds會如何變化统屈，該視圖的子視圖的frame和bounds又會如何變化
frame會同比縮放，而bounds不會變化牙躺，子視圖的frame和bounds都不變
原因猜測(純屬猜測)如下：frame.size代表的是視圖的大小愁憔，這個(gè)大小是邏輯大小，而不是真正的像素大小孽拷。而bounds也是邏輯大小吨掌。以iphone6舉例，在無縮放的情況下脓恕，frame.size.width = 1代表著2個(gè)像素點(diǎn)膜宋，在縮放的過程中。當(dāng)前縮放的視圖的frame.size每個(gè)邏輯大小對應(yīng)的像素點(diǎn)不變炼幔，而bounds.size每個(gè)邏輯大小對應(yīng)的像素點(diǎn)則同比縮放秋茫，對于子視圖來說，frame.size每個(gè)邏輯大小對應(yīng)的像素點(diǎn)等于父視圖的bounds.size每個(gè)邏輯大小對應(yīng)的像素點(diǎn)乃秀，bounds.size每個(gè)邏輯大小對應(yīng)的像素點(diǎn)則等于父視圖的bounds.size每個(gè)邏輯大小對應(yīng)的像素點(diǎn)和自身的縮放的乘積 -
當(dāng)使用transform把視圖放大之后肛著，觸摸點(diǎn)point的范圍是否會放大圆兵，也就是說如果放大之前視圖的大小為375*373，point的范圍為(0,0)-(375,375),那么放大2倍后枢贿，point的范圍是(0,0)-(375,375)還是(0,0)-(750殉农，750)
范圍還是(0,0)-(375,375)，原因猜測如下：手勢獲取坐標(biāo)的時(shí)候是基于視圖的bounds的
-
-
demo的GitHub地址
-
參考文章
