CGA填充算法之种子填充算法

时间:2022-10-20 10:37:03

CGA填充算法之种子填充算法

  平面区域填充算法是计算机图形学领域的一个很重要的算法,区域填充即给出一个区域的边界 (也可以是没有边界,只是给出指定颜色),要求将边界范围内的所有象素单元都修改成指定的颜色(也可能是图案填充)。区域填充中最常用的是多边形填色,本文讨论种子填充算法(Seed Filling)

    如果要填充的区域是以图像元数据方式给出的,通常使用种子填充算法(Seed Filling)进行区域填充。种子填充算法需要给出图像数据的区域,以及区域内的一个点,这种算法比较适合人机交互方式进行的图像填充操作,不适合计算 机自动处理和判断填色。根据对图像区域边界定义方式以及对点的颜色修改方式,种子填充又可细分为几类:

  比如:①注入填充算法(Flood Fill Algorithm)

       ②边界填充算法(Boundary Fill Algorithm)以及

     ③为减少递归和压栈次数而改进的扫描线种子填充算法等等。

所有种子填充算法的核心其实就是一个递归算法,都是从指定的种子点开始,向各个方向上搜索,逐个像素进行处理,直到遇到边界,各种种子填充算法只是在处理 颜色和边界的方式上有所不同。

  在开始介绍种子填充算法之前,首先也介绍两个概念,就是“4-联通算法”和“8-联通算法”。

  既然是搜索就涉及到搜索的方向 问题,从区域内任意一点出发,如果只是通过上、下、左、右四个方向搜索到达区域内的任意像素,则用这种方法填充的区域就称为四连通域,这种填充方法就称为 “4-联通算法”。如果从区域内任意一点出发,通过上、下、左、右、左上、左下、右上和右下全部八个方向到达区域内的任意像素,则这种方法填充的区域就称 为八连通域,这种填充方法就称为“8-联通算法”。

  aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAOoAAAC/CAIAAAB/tdddAAAHM0lEQVR4nO2dUW6jSBRFI4tVjViOlQVZXorVi4m8FKtnPnqSxhhwUfWq3rvFsc5PJw5163JMYwz4418ePGQfH94BePDIf6AvD+HHx+P3A0AU9AVh0BeEQV8QBn1BGPQFYdAXhEFfEAZ9QRj0BWHQF4RBXxAGfUEY9AVh0BeEQV8QBn1BGPQFYdAXhEFfEAZ9QRj0BWHQF4RR0Pc0+GdIZjj5Z+i74SmB9T0NC7inWmE4LeCeqqeGF4mq72KzUftddDe6wVINr4G+BqCvFyH13Wg2Xr8b7sY1WKrhDbT1HU6DF5MMqfo6pp1lRt8Q+kaAra8j6FsK+joSUt/tft2zvSDmrmDDa6CvAejrRVR91/p1T7WCmLuCDS8SWF+Ad4TWd1jZGKz9PAJhN7qKZb5FUt/IpcfUV7HJFFT1Ddt7QH0Va0xEWN+Y1UfTV7HDdLT1fXx/EusedZLHP8PeAt1zZiOvb7R1EETf9Fd1nOoy6ETfOKshgr6KveXRj74Zz6+T2T2AXmnZdKVv3p9YZ6axdvSmb/Zf2WWmrnZ0qG/JH1pkpqt29Klv4d+WZaaodnSr78PpkHB7fctbahzYkJ71NVzInuGa9lM+O/SthVWzLddQM30VyzHnEPraLurdQDTTjqPoa7609VGopR0H0rfGApeGoJN2HEvfSst8Xj6FtONw+j4qH1Crp2+9NioFbsAR9a268Er61ny9oa9ms3X+L7YPqfgybsOh9a0xhK2+ig205Oj6mo9iqK/i9BuDvsYDWemrOPf2oK/xWCb6Kk7cBfQ1Hq5cX8VZe4G+8xGLzz/Um3LjEQ1BX+NxS/R1mS/6dthswbU3mcMpvlbdQV/j0TP0VZxmENDXOMBefRXnGAf0Nc6wS1/FCYYCfY1jpOurOLtooG9qkuQ73ulNzT1DNuhrnCdF31DzChVmL+hrHOmtvtEmFS3PLtDXONWGvo4Hd+VKTgR9jYOt6as4l/igr3G2RX0VJyJBaH2Ds7jiX/WV9iM4ofV1v1N5QsK5mrPMwd2N3/A2EfWV/H7gSXj3DH03PCWcvpLfzv4c3j1Gxw3PQN9amd1T9dTwGrH03Wg2bL/dpA2beQP0rZjZPVsfDW+gqu/bZ0Jeb+4OHELfIBDYl1j6bvfrnm1XWsXM7tn2gr610ipmds+2l3D6rvXrnmpXWsXM7qkyiKivFor6dkNofYOfMDDJ+d7dsHMJGywF9DVOtbHRVZxOcNDXONL2PoPijCKDvsZ53u7yKk4qLOhrHCblHVuoi97iJMkAfY2TpB9wCDK7IDHyQF/jGLuOl0WYYIQM2aCvcYa9h3vd5+geoAT0NQ6Q8WkFN0jNBn1Xh252f1/3mXoNXQ76Go+b/Vmx4mTdQV/jQUtOdXA5oIa+/TRbPmL5mTp8MVY66Gs8nMmJZnwtYSLoazyW1XmSzeaOvvLNGg5keJpvm+mjr3aztqPYnqXeoAH0VW22xjt984ssGpRQdflVOa6+lRZe4xohxR7acFB9ay65VuBqrzf0rYPiCqt6hWaN5OhbC8W1VfsC4wo76+hbB8VV1eD6eOtDJehbB8X11Ob2DqYHqtG3DoorqdndSew+JkTfOhidhND0NK6WN9ex6qdZYHM619fjnLXWFRWf4Ym+dVBcMS63Nis7vx5966C4VrzuzJc9X/StheIqcbyxZO7FeejL+vg7ulhj6MvKmAYQK829sRK60jfCmnDXd28PEUrLphN949z0LoK+e6tzT5tND/qGWgFB9H0kv6RDtbcXeX2jtR9H38R+ohW4C219A1YfTd+3LQXsMJ3Q+m4Ts/eA+m53FbPGRALrq7nNiKlvr8TT9zQs8PycsO5KolxmMH0X3V0yOCwyW1/lkn9AXxvEvlVTtucZkfTd6DR2s3rfCytY8iLoa4CYvrI9v4K+pWy4G9RgzZ4XkdT3z8ehvkzCpOobJDD6ehjsnm0Ftr6OoG8pevpq9rxIMH3XmnVPtYmYu2slK1Q9I56+gujp+1tyM/EK+tog5m4voC8Ig74gDPqCMOgLwqAvCIO+IAz6gjDoC8KgLwiDviAM+oIw6AvCoC8Ig74gDPqCMOgLwqAvCIO+IAz6gjDoC8KgLwiDviAM+lpxO5/Otx0/BwPQ14Jf52HD0a/reBqvX94hewR9y0nYvn5dR7bBFUDfUm6fw3i5v33a/TIOnzf3tJ2BvoXczs87BvfL+PeuulNf2QBXAH3LmO31fl3H03D+9fOrqdm388+vwAj0LeJ+GRfftH1vg+f6puxmQDroW8Srvn/EHS/3lwMO6GsP+pYx23mY/nNJX3YebEHfQp7fuk32d++X8WnngbduFUDfUp4PnN2v//x/2GH8PI+nYfje4nLgrAboW8782NnKc9j02oO+Frz5WJi93lqgrxWcsuMA+oIw6AvCoC8Ig74gDPqCMOgLwqAvCIO+IAz6gjDoC8KgLwiDviAM+oIw/wF7dORZZYomfQAAAABJRU5ErkJggg==" alt="" />aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAATEAAAD2CAIAAAAxnSeHAAANlElEQVR4nO2dYW7bOBdFB4GRRQ26nKALKrqUYBZTdClEvu+HE8e2ZFkkL8XLx2McGEjaXlDP7/BJssfzz/+8H+kjAUzFP72le/LoXiCAg8FJAC9wEsALnATwAicBvMBJAC9wEsALnATwAicBvMBJAC9wEsALnATwAicBvMBJAC9wEsALnATwAicBvMBJAC9wEsALnATwAicBvMBJAC9wEsALnAzL6eV0ej11XwbkgpOhOL2eziquPlfGClfYvVDO4GQQNlS8e5YECtdWf9TCAnZ/HRNOxmCnjTsHpipHG7UzU1i3Xq8mTg5Plo1Pp5MqRxuVG3hklBycHJsCGzfmgCpHG1UWeExUC3ByYIptXB0CqhxtVE1g66hG4OTAVAp5PQE8o+oD20W1AydHpX5IXk8A4cj1md5NF9YOnBwViZDn7d8zSnWYLaKagpOjIpyTnlHOC2sKTo6K4XATPtse4wGvLE4OSXdnxnJSvjCchDUne3fnAd3ffQ04ufLo3v22yFpN2LW9hYmhJU6OiqrJrKMs94vWryxOjoqwwzyjnBfWFJwcFdXen1znpPPCmoKTAyMbR5J+FerNnHR+dO97Z+pH5U2UaICIo1RO6qJag5NjUz+LanMWacKoxOddDR/dm96fsgmgyllNM4m6d1IX1RScjMDdnMkaRDc51WPNJepBoDCqHTgZhG8bV7tq92a/0+rLj0ZR+8aaMKoROBmKz4Zb9n3OTv9I5vtf7vnaG2GU6Fzge1WWQiacjMrO+fMk4bHhXaJU5wLp0ebV9ZT1Ak5Go8WWL+zO+ijJuUC7WtWDk3HYf4HUfanKQ66Qx7NKOBkE55sWhjgXCicjkGVj9znQHfNC4eTwFNg487T0LxROjk2xjXNOyyEKhZNjUynkVKNylFrh5MDUD8mpRuUohcLJgZEIOcmoHKhWODkwzMmQtcLJgRlo7+/OQLXCyVFRbfyTjMqBCoWTo6J0MvqoFG5eB9QKJwdmoL2/f6FwUvXo/nI6M0qTOTBQrXByYJiTIWuFkwPDxWRGrZiTqkf319KcITZ+B1SXlAcsFSfHhiGZUasRhEw4GYCMCTDrkMwuFE5uPLq/kEOwt6tmnZDfhRrhhAIng7AyBJY/zjohnxTKZkKewck43I/E5ZCceELeFGrzfL77JTdORuN7JL4uhuT0Nt5XablzLX55/NpwMjK9umoUlqf0DvsXTtohvN6b/NIxt1Am5cJJC4Q3GHzuVQyBYblwsndP7L77d2TUDNiWCye7toXujrzzzX1DnMuFk/3aouj969ZRM2BeLpzs1Bb5PfFozxZGzYB/uXCyR1uU9sRyzxZGzcAQ5cLJHp1R1xbXG7YwagaGKBdOHt4W1Vv1ZcMWRs3AKOXCycM7Q9EW5w1bGDUDo5QLJw/vDObk+JVvCk4e3hnMyfEr3xScPLYtRFu1/Ll7ZcaqfNOl4uSwnSGN6l6ZsSrfdKk4OWpzaKNmYJRy4eThnaE72+TEtVflm4KTh3cGc3L8yjcFJ8fsjFedk/PMyUHKhZNDNkeLqBkYolw4OWBnlH3ede4hKa98O3CyX3OUulQY9bLy++51sK58p3LhZL/m2NkKO/bpvW6/Po+aAdsJeQYnvZvjdlN/ErVnTk55GVlS+X5X3Thp0BzLebg84dyxTz856b2i+1E7sGsX61EunLRgORKLFbqdiun0kq6HZPcjdeOhmf02r3mdFF61q6IktxO+PFyn+zH6Rtnc95rLSeE1g2HUto0FZhoeo22UkFmcFN7vdo3KY8xjdIySM4WTO6u/Z4M0jcoUcltL02O0jMLJIiFzqr+9O7pGlTPOMTpG4WSRkPnVf7Q7mkZVCLnU0vQYLaNwskjI0uovd0fPKK2TnsfoGYWTpU7WvQCnNv/5hTKqWshrLU2P0TIKJ4uErN4UL1ujZ5TWSc9j9IzCyW5D8rI1ekb5OmlZLm3lcbKnk8Jn6znZuzhN9dauCidjOanbrVVCftG/PivHaLAMnLx/hBFS/xzdSdtnnCx1UvhKWEZJR6XpMXpG4WThgUlb3zFK6KTtMXpG4WSpk6J90TZK7KTlMXpG4SRz8uFuzZzsVXmcLJ2TqpfTMkql5STlklceJ/uMSvMooZO2x+gZhZPdRqV5VL2WU5VLXnmcLNWy7DVYaf2HfzM7SreqGi3XcvKPrv0xekbhZJ2Woh1xPepZWutVlWm5t1z71tan8r2jcLJCS2XrP5skNVF1bVEv5MrCnh1gxjHWzSLPKJys0PJp9Xe/APf/6uX01etXv9kftWcc5bRFjY3rC1sWKmun2D7G8aPkzOLk/Sux3Ptzv9pY0fo3q8qftDsXWVuu1/tClZTr0ciNEiVkLidvXozSjledIj4I/x68miMVRZ0rJiu+8IuS/aIqmchJyUW86lZKbnLmkaqWJKgY5DKFk8+v47+en+SI3nIojj0sSlUxKCC+k6rbm2VCPhXAMEpVMSgjuJNZvbWx99cIuSGAYZSqYlBMZCcLeuvR3t/CSWGaKkpYMSgmrJPFvbXc++uFXOt+WZoqSlgxqCGuk3Xtdb3xz+KkrmJQQ0wn67f8641f7qQwUBUlKRdaSgjqpLTDdH2PkzCtk7o5KRRSDk6GBCdxEie9COikSsghtJSClhbg5Oaz9KuN7fXGSQsCOinU8jNN56Q8ECHjEdRJaYfhJE4eSVAnpXMyqT9bh5OwAU4+uZhMIotulmfopLpiUExMJ1ODT2+qhKxPu8tURckrBmXgZMaWrxKyOMraSYakiLBOptJv8ty+LpIIWRa1EauKyqgYQ7IZkZ1MZXv/s/1eImRu1NNYVdTeQjEhmxHcybRz78/f7ytt3JnTdPBmVGz5IxOyGfGdTMtvSX6065fu97kerv7zr5DTMYM3r2LLcjEhmzGFk2e+N/i1XT87TTQn00dKH6cNCgJlM/y6YndDEhubMZGTF/bcy9n855pZlD7Sto23VK1TVbQDOhLmcrL+7TXd5d9+G7PNlM7wm9J179cZmMXJ+ndBkvI2aZmQz7WUzvAnReveu1GZwsncd0TWQ4qEfCBAEyd1M5zvQe9JfCclnxmoEXIhQI2QD7XUzfDsinVv4mAEd7LkMwNrE0DnZL2QK1oKZ3h9raCSyE4W23g3AeqFvOp+vZPCGV5fK6gntJN1Qp703zOgEvJGS5WTqnJBJWGdrB+Sl+3f2UnhDFedVkAlcZ1UCHmSfm+ds5PCLQwqwclnz7Kmx0nASScn1UI2cFJ0WgGVxHRSJqS1lkIh0+lFU7TuDR2AuE4qtZzDSU5fPYjpZOK+a48hiZMS4jopajJh31s7iZA2xHVS2mQKIc8ohZQsDCfdiOuk6JIyiVr/a2E4CU8I62RSfzBFIeQZmZD1C7ssT3Oqj5MKQjtZPSrvAwVCnpEJWbyq5Qol195QT2QnU02fPdjyFUImrZMFq1pdIUPShOBOptJpuRVYK+QZmZC5q9pYYc2ZRfdWDkN8J9NlAkjbq8LGawQ27lzSzkUyIbszhZPp+qtKG7RXpodLam28W0nlDN9ZKC4jGzGLk2canX25nbzVz/CbyqyWiwnZjMmc1N02bHcHUjh8Tq+nmhn+fXKxHJLY2IxZnBReTLa47SEc4C3OBbiXcyRTOJl73+KYqNzAI6N2ZnZv35DEd1J4Z18YVRZ4TFRuYPcmDkZwJwsUejQEhFE1ga2jygK793EkIjtZrNByAgij6gPbRdUEdm/lMIR2ss6i6+1fGOW8sMrA7t0cg7BO1k+2y/YvjFKtrUWUPA3KiOukwqLz3i+Mcl6YJLB7QwcAJ497/lyYLs12YVADTh7uZO9ltF5Y954enZhOOjT6o351WAZz0pmgTr5KG9czSq0lc9KEmE4m18s2U70bGA44uXBSt+trB4jnwrRmdm/roYnrpOWcnGRhUENcJ0UbvzYquc5JeRoUE9bJ5PpxGU3rC69OmZNmhHayer61iEqun3etP0aclBDZyST9fleLqEWgMCrxeVcPgjuZpN/v2j1qNdAkCidVxHcy3W3/+WOtVZRi5FpE7ThY2M8UTqbrCbDaUjk7fZOozV6//GgUxYRsxixOnvnstmWn5m/zqqhHPt//cqfhqijd6QDkMpeT1wibqT7q2uel5F2ihKcDkMW8TtpiullUn1nATnAS9oKHx4CTAF7gJIAXOAngBU4CeIGTAF7gJIAXOAngBU4CeIGTAF7gJIAXOAngBU4CeIGTAF7gJIAXOAngBU4CeIGTAF7gJIAXODkP728vb+9/fv94Ob39t/ZH/VcIKeHkLPz3dvoS8rTiZEp/fv94+fH7T+91Ak7OwdUYXJ+Tlz9iWvYHJ+Pz/vP049ffzx83nPxIf3/9OP18777gycHJ8Ly/XZ+Ufjr59/e/569Ovj1fZVQagJPROV9JXn78vKT8VPH95+nmTz/e3x5PUTgGnAzO318/lk5eWXcn4fvby9WJLvQAJ4Ozx8krCXGyPzgZnbVz128n798C4dy1PzgZntV7POcf//7+93Rzo5V7PAbgZHxu3gv5PJv9/P/V3Z2m8l6IAzg5A7ejcuuvMST7g5Nz8Pyjc1xJuoCT87AxBpmQRuAkgBc4CeAFTgJ4gZMAXuAkgBc4CeAFTgJ4gZMAXuAkgBc4CeAFTgJ4gZMAXvwfUtwa3Jh5sMUAAAAASUVORK5CYII=" alt="" />aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAARgAAADtCAIAAADrxP3FAAAOKUlEQVR4nO2cbW7byBJFB4LgRQVejjALCrwUI4sJvJSGZ37Ilil+9sdp9m3yPhwYyEtyp1mqU0Uyhv8Jn8GYc/If979/ml+MMa2wSMYAWCRjACySMQAWyRgAi2QMgEUyBsAiGQNgkYwBsEjGAFgkYwAskjEAFskYAItkDIBFMgbAIhkDYJF0uV6u15dr82OYGCySFteX692f2a+FseAJmxdKDYukwoo/o69IIHi28qsGC9jq47NIEkQqFLmaqBw2KjITrNuen6BFak+SQpt7gMpho1ID94xCsEiNyVBoZeJSOWxUXuA+URQWqSXZCs2OWyqHjSoJrB0FYpFaUmjRcNZqRpUH1otisUjNKF9Hw1kLLjedPVn1YCwWqRmIRfdBqxlFXWaNKByL1AxwI2lGKR8MxyI1Q3CNgF9lr7HSp2mR+rZI9qvsZVb6QC1SO5Fat9QOLdv8DBbp+GD9AbZa6y7v1yWL1E4kqDOkoyQlr/FpWqR2InFtkfDnN6PQZiWvUdiiYJEaQk3ZEC/S1n8xISpiI7Fp7MFwLFJL9h78MRsJ6df1t3beSBaJpXwpPUXFrCMkKnrqz/8XszeSRTJLlE/9qJwhW2nUOvpKW1I6Y1ioWhQskgJ5szYhZ8TqDik50uzBxlHrPs/9FnIqi3QKxn2fMvIXc2bXUXRa+S6aidpUevRbs1oSexLHIqnw00Bbc3o7Z2Udbe2itaitNbIdta705Lc2CqWxi+5YJC3m2/2btJBp4046OCFqddgnRE2tXtB+I2r9/nBfi4JFkiVyaaxxua6RepjlO8+iK00/zNORWt/RPbBIcgDDdV2hXJ1+jlfw1xdP26pWEBZJiPib/rWceItSOxh0EorKrxKNRVKBeXpOtSiycfWipB6QgkUSIeM11MzEzbNos2v1okoLVQGL1J4MhWbGbYlFK12rF1VaqDpYpMZkK7SHSGAaFFVSrqqfo0VqDCNSuUXT7gfToKiSQtXeSxapJYVt8TNlTyISVa4KWKSWYCMWFwkMhKLKa1V1KVmklshtJDyQi7JIZhFGJNAiHO54FsnUsuirLZrbYpEsUkPIzmguzC4ou2SRmrqkJhIYZZEs0m5gPQGKhAeewKJgkdrCvGz4tEgW6dyQbQFahKRZJIu0JxYpVqQXi2SWIduCsqg8bZQJRclaFCySAgmzdukZ6QFlUXZUVZGKl1K9D9EiSRDbCs9SzachFuVFrcRCUfki+efanYSZcTv95couGoJYlBq1GQtF5e2l2h+fRRJivHym6yhpuBYqFJlTdcUtFWr1dnfnXXTHIsnxs3xeJusouydS5Zn96zuvuJgqLb0W33EX3bFI0hS1ArWRNqPwwPj6TO54gaGThUXi2X6GqR2lt0C2w4lCgZVPxSIxgE+6pVHQcwgclZTcqPIlWKRS4t8d7RGV2vorjQtG5cXuWPlyLFIR4EtYICqv9We7Fowqid2l8ggWKZ+Mf81Ymo5AVEnrj7oWjCo/YeXKU1ikTDI+yKXpyESJi8SlgZUHsUhZFuV+kNPpWBiFtf6jZcGoCmaClbdI7Sn8LIej0SKlicRV3iK1tqh4KD5GIxJFdj8IaNF3IFL2Si5ZpHSRuI+TErK9NvVFouaXRVJBbiM1d2bdJUokziWLJIHcRpKFFckb6UiAHyc5YsHWl7ToyyXhpWSRLNL5RKqwlCxSM5eoKLj7WZG4QOV1ZJGyROLu1LG2OINI3A63SBIobiSkX8HWH1aMEskb6WCAt+kWqYFI3kg6gEORvEuhWp+NgsykRk+llrBILUQafq9dyt/avt2nWl8hai5Wcx0Fi5TNUmfHCJAZNXd7A3TtymU2jFqOTah8TLkgLFI+sZ9fxESMFfJlOyokde3mZTaJ2oqV2kV3LFIRsd0fcYO+PWifl9L28Qr7vkYUt+JEHo0eWKRSfgRYvx+LmIgb94QDks+ZIU+lKG7FRY2e+rvojkVimC6f7L4fGnhvqeE6yj9e/amcALctF3XaS6E7HYsEPj5SUcxzLdRk9R672cpT23KHNwordCYSeB+sGAU+2cteo2pUId2IFP9k2WkU+CAue42aUQh9iBRZsphRpBkFvhqWvUbNqBOJlFSy9TmkGZVp0YJLmteoGXUikTJKtjSHNKOKLJq4pHmNmlEnEim7ZNM5pBnFiqR5jZpRJxOprGrDIaQZBVg0cEnzGjWjTiRS+fh5DCHNKFYkzWvUjDqZSETV7kNIM0pXJMlywZW3SA2/Sm+k1sWp6iR7KovU/jMg5yJl0eUaLhL1mV6jwjFOLVLzcu/RZ0cXSfbryUQCyycZBS4luNuOHnUikYLqCx/4s9R82XD0qJOJBE0g2ShYJMlr1Iw6mUiSwwyei95IrSp/IpFeuM9AMgpz6Rzl4it/EpGQISQeBYoke42aUScTqXgIiUcBLp2pXHzlTyJSKHnEnFRt5U8mR3GnKnJpWq6Mq6t/jZpR5xIp5M6hhKittNqnynQpslxxZ2tT+dZR5xIppN8cp0Wt/nKfUyW7FF+urQtMuMayqa8ZRdGHSCFmDkVXbfy3vrvzOiQ+KmbwJ32WBQrNH2xaqBS9N66x/yiEbkQal286ZVNLRvTr06nSd1rsIQvL9TIuVEa5FpfbUaIK6Uykpwpmtyl0BzV/sMGKYy4WirpXDCs+9QMiJaMy6Ekk5mkSeqZPTk66WCiq7fP3qehDpO0Hyu+vG1GpFkU2rl4UVjETRwciYS/H8iza7Fq9KKxiJhp1kZIaYm3Klli00rV6UVjFTArSImU0xOKUrSESmAZFkRUzKeiKlN0QM1O23KJp94NpUBRZMZOIsEhlPfE0Yk8iElgxk4ioSOXD9WnE4iKBgVAUUi67lI2qSGxbUH1fw0yLdAhURQI3EmgRDnc8i9QWi2SRLNJBRaIs6sMlDrtkkaqJhP4cRjLKIh0LRZGC39rZot5QFYltC4tkkSqjKhK7kT7pbxGySOaZQ4tU4ecwYmm4SHjFTAqiIoUa3zlGWVSeNsqEoviKmWiOK9LscKUsyo5SFsnrqABdkULZT9ZcjEUsyotaiYWiEirmdYQiLVLIm7KbkxWxKDVqMxaKii2UdxGKukghcspmTNZChVZyPvdacfEVm/7SuwilA5HC9Ec6Ls3X7MmaKs+Y6wY1VlxSxabl8i5C6UOkOz+jdG6+JgdSG2nToi8anO2pYqN1ZIVQehLpQdRLhRWgqR8+Q7RF6S6NzgkVbbfP6Gx0JhLwzyDQc0iiQok6YdtyXLrmDXdUuhEJePH9yf6AyDoikdvSP2l1P/oQKfUl+HxOnkXzXZtt0apL2Lb0T1rdmw5EYv5BtsSiUddeCi1CPScq1rwLD4C6SDn/IDs7a0GRSi2ac4nblkCtTDrSImUrNJ615Rb9tCxi0bNLnORArUwW2iKVWfQzaM8hElYuk46uSOXr6GfQUiJdQIt4ybEFbtIRFomw6GvKnkAkcu6YdE4gEotFMnNYpFYWVRCJWuAmHVGRKItglz4DLBLquTdSQ4RF4lw6i0h2ySJNIdtCViTubOTcad2UPSIsEnVfxzVr+Ay6ItmipgiLxHYGY1GwSGYWYZGgx6SvQEykQFqEHMwiCaArUsD/qZ6x6A5kUfnBvo/H3AlbpFy0RSpeSuNMxqIgKFLw99o1RVqkUNIcS8MVsOgOZFHeqeZO6HXUEHWRQu5eWssELAqwSEmnWj5hyQ5v3otd04FI4TFr2Z7IV2gIoVDkkeIO6V3UhD5ECsMf0VajJ9LkGQFZNDxJ2baMLJQfjUC6EelOpZuT4nsbyKIHxdvyqTKz5fIuQulNJO6lU733V+CYv74kyDN/ktlNboVouhEJfECq8fwNrsoaW9cvFWrTh0ipD9D7RKUG7hkVmdm8/w5DByKBL3PBqLzAfaJSA5t34QFQFymj75fGLRhVElg7Ki+weSP2jrRI2X0/nbVgVHlgvaiSwOa92DXaIpW1/nDQglHKBysMbN6O/aIrUvkOeQxaMIo6W40oPM3EIywS0fr3KQtGKR8MCWzekZ1yfJHAr18H49JkD2ZSsUjp/dr6GLUP1rwpe0RUJIXuXGoyhWN4I6mhKtIL2m2aUbRL3kgNERUpqD6KiDpZQUuThLBI3HxlR7XmwVidmvdldwiLJLmRTnIwk4qwSNCIZaOC6kbC00wSuiIF1W8gYPoVfOLyRhJAW6TiTVIjKqh+r135NVqkbKRFCujPtZOImgSCUcHfa9cOdZEC+nPtmkfNBopEWaQSOhApjAZt+gKpFUUsN4moiIs16/QhUhjO2tk+SJmpVaJWG/TxS6Eo7yKUbkS689Ui0/ZKH6hU1JKE4/8zUksqilu8JobORBoCdkB51FDCqZlNosDFazbpWCRZRA0v3uFmBYt0IixPPSySMQAWyRgAi2QMgEUyBsAiGQNgkYwBsEjGAFgkYwAskjEAFskYAItkDIBFMgbAIhkDYJGMAbBIxgBYJGMALJIxABbpYLzfLrf3hP/fMFikA/Hndl2x5e/b6+X17W/rQx4Ui3QYInbO37dX76U6WKSD8P7v9fX3x+Yf+/j9ev33vflpj4dFOgbvt/Ft28fbr++fXzc0x0upDhbpEIyfjj7efn0vqD+36+V6+/P4rffb0y8Ng0U6Ah+/X59EWnvr8H67RN0EmiQs0hGYEenX28f8H7ZIVbBIh2C0gv7crotvun1rVwWLdAxGLxs+3n4N3jH8fbs9VpBfNtTBIh2Eyevv99vl+63d4DbPr78rYZEOw/QN+Oyf8TqqgkU6EBvfBOSno4pYpIPhb1ptg0UyBsAiGQNgkYwBsEjGAFgkYwAskjEAFskYAItkDIBFMgbAIhkDYJGMAQBF+h9mwXTsl8uP6wAAAABJRU5ErkJggg==" alt="" />

  如图1(a)所示,假设中心的蓝色点是当前处理的点,如果是“4-联通算法”,则只搜索处理周围蓝色标 识的四个点,如果是“8-联通算法”则除了处理上、下、左、右四个蓝色标识的点,还搜索处理四个红色标识的点。两种搜索算法的填充效果分别如如图1(b) 和图1(c)所示,假如都是从黄色点开始填充,则“4-联通算法”如图1(b)所示只搜索填充左下角的区域,而“8-联通算法”则如图1(c)所示,将左 下角和右上角的区域都填充了。

   并不能仅仅因为图1的填充效果就认为“8-联通算法”一定比“4-联通算法”好,应该根据应用环境和实际的需求选择联通搜索方式,在很多情况下,只有“4-联通算法”才能得到正确的结果。

1. 注入填充算法(Flood Fill Algorithm)

  边界填充算法与注入填充算法的本质其实是一样的,都是递归和搜索,区别只在于对边界的确 认,也就是递归的结束条件不一样。注入填充算法没有边界的概念,只是对联通区域内指定的颜色进行替换,而边界填充算法恰恰强调边界的存在,只要是边界内的 点无论是什么颜色,都替换成指定的颜色。边界填充算法在应用上也非常的广泛,画图软件中的“油漆桶”功能就是边界填充算法的例子。以下就是边界填充算法的 一个实现:

void FloodSeedFill(int x, int y, int old_color, int new_color)
{
if(GetPixelColor(x, y) == old_color)
{
SetPixelColor(x, y, new_color);
for(int i = ; i < COUNT_OF(direction_8); i++)
{
FloodSeedFill(x + direction_8[i].x_offset,
y + direction_8[i].y_offset, old_color, new_color);
}
}
}

   for循环实现了向8个联通方向的递归搜索,秘密就在direction_8的定义:

typedef struct tagDIRECTION
{
int x_offset;
int y_offset;
}DIRECTION; DIRECTION direction_8[] = { {-, }, {-, }, {, }, {, }, {, }, {, -}, {, -}, {-, -} };

  下图就是应用本算法实现的“4-联通”和“8-联通”填充效果:

aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAASsAAAEhCAIAAACoXRGFAAAMLklEQVR4nO2b247jOhIEDxbn/7/Y2N2HBoSCrEuVLDKTZAziYaYn7GYVmZZtiv/877c/n/9+AOAx/5BAACEkEEAJCQRQQgIBlJBAACUkEECJLIH//uffCD7+Uv6GJoG7Ud4OGh9/Jj+iT2DmZQMffyY/Ik7gNtxkhfj4E/gRfQLjP/HxV/AjygTuXjnw8RfxI+IExn/i4y/iR/TfxOQrxMefw4+wH4iPL/A3uCcGQAkJBFBCAgGUkEAAJSQQQAkJBFBCAgGUsB84gF/tp5vv1k8Hf4N7Ytz9zIw6+279dPAj+gRmXjbwq/108936qfUj+tNJpQoX8c9mdxTfrZ9ufkSfwMykruZ/P7DaWK3v1k83P8L5QEd/N6+lrjr4bv108yOcD3T0q7Po5rv1082P6L+JyVe4pl+Nq5vv1k8HP8J+oKO/k4fz3fpp6G9wTwyAEhIIoIQEAighgQBKSCCAEhIIoIQEAihhP1DgV/szuu/Wfwd/g3tievuZGZrJd+u/gx/RJzDzsjGfX+3P6L5b/7V+RH86qVThoP7ZbM3qu/XfzY/oE5iZ1NH97wdWGzWW79Z/Nz/C+cAe/m6eSl0a0Xfrv5sf4XxgD786K6P7bv138yP6b2LyFc7hV+M6uu/Wfwc/wn5gD38nT++79d/Q3+CeGAAlJBBACQkEUEICAZSQQAAlJBBACQkEUMJ+oMCv9md0363/Dv4G98T09jMzNJPv1n8HP6JPYOZlYz6/2p/Rfbf+a/2I/nRSqcJB/bPZmtV367+bH9EnMDOpo/vfD6w2aizfrf9ufoTzgT383TyVujSi79Z/Nz/C+cAefnVWRvfd+u/mR/TfxOQrnMOvxnV0363/Dn6E/cAe/k6e3nfrv6G/wT0xAEpIIIASEgighAQCKCGBAEpIIIASEgigZIn9wOp48LW+w37d5PuBu1HeDvoXP7/jjO/gV+d3RD+iT2DmZeN3v92KwW/ht14PWj+iP51UqjDpn3UH39NvvR7c/Ig+gZlJqvpNlwv+637r9eDmR+Y8H9h0ueC/7rdeD25+ZM7zgU2XC/7rfuv14OZH9N/E5Ct85lfjiq/1q/M7oh+Zcz9wJ+Ob+63Xg6G/wT0xAEpIIIASEgighAQCKCGBAEpIIIASEgigZM79wJ1fHQ++1nfYr5t8P3A3yttB/+Lnd5DxHfzq/I7oR/QJzLxs/O63WzH4LfzW60HrR/Snk0oVJv2z7uB7+q3Xg5sf0ScwM0lVv+lywX/db70e3PwI5wPx9X7r9eDmRzgfiK/3W68HNz+i/yYmX+EzvxpXfK1fnd8R/cic+4E7Gd/cb70eDP0N7okBUEICAZSQQAAlJBBACQkEUEICAZSQQAAlc+4H7vzqePDf9R3239z8De6JwW/rt57fEf2IPoGZl43f/ep48N/1W8/vWH5EfzqpVGHSP+sOfh+/9fyO7kf0CcxMatUvLRf81/3W8zu6H+F8IP77fuv5Hd2PcD4Q/32/9fyO7kf038TkK3zmV+OK/67fen5H9CNz7gfuZPzOfuv5ncDf4J4YACUkEEAJCQRQQgIBlJBAACUkEEAJCQRQMud+4M6vjmc1f/T+O+zvDbYfuBvl7aB/8fM7zmv6o/e/9fhb+BF9AjMvG7/77VbAHP7o/W89/nf9iP50UqnCpH/WHfw5+t96/D37o09gpulVv+n0T+CP3v/W4+/Wn4/8dFKpwrzfdPon8Efvf+vx9+nPH5wPXNEfvf+tx9+hPxv6b2LyFT7zq8tlNX/0/rcefws/Mud+4E7Gn6z/rcffwd/gnhgAJSQQQAkJBFBCAgGUkEAAJSQQQAkJBFAy537gzq+OZ3Sffmr7M8B+4G6Ut4P+xc/vCM/h009tf5JD2tAnMPOy8bvvswL6+PRT259hErgNN1lh0j/rzqw+/dT255d+6hOYaWLVt5r+Dj791PbncT8/8tNJpQrzvtX0d/Dpp7Y/z/r5B+cDZ/Dpp7Y/D/q5of8mJl/hM7+6vEb36ae2P8khbcy5H7iTp/fpp7Y/D/wN7okBUEICAZSQQAAlJBBACQkEUEICAZSQQAAlc+4H/uhXx9/aX61eN3/C/cDdKG8H3dPP7wj38Ver181v0f+IPoGZl43+vs8KWLNeN//d/kf0p5NKFTbyz7qp8ler183v2X99AjNNae1bTf+C9br53fr/kZ9OKlXYzrea/gXrdfP79P+POc8HVn2r6V+wXje/Q/839N/E5Cvs41eXb2t/tXrd/Bb9j7AfeCDL/dXqdfNb9z/CPTEASkgggBISCKCEBAIoIYEASkgggBISCKCE/cADvzr+1v5q9br5E+4H7kZ5O+iefn6Ht4+/Wr1ufov+R/QJzLxs9Pd9VsCa9br57/Y/oj+dVKqwkX/WTZW/Wr1ufs/+6xOYaUpr32r6F6zXze/W/4/8dFKpwna+1fQvWK+b36f/f3A+0G76F6zXze/Q/w39NzH5Cvv41eXb2l+tXje/Rf8j7AceyHJ/tXrd/Nb9j3BPDIASEgighAQCKCGBAEpIIIASEgighAQCKGE/EL/sV+d3dH/C/cDdKG8Hje/jZ1bYTH6Lfkb0Ccy8bOC7+dX5Hd1/t58R/emkUoX4Ev9stc3q9+ynPoGZpuBr/e8HVid6LL9bPz/y00mlCvFV/m6dlWZ5RL9PP//gfCB++aNRfooH9Tv0c0P/TUy+QnwHvxrX0f0W/YywH4ifXZHr+B36v8E9MQBKSCCAEhIIoIQEAighgQBKSCCAEhIIoIT9QPyyX51fN9+hnxvcE4O/1j0xDv2M6BOYednAd/Or8+vma/sZ0Z9OKlWIL/HPVtsovnM/9QnMNBFf638/sDrRWt+2nx/56aRShfgqf7fOSrPs4Hv28w/OB+KXP0rlp9jEN+znhv6bmHyF+A5+Na5uvkM/I+wH4mdX8Li+Wz8j3BMDoIQEAighgQBKSCCAEhIIoIQEAighgQBK2A/EL/vV+W3tu/VngP3A3ShvB43v42dWWE/frT/JEjb0Ccy8bOC7+dX5be279WeYBG7DTVaIL/HPVpvKd+vPL/3UJzDTdHyt//3A6kS/67v153E/P/LTSaUK8VX+bp2VZrmF79afZ/38g/OB+OWPXvkpbuS79edBPzf038TkK8R38Ktxbe279SdZwgb7gfjZFe/ju/Xngb/BPTEASkgggBISCKCEBAIoIYEASkgggBISCKCE/UD8sl+dX9bDBdwTg+91T4xbvS38iD6BmZcNfDe/Or+shzP0p5NKFeJL/LPV9pbvVm/PfuoTmJkkfK3//cDqRLMezuB8IH45J6VZZj1cw/lA/NobxdIUsx5u0X8Tk68Q38GvxvVBvK3qbeFH2A/Ezyakne9Wbwd/g3tiAJSQQAAlJBBACQkEUEICAZSQQAAlJBBACfuB+PgCf4N7YvDxe/sRfQIzLxv4+DP5Ef3ppFKF+PgT+BF9AuM/8fFX8COcD8TH7+1HOB+Ij9/bj+i/iclXiI8/hx9hPxAfX+BvcE8MgBISCKCEBAIoIYEASkgggBISCKCEBAIoIYEASkgggBISCKCEBN5weIdR6baj/PO/+LTXT/j6L4LHrJXA3c17hxw+JP/DX54/Y5ae/zqB5NCB5RK4++ftKsxfAzNXs8NcJR9+MdTqte7wl4KE1RNYfcjnfPnuInR4aTp7SOaadp3A69CWLsvQk0UTmHn/VorQg79/QnJKj714UTgb/60PKtZN4Nl/XfjX15Bv+ftpv6+Thz/P/D3zTpJ3of6sm8DMm7GzdH0L8TkP//fweX58F3oY8tt6v38un5eVWTeBZ/91+JPMMj0M53WKrhN+kfbkwK6vz8m6oCkkcP9fhz+5uFidObunOrzSnn0sjA+5HWHyGvj9EOLnwLoJzL8LTV6XrjNz8bFw98Dbt8RnT56s92wwIGHRBF785FvIJ/D2N94G+HMej+thXP/267e7IGTRBJ59Ljp7yNnC/fFj2/dnxYsQXofnMIRnl/fv3wgqFkrgxQXnc76Cd38vXQMzH/wO5cNRXb9Y3F4VD0u+eELow4oJvPiodntNu/j0mHmLe3sNvB5qhsPCL2ongVpWSWDm/efth7rvn/+YkLOItkjF7UUeJCyXwNsfvvsrrp0OowJzVkkggCckEEAJCQRQQgIBlJBAACUkEEAJCQRQ8n9UvOL8qemDvgAAAABJRU5ErkJggg==" alt="" />      aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAlsAAAElCAIAAABcZ7AKAAAWi0lEQVR4nO2d0a7sKA5FW6P6/y9GrXmIOkpBTmKnMGyTJa2Hc3sW52KDy5nuIvxT/i0AAADwz/QZAAAAKEBHBAAAKIWOCAAAsEFHBAAAKIWOCJCXz/8+R/DxX+VHcNMR1VKAjz/SV6YK4TYifPyV/CCuOqJaCvDxR/riHOf/MfR4fPyV/CCsHVEhBfj4I31x9vnvsRjDx8dfwA/C1BFFUoCPP9IX5xjO8Y/4+G/wg7B2RIUU4OOP9MX5fPd1Y/j4+Gv4Qdx3RJ0U4OOP9MU5xuIKHx9/AT8IU0cUSQE+/khfnGr+xvDx8dfwg+C7pvj4Wfn81+ONseDjr+RHwHlEfHwAgFJ4Zw0AAMAGHREAAKAUOiIAAMAGHREAAKAUOiIAAMAGHREAAKAUOiJAXtQOq6j51cB0vlo+1fwIOI/YZ0mS+mr5VPOVqUK4jehtfmXal1vEV8unmh8E76zpsCQiJeT11fKp5otznL9lxd/mV6a3lqf7avlU84PgfsRfl0SnhLy+Wj7VfHH2+RtX/G1+O8Sb0rm+Wj7V/CC4H/GnJZEqIa+vlk81X5xjOJYVf61vkZV9tXyK+EFwP2IH37h+sr5aPkV8cT7ffd0Y/jv948CMvlo+FfwguB+xj69WQpTc77441RLbw3+J34715naur5ZPNT8I7kfssyQKJeT11fKp5otTzd8Y/nv8i7EpfLV8qvlB8F3TPkuiUEJeXy2far4+e483xvI2vx2Vy1fLp5ofAecROyyJTgl5fbV8qvkA8Cp4Zw0AAEApdEQAAIANOiIAAEApdEQAAIANOiIAAEApdEQAAIANOiJAVtQOqww7DPMSXy3/an4EnEe8Gri8r5Z/NV+ZKoTbiLL77SK6EpXOV8u/mh8E76z5c+D0koj21fKv5otznL9lxbP7lemt5XS+Wv7V/CC4H/F8lEJJRPtq+Vfzxdnnb1zx7H47xJuiXL5a/tX8ILgf8WrIbfpS+2r5V/PFOYZjWfFlfIu8kq+WfxE/CO5HPPGN67GMr5Z/EV+cz3dfN4a/hn8c+AZfLf8KfhDcj3juq5UEJTfeF6daYnv4Sf12rDdXuXy1/Kv5QXA/4tVYex4z+mr5V/PFqeZvDD+vfzF2SV8t/2p+EHzX1DR2SV8t/2q+PnuPN8aS3W9Hre2r5V/Nj4DziDej1vbV8q/mA8Cr4J01AAAApdARAQAANuiIAAAApdARAQAANuiIAAAApdARAQAANuiIAFlRO6wy7DDMS3y1/Kv5EXAe8Wrg8r5a/tV8ZaoQbiPK7reL6EpUOl8t/2p+ELyz5s+B00si2lfLv5ovznH+lhXP7lemt5bT+Wr5V/OD4H7E81EKJRHtq+VfzRdnn79xxbP77RBvinL5avlX84PgfsSrIbfpS+2r5V/NF+cYjmXFl/Et8kq+Wv5F/CC4H/HEN67HMr5a/kV8cT7ffd0Y/hr+ceAbfLX8K/hBcD/iua9WEpTceF+caont4Sf127HeXOXy1fKv5gfB/YhXY+15zOir5V/NF6eavzH8vP7F2CV9tfyr+UHwXVPT2CV9tfyr+frsPd4YS3a/HbW2r5Z/NT8CziPejFrbV8u/mg8Ar4J31gAAAJRCRwQAANigIwIAAJRCRwQAANigIwIAAJRCRwQAANigIwJkZdjhE/wUvtrhpYyHoyafR6wG4ov7aiWRseR6UYVwG5HXb5Pmmhj+YD96P6j5Qcx8Z01lTt9S+Bbtrz+u54tznL9lBb1+ZXprGX+wH70f1PwgZt6P6F1y/Lm+WkkkLble7PM3rqDXb4d4p4Q/0o/eD2p+EDPvR/QuOf5cX60kkpZcL47hWFbwsW+R8XX86P0g4gchcT+id8nx5/oiJZG05Hrx+e7rxvCf+ceB+Pp+9H5Q8INQuR9RbUvhz90PCr441ZLZwzf67Vjv3PBH+tH7Qc0PYub9iO1Y+7zxx/tqJZG05HpRzd8Yvt2/GIsv6EfvBzU/CInvmj6IH3+8r1YSSUuuI3uPN8bi9dtR+Mp+9H5Q8yOQOI+os6Xw+65vdh8AXgXvrAEAACiFjggAALBBRwQAACiFjggAALBBRwQAACiFjggAALBBRwTIyrDDJ/gpfLXDSxkPR0mcRywyWwrfoumURMaS60UVwm1EXr9Nmmti+IP96P2g5gch8c4akS2Fb9H++uN6vjjH+VtW0OtXpreW8Qf70ftBzQ+C+xHxKbmU7PM3rqDXb4d4p4Q/0o/eD2p+ENyPiE/JpeQYjmUFH/sWGV/Hj94PIn4Q3I+I7/ZFSiJpyfXi893XjeE/848D8fX96P2g4AfB/Yj4lFxKqiWzh2/027HeueGP9KP3g5ofBPcj4lt9tZJIWnK9qOZvDN/uX4zFF/Sj94OaH4TEd00fxI8/3lcriaQl15G9xxtj8frtKHxlP3o/qPkRSJxH1NlS+H3XN7sPAK+Cd9YAAACUQkcEAADYoCMCAACUQkcEAADYoCMCAACUQkcEAADYoCMCZGXY4RP8Kb7aYSQ1PwKJ84hFZgu+zVfb4mq+MlUItxF5/TZpronh/+hHr292PwiJd9aIbMG3+WpbXM0X5zh/y4p7/cr01jL+j370+mb3g+B+xPf6altczRdnn79xxb1+O8Q7Jfxf/Oj1ze4Hwf2I7/XVtriaL84xHMuKP/YtMn6cH72+Sf0guB8RX2WLq/nifL77ujH8Z/5xIP54P3p9M/pBcD8ivsoWV/PFqZbYHr7Rb8d654b/ix+9vtn9ILgf8b2+2hZX88Wp5m8M3+5fjMUf4Eevb3Y/CInvmj6IH/93X22Lq/n67D3eGIvXb0fhj/Sj1ze7H4HEeUSdLfg2X22Lq/kA8Cp4Zw0AAEApdEQAAIANOiIAAEApdEQAAIANOiIAAEApdEQAAIANOiJAVoYdPsGfkv+Rx7TU4p11OEriPGKR2eJqfvb8q5WQQsn1ogrhNiKv3ybNNbHl/ej8HwXvfNTmH+EHIfHOGpEtruZnz79aCYmUXC/aT0DvJ6wlfO8DxHv86PyP7Ihj5h+xP7vD/Yi6fvb8q5WQSMn1Yp+/cUW8fjvEO6W1/QH5b8d29KPnPzI/HeF+RF0/e/7VSkik5HpxDMeyIo9973K/zQ/K/+nEOvrD9k90fvrC/YgJ/Oz5FykhkZLrxee7rxvDf+YfB+KPyf9xlHdXqO2fuPx0h/sRc/jZ8x89/whfnGoJ7OEb/Xasd25r+wPyHxpm9PxH7s+OcD+irp89/2olJFJyvajmbwzftYLP5Jf40fn/pX2qzT/CD0Liu6YP4n+Dnz3/aiUkUnId2Xu8MRav347CH5b/Su7uR89/gB+BxHlEnS2u5mfPv1oJKZQcAMjCO2sAAABKoSMCAABs0BEBAABKoSMCAABs0BEBAABKoSMCAABs0BEBsjLs8MlL/JGHf7zrq+Yr5DMCifOIRaYkon3yOTc/CiXXiyqE24i8fps018TS+dH5PAre+aj50fkxTikCiXfWiJREtE8+5+ZHpOR60X6ieT+RLeF7HyDy+tH5VO5wmvmR7oiU3O8++ZybH5GS68U+f2OGvX47xDulXP6AfLZjE/nR+fklnx3hfsRxPvmcmx+RkuvFMRxLhh/73uXL7gfl83Riifxh+82bz75wP+IEn3zOzc/ckuvF57uvG8N/5h8HvsGPyOdxlHeVFfyR++1BIL3gfsQ5Pvmcmx+LL06VUnv4Rr8d651bLn9APhXCfOxH5+eX/dkR7kcc55PPufkRKbleVPM3hv9sBRW2R7Qfnc9f2qeaH52fB0vcC4nvmj6IP6NPPufmR6TkOrL3eGMsXr8dtbYfms9KTudH5+eBH4HEeUSdkoj2yefc/CiUHADIwjtrAAAASqEjAgAAbNARAQAASqEjAgAAbNARAQAASqEjAgAAbNARAbIie1hFxB+ZH+96vc3Pcjhq8nlESi5XvGp+xpLrRRXCbUTRfptkVyDd/ZH58c7nbX5E/oOY+c4aSi5XvGp+0pLrRfsJ5f0E7+tXpndvd/fH58c7n7f5EfutOzPvR6TkcsWr5ictuV7s8zdmLNpvh3hD6OsPiLcdiz8l/x2ZeT8iJZcrXjU/acn14hiOJWPDfO/yRftB8Z5ODH98/vsicT8iJZcrXjU/V8n14vPd143hj/GPAxX8iHiPo7yr9gZ/TP67o3I/otd/Q8kpx6vmR+RfnCpF9vCD/HasN5a+/oB4FcKU9Ufut47MvB+RkssVr5qftOR6Uc3fGH6c712+aH9kfrzzeZsfkf8gUn7X9EG+MpacWrxqftKS68je442xRPvtqLl+aLyVjD84/0GkPI/4kpITjFfNz1hyACAL76wBAAAohY4IAACwQUcEAAAohY4IAACwQUcEAAAohY4IAACwQUcEyIrm4ah94HR/ZH686/U2P8vhqJTnEctrSk4tXjU/Y8n1ogrhNqJov02yK5Du/sj8eOfzNj8i/0GkfGfNS0pOLV41P2nJ9aL9hPJ+gvf1K9O7t7v74/Pjnc/b/Ij91h3uR3zuvy1eNT9pyfVin78xY9F+O8QbQl9/QLztWPwp+e8I9yM+998Wr5qftOR6cQzHkrFhvnf5ov2geE8nhj8+/33hfsQO/tviVfNzlVwvPt993Rj+GP84UMGPiPc4yrtqb/DH5L873I/Yx39bvGp+RP7FqVJkDz/Ib8d6Y+nrD4hXIUxZf+R+6wj3Iz733xavmp+05HpRzd8YfpzvXb5of2R+vPN5mx+R/yBSftf0Qb4ylpxavGp+0pLryN7jjbFE++2ouX5ovJWMPzj/QaQ8j/iSkhOMV83PWHIAIAvvrAEAACiFjggAALBBRwQAACiFjggAALBBRwQAACiFjggAALBBRwTIitrhKHy7713f7H6Ww1HJziPiG3mJn7HkelGFcBsRvo5v2X4r+RH5DCLTO2vwjVvE+4mf1E9acr1oP6G8n8j4c33v+mb3++YziEz3I+JbtshuGvdTXj9pyfVin78xY/hz/dOxC/sj89mRTPcj4nt34e3yp/aTllwvjuFYMoY/128Hehc6lz8sn31JeT8i/rVvkVfyc5VcLz7ffd0YPv4s/zjKu8oZ/TH57E7W+xHxr/3jwDf4EfkUp0qRPXz8Kb7RWcYfkM8IMt2PiO/djvZ9kNFPWnK9qOZvDB9fwfe2z+x+RD6D4Lum6/gXY5f0k5ZcR/Yeb4wFf6Jfycv7A/IfAecRl/LbUWv7GUsOAGThnTUAAACl0BEBAAA26IgAAACl0BEBAAA26IgAAACl0BEBAAA26IgAWVE7/INv973rq+Yr5DMCziMu5VcD0/my+RSkCuE2Inwd37L9lH2FfAbBO2vW8SvTvp9EfNl8atJ+onk/kfHn+t71VfPn5jMI7kdcx69M437S8TXzKcs+f2OG8ef6p2MT+cr57Aj3I67jt0Nul1/KF8ynMsdwLBnGn+u3A70LPdeXzWdfuB9xQd8iK/si+RTn893XjeHjz/KPo7yrrOBr5rM73I+4pn8cmNFXyKc4VUrt4eNP8Y2OrC+Yzwi4H3Edvx1r3wcKvnI+BanmbwwfX8G3l4Omr5DPIPiu6Tr+xdgUvnI+Ndl7vDEW/Il+Jafz1fIZBOcRl/LbUbl8zXwCwEvgnTUAAACl0BEBAAA26IgAAACl0BEBAAA26IgAAACl0BEBAAA26IgAWVE7rIJv973rG+2r5WfW4SjOIy7lVwOn+2r5USi5XlQh3EaEr+Nbtt9IXy0/xhAi4J016/iVad9PQb5afkRKrhftJ6D3Exl/ru9d32hfLT9TypP7EdfxK9O4n+J8tfyIlFwv9vkbVwR/rn86dqKvlp9f8tkR7kdcx2+H3C5/qK+WH5GS68UxHMuK4M/124Hehe7rq+XncT77wv2IC/oWeaSvlp+5JdeLz3dfN4aPP8s/jvKucoSvlp9n+ewO9yOu6R8HKvhq+bH44lRLYA8ff4pvdIb5avl5kM8IuB9xHb8da98HEb5afkRKrhfV/I3h4yv49vIZ46vlxxhCBHzXdB3/YuwUXy0/IiXXkb3HG2PBn+hX8nRfLT8P/Ag4j7iU346a66vlR6HkAEAW3lkDAABQCh0RAABgg44IAABQCh0RAABgg44IAABQCh0RAABgg44IkBW1wyr4dt+7vuyHMXAecSm/GtjdV4s3Y8n1ogrhNiJ8Hd+y/X7x1eKN8IPgnTXr+JVp309GXy3epCXXi/YT0/uJjD/X964v+2EA3I+4jl+Zxv1k99XiTVpyvdjnb1xB/Ln+6diOvlq8I/PZEe5HXMdvh9wuv8tXizdpyfXiGI5lBfHn+u1A70KzHwbA/YgL+hb5F18t3lwl14vPd183ho8/yz+O8q4y+2EY3I+4pn8cGOGrxRvhi1MtmT18/Cm+0Xnsq8U7IJ8RcD/iOn471r4P7PWsE2/SkutFNX9j+PgKvr3cnvlq8Ub4QfBd03X8i7FdfLV4k5ZcRz7/9XhjLPgT/Uru7qvFO8CPgPOIS/ntqL6+WrwZSw4AZOGdNQAAAKXQEQEAADboiAAAAKXQEQEAADboiAAAAKXQEQEAADboiABZUTusgo8/0o+A84j4+CmpQriNCB9/JT8I3lmDj5+S4/w/hh6Pj7+SHwT3I+Ljp2Sf/x6LMXx8/AX8ILgfER8/Jcdwjn/Ex3+DHwT3I+Ljp+Tz3deN4ePjr+EHwf2I+PgpOcbiCh8ffwE/CO5HxMdPSTV/Y/j4+Gv4QfBdU3z8rHz+6/HGWPDxV/Ij4DwiPj4AQCm8swYAAGCDjggAAFAKHREAAGCDjggAAFAKHREAAGCDjggAAFAKHREAAGCDjggAAFAKHREAOlK99+D6jw9+oev3/KLxAod3QkcEgCdULwDaXwN07CXtu4H2P54Ob/vQj+3qcVO8eKvRXzOniS5Avo7IQyiACFXza3+2dLgLuRg66LEVXTsXfcvYiY1RQ16kOyIPoTyEwiyM74m9+NlVRBe18GxuFu26ubpGUZ5rIN0RCw+hPITCDIyf78Zy+Ksirs3TR2F7E6oGXkdRmkK7+Fsoz4WZ0BFdj1Q8hPIQCoOxF9dFP7CURvvz9YOj/bHyuo399UtOp3H6l1KeqzK6Iz4oGx5C7ekC+BHLE1srt/5FI6n+eF1u11Xjepy1yKefEsYMwAIk6Ih9x/IQCnCBtyNanupuf3/H8vQ+Ot9Og474KpbqiDyEAvzCxb+cOK2LW+ditz/riPZnxOvH0OMvvAjfHiBPrmsw578jVj9cyzyEjl8jeCf2bXnrW8rzcflYJmn/nGmb31//sB1I/1uMOd81PW1vPITyEApz8W6ztr21/9PFkOt/2P7mH8vTEsjtP6z+V0vjhEQk+P+Ipz9fDOchFOB3LLv6r4fXi+F/dcSLB8SL33n7t1gCOU7AmIHTp2HqdAHS/HdEHkIHrxS8nF8eWC827UV5XtfaNcaJnf4trildfwrxCJsd6Y7IQ2j1A5UGA7A8Dp6Oan9+8O9FHvwtF473j+W70NrH5eu/68foYDrSHbH8XQA8hA5eOIBrLrrgxcOosdxOf3M561J/fSa0v/x0rLfDUYmLof7Ommpg+zMPoQAKXDzhdfz91/98fGlQjIuh/l7TIzyEAgBAHPk6Ig+hAAAQQaaOCAAAEAcdEQAAoBQ6IgAAwAYdEQAAoBQ6IgAAwAYdEQAAoBQ6IgAAwAYdEQAAoBQ6IgAAwAYdEQAAoBQ6IgAAwAYdEQAAoJR/y/8BSiMdEtFONGkAAAAASUVORK5CYII=" alt="" />

2. 边界填充算法(Boundary Fill Algorithm)

   边界填充算法与注入填充算法的本质其实是一样的,都是递归和搜索,区别只在于对边界的确认,也就是递归的结束条件不一样。注入填充算法没有边界的概念,只 是对联通区域内指定的颜色进行替换,而边界填充算法恰恰强调边界的存在,只要是边界内的点无论是什么颜色,都替换成指定的颜色。边界填充算法在应用上也非 常的广泛,画图软件中的“油漆桶”功能就是边界填充算法的例子。以下就是边界填充算法的一个实现:

void BoundarySeedFill(int x, int y, int new_color, int boundary_color)
{
int curColor = GetPixelColor(x, y);
if( (curColor != boundary_color)&& (curColor != new_color) )
{
SetPixelColor(x, y, new_color);
for(int i = ; i < COUNT_OF(direction_8); i++)
{
BoundarySeedFill(x + direction_8[i].x_offset,
y + direction_8[i].y_offset, new_color, boundary_color);
}
}
}

  关于direction_8的说明请参考上一节,图3就是应用本算法实现的“4-联通”和“8-联通”填充效果(其中颜色值是1的点就是指定的边界):

  aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAARcAAAEjCAIAAACXWtI4AAAM2ElEQVR4nO2b0a7jqBYFR1fz/1+MRvchLZTGjr0Xy+CNXVI9nD5dGAysOCdk/1P+KwDg8M/tIwBYHVIE4EKKAFxIEYALKQJwIUUALqQIwIUUAbi4Kfr3f/9+g4//Kv+DlaKmp9OO8fGf5FcuS1Ekvvj4T/Ir16SodhkcJT7+A/zKZSn6/ic+/hv8ygUpahKMj/8Sv3JNir7/iY//Er/CZ3T4+J1+hfMifPx+/wPfXQBwIUUALqQIwIUUAbiQIgAXUgTgQooAXDgv6jkfiJtv87Ot1wLnRU1Ppx2v7kvaC/1s6zVnPxTqizp8dVe9zc+2XuP8CvVFgr+da2mWHu9nW685+6FQXyT5TSt1lh7vZ1uvOfuhUF8k+c1cS7P0Bj/bes3ZD4X6IsmXtBf62dZrzn4ofEYn+erkvs3Ptl5z9kPhvEjyGxk/+XpN8D/w3QUAF1IE4EKKAFxIEYALKQJwIUUALqQIwOXt50W1lXrXHfOzou/cb4b1XeC8qOnptONsvqR1+N9m/JQzj2+at6/vnP1TqC+a8MIfX5KcvnO/GdZ3nF95dX3Rdu6ku+6bq+X8DjPJ+s7ZP+Xl9UVNK/WuxzVJ5felaMR6ZfMrr64vauZOumv8/Os7Z/+Ul9cXSVqfn2eL9/lSk2zrO2f/FD6jkyZL9dUlyeab5u3rO2f/lJefFzUyvulnW98J/ge+uwDgQooAXEgRgAspAnAhRQAupAjAhRQBuMw+L6qt1F6S+OrNru7PnM8M5z83nBc1PUkD7e7lRv/bjJ9aruvPnM9Iw2x+5Yb6ojwvtH1+fIqf4c+cz/guz+BXptYXxdcvs59zVNOeGCOuHNw/2fzK1Pqi0asyx084pKH+nBRFGmbzK1Pri0avCv5avrp/svmVqfVF2Vaxw081mAn+0C7U/ZPNr/AZXedfCJFWq/sz5zPSMJtfmXpe1Mj4L/fV/ZPQ/8B3FwBcSBGACykCcCFFAC6kCMCFFAG4kCIAl+z1RerF8e/1nfXNcP5zw3lR05M0UPX68VM//Lt80zxtmM2vLFBfFL8l/Ay+s77xXZ7BryxQX9TXCv8uv8MM7p9sfmWB+qKOJvg3+n0pijTM5leoL8K/zVf3Tza/kr2+KM+S41/eRN0/2fwKn9HhX+abZnCX5/Er1Bfh3+ar+yeh/4HvLgC4kCIAF1IE4EKKAFxIEYALKQJwIUUALtQX4V/pO+ub4fznhvOipidpoOr146d++Hf5pnnaMJtfeXV90cEM3jKeZ/jO+sZ3eQa/Qn0R/sV+hxncP9n8CvVF2qvOhPGs7velKNIwm1+hvqh/7ZOMf11f3T/Z/Mrb64vUhnm2YE5faqLun2x+hc/o8C/zTTO4y/P4lVfXFzVN1Ju9ffyr++r+Seh/4LsLAC6kCMCFFAG4kCIAF1IE4EKKAFxIEYAL9UX4V67XaP+B50VNT9JA1evHT/3wr/JVc7Sv7rfRfoX6ooFrny0VfX6eB2PffhvnV6gvwl9vJMH9NtqvUF+kvep0+KPHP2d+MgxG3W+j/Qr1RfPW/vaRrO6r+220X6G+aGxHebZg9/zkGZK630b7FT6jw79svUb76n4b7VeoL9L+juy+eIb7Xd3fNrnd/8B3FwBcSBGACykCcCFFAC6kCMCFFAG4kCIAF+qL1vbV+cw2/zPHn/S8qOlJGqh6/fgp3nt81cw2/zPHH2nYt59L8voide76VnHc9eeMZ/SDcfT8zBx/PEVSR9QXLe+PHsm641f3Z99+LkvUF3U8viR/9PVHj2dCiibc74iLq/uzbz+XJeqLuucuyfVXH8+6vro/+/ZzyV9fpLbqu/i4648ez+ghLf2gU/dn334ufEa3tK+a2eZ/5vgjDfv2c0leX9Q0UQdz+/VXH8/q/rbJ5f4HvrsA4EKKAFxIEYALKQJwIUUALqQIwIUUAbhQX5TLV+fnbfM5c34mnRc1PUkHW+r146dy6/qq+bb5nDk/UsPU9UXZVnGOP/qFP8/9/mqbZ36mpkgarjq/41Ylpz96JNnuN8/89O3nskR9UaolnOBPSFHC+80wP337uSxRX4T/bF9tNTpF6n4u+euLsi356g+KhPerNpyQIrUhn9El8lXzbfM5c36khqnri/Cf7TdNJHnCeOJZ5bsLAC6kCMCFFAG4kCIAF1IE4EKKAFxIEYBL9voi1VcHM9p/2/1m8535nHRe1PQkHWx19xI046dy4/y33W823zTjDReoL1p9V73nfn+1XWv+m7aRhgvUF6n+nF4yPIty3m82v8NU47dAfVHHrsqzhK+932zjkUxpPxfqi/Av99VWecbft59L/voi1c+zJK+9X6lhqvnv28+Fz+iG+m+732y+aU5KUfmKb3wW8J/qN03UzZNt/PHXPr67AOBCigBcSBGACykCcCFFAC6kCMCFFAG4zK4v6vs8XjKli4/21fGvfr/ZfGc+J50XNT2ddqz6ktaY8VO5cb5qrn6/2XzTjDe8ob5I9VffVaNfmMeN/1fbZ89/0zbScGp9ker3rXdfqzlPjBF+tvvN5neYavym1hepft/8plrCCYOZM/488zlu/vv2Z5lcX6T6CZfkhb7aKtv41ZGr+7NMri9S/Y5Zy7Mkc7qYE6FBi5Vt/vv2Z+EzuqG+aq5+v9l805yUovIVXykSQb+R8Sf7TRN1cW8fv3m/8dc+vrsA4EKKAFxIEYALKQJwIUUALqQIwIUUAbikPi/6bqWOCv90/t/gO/Mz6byo6em0Y9WXNHzJjJ9aruubZrzhA+uL8OPzf63/q+1Vft/4nfmZmqLgcFU/z/o9yc85qjlP4KCpxu+B9UX493Yh7b8Ov288kintz0J9Ef7l/uheRl9Z3Z/lefVF+PcOZnRHQx+8ffuz8Bndq3x1i6zum+akFJWv+EqRCPqNjJ/cb5qo+0fdPKPHH38t47sLAC6kCMCFFAG4kCIAF1IE4EKKAFxIEYBL6vMi/PgqdKzXir56v878TDovano67Rj/Wl/SGjN+apnHV03zyvGGC9QX4R/741L0q+1Vfl/q1Pt15mdqioLDxb/W3659x9ot50+4shq/1PVF+INSJDWR9lOH3zeeERfvm/+SvL4If0SKOlI3tJfR41dHos5/SV5fhH95ivoi1NFw0EvAuJF0z3/hM7qlfUlrzEirbL5qmleelKLyFV9pyfEv8Rv5cr9pou4H9Waz3W88q3x3AcCFFAG4kCIAF1IE4EKKAFxIEYALKQJw4bxobb+26livDL46fud+k54XNT2ddox/rS9pjRk/tRznq6Z55UHzX6gveoC/bor6xu/c77XzX6G+aGF/u/Yda3e7P+HKQ+e/UF+0tN+06li4DP6cFI2b/0J90dJ+s/bSqr3BnzP/hfqipX1J65An+EO7mDP/hc/olvYlrTEjrUb7qmleedD8F86LlvYbGX/+en3guwsALqQIwIUUAbiQIgAXUgTgQooAXEgRgAvnRWv7tZW6aov6Oeef7y4s7EvaA/yc81+oL3qAr+7C1f0881+hvmhhf7v20qot5+ec/0J90dJ+00pdteX8nPNfqC9a2m/WXlq1Ff2c81+oL1ral7QH+Dnnv/AZ3dK+pD3Azzn/hfOipf1Gfryfbf4rfHcBwIUUAbiQIgAXUgTgQooAXEgRgAspAnDhvAgfv9//wHcX8PE7/Qr1Rfj4nX6F+iJ8/E6/Qn0RPn6nX6G+CB+/069QX4SP3+lX+IwOH7/Tr3BehI/f73/guwsALqQIwIUUAbiQIgAXUgTgQooAXEgRgAspAnAhRQAupAjAhRQBuJAiABdSpLH7DcX41xal61942eMLXt7R23h1ipov8O6y2yT+S+f6EVO6/nGKyFI3b09R88/TnRR/FkWeKrvZCDY/GKr6zNntFOKQop//jDQpv7dgE4PdR8SvJpFny3GKjoMnPR7hFFL054fT90JSDDp+Ll+7X2p7EOxf4z/1QYIU/fXD9r8O/OPX8q28vez2ebX7+8jPkXdlvKMbBCn680Pkjc2vhGyF72vu/u/udcx3dLtBPb3f7e9vX5flIEV//bD9r93fRLbabsCOk3Cc0oPEBgd2/JwM3hdsIUV//bD9r93fHDw0fjnNpXafeL/+TPpucjrC4LNo24QIdUOK/vwQf0cXfD4c7/uDP5OahqdvL39dPHi/vwYDcUjRyW+2QjxFpz2ehrD83uLHwzju/fitI6iQop0fTt8U/dp85p8x27+dDoJ0HIDdIP16zG57BIn3pujghb/83oXNz9KzKPKH0K68O6rjwJ8+nXZv+eCCcAAp+rn1I2/eDv6airxdPH0WHQ81wu6NH9w7KergpSmKvJc7/SNn+3tzl/+K2YidffqwhThvT9HpL6/t4tiZMCoYwUtTBHAhpAjAhRQBuJAiABdSBODyf4hPZKO5jQxWAAAAAElFTkSuQmCC" alt="" />aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAisAAAEmCAIAAAAsukc8AAAVWklEQVR4nO2d3c7jOo5FG4N+/ycO5sxFA2mPkvgTtyxyS1rAuqiqXrJ+KJo+jdj61z///PP63xcAAEAy/6ICAQBACVQgAACogQoEAAA1UIEAAKAGKhAAANRABQIAgBqoQAAAUAMVCAAAaqACAQBADUMV6N//8+8r+PhH+TJuE8HHz/Sv6BWo6ezPvvHxd/Jl3CaCj5/pNzxTgf7dUf3w8XfyZdwmgo+f6Tc8UIHevXYOFB9/A1/GbSL4+Jl+wzMV6PpXfPwTfBm3ieDjZ/oNoxXo2n3PQPHx9/Bl3CaCj5/pNzxQga5/xcc/xJdxmwg+fqbfwG/h8PEVX8ZtIvj4mX4D7wPh44u+jNtE8PEz/St8EwEAAGqgAgEAQA1UIAAAqIEKBAAANVCBAACgBioQAADUQAUCAIAaeB8o/DP26A/ez/Hd4pX5WkN0Sa0mQuLU+m7xWuN9oKazP/te3Q9pB/pu8crZDwJuEyFxan23eCUnDucDxfzoxjrNd4vXPF/GbSIkjoPvFq95fgPnA8V2THR9z/Hd4pWzHwTcJkLi1Ppu8UpOHM4H6vWbVtFV2t53i1fOfhBwmwiJU+u7xSs5cTgfqNdvlju0Sif4bvHK2Q8CbhMhcWp9t3glJw7nA/X6Ie1A3y1eOftBwG0iJE6t7xav5MTht3CxHeOzcd18t3jl7AcBt4mQOLW+W7ySE4f3gXr9RsY3j1eCL+M2ERKn0HeLV4J/hW8iAABADVQgAACogQoEAAA1UIEAAKAGKhAAANRABQIAgBqoQAAAUMPR7wO9W0VnrS3Uon7ItIpv5msNIdwmQuLM8EmcHs79JkJIk/1reFb0ZbM8vjn7R8BtIiTODJ/E6eT084GiG0VLvHm9zPO1K7vFd54v4zYREudZn8QJBfrc84E+ly80a2GJlvM10yS+OftHwG0iJM7jvmaaxDc5cc49H6hpFZ11yOxp5ebLpkl8c/aPgNtESJxnfdk0iW9y4px7PlCzfKFZR9fnOrBV/JH5OsQ3Z/8IuE2ExCFx8vfPm3PPBwppsp/Ty+zbQb/pE9+c/SPgNhESZ4ZP4nTCb+FIpClmeXxz9o+A20RInBk+idPJue8DNfLj/teGC/nCfE/zZdwmQuI86JM4nfH9D3wTAQAAaqACAQBADVQgAACogQoEAAA1UIEAAKAGKhAAANRABQIAgBpS3wd6t4r2YuW/J36IP2893V5TsH0faHYgcvyX2cae7ZM4PeR9E0EIoaF/Xe4T/HnrGd0/br4MiXOCT+J0kn0+UHShfXzPUc3zc0bStF3IlyFx9vZJnNDGyDsf6HO40eUu95spb+9PXc/o/nHzZUic7f2p6+mWCIOJk3c+0OzAzPavZk+r1f209ezcP26+DImzt5+2niaJMJg4eecDzQ7MbP863+vEd/Uz17OnoZsvQ+KslQgkztTEyTsfaHZgcnzPUc3e7vOu3L9/3HwZEucEn8TphN/CkUgWV+7c6D6+DIlzgk/idJL3PlAjL+d/bbixn7Ceq/syVhubxCFxkv0rfBMBAABqoAIBAEANVCAAAKiBCgQAADVQgQAAoAYqEAAA1EAFAgCAGhY4H+jdEf4SvvaCiMNrCp7vAwkLqwUOv9Y/M3Hcv4lwnR6+vy+bfzZ082VIHPxfsmCWJ8Jg4vieD6S1wq/ytSs3bRfyZUgc/PErN20X8huszwdqusA39zWzc/+4+TIkDv5IfN0SYTBxfM8Hupo9rfBrfdns3D9uvgyJg/9IfE0SYTBxfM8Hul7/2hG+pz8S356Gbr4MiYP/VHx7Grr5De7nA2mt8Kt8IZE6G7r5MiQO/rjpkwiDibPAb+GEVvhVvmx2bnQfX4bEwX/QLE+EwcTxPR/oa0N8W1+I7+q+DImDPxLf1f0rfBMBAABqoAIBAEANVCAAAKiBCgQAADVQgQAAoAYqEAAA1EAFAgCAGjgfCP9hX3thxeE1Bc/3gYSF1QKHX+ufmTgLfBNBSFT8Kl82/2zo5suQOPi/ZMEsT4TBxOF8IPxnfO3KTduFfBkSB3/8yk3bhfwGzgfCf8zXzM794+bLkDj4I/F1S4TBxOF8IPxnfNns3D9uvgyJg/9IfE0SYTBxOB8I/xl/JL49Dd18GRIH/6n49jR08xs4Hwj/SV9IpM6Gbr4MiYM/bvokwmDiLPBbOKEVfpUvm50b3ceXIXHwHzTLE2EwcTgfCP8ZX4jv6r4MiYM/Et/V/St8EwEAAGqgAgEAQA1UIAAAqIEKBAAANVCBAACgBioQAADUQAUCAIAaOB8I/+F4zfOdX2uITpnE2d4ncXpY4JsIQqLiP+X7pHR0v832ZUicE3wSpxPOB8J3H8nVb9oW+jIkzt6+z0iuftO20G/gfCD8x+I11Y/ut9m+DImzvR+N11TfPHE4Hwj/mXjN9qP7bbYvQ+Ls7UfN2b554nA+EP4z8ZrtR/fbbF+GxNnbj8Zrtm+eOJwPhL/SSPr322xfhsQ5wXcbiW3iLPBbOKtwnubbjqQzMeb5MiTOCb7tSNwSh/OB8J+J12z/s0m5L0PibOyTOD2L+YZvIgAAQA1UIAAAqIEKBAAANVCBAACgBioQAADUQAUCAIAaqEAAAFAD5wMt70fX0239541/j/eBbAO3up+z8Wb4meP3fR+o6Sw0VqEjYflO8Gen9Lrjj+5PbT8LkDgOfs7G62kV9TPH39NwMHE4H2hVf/ZIVh+/tj/7fRkSp9bP33gz/G0Sh/OBFvaj6+m2/lPHH92f2n4WIHHK/eh6Cv7sXrZJHM4HWtWPmm7rnzb+zv2p7WcBEqfWj5qaP7uLbRKH84FW9aPr6bb+mePvaajtZwESZ+/EWd1PThzOB1rbnz2Sdccf3Z/afhYgcRz8qSNJyMptEmeB38JNXe7VfSpQp9mZSIMLNWNgnoFb3c+5ck8r7fa9TeJwPtCqfnQ93dY/YfyzfZmlA7e6P3vjre5/Nnncv8I3EQAAoAYqEAAA1EAFAgCAGqhAAABQAxUIAABqoAIBAEANVCAAAKiB84Hs/Oj6nLae89bH830geeJugZvt52yMFf3M9cl7H6jpLPTuktCRsBwr+rNT2m2+Puuj7WcBEmeGn7Mxelq5+ZnrI3TE+UAu/uyRuM3XbX2i+1mGxHnWz98Ytf6vtj7rE5oC5wMZ+dH1OW09p66Ptp8FSJzH/ej6CH5OLwnbe96VtcThfCAXP2qetp5p6xO990UhcZ71o6bmJ3QR8qP3etvE4XwgFz+6PqetZ+b6CB1Fh0TirLIxPP1oK9vE4XwgL99t47r5CYk0srDzOjot0Fr4Jo3EZ5qG6zOYOAv8Fm7q8rn5VCCTK8+uQNGOTgt01M+5ck8rNz955fMq0LuzpgZ2ytEHEKEmr+VH1+e09UxYH209BQj0g/7sjeHmR1fSPHH4JgIAANRABQIAgBqoQAAAUAMVCAAAaqACAQBADVQgAACogQoEAAA1LHA+kPBmRvRn6VP90+br5msv0Pi8DyRMRPPXDVzUN3mTydYfWc+894GazkLvLsm9hJbDwT9tvm6+bM4rQiTOjPFrV+5pdZo/aEYD53s+kFy3TZ4mTpuvm69duWnbH4hoyPo7Om0j5Yzk889V/q+2teNPSxzr84GifjOkcv+0+br5mqndwYUQkzhV803rZV0/LXF8zwcaWbL+Uj/PP22+br5sRu+VUUicZ8ev+QldCA8BbuMJmVri+J4PpC1EQ6F/2nzd/JH1FAIXDTGJUzVfT1+LmsP4BxPH/Xyg2YHMCc8583XzhUQaCcS8jk7bSFNH4jNNrWHCeNISZ8PfwiX0YpJIhvN182VzdgWKdnTaRsq5ck+r0/xBM68CvTtramCn/Lj/tWGhf9p83XxhPbX1FyBxCufr5kdX0nz80cThmwgAAFADFQgAAGqgAgEAQA1UIAAAqIEKBAAANVCBAACgBioQAADUkHo+kPyagjYwEz86/tXn6+ZrL8T4vA8kD2z1jTQvcUzefLL1R9Yz732gprM/+476Ie3rcjj4s1Pabb5uvmzOK0IkzrOBi/pXs6fVaf6gGQ1c9vlAUV/biPOeDvr92SNxm6+br125adsfiGjI+jsicWYH+ln/V9uq8Wh+WuLknQ8U9YWQN12U+9Hxrz5fN18ztTu4EGIS56nxC35OL+v6aYmTdz5Q1B9Zsp5Ws/2oufp83XzZjN4ro5A4zwZO82d3IdyLrfy0xMk7HyjqawvRUOgLUV96vm7+yHoKgYuGmMR5avyevhYFn/GnJU7e+UBRX1s4z/DMG4nbfN18IZFGAjGjIxLncT8nK+cFK2H8aYmz4W/hEiJkkkiG83XzZXN2BerviMSZd+WeVqf5g2ZeBXp31tTAp/xGjj7gCDX8WT86/tXn6+YL66mtvwCJ8+D43fzoyriNPzlx+CYCAADUQAUCAIAaqEAAAFADFQgAAGqgAgEAQA1UIAAAqIEKBAAANfi+D3RtFR0Vfk8gDvG1F2LWfR9ImDh+//qf4I+sT977QE1nf/Yd9UMafrSJsL1W9GVzXhEicdbyr2ZPq9X9QTMaiH3OB8J36MXH167ctO1f2GgI+jsicRz8zz8/5f9q+5SvjT8tcbY6Hwg/FLLtfc2MZmAUEmdF33NU8/y0xNnnfCD8frOn1eq+bEaLXBQSZ0V/dhfRe7dwrxeuHzK1xNnnfCD8/nj1bN/V/ZH1EQIRDRmJg5/ZS86NRehot/OB8B168fGFRBpZ2BkdkTjlfk5WzutIGE9a4vBbuLN8z1H5VKDBhZ3REYlT60dvr6v7g2ZeBXp31tTAp/xGxh/0vzbc2BfWR1tPARIH/1eT6P6Jbp7Z448mDt9EAACAGqhAAABQAxUIAABqoAIBAEANVCAAAKiBCgQAADVQgQAAoAbf94Hw+6OgBW5RPzrf0JXl1xqE9ffZSKf571ZCvFb0o/MdWZ+894Gazv7sG/9ZP6R9NhG2l4M/r7Zp6y/gtpFO86PxvZo9rdz8qDl45WhH7ucD4d/72saKbi8HP2ck/esv47mRTvNHNoYW66f86HjME8f3fCD8nkCG4t10sZwfna925WgGRnHbSKf50Y0x0srHt00c3/OB8J9NpKvZ08rNj5rylUPrL+C2kU7zm1ZC4Prleb42nhkXH0wc3/OB8J9NpOv1e7a7mx+d78j6CB1Fh+SzkU7zoxtD82f3Mnv8aYnjez4Q/oxE0lr5+AmJNLKwMzrCL08ceTNM2q7CeGwTh9/CreqHtMFWPn7alWdXoP6O8GsTJ3p7dfOj5uCV8yrQu7OmBuLn+I3cH/VoExM/Ol9hfbT1FLDaSKf5yRspuh+ik3WbbzRx+CYCAADUQAUCAIAaqEAAAFADFQgAAGqgAgEAQA1UIAAAqIEKBAAANfA+0ML+u5UWOBM/Ov7QldNeaxDW32cjnea/WwnxcvCj4x+Zr+/7QE1nf/aN/6wf0j6bCNtxhj+vtuWsv4DbRjrNj8b3ava0mu1HzcErz04czgda29c2YnQ7zvBzRjJv/WU8N9Jp/shGcvC3SRzOB1rV/wx/NGTlfnT82pWnrr+A20Y6zW9aabEr97dJHM4HWtVvWoXMnlaz/agpX3nq+gu4baTT/KaVEDgHf5vE4XygVf0m/KF4XTuq8qPjH5nvvPUXcNtIp/nXVtGoneAnJw7nA63qh7TBVrO3+7wrz15/AbeNdJovxNcnXxK6SE4cfgu3qh/SBlutW4Fmr7+A20Y6zY/GN3p7ne1HzcErz04c3gda1W/k/qhHm0zyo+MX5jvbl3GbyFH+7I23up8Qryt8EwEAAGqgAgEAQA1UIAAAqIEKBAAANVCBAACgBioQAADUQAUCAIAaeB9oYf/dKhq1RX3P9Rdwm8hp/rtVNGqL+p7r/x/4JsKqfkjbwPdcfwG3iZzma/Fd1/dc/zecD7S2H92Iq/s+6y/jNpEzfbeNfWzicD7Qqv5n+ENRW873XH8Bt4mc5jetolFbzvdc/zecD7Sq37SKRm0533P9BdwmcprftIpGbTnfc/3fcD7Qqn4T/lDUVvQ911/AbSKn+ddW0ait6Huu/xvOB1rVD2kb+J7rL+A2kdN8Lb7r+p7r/4bfwq3qh7QNfM/1F3CbyGm+Ft91fc/1f8P7QKv6jby977b+I7hN5CjfbWMfnjh8EwEAAGqgAgEAQA1UIAAAqIEKBAAANVCBAACgBioQAADUQAUCAIAaeB8IH1/0Zdwmgo+f6V/hmwj4+Iov4zYRfPxMv4HzgfDxFV/GbSL4+Jl+A+cD4eMrvozbRPDxM/0GzgfCx1d8GbeJ4ONn+g2cD4SPr/gybhPBx8/0GzgfCB9f8WXcJoKPn+k38Fs4fHzFl3GbCD5+pt/A+0D4+KIv4zYRfPxM/wrfRAAAgBqoQAAAUAMVCAAAaqACAQBADVQgAACogQoEAAA1UIEAAKAGKhAAANRABQIAgBqoQAAAUAMVCAAWoPncy/1fhQuGrjOiTf3g03JQgQDAi+Y7Y++vjV3v3Z+fIHv/9Wvzz/v+YHmQi9DNx9N+jXzjokUF+i88ZAGY0BSbzz/3VJQb+dVRsa63/nvnpk50Vr7OWe/HoRWIh6xzHrLAjc7PLd/8OZREN7mgja1Huy9moVZ7p+ehFejFQ9YxD1lgRef9tDMdfmXEvfn10bP/pt80vJ/F6yPRbno5MD23qkChRwYesg55yAIf+pPr5v7bkxqff75/UOt/jLsvG78u8nUYXzs9LT33qUDCNuUhq3+5AAbpeUL6lD/9mxt389f7dLvPmtDjY4/89S7RuQIbc3QFerYtD1kAN0QrUM9T1J/XfzA9o4+qfw6DCvSiAnW25SELYISb//j+mhd/Oje7XatA/c9k94991wveTL9/gns/Ke5TgV48ZHV02jNNgMfp35Z/+j3pKadPzyD77zOfxebXP3423LLefLJVBXr9+L+weMg6+SELHIhus89y8vk/3TS5/8fPKw+mZ89E/vzH5n/tKVQbsFUFkncGD1kAafTs6l8PizfNf1Wgmweym2v+2UvPRK4D6FyBr0+fG+fpPhWoc5t+CjxklccOjmLkAfFm096k532u3dM5sK+9hIZ0fxfa9ZHx0ArEQ1bzh/12NhjS8/j1tdXnn4X/7hd6uXGif339/0T7fDy972twdrYcWoFevzccD1nloQS4clN1bh7+OtPt65Vf36rCr3vC58W/to1WlEMycZ8K9FKfsF48ZP01KoBCbp6oHrz+/b/np8YhybhVBZLhIQsAIB8q0OvFQxYAQAVUIAAAqIEKBAAANVCBAACgBioQAADUQAUCAIAaqEAAAFADFQgAAGr4P8P6noLVyP/DAAAAAElFTkSuQmCC" alt="" />

3. 扫描线种子填充算法(ScanLineSeed Fill Algorithm)

  前面介绍的1与2,介绍的两种种子填充算法的优点是非常简单,缺点是使用了递归算法,这不但 需要大量栈空间来存储相邻的点,而且效率不高。为了减少算法中的递归调用,节省栈空间的使用,人们提出了很多改进算法,其中一种就是扫描线种子填充算法。

  扫描线种子填充算法不再采用递归的方式处理“4-联通”和“8-联通”的相邻点,而是通过沿水平扫描线填充像素段,一段一段地来处理“4-联通”和“8- 联通”的相邻点。这样算法处理过程中就只需要将每个水平像素段的起始点位置压入一个特殊的栈,而不需要象递归算法那样将当前位置周围尚未处理的所有相邻点 都压入堆栈,从而可以节省堆栈空间。应该说,扫描线填充算法只是一种避免递归,提高效率的思想,前面提到的注入填充算法和边界填充算法都可以改进成扫描线 填充算法,下面介绍的就是结合了边界填充算法的扫描线种子填充算法。

   扫描线种子填充算法的基本过程如下:当给定种子点(x, y)时,首先分别向左和向右两个方向填充种子点所在扫描线上的位于给定区域的一个区段,同时记下这个区段的范围[xLeft, xRight],然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段,并依次保存下来。反复这个过程,直到填充结束。

  扫描线种子填充算法可由下列四个步骤实现:

  (1) 初始化一个空的栈用于存放种子点,将种子点(x, y)入栈;

  (2)判断栈是否为空,如果栈为空则结束算法,否则取出栈顶元素作为当前扫描线的种子点(x, y),y是当前的扫描线;

  (3) 从种子点(x, y)出发,沿当前扫描线向左、右两个方向填充,直到边界。分别标记区段的左、右端点坐标为xLeft和xRight;

  (4)分别检查与当前扫描线相邻的y - 1和y + 1两条扫描线在区间[xLeft, xRight]中的像素,从xLeft开始向xRight方向搜索,若存在非边界且未填充的像素点,则找出这些相邻的像素点中最右边的一个,并将其作为种 子点压入栈中,然后返回第(2)步;

  这个算法中最关键的是第(4)步,就是从当前扫描线的上一条扫描线和下一条扫描线中寻找新 的种子点。这里比较难理解的一点就是为什么只是检查新扫描线上区间[xLeft, xRight]中的像素?如果新扫描线的实际范围比这个区间大(而且不连续)怎么处理?我查了很多计算机图形学的书籍和论文,好像都没有对此做过特殊说 明,这使得很多人在学习这门课程时对此有挥之不去的疑惑。本着“毁人”不倦的思想,本文就罗嗦解释一下,希望能解除大家的疑惑。

     如果新扫描线上实际点的区间比当前扫描线的[xLeft, xRight]区间大,而且是连续的情况下,算法的第(3)步就处理了这种情况。如下图所示:

  CGA填充算法之种子填充算法

  假设当前处理的扫描线是黄色点所在的第7行,则经过第3步处理后可以得到一个区间 [6,10]。然后第4步操作,从相邻的第6行和第8行两条扫描线的第6列开始向右搜索,确定红色的两个点分别是第6行和第8行的种子点,于是按照顺序将 (6, 10)和(8, 10)两个种子点入栈。接下来的循环会处理(8, 10)这个种子点,根据算法第3步说明,会从(8, 10)开始向左和向右填充,由于中间没有边界点,因此填充会直到遇到边界为止,所以尽管第8行实际区域比第7行的区间[6,10]大,但是仍然得到了正确 的填充。

     如果新扫描线上实际点的区间比当前扫描线的[xLeft, xRight]区间大,而且中间有边界点的情况,算法又是怎么处理呢?算法描述中虽然没有明确对这种情况的处理方法,但是第4步确定上、下相邻扫描线的种 子点的方法,以及靠右取点的原则,实际上暗含了从相邻扫描线绕过障碍点的方法。下面以下图为例说明:

  CGA填充算法之种子填充算法

  算法第3步处理完第5行后,确定了区间[7, 9],相邻的第4行虽然实际范围比区间[7, 9]大,但是因为被(4, 6)这个边界点阻碍,使得在确定种子点(4, 9)后向左填充只能填充右边的第7列到第10列之间的区域,而左边的第3列到第5列之间的区域没有填充。虽然作为第5行的相邻行,第一次对第4行的扫描根 据靠右原则只确定了(4, 9)一个种子点。但是对第3行处理完后,第4行的左边部分作为第3行下边的相邻行,再次得到扫描的机会。第3行的区间是[3, 9],向左跨过了第6列这个障碍点,第2次扫描第4行的时候就从第3列开始,向右找,可以确定种子点(4, 5)。这样第4行就有了两个种子点,就可以被完整地填充了。

   由此可见,对于有障碍点的行,通过相邻边的关系,可以跨越障碍点,通过多次扫描得到完整的填充,算法已经隐含了对这种情况的处理。

4. 根据本节总结的四个步骤实现并运行通过程序片段如下:

 //扫描线绘制算法,提高填充效率,种子是基于鼠标点击的像素位置
inline void CScanLineSeedFill::scanLineSeedFill(CPoint clickPos, GLfloat (&frameWork)[][] )
{
//首先判定当前点是否有效,无效直接返回
assert(isInialDone);
//鼠标的点击点必须在外围框之内
GLdouble winFramePos[][];
getViewPortCoordPos(frameWork, winFramePos);
int frameLeft = (int)winFramePos[][];
int frameDown = (int)winFramePos[][];
int frameRight = (int)winFramePos[][];
int frameUp = (int)winFramePos[][];
//对绘制的范围进行限定:点击框架之外,或者原点无效
//计算click位置在视口中的坐标
PointInt clickViewPos(clickPos.x, (this->winHigh) - (clickPos.y));
if ((clickPos.x== && clickPos.y==) ||!(clickViewPos.x>frameLeft && clickViewPos.x<frameRight && clickViewPos.y>frameDown && clickViewPos.y<frameUp))
return ; GLubyte readColor[];
glReadPixels(clickViewPos.x, clickViewPos.y, , , GL_RGB, GL_UNSIGNED_BYTE, readColor);
if (sameColor(readColor, boundryColor) || sameColor(readColor, fillColor))//如果种子是边界点或填充颜色则直接退出
return; glColor3ubv(fillColor);
//一开始非边界的种子,必然可以绘制扫描描线
//PointInt startPoint;
//startPoint.x = clickViewPos.x;
//startPoint.y = clickViewPos.y;
seedsStack.push(clickViewPos);
//pixelStack.push(point);
float viewPosition[];
double worldPosition[];//世界坐标系 int saveX;
int xRight,xLeft;
int x,y;
//如果栈不为空
while(!seedsStack.empty())
{
//获取最顶端的元素
PointInt tempPoint=seedsStack.top();
//删除最顶端的元素
seedsStack.pop(); saveX = tempPoint.x;//绘制点的X坐标,从当前点向左向右扫描
x = tempPoint.x;
y = tempPoint.y;
glReadPixels(x, y, , , GL_RGB, GL_UNSIGNED_BYTE, &readColor);
//向右:如果没有到达右边界,就填充
while(!sameColor(readColor, boundryColor))
{
x=x+;
glReadPixels(x, y, , ,GL_RGB,GL_UNSIGNED_BYTE, &readColor);
}
xRight=x-;
x=saveX-;
glReadPixels(x, y, , , GL_RGB, GL_UNSIGNED_BYTE, &readColor); //向左:如果没有到达左边界,就填充
while(!sameColor(readColor, boundryColor))
{
x=x-;
glReadPixels(x, y, , , GL_RGB,GL_UNSIGNED_BYTE, &readColor);
}
//保存左端点
xLeft=x+; //把当前像素点还原为世界坐标系中的点然后再绘制
glBegin(GL_LINES);
viewPosition[] = xLeft;
viewPosition[] = y;
viewPosition[] = ;
getWorldCoordPos(viewPosition, worldPosition);
glVertex3f(worldPosition[], worldPosition[], worldPosition[]);
viewPosition[] = xRight;
getWorldCoordPos(viewPosition, worldPosition);
glVertex3f(worldPosition[], worldPosition[], worldPosition[]);
glEnd(); //从右边的点开始
x=xRight;
//检查上端的扫描线
searchNewLineSeed(seedsStack, xLeft, xRight, y+);
searchNewLineSeed(seedsStack, xLeft, xRight, y-);
}
 //查找新扫描线的种子
inline void CScanLineSeedFill::searchNewLineSeed(stack<PointInt>& stk, int xLeft, int xRight, int y)
{
unsigned char readColor[];
int xt = xLeft;
bool findNewSeed = false;
while(xt <= xRight)
{
findNewSeed = false;
glReadPixels(xt, y, , , GL_RGB, GL_UNSIGNED_BYTE, readColor);
while(!sameColor(readColor, boundryColor) && !sameColor(readColor, fillColor) && (xt < xRight))
{
findNewSeed = true;
xt++;
glReadPixels(xt, y, , , GL_RGB, GL_UNSIGNED_BYTE, &readColor);
} if(findNewSeed)
{
if(!sameColor(readColor, boundryColor) && !sameColor(readColor, fillColor) && (xt == xRight))//到达边界
{
stk.push(PointInt(xt, y));
}
else
stk.push(PointInt(xt - , y));//不到边界
} /*向右跳过内部的无效点(边界点), 即与边界相同颜色的点
(处理区间右端有障碍点的情况)*/
//xt或者在障碍点上,或者为右边端点
int tag = xt;
while((sameColor(readColor, boundryColor) || sameColor(readColor, fillColor)) && (xt < xRight))
{
xt++;
glReadPixels(xt, y, , , GL_RGB, GL_UNSIGNED_BYTE, &readColor);
}
if (tag == xt)//如果xt>= xRight or 都不为边界或已经填充则右移动
xt += ; }
}

  程序运行结果如下:

  aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAjUAAAFMCAIAAAC8stpbAAARbklEQVR4nO3dv49m1XnA8dPSjUSbaLZKu3EZGvsf8Jou3ZCUcbTQUIJnpbewRGNcoti7cRdkDEg0LsBeuwgFWGwaqAw0KFEKNgUSQrb3TfGul3fPzo87M/fe85znfI4+HbB77/s+5/3qDHdmyuatfwOAaErzKwCAJ+kTABHpEwAR6RMAEekTABHpEwAR6RMAEekTABHpEwAR6RMAEekTABHpEwAR6RMAEekTABHpEwAR6RMAEekTABHpEwAR6RMAEekTABHpEwAR6RMAEekTABHpEwAR6RMAEekTABHpEwAR6RMAEekTABHpEwAR6RMAEekTABHpEwAR6RMAEekTABHpEwAR6RMAEekTABHpEwAR6RMAEekTABHpEwAR6RMAEekTABHpEwAR6RMAEekTABHpEwAR6RMAEekTABHpEwAR6RMAEekTABHpEwAR6RMAEekTABHpEwAR6RMAEekTABHpEwAR6RO1UraQWPMtxkT6RM0GJjHj3RF9omYDk5jx7og+UbOBScx4d0SfqNnAJGa8O6JP1GxgEjPeHdEnajYwiRnvjugTNRuYxIx3R/SJmg1MYsa7I/pEzQYmMePdEX2iZgOTmPHuiD5Rs4FJzHh3RJ+o2cAkZrw7ok/UbGASM94d0SdqNjCJGe+O6BM1G5jEjHdH9ImaDUxixrsj+kTNBiYx490RfaJmA5OY8e6IPlGzgUnMeHdEn6jZwCRmvDuiT9RsYBIz3h3RJ2o2MIkZ747oEzUbmMSMd0f0iZoNTGLGuyP6RM0GJjHj3RF9omYDk5jx7og+UbOBScx4d0SfqNnAJGa8O6JP1GxgEjPeHdEnajYwiRnvjugTNRuYxIx3R/SJmg1MYsa7I/pEzQYmMePdEX2iZgOTmPHuiD5Rs4FJzHh3RJ+o2cAkZrw7ok/UbGASM94d0SdqNjCJGe+O6BM1G5jEjHdH9ImaDUxixrsj+kTNBiYx490RfaJmA5OY8e6IPlGzgUnMeHdEn6jZwCRmvDuiT9RsYBIz3h3RJ2o2MIkZ747oEzUbmMSMd0f0iZoNTGLGuyP6RM0GJjHj3RF9omYDk5jx7og+UbOBScx4d0SfqNnAJGa8O6JP1GxgEjPeHdEnajYwiRnvjugTNRuYxIx3R/SJmg1MYsa7I/pEzQYmMePdEX2iZgOTmPHuiD5Rs4FJzHh3RJ+o2cAkZrw7ok/UbGASM94d0SdqNjCJGe+O6BM1G5jEjHdH9ImaDUxixrsj+kTNBiYx490RfaJmA5OY8e6IPlGzgUnMeHdEn6jZwCRmvDuiT9RsYBIz3h3RJ2o2MIkZ747oEzUbmMSMd0f0iZoNTGLGuyP6RM0GJjHj3RF9omYDk5jx7og+UbOBScx4d0SfqNnAJGa8O6JP1GxgEjPeHdEnajYwiRnvjugTNRuYxIx3R/SJmg1MYsa7I/pEzQYmMePdEX2iZgOTmPHuiD5Rs4FJzHh3RJ+o2cAdKWW7juZ3OuMr1vwamEifqNnAvShlW5Zfm1wjkele0tMnajZwF9aJkz7RkD5Rs4GD++vX3FZam1wjkele0tMnajZwZGuWSZ9oS5+o2cBhrR8nfaIhfaJmAwe08tf09IkI9ImaDRxNqzLpE23pEzUbOJS2cdInGtInajZwEA2/pqdPRKBP1GzgCCKUabc2uUYi072kp0/UbODm4sSp6BPt6BM1G7jtix8qTkWfaEefqNnADV/51jE6YSUbiUz3kp4+UbOBW73srUt08ko2EpnuJT19omYDr/+Ch41T0Sfa0SdqNvDKr3brAJ2zko1EpntJT5+ozbiBk/1quyVe6tb1OX/NOxLNZbqX9PSJ2rx9mvcPTCP41/T2V7J3MNO9pKdP1OY+P5WNg9RJL0sva96RaC7TvaSnT9Rm71PKj7lZXpMuVrI3LtO9pKdP1BbqUxn+INXR1/T217wj0Vyme0lPn6gt16eUn3dXeSm6WMner0z3kp4+UVu6T2W8g1S/cSrZ+/TKO6/uNL8wnqRP1FboU8oPvtNfgY7jVNK9TY/u5bX3Xv73372oTJHpE7XV+lSyH6R6L9NuzTsSzR0cfPkf//mvr7//Q2WKT5+ordmnlJ+AF7r3+CvNu/Paey/f/fjGjRtvK1Mv9Ina+n0quQ5SCb6mt7/mHYn1vfLOq29/+M/3Pv+Htz/8p97vZTT6RK1Jn3J8FF7iluOvft+U1957+aPPn/nki+/84vcv7r9BzS+MifSJWsM+lc4PUvniVDrs0+7A9N/3//be58/89Nc/fvI9an6FTKRP1Nr2qdPPxGRf09tfHb0Xv/j9ix99/szX3zx19+PvP1mmR+9U8+tkIn2iFqFPpauDVNYy7da8I7GEV9559df/9Y9ffvX0/a+evvvx989+/CH4vbBPn6gF6VMvH46541RivwW7A9N2W+5/9fTu8Ycp71fzy2YifaIWqk8l8EEq8df09te8IzGLRwem7bZ89r9/t//4w5R3rfn1M5E+UYvWp5ifkiOUabdCvfKPDkzbbbn3+TOvvffyJd645nfBRPpELWafSqSD1DhxKjH6tH9g+vqbp058MG/6e9d8fphIn6iF7VOEj8tBvqa3v9q+4PsHpt2DeVf86Q/61BF9oha8T6XdQWq0Mu3WvCMx0f6B6UKPP6w53ixNn6jF71OTz80x41RWf533D0y7xx9ef/9fYo43S9Mnar30qax1kBrwa3r7a96ROE11YNpuyydf/P2FHsxbf7xZmj5R66hPK3yAjlym3Vr05d08cWDaPZh36ccf1hxvlqZP1LrrU1nsICVOZbE+PXlgmuXxhzXHm6XpE7Ue+zT7J+ngX9PbX/OOxOakA9Pu8Yd1fi2TPnVEn6j126cy00FKmfbXXCPx5IFpuy3/839/M9eDeeuPN0vTJ2pd9+nqH6niVK2rj8Tr7//wky++s5+lS/xcooDjzdL0iVqCPpVLHaR8Te/EdemR+Omvf3z34xvVgWnpxx/WHG+Wpk/UcvTpop+tzS817LrESJx4YDr71zL1ON4sTZ+oZepTmXaQinCdYdf0kTjtwDTl1zL1ON4sTZ+oJevTbp12X76md+6aMhInHpjm/blEAcebpekTtZR9KicdpEJdXth1xkicdmBq+PjDmuPN0vSJWtY+7dajGwx4bTHXiSNx2oHp0r+WqcfxZmn6NKiyPfWtz92n8u1Bypq09kfijAPTFX8t03qTr0/90KdBjdwn60Jr9z6ecWBa5+cSzTiTza+BifRpUPpkTVmHh+Xuxzc+/fTaiWUK+PjDlJlsfg1MpE+D0ifr7PWDH5Q33zyhSQv9Wqb1Jl+f+qFPg9In68R1eFh+9KPy6aenlmmhX8u03uTrUz/0aVD6ZFXr7ANT859LNONMNr8GJtKnQemTtVvnHpi+/uap4+PjXh5/mDKTza+BifRpUPpkHR2dc2D67LPy3HPllXdezfSZnule0tOnQenTsOvwsPzkJ+XLL8/8Ut698txzD//9eUeiuUz3kp4+DUqfBlxHR+U3vzkrS9tt+e1vy3e/+9h/Ne9INJfpXtLTp0Hp0zhryoFpuy137pTDwxP+83lHorlM95KePg1Kn0ZYUw5M9++X4+OTy7Rb845Ec5nuJT19GpQ+JV4TD0yffVaOj8vBwTl/2rwj0Vyme0lPnwalTynXlAPTowfzJq55R6K5TPeSnj4NSp8yrYkHphMffzh3zTsSzWW6l/T0aVD6lGNNPDDtHn+4fv0yf8W8I9FcpntJT58GpU9dr+kHpvv3T30wb+KadySay3Qv6enToPSp0zX9wLR7MO/cxx/OXfOORHOZ7iU9fRqUPvW1ph+YLvr4w7lr3pFoLtO9pKdPg9KnXtb0A9Pu8Ydnn535AuYdieYy3Ut6+jQofQq+LnRg2m7LW29d+MG8iWvekWgu072kp0+D0qeY6+DgYgem7ek/l2iuNe9INJfpXtLTp0HpU7R1/Xq5ffsCB6a5Hn84d807Es1lupf09GlQ+hRk7Q5MH310gQPT7vGHFcq0W/OORHOZ7iU9fRqUPjVfFz0wbR//tUyrrXlHorlM95KePg1Kn5ZbR0dnPapwiQPT9lI/l2iuNe9INJfpXtLTp0Hp00Lrxo2y3ZZ33z3hH13iwLTC4w/nrnlHorlM95KePg1Kn5ZY169/m59Hx53LHZjO/bVMq615R6K5TPeSnj4NSp9mXwcHj52N3n33kgemib+WabU170g0l+le0tOnQenTvOvgoPzhDxfr0GkP5kVb845Ec5nuJT19GpQ+zbveeONKZWr4+MO5a96RaC7TvaSnT4PSpxnXz39++TJd+tcyrbbmHYnmMt1Levo0KH2aax0dXSZLV/+1TKuteUeiuUz3kp4+DUqfZlm7p8kv8WBenMcfzl3zjkRzme4lPX0alD5dfe0/Td7v4w+nrb++fdtkH+jJbic3fRqUPl1xVU+Tn/v4w+y/lmmhtUmapSXGm6Xp06D06Srrok+TX7vW+orPW5vsWVpivFmaPg1Kn66yLvo0+dFR6ys+ZW2GydIS483S9GlQ+nTpdYmnyX/2s9YX/fjajJelJcabpenToPTpiuv69fK97z307LPl1q1vvfVWuXv3oXv3ynZb/vjH1pdbShk7S0uMN0vTp0Hp0zhrI0vLjDdL06dB6dPhYXn++XJ8XJ5/vo/vk73o2sjSwuPN0vRpUCP36eDghAcc3nyzp++ZPWNtZOm8mWx+DUykT4Matk8HB+WDD05+iuGDDzpO1EaWJs9k82tgIn0a1LB9+uUvH/vZrLdulTt3yoMH5cGDst2WN95ofX0XXBtZuvhMNr8GJtKnQY3Zp2vXyp/+dML3JN28+bBPXXwvbZGlq81k82tgIn0a1Jh9unnz1G9IevR/pG7ebHFl09ZGluaYyebXwET6NKgx+/TSSw8j9NJLF/hHzddGlubjNeyIPg1qzD71dX7ayNICvJgd0adBjdmna9fKn/98wv9/Ojoqf/lLlP//tJGlJXlVO6JPgxqzT+Xx5/du3y7Hx+X27YdxevCg5Q/K28jSKry8HdGnQa3Tp83eZ26zD/7H18FB+fDDQN//tJGldXmdO6JPg1qtT/t/bJBQHRyUX/2qjtOdO6vGaSNLjXjBO6JPg1q/T/t/foRQHR6WF14ot26VF15Y7+fvbWSpNa98R/RpUA37tP8XRQjVCmsjS2F4CzqiT4OK0Kf9vzFlqDayFI/3oiP6NKhQfdr/qxOEaiNLgXlTOqJPg4rZp/1r6C5UG1nqgXenI/o0qOB92r+Y4KHayFJXvE0d0adB9dKn/asKFaqNLPXJ+9URfRpUd33av7yGodrIUue8cR3Rp0H126f961wtVBtZysI72BF9GlSCPu1f8EKh2shSOt7KjujToDL1af/KZwnVRpby8p52RJ8GlbJP+7dwiVBtZGkA3tyO6NOgcvdp/17ODdVGlkbiXe6IPg1qkD7t31QVqo0sDcnb3RF9GtRofdq/O1kamfe9I/o0qGH7xOCMd0f0aVD6xJiMd0f0aVD6xJiMd0f0aVD6xJiMd0f0aVD6xJiMd0f0aVD6xJiMd0f0aVD6xJiMd0f0aVD6xJiMd0f0aVBn9wmyar71mE6fBlVO7xNABD6kBqVPQHA+pAalT0BwPqQGpU9AcD6kBqVPQHA+pAalT0BwPqQGpU9AcD6kxtX+W1Haaf7iA+eyUQGISJ8AiEifAIhInwCISJ8AiEifAIhInwCISJ8AiEifAIhInwCISJ8AiEifAIhInwCISJ8AiEifAIhInwCISJ8AiEifAIhInwCISJ8AiEifAIhInwCISJ8AiEifAIhInwCISJ8AiEifAIhInwCISJ8AiEifAIhInwCISJ8AiEifAIhInwCISJ8AiEifAIhInwCISJ8AiEifAIhInwCISJ8AiEifAIhInwCISJ8AiEifAIhInwCISJ8AiEifAIhInwCISJ8AiEifAIjo/wEKioBlqdGxZQAAAABJRU5ErkJggg==" alt="" />

  算 法的实现其实就在ScanLineSeedFill()和SearchLineNewSeed()两个函数中,神秘的扫描线种子填充算法也并不复杂,对 吧?至此,种子填充算法的几种常见算法都已经介绍完毕,接下来将介绍两种适合矢量图形区域填充的填充算法,分别是扫描线算法和边标志填充算法,注意适合矢量图形的扫描线填充算法有时又被称为“有序边表法”,和扫描线种子填充算法是有区别的。

  总结:

  种子填充算法效率不是太高,及时是我实现的扫描线填充算法,可能我在判定当前像素信息是需要使用opengl获取缓存栈中的内容,效果不是很理想。

CGA填充算法之种子填充算法的更多相关文章

  1. &lbrack;计算机图形学&rsqb; 基于C&num;窗口的Bresenham直线扫描算法、种子填充法、扫描线填充法模拟软件设计(二)

    上一节链接:http://www.cnblogs.com/zjutlitao/p/4116783.html 前言: 在上一节中我们已经大致介绍了该软件的是什么.可以干什么以及界面的大致样子.此外还详细 ...

  2. 种子填充算法描述及C&plus;&plus;代码实现

    项目需要看了种子填充算法,改进了算法主要去除面积小的部分.种子填充算法分为两种,简单的和基于扫描线的方法,简单的算法如下描述(笔者针对的是二值图像): (1)从上到下,从左到有,依次扫描每个像素: ( ...

  3. Open gl 的不规则图形的4联通种子递归填充和扫描线种子递归填充算法实现

    实验题目:不规则区域的填充算法 实验目的:验证不规则区域的填充算法 实验内容:利用VC与OpenGL,实现不规则区域的填充算法. 1.必做:实现简单递归的不规则区域填充算法. 2.选做:针对简单递归算 ...

  4. openGL实现图形学扫描线种子填充算法

    title: "openGL实现图形学扫描线种子填充算法" date: 2018-06-11T19:41:30+08:00 tags: ["图形学"] cate ...

  5. Atitit Seed-Filling种子填充算法attilax总结

    Atitit Seed-Filling种子填充算法attilax总结 种子填充的原理,4联通与8联通区域的选择.. 三个队列 waitProcessPixList tempPixList Proces ...

  6. JAVA实现种子填充算法

    种子填充算法原理在网上很多地方都能找到,这篇是继上篇扫描线算法后另一种填充算法,直接上实现代码啦0.0 我的实现只是实现了种子填充算法,但是运行效率不快,如果大佬有改进方法,欢迎和我交流,谢谢! 最后 ...

  7. UVA 572 -- Oil Deposits(DFS求连通块&plus;种子填充算法)

    UVA 572 -- Oil Deposits(DFS求连通块) 图也有DFS和BFS遍历,由于DFS更好写,所以一般用DFS寻找连通块. 下述代码用一个二重循环来找到当前格子的相邻8个格子,也可用常 ...

  8. CGA裁剪算法之线段裁剪算法

    CGA裁剪算法之线段裁剪算法 常用的线段裁剪算法有三种:[1]Cohen_SutherLand裁剪算法,[2]中点分割裁剪算法,[3]参数化方法. 1. Cohen_SutherLand裁剪算法 为了 ...

  9. 一步步学算法&lpar;算法分析&rpar;---6&lpar;Floyd算法&rpar;

    Floyd算法 Floyd算法又称为弗洛伊德算法,插点法,是一种用于寻找给定的加权图中顶点间最短路径的算法.该算法名称以创始人之一.1978年图灵奖获得者.斯坦福大学计算机科学系教授罗伯特·弗洛伊德命 ...

随机推荐

  1. loj 1379&lpar;最短路变形&rpar;

    题目链接:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=27087 思路:题目的意思是求S->T的所有路径中花费总和小于 ...

  2. 开始进入Windows Phone 8开发

    和大家一起分享从零开始,入手Windows Phone 8开发,大家一起来吧!

  3. WARNING OGG-01223 TCP&sol;IP error 111 &lpar;Connection refused&rpar;

    一:问题描述 GGSCI (source_pc) 64> info all Program     Status      Group       Lag at Chkpt  Time Sinc ...

  4. Struct和Class的区别(转载)

    转载来源:http://blog.sina.com.cn/s/blog_48f587a80100k630.html C++中的struct对C中的struct进行了扩充,它已经不再只是一个包含不同数据 ...

  5. Flex 基础语法(三)

    2.flex-wrap 默认情况下,项目都排在一条线(又称"轴线")上.flex-wrap属性定义,如果一条轴线排不下,如何换行 属性 含义 nowrap(默认值) 不换行 wra ...

  6. Hadoop加速器GridGain

    GridGain的Hadoop加速器 像GridGain等内存网格产品(IMDG)不仅可以作为简单的缓存,加速Hadoop中MapReduce计算也是IMDG的一个亮点.这样内存计算领域又多了一种思路 ...

  7. H5 百度一下&comma;你就知道

    <!DOCTYPE html> <html> <head lang="en"> <meta charset="UTF-8&quo ...

  8. 全栈开发工程师微信小程序-中

    全栈开发工程师微信小程序-中 多媒体及其他的组件 navigator 页面链接 target 在哪个目标上发生跳转,默认当前小程序,可选值self/miniProgram url 当前小程序内的跳转链 ...

  9. 微信小程序unionid获取问题

    微信小程序使用login获取unionid时可能获取不到,原因可能是该微信账号没有关注小程序所在公众号等.但在微信小程序中使用微信注册,必须要用unionid注册时,大部分用户就会因此无法注册成功. ...

  10. Oracle数据库 查看表是否是 索引组织表的方法

    1. 最近在工作过程中发现 一个表插入很慢 以为是索引组织表, 所以一直有点纠结 但是发现 产品里面是没有IOT的 于是找了下公司的OCP 问了下 如何查看 就是 user_tables 视图里面的一 ...