How can I generate echo path for concave polygon

Question

I need an algorithm to draw echo path for an arbitrary polygon. If a polygon is convex problem is quite easy to solve. To understand what I mean please look at the picture bellow where in black is original polygon and in red color echoed polygons generated from original one.

d is distance between echo paths which is given

β angle is easy to calculate knowing coordinates of vertices which we have

So as you can see for each vertex we can calculate L and thus have new vertices for next echo path.

The problem is when we have concave polygon at some point we will get an ugly picture of self crossing polygon. Please take a look to this picture.

What I want to do is generate echo polygon without self crossing part i.e. without part that is with dash lines. An algorithm or java code would be very helpful. Thanks.

Edit

Just adding piece of code that generates echo path for convex polygon as it was asked in comment.

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

Answer 1

You are looking for the straight skeleton:

---

^{(Image from Wikipedia.)}

---

Answer 2

This problem is called computing polygon offsetting. There are two common ways to solve this problem:

1) the most effective way is to compute offset polygon by computing winding numbers ( As I understood, this algorithm is used by Clipper library)

2) computing straight skeleton graph, which help you to build offset polygon

Interesting articles on this topic :

Chen, polygon offsetting by computing winding numbers

Felkel's algorithm to compute straight skeleton

Answer 3

Ok, found a library that can do what I need. It called Clipper

There is also java implementation for it here if anybody interested.

With Java library couple lines of code do the trick

    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.

It is open source so I will dive in for implementation details. Thanks everyone who tried to help.