我需要一个算法来绘制任意多边形的回声路径 . 如果多边形是凸的问题很容易解决 . 要理解我的意思,请看下面的图片,其中黑色是原始多边形,红色是从原始多边形生成的回声多边形 .
d
是给定的回波路径之间的距离
知道我们所拥有的顶点坐标,很容易计算出角度
因此,您可以看到每个顶点我们可以计算 L
,从而为下一个回波路径提供新的顶点 .
问题是当我们在某一点上有凹多边形时,我们会得到一个自交叉多边形的丑陋图像 . 请看一下这张照片 .
我想要做的是生成没有自交叉部分的回波多边形,即没有带虚线的部分 . 算法或 java
代码将非常有用 . 谢谢 .
Edit
只需添加一段代码,为评论中提出的凸多边形生成回声路径 .
public List<MyPath> createEchoCoCentral( List<Point> pointsOriginal, float encoderEchoDistance, int appliqueEchoCount){
List<Point> contourPoints = pointsOriginal;
List<MyPath> echoPaths = new ArrayList<>();
for (int round = 0; round < appliqueEchoCount; round++) {
List<Point> echoedPoints = new ArrayList<>();
int size = contourPoints.size()+1;//+1 because we connect end to start
Point previousPoint = contourPoints.get(contourPoints.size() - 1);
for (int i = 0; i < size; i++) {
Point currentPoint;
if (i == contourPoints.size()) {
currentPoint = new Point(contourPoints.get(0));
} else {
currentPoint = contourPoints.get(i);
}
final Point nextPoint;
if (i + 1 == contourPoints.size()) {
nextPoint = contourPoints.get(0);
} else if (i == contourPoints.size()) {
nextPoint = contourPoints.get(1);
} else {
nextPoint = contourPoints.get(i + 1);
}
if (currentPoint.x == previousPoint.x && currentPoint.y == previousPoint.y) continue;
if (currentPoint.x == nextPoint.x && currentPoint.y == nextPoint.y) continue;
// signs needed o determine to which side of polygon new point will go
float currentSlope = (float) (Math.atan((previousPoint.y - currentPoint.y) / (previousPoint.x - currentPoint.x)));
float signX = Math.signum((previousPoint.x - currentPoint.x));
float signY = Math.signum((previousPoint.y - currentPoint.y));
signX = signX == 0 ? 1 : signX;
signY = signY == 0 ? 1 : signY;
float nextSignX = Math.signum((currentPoint.x - nextPoint.x));
float nextSignY = Math.signum((currentPoint.y - nextPoint.y));
nextSignX = nextSignX == 0 ? 1 : nextSignX;
nextSignY = nextSignY == 0 ? 1 : nextSignY;
float nextSlope = (float) (Math.atan((currentPoint.y - nextPoint.y) / (currentPoint.x - nextPoint.x)));
float nextSlopeD = (float) Math.toDegrees(nextSlope);
//calculateMidAngle - is a bit tricky function that calculates angle between two adjacent edges
double S = calculateMidAngle(currentSlope, nextSlope, signX, signY, nextSignX, nextSignY);
Point p2 = new Point();
double ew = encoderEchoDistance / Math.cos(S - (Math.PI / 2));
p2.x = (int) (currentPoint.x + (Math.cos(currentSlope - S)) * ew * signX);
p2.y = (int) (currentPoint.y + (Math.sin(currentSlope - S)) * ew * signX);
echoedPoints.add(p2);
previousPoint = currentPoint;
}
//createPathFromPoints just creates MyPath objects from given Poins set
echoPaths.add(createPathFromPoints(echoedPoints));
//remove last point since it was just to connect end to first point
echoedPoints.remove(echoedPoints.size() - 1);
contourPoints = echoedPoints;
}
return echoPaths;
}
3 回答
您正在寻找straight skeleton:
(图片来自维基百科 . )
此问题称为计算多边形偏移 . 有两种常见的方法可以解决这个问题:
1)最有效的方法是通过计算绕组数来计算偏移多边形(据我所知,这个算法由Clipper库使用)
2)计算直骨架图,帮助您构建偏移多边形
关于这个主题的有趣文章:
Chen,通过计算绕组数来抵消多边形
费尔克尔计算直骨架的算法
好的,找到了一个可以做我需要的库 . 它叫Clipper
如果有兴趣的话,还有java实现here .
使用Java库,几行代码可以解决问题
它是开源的,所以我将深入了解实现细节 . 谢谢所有试图提供帮助的人 .