Use the normals of your surfaces to calculate this.
Essentially, you're taking your existing edge, and growing it. Then, in some cases, optimizing it to cut out loops or tight corners.
For each corner, you get the averaged normal for the two surfaces that make up that corner. For interior corners, since the average would be pointing towards each other, you'd use the cross product to get the perpendicular vector.
This will grow the edge. This works great for your green line, since it's the same edge as your shape. However, for your red line, this can produce problems. You can use some pathfinding shortcut techniques to optimize out sharp turns.
For example, you'd want the shortcut between 4 and 9, so you can skip 5-8. There's a few approaches to this. For example, detecting loops, like 5-8 would create or a pathfinding optimization for reducing redundant nodes.
Check page 12.
Likely the easiest way of detecting these loops is to find nodes that are close together and remove them. Build up your entire path, then test each node and its neighbors to ensure they aren't too close. If nodes are removed, repeat the comparison until no nodes are removed. In my example image, nodes 6 and 7 would be removed for being too close. That would reorder nodes 5 and 8 to be nodes 5 and 6. Then nodes 5 and 6 would be removed for being too close. After that, there are no more nodes that are too close.