扫描线填充

Java

  1. import javax.swing.*;
  2. import java.awt.*;
  3. import java.util.ArrayList;
  4. import java.util.Collections;
  6. public class FillTest extends JFrame {
  8.     private ArrayList<Edge> edgeTable = new ArrayList<>();
  10.     private int getYmin() {
  11.         int yMin = edgeTable.get(0).y1;
  12.         for (Edge edge : edgeTable) {
  13.             if (edge.y1 < yMin)
  14.                 yMin = edge.y1;
  15.         }
  16.         return yMin;
  17.     }
  19.     private int getYmax() {
  20.         int yMax = edgeTable.get(0).y1;
  21.         for (Edge edge : edgeTable) {
  22.             if (edge.y1 > yMax)
  23.                 yMax = edge.y1;
  24.         }
  25.         return yMax;
  26.     }
  28.     private boolean isActive(Edge edge, int currentY) {
  29.         return edge.y1 < currentY && currentY <= edge.y2 || edge.y1 >= currentY && currentY > edge.y2;
  30.     }
  32.     private void updateActiveEdges(ArrayList<Edge> activeEdges, int y) {
  33.         for (Edge edge : edgeTable) {
  34.             if (isActive(edge, y)) {
  35.                 if (!activeEdges.contains(edge)) {
  36.                     activeEdges.add(edge);
  37.                 }
  38.             } else {
  39.                 activeEdges.remove(edge);
  40.             }
  41.         }
  42.     }
  44.     private void findIntersections(ArrayList<Integer> intersections, ArrayList<Edge> activeEdges, int currentY) {
  45.         intersections.clear();
  46.         for (Edge edge : activeEdges) {
  47.             int x = edge.x1 + ((currentY - edge.y1) * (edge.dx)) / (edge.dy);
  48.             intersections.add(x);
  49.         }
  50.     }
  52.     public void fill() {
  53.         ArrayList<Edge> activeEdges = new ArrayList(10);
  54.         ArrayList<Integer> intersections = new ArrayList(20);
  56.         Graphics g = getGraphics();
  57.         g.setColor(Color.red);
  58.         // x1,y1,x2,y2
  59.         edgeTable.add(new Edge(100, 100, 100, 600));
  60.         edgeTable.add(new Edge(100, 600,500,400));
  61.         edgeTable.add(new Edge(500,400, 100, 100));
  63.         int yMin = getYmin();
  64.         int yMax = getYmax();
  66.         for (int y = yMin; y < yMax; y++) {
  67.             updateActiveEdges(activeEdges, y);
  68.             findIntersections(intersections, activeEdges, y);
  69.             Collections.sort(intersections);
  70.             for (int i = 0; i < intersections.size(); i += 2) {
  71.                 int x1 = intersections.get(i);
  72.                 if (i + 1 >= intersections.size()){
  73.                     break;
  74.                 }
  75.                 int x2 = intersections.get(i + 1);
  76.                 g.drawLine(x1, y, x2, y);
  77.             }
  78.         }
  79.     }
  81.     public static void main(String[] args) {
  82.         FillTest s = new FillTest();
  83.         s.setSize(800, 800);
  84.         s.setVisible(true);
  85.         s.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  86.         s.fill();
  87.     }
  88. }
  90. class Edge {
  91.     int x1, y1, x2, y2, dx, dy;
  92.     Edge(int x1, int y1, int x2, int y2) {
  93.         this.x1 = x1;
  94.         this.y1 = y1;
  95.         this.x2 = x2;
  96.         this.y2 = y2;
  97.         this.dx = x2 - x1;
  98.         this.dy = y2 - y1;
  99.     }
  100. }

C++

ScanlineFilling.h
  1. #include <iostream>
  2. #include <vector>
  3. class ScanlineFilling
  4. {
  5.     public:
  6.         class Edge {
  7.         public:
  8.             int x1, y1, x2, y2, dx, dy;
  9.             Edge(int x1, int y1, int x2, int y2);
  10.         };
  12.     private:
  13.         std::vector<Edge> edgeTable;
  14.         int  getYmin();
  15.         int  getYmax();
  16.         bool  isActive(Edge edge, int currentY);
  17.         void  updateActiveEdges(std::vector<Edge>& activeEdges, int y);
  18.         void  findIntersections(std::vector<int>& intersections, std::vector <Edge> activeEdges, int currentY);
  19.     public:
  20.         // 多边形填充
  21.         void fill(int** matrix, int x, int y, int** position, int len, int fillValue);
  22. };

ScanlineFilling.cpp
  1. #include "ScanlineFilling.h"
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  6. using namespace std;
  8. ScanlineFilling::Edge::Edge(int x1, int y1, int x2, int y2) {
  9.     this->x1 = x1;
  10.     this->y1 = y1;
  11.     this->x2 = x2;
  12.     this->y2 = y2;
  13.     this->dx = x2 - x1;
  14.     this->dy = y2 - y1;
  15. }
  17. int ScanlineFilling::getYmin() {
  18.     int yMin = edgeTable.front().y1;
  19.     for (Edge edge : edgeTable) {
  20.         if (edge.y1 < yMin)
  21.             yMin = edge.y1;
  22.     }
  23.     return yMin;
  24. }
  26. int ScanlineFilling::getYmax() {
  27.     int yMax = edgeTable.front().y1;
  28.     for (Edge edge : edgeTable) {
  29.         if (edge.y1 > yMax)
  30.             yMax = edge.y1;
  31.     }
  32.     return yMax;
  33. }
  35. bool ScanlineFilling::isActive(Edge edge, int currentY) {
  36.     return edge.y1 < currentY && currentY <= edge.y2 || edge.y1 >= currentY && currentY > edge.y2;
  37. }
  39. void ScanlineFilling::updateActiveEdges(std::vector<Edge>& activeEdges, int y) {
  40.     for (Edge edge : edgeTable) {
  41.         if (isActive(edge, y)) {
  42.             activeEdges.push_back(edge);
  43.         }
  44.     }
  45. }
  47. void ScanlineFilling::findIntersections(std::vector<int>& intersections, std::vector<Edge> activeEdges, int currentY) {
  48.     for (Edge edge : activeEdges) {
  49.         int x = edge.x1 + ((currentY - edge.y1) * (edge.dx)) / (edge.dy);
  50.         intersections.push_back(x);
  51.     }
  52. }
  54. //参数：要填充的二维数组，数组的行列，多边形的坐标[x,y]，多边形坐标的个数(从起点到终点的个数，其中起点==终点)，填充的值
  55. void ScanlineFilling::fill(int** matrix, int x, int y, int** position, int len,int fillValue) {
  56.     vector<Edge> activeEdges;
  57.     vector<int> intersections;
  58.     int firstX, firstY;
  59.     edgeTable.clear();
  60.     // 获取面的点
  61.     for (int i = 0; i < len; i++) {
  62.         if (i == 0) {
  63.             firstX = position[i][0];
  64.             firstY = position[i][1];
  65.             continue;
  66.         }
  67.         edgeTable.push_back(*(new Edge(firstX, firstY, position[i][0], position[i][1])));
  68.         firstX = position[i][0];
  69.         firstY = position[i][1];
  70.     }
  71.     int yMin = getYmin();
  72.     int yMax = getYmax();
  73.     for (int y = yMin; y < yMax; y++) {
  74.         activeEdges.clear();
  75.         intersections.clear();
  76.         updateActiveEdges(activeEdges, y);
  77.         findIntersections(intersections, activeEdges, y);
  78.         // 升序
  79.         sort(intersections.begin(),intersections.end());
  80.         for (int i = 0; i < intersections.size(); i += 2) {
  81.             int x1 = intersections[i];
  82.             if ((i + 1) >= intersections.size()) {
  83.                 break;
  84.             }
  85.             int x2 = intersections[i + 1];
  86.             for (int k = x1; k < x2; k++) {
  87.                 matrix[k][y] = fillValue;
  88.             }
  89.         }
  90.     }
  91. }