我正在尝试用颜色填充一个凹多边形。我在网上找到了一些算法,比如我现在使用的奇偶算法。我首先了解了如何检查两条线段是否从以下位置相交: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);
}
但是,正如您所看到的,这并不能产生任何令人满意的结果:
多边形填充
是否有人知道我做错了什么,或者是否有其他方法?
1条答案
按热度按时间e4yzc0pl1#
示例代码-不准备生产,只是为了测试(和一些乐趣)!!!
使用
List
点而不是数组,但转换为数组以避免更改问题代码。正如前面提到的,锁定是以一种非常简单、快速(容易出错)的方式完成的,只用于测试!
用作背景的图像:map26bw.png(
mAp26bw2.png
(只有4倍大)