用奇偶规则填充凹多边形不能正常工作？

我正在尝试用颜色填充一个凹多边形。我在网上找到了一些算法，比如我现在使用的奇偶算法。我首先了解了如何检查两条线段是否从以下位置相交：https://bryceboe.com/2006/10/23/line-segment-intersection-algorithm/
然后我用java实现了它，如下所示：

public boolean contains(PointD point) {
        if (Arrays.stream(vertices).anyMatch(vertex -> vertex == point))
            return true;

        //  Create point at the border of the image
        //  Line segment AB represents the ray used in the even-odd algorithm
        PointD a = point;
        PointD b = new PointD(SIZE - 1, y);

        //  Count how many times AB crosses the individual line segments of
        //  the concave polygon
        int crossing = 0;
        for (int i = 0; i < vertices.length; i++) {
            PointD c = vertices[i];
            PointD d = vertices[(i + 1) % vertices.length];

            if (ccw(a, c, d) != ccw(b, c, d) && ccw(a, b, c) != ccw(a, b, d))
                crossing += 1;
        }

        //  If the amount of crossings is odd, the point is inside the polygon
        return crossing % 2 == 1;
    }

    private boolean ccw(PointD a, PointD b, PointD c) {
        return (c.y - a.y) * (b.x - a.x) > (b.y - a.y) * (c.x - a.y);
    }

但是，正如您所看到的，这并不能产生任何令人满意的结果：
多边形填充
是否有人知道我做错了什么，或者是否有其他方法？

示例代码-不准备生产，只是为了测试（和一些乐趣）！！！
使用 List 点而不是数组，但转换为数组以避免更改问题代码。
正如前面提到的，锁定是以一种非常简单、快速（容易出错）的方式完成的，只用于测试！

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Image;
import java.awt.Point;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.awt.image.BufferedImage;
import java.net.URL;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.ExecutionException;

import javax.imageio.ImageIO;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingWorker;

public class Polyg extends JPanel {

    private static final Color LINE_COLOR = new Color(0, 0, 255, 112);
    private static final Color AREA_COLOR = new Color(0, 255, 0, 112);

    public static void main(String[] args) throws Exception {
        var panel = switch (20) {  // test cases
            case 10 -> new Polyg(new Dimension(400, 300), 100, 100, 200, 200, 300, 100, 200, 150);
            case 20 -> new Polyg(ImageIO.read(new URL("file:mAp26bw.png")));
            case 22 -> new Polyg(ImageIO.read(new URL("file:mAp26bw2.png")));
            default -> throw new IllegalArgumentException("not implemented");
        };

        var f = new JFrame();
        f.setDefaultCloseOperation(f.DISPOSE_ON_CLOSE);
        f.add(panel);
        f.pack();
        f.setLocationRelativeTo(null);
        f.setVisible(true);
    }

    private final Image background;
    private final Dimension size;
    private final List<Point> points;
    private final BufferedImage inside;

    private volatile boolean lock = false;

    private Polyg(Image background) {
        this.background = background;
        this.size = new Dimension(background.getWidth(null), background.getHeight(null));
        this.points = new ArrayList<>();
        this.inside = new BufferedImage(size.width, size.height, BufferedImage.TYPE_INT_ARGB);
        setToolTipText("""
            <html>
              <b>left-button:</b> add point<br/>
              <b>right-button:</b> delete point<br/>
              <b>middle-button:</b> print points to console
            """);
        addMouseListener(new MouseAdapter() {
            @Override
            public void mouseClicked(MouseEvent e) {
                if (e.getClickCount() > 1)
                    return;
                switch(e.getButton()) {
                    case 1:
                        if (!lock) {
                            points.add(e.getPoint());
                            calc();
                        }
                        break;
                    case 2:
                        points.forEach(System.out::println);
                        System.out.println();
                        break;
                    case 3:
                        if (!lock && !points.isEmpty()) {
                            points.remove(points.size()-1);
                            calc();
                        }
                        break;
                    default:
                        break;
                }
            }
        });
    }

    private Polyg(Dimension size, int... coords) {
        this.background = null;
        this.size = size;
        var list = new ArrayList<Point>();
        for (var i = 0; i+1 < coords.length; i += 2) {
            list.add(new Point(coords[i], coords[i+1]));
        }
        this.points = Collections.unmodifiableList(list);
        this.inside = new BufferedImage(size.width, size.height, BufferedImage.TYPE_INT_ARGB);
        calc();
    }

    private void calc() {
        lock = true;
        for (var x = 0; x < inside.getWidth(); x++) {
            for (var y = 0; y < inside.getHeight(); y++) {
                inside.setRGB(x, y, 0);
            }
        }
        new SwingWorker<Void, Void>() {

            @Override
            protected Void doInBackground() throws Exception {
                for (var x = 0; x < size.width; x++) {
                    for (var y = 0; y < size.height; y++) {
                        if (containsP(x, y)) {
                            inside.setRGB(x, y, AREA_COLOR.getRGB());
                        }
                    }
                    publish((Void) null);
                }
                return null;
            }

            @Override
            protected void process(java.util.List<Void> chunks) {
                repaint();
            }

            @Override
            protected void done() {
                try {
                    get();
                } catch (InterruptedException | ExecutionException ex) {
                    ex.printStackTrace();
                }
                repaint();
                lock = false;
            }
        }.execute();
    }

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);

        Graphics2D gg = (Graphics2D) g.create();
        try {
            if (background != null) {
                gg.drawImage(background, 0, 0, this);
            }
            gg.drawImage(inside, 0, 0, this);
            gg.setColor(LINE_COLOR);
            Point first = null;
            Point p1 = null;
            for (var p2 : points) {
                if (p1 == null) {
                    first = p2;
                } else {
                    gg.drawLine(p1.x, p1.y, p2.x, p2.y);
                }
                p1 = p2;
            }
            if (first != null && p1 != null) {
                gg.drawLine(first.x, first.y, p1.x, p1.y);
            }
        } finally {
            gg.dispose();
        }
    }

    @Override
    public Dimension getPreferredSize() {
        return size;
    }

    private boolean containsP(int x, int y) {
        var vertices = points.toArray(Point[]::new);  // avoid changing posted code
        Point a = new Point(x, y);
        if (Arrays.stream(vertices).anyMatch(vertex -> vertex == a))
            return true;

        //  Create point at the border of the image
        //  Line segment AB represents the ray used in the even-odd algorithm
        Point b = new Point(size.width - 1, y);

        //  Count how many times AB crosses the individual line segments of
        //  the concave polygon
        int crossing = 0;
        for (int i = 0; i < vertices.length; i++) {
            Point c = vertices[i];
            Point d = vertices[(i + 1) % vertices.length];

            if (ccw(a, c, d) != ccw(b, c, d) && ccw(a, b, c) != ccw(a, b, d))
                crossing += 1;
        }

        //  If the amount of crossings is odd, the point is inside the polygon
        return crossing % 2 == 1;
    }

    private boolean ccw(Point a, Point b, Point c) {
        return (c.y - a.y) * (b.x - a.x) > (b.y - a.y) * (c.x - a.x);
    }
}

用作背景的图像：map26bw.png( mAp26bw2.png （只有4倍大）

用奇偶规则填充凹多边形不能正常工作？

1条答案

相关问题

热门标签

最新问答