用奇偶规则填充凹多边形不能正常工作？
Filling concave polygon with even-odd rule doesn't work properly?
我目前正在尝试用颜色填充凹多边形。我在网上找到了一些算法，比如我现在使用的奇偶算法。我首先发现如何检查两条线段是否与以下相交：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);
}
然而，这并没有产生任何令人满意的结果，如您所见：
Polygon-fill
有谁知道我做错了什么或者有没有其他方法？
示例代码 - 尚未准备好生产，仅用于测试（和一些乐趣）!!!
使用 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 倍）
我目前正在尝试用颜色填充凹多边形。我在网上找到了一些算法，比如我现在使用的奇偶算法。我首先发现如何检查两条线段是否与以下相交：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);
}
然而，这并没有产生任何令人满意的结果，如您所见：
Polygon-fill
有谁知道我做错了什么或者有没有其他方法？
示例代码 - 尚未准备好生产，仅用于测试（和一些乐趣）!!!
使用 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 倍）