Drawing a path surrounding a given path

Question

* Update *

Found a solution using Clipper library. Solution added as answer. New / better / easier ideas are still welcome though!

---

Given a path like this:

I want to create a path surrounding this path with a given distance, e.g. 1 cm. The following sketch demonstrates that - the red path surrounds the black path with a distance of 1 cm.

How can this be done in a generic way using PDFSharp? (Meaning I want to finally draw it with PDFSharp, I don't care where the calculations are done) Here is the code for the black path:

// helper for easily getting an XPoint in centimeters
private XPoint cmPoint(double x, double y)
{
    return new XPoint(
        XUnit.FromCentimeter(x),
        XUnit.FromCentimeter(y)
        );
}


// the path to be drawn
private XGraphicsPath getMyPath()
{
    XGraphicsPath path = new XGraphicsPath();

    XPoint[] points = new XPoint[3];
    points[0] = cmPoint(0, 0);
    points[1] = cmPoint(5, 2);
    points[2] = cmPoint(10,0);

    path.AddCurve(points);
    path.AddLine(cmPoint(10, 0), cmPoint(10, 10));
    path.AddLine(cmPoint(10, 10), cmPoint(0, 10));
    path.CloseFigure(); 

    return path;
}


// generate the PDF file
private void button3_Click(object sender, RoutedEventArgs e)
{
    // Create a temporary file
    string filename = String.Format("{0}_tempfile.pdf", Guid.NewGuid().ToString("D").ToUpper());

    XPen penBlack = new XPen(XColors.Black, 1);
    XPen penRed = new XPen(XColors.Red, 1);

    PdfDocument pdfDocument = new PdfDocument();

    PdfPage page = pdfDocument.AddPage();
    page.Size = PdfSharp.PageSize.A1;

    XGraphics gfx = XGraphics.FromPdfPage(page);

    //give us some space to the left and top
    gfx.TranslateTransform(XUnit.FromCentimeter(3), XUnit.FromCentimeter(3));

    // draw the desired path
    gfx.DrawPath(penBlack, getMyPath());


    // Save the pdfDocument...
    pdfDocument.Save(filename);
    // ...and start a viewer
    Process.Start(filename);
}

Thanks for any help on this topic!

Decanal

Related: https://mcmap.net/q/907479/-draw-parallel-line – Getter

In fact, the sketch does not correspond to what you are describing: the top corners of the red curve are more than 1 cm away from any point of the black curve.. And even for a rectangle inside a rectangle that is true: the corners are sqrt(2) cm away from the corners of the inner rectangle.. So I think you have either to update the image or change the wording. – Heterologous

You are right, but I don't know how to better describe this in words. Maybe with the term polygon offset which I meanwhile learned ;-) – Decanal

Answer 1

You can use Widen() function, which replaces the path with curves that enclose the area that is filled when the path is drawn by a specified pen, adding an additional outline to the path.

This function receives as parameter a XPen, so you can create this XPen using the desired offset as width and an outer path will be added at a constant distance (pen's width).

XGraphicsPath class is in fact a wrapper of System.Drawing.Drawing2D.GraphicsPath, so you can use Widen() function in XGraphicsPath, get the internal object and iterate on it using GraphicsPathIterator class to get the path added.

This method will do the job:

public XGraphicsPath GetSurroundPath(XGraphicsPath path, double width)
{
    XGraphicsPath container = new XGraphicsPath();

    container.StartFigure();
    container.AddPath(path, false);
    container.CloseFigure();

    var penOffset = new XPen(XColors.Black, width);

    container.StartFigure();
    container.Widen(penOffset);
    container.CloseFigure();

    var iterator = new GraphicsPathIterator(container.Internals.GdiPath);

    bool isClosed;
    var outline = new XGraphicsPath();
    iterator.NextSubpath(outline.Internals.GdiPath, out isClosed);

    return outline;
}

You can handle level of flatness in curves using the overload Widen(XPen pen, XMatrix matrix, double flatness). Doing this call container.Widen(penOffset, XMatrix.Identity, 0.05); results in more rounded edges.

Then draw an outer path using this function:

string filename = String.Format("{0}_tempfile.pdf", Guid.NewGuid().ToString("D").ToUpper());

XPen penBlack = new XPen(XColors.Black, 1);
XPen penRed = new XPen(XColors.Red, 1);

PdfDocument pdfDocument = new PdfDocument();

PdfPage page = pdfDocument.AddPage();
page.Size = PdfSharp.PageSize.A1;

XGraphics gfx = XGraphics.FromPdfPage(page);

//give us some space to the left and top
gfx.TranslateTransform(XUnit.FromCentimeter(3), XUnit.FromCentimeter(3));

var path = getMyPath();

// draw the desired path
gfx.DrawPath(penBlack, path);
gfx.DrawPath(penRed, GetSurroundPath(path, XUnit.FromCentimeter(1).Point));

// Save the pdfDocument...
pdfDocument.Save(filename);
// ...and start a viewer
Process.Start(filename);

This is what you get:

Another way may be using reflection to retrieve internal Pen in XPen and setup CompoundArray property. This allows you draws parallel lines and spaces. Using this property you can do something like this:

But the problem is that you can only use one color, anyway this is just an idea, I have not tried in PDFsharp

Also, you should search for offset polyline curves or offsetting polygon algorithms.

Probative

That looks really good! In the star like figure, is it possible to get more rounded edges? – Decanal

Yes, it is posible. XGraphicsPath.Widen() have an overload you can pass flatness as parameter, you can control the level of detail of the curves using this parameter, smaller values will give you more rounded edges – Probative

I accepted this as answer, as it looks really promising and the county ended. Yet didn't have the change to experiment with it. – Decanal

Answer 2

This can be done using Clipper

double scale = 1024.0;

List<IntPoint> points = new List<IntPoint>();
points.Add(new IntPoint(0*scale, 0*scale));
points.Add(new IntPoint(5*scale, 2*scale));
points.Add(new IntPoint(10*scale, 0*scale));
points.Add(new IntPoint(10*scale, 10*scale));
points.Add(new IntPoint(0*scale, 10*scale));
points.Reverse();

List<List<IntPoint>> solution = new List<List<IntPoint>>();



ClipperOffset co = new ClipperOffset();
co.AddPath(points, JoinType.jtMiter, EndType.etClosedPolygon);
co.Execute(ref solution, 1 * scale);  

foreach (IntPoint point in solution[0])
{
    Console.WriteLine("OUTPUT: " + point.X + "/" + point.Y + " -> " + point.X/scale + "/" + point.Y/scale);
}

And the output:

OUTPUT: 11264/11264 -> 11/11
OUTPUT: -1024/11264 -> -1/11
OUTPUT: -1024/-1512 -> -1/-1,4765625
OUTPUT: 5120/945 -> 5/0,9228515625
OUTPUT: 11264/-1512 -> 11/-1,4765625

Drawn original and offset path:

This is still not perfect for various mathematical reasons, but already quite good.

Decanal

Answer 3

• This is an updated Answer requested

The XGraphicPath is sealed class which was implemented with bad practices IMO, so the only way is to use a wrapper around it. I tried to make the code as self documented as possible

public class OGraphicPath
{
    private readonly ICollection<XPoint[]> _curves;
    private readonly ICollection<Tuple<XPoint, XPoint>> _lines;

    public OGraphicPath()
    {
        _lines = new List<Tuple<XPoint, XPoint>>();
        _curves = new List<XPoint[]>();
    }

    public XGraphicsPath XGraphicsPath
    {
        get
        {
            var path = new XGraphicsPath();

            foreach (var curve in _curves)
            {
                path.AddCurve(curve);
            }

            foreach (var line in _lines)
            {
                path.AddLine(line.Item1, line.Item2);
            }

            path.CloseFigure();

            return path;
        }
    }

    public void AddCurve(XPoint[] points)
    {
        _curves.Add(points);
    }

    public void AddLine(XPoint point1, XPoint point2)
    {
        _lines.Add(new Tuple<XPoint, XPoint>(point1, point2));
    }

    // Finds Highest and lowest X and Y to find the Center O(x,y)
    private XPoint FindO()
    {
        var xs = new List<double>();
        var ys = new List<double>();
        foreach (var point in _curves.SelectMany(points => points))
        {
            xs.Add(point.X);
            ys.Add(point.Y);
        }
        foreach (var line in _lines)
        {
            xs.Add(line.Item1.X);
            xs.Add(line.Item2.X);

            ys.Add(line.Item1.Y);
            ys.Add(line.Item2.Y);
        }

        var OX = xs.Min() + xs.Max()/2;
        var OY = ys.Min() + ys.Max()/2;

        return new XPoint(OX, OY);
    }


    // If a point is above O, it's surrounded point is even higher, if it's below O, it's surrunded point is below O too...
    private double FindPlace(double p, double o, double distance)
    {
        var dp = p - o;
        if (dp < 0)
        {
            return p - distance;
        }
        if (dp > 0)
        {
            return p + distance;
        }
        return p;
    }

    public XGraphicsPath Surrond(double distance)
    {
        var path = new XGraphicsPath();

        var O = FindO();

        foreach (var curve in _curves)
        {
            var points = new XPoint[curve.Length];
            for (var i = 0; i < curve.Length; i++)
            {
                var point = curve[i];
                var x = FindPlace(point.X, O.X, distance);
                var y = FindPlace(point.Y, O.Y, distance);
                points[i] = new XPoint(x, y);
            }
            path.AddCurve(points);
        }

        foreach (var line in _lines)
        {
            var ax = FindPlace(line.Item1.X, O.X, distance);
            var ay = FindPlace(line.Item1.Y, O.Y, distance);
            var a = new XPoint(ax, ay);

            var bx = FindPlace(line.Item2.X, O.X, distance);
            var by = FindPlace(line.Item2.Y, O.Y, distance);
            var b = new XPoint(bx, by);

            path.AddLine(a, b);
        }

        path.CloseFigure();

        return path;
    }
}

And is Consumed Like this

// draw the desired path
        var path = getMyPath();
        gfx.DrawPath(penBlack, path.XGraphicsPath);
        gfx.DrawPath(penRed, path.Surrond(XUnit.FromCentimeter(1)));

Opinionative

Thanks for your efforts! Unfortunately I need a more generic solution, something like SurroundMe(Path myPath) ): Also the result would be better if one could offset the path itself (more points) instead of just the points that were input to the Path. – Decanal

@stefan.at.wpf How about this one? – Opinionative

Thanks again! As one can see on he screenshot though, this solution is still to simple. I added an answer using the Clipper library, which improves the result. – Decanal

@stefan.at.wpf well the question was how to do it using pdfsharp and using it's graphicpath :) – Opinionative

well, the answer is there is no direct function for that in pdfsharp. the new coordinates have to be calculated externally like e.g. using Clipper or your approach and then it can be drawn using pdfsharp. the last thing is important, not if one also gets the new coordinates using pdfsharp. – Decanal

Answer 4

What if we made a "DrawOutline" extension to xGraphics?

 public static class XGraphicsExtentions
    {
        public static void DrawOutline(this XGraphics gfx, XPen pen, XGraphicsPath path, int offset)
        {
            // finding the size of the original path so that we know how much to scale it in x and y
            var points = path.Internals.GdiPath.PathPoints;
            float minX, minY;
            float maxX, maxY;
            GetMinMaxValues(points, out minX, out minY, out maxX, out maxY);

            var deltaY = XUnit.FromPoint(maxY - minY);
            var deltaX = XUnit.FromPoint(maxX - minX);

            var offsetInPoints = XUnit.FromCentimeter(offset);

            var scaleX = XUnit.FromPoint((deltaX + offsetInPoints)/deltaX);
            var scaleY = XUnit.FromPoint((deltaY + offsetInPoints)/deltaY);
            var transform = -offsetInPoints/2.0;

            gfx.TranslateTransform(transform, transform);
            gfx.ScaleTransform(scaleX, scaleY);

            gfx.DrawPath(pen, path);

            // revert changes to graphics object before exiting
            gfx.ScaleTransform(1/scaleX,1/scaleY);
            gfx.TranslateTransform(-transform, -transform);
        }

        private static void GetMinMaxValues(PointF[] points, out float minX, out float minY, out float maxX, out float maxY)
        {
            minX = float.MaxValue;
            maxX = float.MinValue;
            minY = float.MaxValue;
            maxY = float.MinValue;

            foreach (var point in points)
            {
                if (point.X < minX)
                    minX = point.X;

                if (point.X > maxX)
                    maxX = point.X;

                if (point.Y < minY)
                    minY = point.Y;

                if (point.Y > maxY)
                    maxY = point.Y;
            }

        }
    }

Usage:

// draw the desired path
gfx.DrawPath(penBlack, getMyPath());
gfx.DrawOutline(penRed, getMyPath(), 2);

Result:

Lafleur

Thanks, but unfortunately - as you can see on your result screenshot - the distances aren't equal. You might have a look at my own reply. – Decanal

Answer 5

Clipper is a great choice, but depending on your needs it will not result in a perfect offset. offset from edge is not equal to offset from corner A better solution, which will require you to remove any beizer curves and only use line primitives, is using CGAL library for contour offsets: http://doc.cgal.org/latest/Straight_skeleton_2/index.html

Another way of doing it, which is actually pretty cool (albeit taking a lot of memory), is to convert your path to a bitmap and then apply a dilate operation, https://en.wikipedia.org/wiki/Dilation_(morphology). This will give you a correct transformation, but in the bitmap resolution. You can the convert the bitmap to vector graphics, using a tool like https://en.wikipedia.org/wiki/Potrace

A good image toolbox is OpenCV, and http://www.emgu.com/wiki/index.php/Main_Page for .NET/C#. It includes dilation.

This will give you a somewhat limited resolution approach, but the end result will be precise to the bitmap resolution (and actually a lot higher since you are using a contour offset that, in fact, is limiting the offsetted contour details).

Copt

Could someone, with higher reputation, please add http to the links. I was only allowed one hyperlink before reaching 10 reputation points... – Copt

Thanks for these informations! The pure WPF or Clipper solution will suit my case better, but I learned something new here :-) – Decanal

Answer 6

try this:

public Lis<Point> Draw(Point[] points /*Current polygon*/, int distance  /*distance to new polygon*/) {
    List<Point> lResult = new List<Point>();

    foreach(Point lPoint in points) {
        Point lNewPoint =  new Point(lPoint.X - distance, lPoint.Y);
        if(!CheckCurrentPoint(lNewPoint, points)) {
            lResult.Add(lNewPoint)
            continue;
        }

        lNewPoint =  new Point(lPoint.X + distance, lPoint.Y);
        if(!CheckCurrentPoint(lNewPoint, points)) {
            lResult.Add(lNewPoint)
            continue;
        }

        lNewPoint =  new Point(lPoint.X, lPoint.Y - distance);
        if(!CheckCurrentPoint(lNewPoint, points)) {
            lResult.Add(lNewPoint)
            continue;
        }

        lNewPoint =  new Point(lPoint.X, lPoint.Y + distance);
        if(!CheckCurrentPoint(lNewPoint, points)) {
            lResult.Add(lNewPoint)
            continue;
        }
    }

    return lResult; // Points of new polygon
}

private static int Crs(Point a1, Point a2, Point p, ref bool ans) {
    const double e = 0.00000000000001;

    int lCrsResult = 0;

    if (Math.Abs(a1.Y - a2.Y) < e)
        if ((Math.Abs(p.Y - a1.Y) < e) && ((p.X - a1.X) * (p.X - a2.X) < 0.0))
            ans = false;

    if ((a1.Y - p.Y) * (a2.Y - p.Y) > 0.0)
        return lCrsResult;

    double lX = a2.X - (a2.Y - p.Y) / (a2.Y - a1.Y) * (a2.X - a1.X);

    if (Math.Abs(lX - p.X) < e)
        ans = false;
    else if (lX < p.X) {
        lCrsResult = 1;

        if ((Math.Abs(a1.Y - p.Y) < e) && (a1.Y < a2.Y))
            lCrsResult = 0;
        else if ((Math.Abs(a2.Y - p.Y) < e) && (a2.Y < a1.Y))
            lCrsResult = 0;
    }
    return lCrsResult;
}

private static bool CheckCurrentPoint(Point p /*Point of new posible polygon*/, Points[] points /*points of current polygon*/) {
    if (points.Count == 0)
        return false;

    int lC = 0;
    bool lAns = true;

    for (int lIndex = 1; lIndex < points.Count; lIndex++) {
        lC += Crs(points[lIndex - 1], points[lIndex], p, ref lAns);

        if (!lAns)
            return false;
    }

    lC += Crs(points[points.Count - 1], points[0], p, ref lAns);

    if (!lAns)
        return false;

    return (lC & 1) > 0;
}

From mentioned sample in comments

Lawanda

Thanks for your reply! Can you please explain it and maybe add a sample of the result? – Decanal

I Find faster way to do this, sample in link: link, you cant use part of this code to correct transform – Lawanda

Thanks for your efforts, I added a screenshot of your result to your reply. Unfortunately the distance of the outer polygon is not constant, also I have a curve in the original. – Decanal