อัลกอริทึมการเติมรูปหลายเหลี่ยม

รูปหลายเหลี่ยมเป็นรายการเรียงลำดับของจุดยอดดังแสดงในรูปต่อไปนี้ สำหรับการเติมรูปหลายเหลี่ยมด้วยสีเฉพาะคุณต้องกำหนดพิกเซลที่ตกลงบนขอบของรูปหลายเหลี่ยมและพิกเซลที่อยู่ภายในรูปหลายเหลี่ยม ในบทนี้เราจะมาดูวิธีเติมรูปหลายเหลี่ยมโดยใช้เทคนิคต่างๆ

Scan Line Algorithm

อัลกอริทึมนี้ทำงานโดยการตัดกันเส้นสแกนกับขอบรูปหลายเหลี่ยมและเติมรูปหลายเหลี่ยมระหว่างจุดตัดคู่ ขั้นตอนต่อไปนี้แสดงให้เห็นว่าอัลกอริทึมนี้ทำงานอย่างไร

Step 1 - ค้นหา Ymin และ Ymax จากรูปหลายเหลี่ยมที่กำหนด

Step 2- ScanLine ตัดกับขอบแต่ละด้านของรูปหลายเหลี่ยมจาก Ymin ถึง Ymax ตั้งชื่อจุดตัดกันของรูปหลายเหลี่ยมแต่ละจุด ตามรูปที่แสดงด้านบนพวกเขาถูกตั้งชื่อเป็น p0, p1, p2, p3

Step 3 - เรียงลำดับจุดตัดตามลำดับที่เพิ่มขึ้นของพิกัด X ได้แก่ (p0, p1), (p1, p2) และ (p2, p3)

Step 4 - กรอกคู่พิกัดทั้งหมดที่อยู่ภายในรูปหลายเหลี่ยมและละเว้นคู่อื่น

อัลกอริทึมการเติมน้ำท่วม

บางครั้งเราเจอวัตถุที่ต้องการเติมเต็มพื้นที่และขอบเขตของมันด้วยสีที่ต่างกัน เราสามารถทาสีวัตถุดังกล่าวด้วยสีภายในที่ระบุแทนการค้นหาสีขอบเขตเฉพาะเช่นเดียวกับอัลกอริทึมการเติมขอบเขต

แทนที่จะอาศัยขอบเขตของวัตถุ แต่อาศัยสีเติม กล่าวอีกนัยหนึ่งคือแทนที่สีภายในของวัตถุด้วยสีเติม เมื่อไม่มีพิกเซลของสีภายในดั้งเดิมอีกต่อไปอัลกอริทึมจะเสร็จสมบูรณ์

อีกครั้งอัลกอริทึมนี้อาศัยวิธีการเชื่อมต่อแบบ Four-connect หรือ Eight-connect ในการเติมพิกเซล แต่แทนที่จะมองหาสีขอบเขตมันกำลังมองหาพิกเซลที่อยู่ติดกันทั้งหมดที่เป็นส่วนหนึ่งของการตกแต่งภายใน

อัลกอริทึมการเติมขอบเขต

อัลกอริทึมการเติมขอบเขตทำงานเป็นชื่อของมัน อัลกอริทึมนี้เลือกจุดภายในวัตถุและเริ่มเติมจนกว่าจะถึงขอบเขตของวัตถุ สีของขอบเขตและสีที่เราเติมควรแตกต่างกันเพื่อให้อัลกอริทึมนี้ทำงานได้

ในอัลกอริทึมนี้เราถือว่าสีของขอบเขตนั้นเหมือนกันสำหรับวัตถุทั้งหมด อัลกอริทึมการเติมขอบเขตสามารถใช้งานได้โดยพิกเซลที่เชื่อมต่อ 4 พิกเซลหรือพิกเซลที่เชื่อมต่อ 8 พิกเซล

รูปหลายเหลี่ยมที่เชื่อมต่อ 4 รูปแบบ

ในเทคนิคนี้ใช้พิกเซลที่เชื่อมต่อ 4 จุดดังแสดงในรูป เรากำลังวางพิกเซลด้านบนด้านล่างไปทางขวาและทางด้านซ้ายของพิกเซลปัจจุบันและกระบวนการนี้จะดำเนินต่อไปจนกว่าเราจะพบขอบเขตที่มีสีต่างกัน

อัลกอริทึม

Step 1 - เริ่มต้นค่าของ seed point (seedx, seedy), fcolor และ dcol

Step 2 - กำหนดค่าขอบเขตของรูปหลายเหลี่ยม

Step 3 - ตรวจสอบว่าจุดเริ่มต้นปัจจุบันเป็นสีเริ่มต้นหรือไม่จากนั้นทำซ้ำขั้นตอนที่ 4 และ 5 จนกระทั่งถึงพิกเซลขอบเขต

If getpixel(x, y) = dcol then repeat step 4 and 5

Step 4 - เปลี่ยนสีเริ่มต้นด้วยสีเติมที่จุดเริ่มต้น

setPixel(seedx, seedy, fcol)

Step 5 - ทำตามขั้นตอนซ้ำ ๆ โดยมีจุดใกล้เคียงสี่จุด

FloodFill (seedx – 1, seedy, fcol, dcol)
FloodFill (seedx + 1, seedy, fcol, dcol)
FloodFill (seedx, seedy - 1, fcol, dcol)
FloodFill (seedx – 1, seedy + 1, fcol, dcol)

Step 6 - ออก

มีปัญหากับเทคนิคนี้ พิจารณากรณีดังที่แสดงด้านล่างที่เราพยายามเติมเต็มทั้งภูมิภาค ที่นี่ภาพจะเต็มไปเพียงบางส่วน ในกรณีเช่นนี้ไม่สามารถใช้เทคนิค 4-connected pixels ได้

รูปหลายเหลี่ยมที่เชื่อมต่อกัน 8 รูป

ในเทคนิคนี้จะใช้พิกเซลที่เชื่อมต่อ 8 พิกเซลดังแสดงในรูป เราวางพิกเซลไว้ด้านบนด้านล่างด้านขวาและด้านซ้ายของพิกเซลปัจจุบันตามที่เราทำในเทคนิค 4-connected

นอกจากนี้เรายังวางพิกเซลในแนวทแยงมุมเพื่อให้ครอบคลุมพื้นที่ทั้งหมดของพิกเซลปัจจุบัน กระบวนการนี้จะดำเนินต่อไปจนกว่าเราจะพบขอบเขตที่มีสีต่างกัน

อัลกอริทึม

Step 1 - เริ่มต้นค่าของ seed point (seedx, seedy), fcolor และ dcol

Step 2 - กำหนดค่าขอบเขตของรูปหลายเหลี่ยม

Step 3 - ตรวจสอบว่าจุดเริ่มต้นปัจจุบันเป็นสีเริ่มต้นหรือไม่จากนั้นทำซ้ำขั้นตอนที่ 4 และ 5 จนกระทั่งถึงพิกเซลขอบเขต

If getpixel(x,y) = dcol then repeat step 4 and 5

Step 4 - เปลี่ยนสีเริ่มต้นด้วยสีเติมที่จุดเริ่มต้น

setPixel(seedx, seedy, fcol)

Step 5 - ทำตามขั้นตอนซ้ำ ๆ โดยมีจุดใกล้เคียงสี่จุด

FloodFill (seedx – 1, seedy, fcol, dcol)
FloodFill (seedx + 1, seedy, fcol, dcol)
FloodFill (seedx, seedy - 1, fcol, dcol)
FloodFill (seedx, seedy + 1, fcol, dcol)
FloodFill (seedx – 1, seedy + 1, fcol, dcol)
FloodFill (seedx + 1, seedy + 1, fcol, dcol)
FloodFill (seedx + 1, seedy - 1, fcol, dcol)
FloodFill (seedx – 1, seedy - 1, fcol, dcol)

Step 6 - ออก

เทคนิคพิกเซลที่เชื่อมต่อ 4 จุดล้มเหลวในการเติมเต็มพื้นที่ตามที่ทำเครื่องหมายในรูปต่อไปนี้ซึ่งจะไม่เกิดขึ้นกับเทคนิค 8-connected

การทดสอบภายใน - ภายนอก

วิธีนี้เรียกอีกอย่างว่า counting number method. ในขณะเติมวัตถุเรามักจะต้องระบุว่าจุดใดจุดหนึ่งอยู่ภายในวัตถุหรือภายนอกวัตถุนั้น มีสองวิธีที่เราสามารถระบุได้ว่าจุดใดจุดหนึ่งอยู่ภายในวัตถุหรือภายนอก

  • กฎคี่ - คู่
  • กฎเลขที่คดเคี้ยวไม่ใช่ศูนย์

กฎคี่ - คู่

ในเทคนิคนี้เราจะนับขอบที่ข้ามไปตามเส้นจากจุดใด ๆ (x, y) ถึงอินฟินิตี้ ถ้าจำนวนการโต้ตอบเป็นเลขคี่จุด (x, y) คือจุดภายใน และถ้าจำนวนการโต้ตอบเป็นจำนวนเท่ากันจุด (x, y) ก็คือจุดภายนอก ตัวอย่างต่อไปนี้แสดงให้เห็นถึงแนวคิดนี้

จากรูปด้านบนเราจะเห็นว่าจากจุด (x, y) จำนวนจุดปฏิสัมพันธ์ทางด้านซ้ายคือ 5 และทางด้านขวาคือ 3 จากปลายทั้งสองข้างจำนวนจุดปฏิสัมพันธ์จะเป็นเลขคี่ จุดจะพิจารณาภายในวัตถุ

กฎเลขที่คดเคี้ยวที่ไม่ใช่ศูนย์

วิธีนี้ยังใช้กับรูปหลายเหลี่ยมธรรมดาเพื่อทดสอบจุดที่กำหนดว่าอยู่ภายในหรือไม่ สามารถเข้าใจได้ง่ายๆด้วยความช่วยเหลือของหมุดและแถบยาง ยึดหมุดที่ขอบด้านใดด้านหนึ่งของรูปหลายเหลี่ยมแล้วมัดแถบยางเข้าด้วยกันจากนั้นยืดแถบยางตามขอบของรูปหลายเหลี่ยม

เมื่อขอบทั้งหมดของรูปหลายเหลี่ยมถูกรัดด้วยแถบยางให้ตรวจสอบหมุดที่ยึดไว้ตรงจุดที่จะทดสอบ ถ้าเราพบลมอย่างน้อยหนึ่งจุดให้พิจารณาภายในรูปหลายเหลี่ยมมิฉะนั้นเราสามารถพูดได้ว่าจุดนั้นไม่ได้อยู่ในรูปหลายเหลี่ยม

ในวิธีอื่นให้บอกทิศทางไปยังขอบทั้งหมดของรูปหลายเหลี่ยม ลากเส้นสแกนจากจุดที่จะทดสอบไปทางซ้ายสุดของทิศทาง X

  • ให้ค่า 1 กับขอบทั้งหมดซึ่งจะขึ้นไปและ -1 อื่น ๆ ทั้งหมดเป็นค่าทิศทาง

  • ตรวจสอบค่าทิศทางขอบที่เส้นสแกนกำลังผ่านและสรุปผล

  • หากผลรวมทั้งหมดของค่าทิศทางนี้ไม่เป็นศูนย์จุดที่จะทดสอบนี้คือ interior point, มิฉะนั้นจะเป็นไฟล์ exterior point.

  • ในรูปด้านบนเราสรุปค่าทิศทางที่เส้นสแกนกำลังผ่านจากนั้นผลรวมคือ 1 - 1 + 1 = 1; ซึ่งไม่ใช่ศูนย์ ดังนั้นจุดที่กล่าวว่าเป็นจุดภายใน