java 多边形填充算法

Java中多边形填充算法有很多种，其中比较常见的有扫描线算法和边界填充算法。下面分别介绍这两种算法的实现方法。

1. 扫描线算法

扫描线算法的基本思想是先确定多边形的边界，然后从多边形的最下面一条边开始，用一条扫描线沿y轴方向往上扫描，记录扫描线和多边形的交点，然后对相邻的交点进行配对，形成一个线段，将这个线段中的像素点进行填充。重复上述步骤，直到扫描线扫描到多边形的最上面一条边。

扫描线算法的实现步骤如下：

1. 确定多边形的边界，即计算出多边形的最大和最小y坐标。

2. 从最小y坐标开始，往上扫描，记录扫描线和多边形的交点。

3. 对相邻的交点进行配对，形成线段，并对线段中的像素点进行填充。

4. 重复2-3步骤，直到扫描线扫描到多边形的最大y坐标。

以下是Java中使用扫描线算法实现多边形填充的代码示例：

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Polygon;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class ScanLineFill extends JPanel {
    private static final long serialVersionUID = 1L;

    public void paint(Graphics g) {
        int[] xPoints = { 50, 200, 200, 50 };
        int[] yPoints = { 50, 50, 200, 200 };
        Polygon polygon = new Polygon(xPoints, yPoints, xPoints.length);
        scanLineFill(polygon, Color.BLUE, g);
    }

    // 扫描线填充算法
    public void scanLineFill(Polygon p, Color c, Graphics g) {
        int xMax = p.xpoints[0], xMin = p.xpoints[0];
        int yMax = p.ypoints[0], yMin = p.ypoints[0];
        // 计算多边形的边界
        for (int i = 1; i < p.npoints; i++) {
            if (p.xpoints[i] > xMax)
                xMax = p.xpoints[i];
            if (p.xpoints[i] < xMin)
                xMin = p.xpoints[i];
            if (p.ypoints[i] > yMax)
                yMax = p.ypoints[i];
            if (p.ypoints[i] < yMin)
                yMin = p.ypoints[i];
        }
        // 扫描线算法
        for (int y = yMin; y <= yMax; y++) {
            int startX = 0;
            boolean inPolygon = false;
            for (int x = xMin; x <= xMax; x++) {
                if (p.contains(x, y)) {
                    if (!inPolygon) {
                        inPolygon = true;
                        startX = x;
                    }
                } else {
                    if (inPolygon) {
                        inPolygon = false;
                        g.setColor(c);
                        g.drawLine(startX, y, x - 1, y);
                    }
                }
            }
            if (inPolygon) {
                g.setColor(c);
                g.drawLine(startX, y, xMax, y);
            }
        }
    }

    public static void main(String[] args) {
        JFrame frame = new JFrame("Scan Line Fill");
        frame.add(new ScanLineFill());
        frame.setSize(300, 300);
        frame.setVisible(true);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    }
}

2. 边界填充算法

边界填充算法的基本思想是从多边形的边界开始，将多边形内部的像素点逐步填充。具体实现方法如下：

1. 首先找到多边形的边界，即计算出多边形的所有边。

2. 对于每条边，找到边上的所有像素点，并将其记录在一个队列中。

3. 遍历队列中的像素点，如果该像素点的上下左右四个方向的像素点都不在多边形内部，则将该像素点填充。

4. 重复2-3步骤，直到队列为空。

以下是Java中使用边界填充算法实现多边形填充的代码示例：

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Polygon;
import java.util.LinkedList;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class BoundaryFill extends JPanel {
    private static final long serialVersionUID = 1L;

    public void paint(Graphics g) {
        int[] xPoints = { 50, 200, 200, 50 };
        int[] yPoints = { 50, 50, 200, 200 };
        Polygon polygon = new Polygon(xPoints, yPoints, xPoints.length);
        boundaryFill(polygon, 100, 100, Color.BLUE, g);
    }

    // 边界填充算法
    public void boundaryFill(Polygon p, int x, int y, Color fill, Graphics g) {
        LinkedList<Point> queue = new LinkedList<Point>();
        Color boundary = g.getColor();
        queue.add(new Point(x, y));
        while (!queue.isEmpty()) {
            Point point = queue.remove();
            if (point.x < 0 || point.y < 0 || point.x >= getWidth()
                    || point.y >= getHeight())
                continue;
            Color color = new Color(getRGB(point.x, point.y));
            if (!color.equals(fill) && !color.equals(boundary)) {
                g.setColor(fill);
                g.fillRect(point.x, point.y, 1, 1);
                queue.add(new Point(point.x - 1, point.y));
                queue.add(new Point(point.x + 1, point.y));
                queue.add(new Point(point.x, point.y - 1));
                queue.add(new Point(point.x, point.y + 1));
            }
        }
    }

    public static void main(String[] args) {
        JFrame frame = new JFrame("Boundary Fill");
        frame.add(new BoundaryFill());
        frame.setSize(300, 300);
        frame.setVisible(true);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    }
}

class Point {
    int x, y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

以上就是Java中实现多边形填充的两种常见算法。具体使用哪种算法，需要根据具体的应用场景和性能需求来选择。