如何为凹多边形生成回声路径

Question

我需要一个算法来绘制任意多边形的回声路径。如果一个多边形是凸的，问题就很容易解决。请看下面的图片，黑色为原始多边形，红色为从原始多边形生成的回声多边形。 d 是回声路径之间的距离，已知。 已知顶点坐标，可以轻松计算出 β 角度。 因此，对于每个顶点，我们都可以计算出 L，从而得到下一个回声路径的新顶点。 问题在于，当我们有凹多边形时，会得到一个丑陋的自交多边形图像。请看这张图片。 我想做的是生成没有自交部分（即虚线部分）的回声多边形。一个算法或者 java 代码将非常有帮助。谢谢。 编辑 只是添加了一段代码，用于生成凸多边形的回声路径，因为在评论中被问到了。

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;
}

- Vilen

---

你能展示一下凸多边形的算法/代码吗？如果不看你是如何实现的，这个问题就太过开放了。一个框架会帮助别人填补空白。 - Andrew Cheong

@AndrewCheong 这是一段有点长的代码，但总体上我只是遍历所有顶点，计算相邻两条边之间的角度，根据该角度找到一个距离顶点等于L的点，并将该点添加到下一路径的点列表中。等我接近电脑时，我会添加代码。 - Vilen

那么，您不想在底部示例中将孤立的三角形包含在“C”内吗？ - samgak

@samgak 我不想包含带有虚线的部分，它也有点淡化了。不过我已经找到了解决方案。 - Vilen

如何为多边形创建内部螺旋线？参见相关问题：How can I create an internal spiral for a polygon? 和 画一些连通线的轮廓。 - Spektre

Answer 1

这个问题被称为计算多边形偏移。有两种常见的解决方法：

1）最有效的方法是通过计算绕数来计算偏移多边形（据我所知，Clipper库使用此算法）

2）计算直线骨架图，以帮助您构建偏移多边形

关于这个主题的有趣文章：

陈先生的“通过计算绕数进行多边形偏移”

Felkel的算法来计算直线骨架图

- Alex Aparin

Answer 2

你正在寻找直线骨架:

---

         
          ^{（图片来自维基百科。）}

---

- Joseph O'Rourke

Answer 3

好的，我找到了一个可以满足我的需求的库。它叫做Clipper。

如果有人感兴趣，这里还有它的Java实现here。

使用Java库只需要几行代码就可以搞定。

    Path originalPath = new Path();
    for (PointF areaPoint:pointsOriginal){
        originalPath.add(new LongPoint((long)areaPoint.x, (long)areaPoint.y));
    }
    final ClipperOffset clo = new ClipperOffset();
    Paths clips = new Paths();
    Paths solution = new Paths();
    clips.add(originalPath);
    clo.addPaths( clips, Clipper.JoinType.SQUARE, Clipper.EndType.CLOSED_LINE );
    float encoderEchoDistance = (float) UnitUtils.convertInchOrMmUnitsToEncoderUnits(this, inchOrMm, appliqueEchoDistance);
    clo.execute( solution, encoderEchoDistance );
    // Now solution.get(0) will contain path that has offset from original path
    // and what is most important it will not have self intersections.

它是开源的，所以我会深入了解实现细节。感谢所有试图帮助我的人。

- Vilen