.Net与GraphicsPath.Widen()相反

Question

我需要与GraphicsPath.Widen().Net 中的方法相反:

public GraphicsPath Widen()

该Widen()方法不接受否定参数,因此我需要等效的Inset方法:

public GraphicsPath Inset()

您可以在开源Inkscape应用程序(www.Inkscape.org)中执行此操作,方法是转到菜单并选择"Path/Inset"(插入量存储在Inkscape属性对话框中).由于Inkscape是开源的,所以应该可以在C#.Net中执行此操作,但我不能在生命中使用Inkscape C++源代码(我只需要这个函数,所以我不能证明学习C++是正确的完成这个).

基本上,我需要一个带有此签名的GraphicsPath扩展方法:

public static GraphicsPath Inset(this GraphicsPath original, float amount)
{
   //implementation
}

正如签名所述,它将采用一个GraphicsPath对象和.Inset()路径传递的数量......就像今天的Inkscape一样.如果它简化了任何问题,那么所讨论的GraphicsPath都是从该.PolyBezier方法创建的(并且没有其他内容),因此除非您想要完整性,否则不需要考虑rects,省略号或任何其他形状.

不幸的是,我没有使用C++代码的经验,所以我几乎不可能遵循Inkscape中包含的C++逻辑.

.

[编辑:]根据要求,这里是"MakeOffset"Inkscape代码.对于Inset,第二个参数(double dec)将为负,并且该参数的绝对值是引入形状的量.

我知道这里有很多依赖项.如果您需要查看更多的Inkscape源文件,请访问:http://sourceforge.net/projects/inkscape/files/inkscape/0.48/

int
Shape::MakeOffset (Shape * a, double dec, JoinType join, double miter, bool do_profile, double cx, double cy, double radius, Geom::Matrix *i2doc)
{
  Reset (0, 0);
  MakeBackData(a->_has_back_data);

    bool done_something = false;

  if (dec == 0)
  {
    _pts = a->_pts;
    if (numberOfPoints() > maxPt)
    {
      maxPt = numberOfPoints();
      if (_has_points_data) {
        pData.resize(maxPt);
        _point_data_initialised = false;
        _bbox_up_to_date = false;
        }
    }

    _aretes = a->_aretes;
    if (numberOfEdges() > maxAr)
    {
      maxAr = numberOfEdges();
      if (_has_edges_data)
    eData.resize(maxAr);
      if (_has_sweep_src_data)
        swsData.resize(maxAr);
      if (_has_sweep_dest_data)
        swdData.resize(maxAr);
      if (_has_raster_data)
        swrData.resize(maxAr);
      if (_has_back_data)
        ebData.resize(maxAr);
    }
    return 0;
  }
  if (a->numberOfPoints() <= 1 || a->numberOfEdges() <= 1 || a->type != shape_polygon)
    return shape_input_err;

  a->SortEdges ();

  a->MakeSweepDestData (true);
  a->MakeSweepSrcData (true);

  for (int i = 0; i < a->numberOfEdges(); i++)
  {
    //              int    stP=a->swsData[i].stPt/*,enP=a->swsData[i].enPt*/;
    int stB = -1, enB = -1;
    if (dec > 0)
    {
      stB = a->CycleNextAt (a->getEdge(i).st, i);
      enB = a->CyclePrevAt (a->getEdge(i).en, i);
    }
    else
    {
      stB = a->CyclePrevAt (a->getEdge(i).st, i);
      enB = a->CycleNextAt (a->getEdge(i).en, i);
    }

    Geom::Point stD, seD, enD;
    double stL, seL, enL;
    stD = a->getEdge(stB).dx;
    seD = a->getEdge(i).dx;
    enD = a->getEdge(enB).dx;

    stL = sqrt (dot(stD,stD));
    seL = sqrt (dot(seD,seD));
    enL = sqrt (dot(enD,enD));
    MiscNormalize (stD);
    MiscNormalize (enD);
    MiscNormalize (seD);

    Geom::Point ptP;
    int stNo, enNo;
    ptP = a->getPoint(a->getEdge(i).st).x;

        double this_dec;
        if (do_profile && i2doc) {
            double alpha = 1;
            double x = (Geom::L2(ptP * (*i2doc) - Geom::Point(cx,cy))/radius);
            if (x > 1) {
                this_dec = 0;
            } else if (x <= 0) {
                this_dec = dec;
            } else {
                this_dec = dec * (0.5 * cos (M_PI * (pow(x, alpha))) + 0.5);
            }
        } else {
            this_dec = dec;
        }

        if (this_dec != 0)
            done_something = true;

    int   usePathID=-1;
    int   usePieceID=0;
    double useT=0.0;
    if ( a->_has_back_data ) {
      if ( a->ebData[i].pathID >= 0 && a->ebData[stB].pathID == a->ebData[i].pathID && a->ebData[stB].pieceID == a->ebData[i].pieceID
           && a->ebData[stB].tEn == a->ebData[i].tSt ) {
        usePathID=a->ebData[i].pathID;
        usePieceID=a->ebData[i].pieceID;
        useT=a->ebData[i].tSt;
      } else {
        usePathID=a->ebData[i].pathID;
        usePieceID=0;
        useT=0;
      }
    }
    if (dec > 0)
    {
      Path::DoRightJoin (this, this_dec, join, ptP, stD, seD, miter, stL, seL,
                         stNo, enNo,usePathID,usePieceID,useT);
      a->swsData[i].stPt = enNo;
      a->swsData[stB].enPt = stNo;
    }
    else
    {
      Path::DoLeftJoin (this, -this_dec, join, ptP, stD, seD, miter, stL, seL,
                        stNo, enNo,usePathID,usePieceID,useT);
      a->swsData[i].stPt = enNo;
      a->swsData[stB].enPt = stNo;
    }
  }

  if (dec < 0)
  {
    for (int i = 0; i < numberOfEdges(); i++)
      Inverse (i);
  }

  if ( _has_back_data ) {
    for (int i = 0; i < a->numberOfEdges(); i++)
    {
      int nEd=AddEdge (a->swsData[i].stPt, a->swsData[i].enPt);
      ebData[nEd]=a->ebData[i];
    }
  } else {
    for (int i = 0; i < a->numberOfEdges(); i++)
    {
      AddEdge (a->swsData[i].stPt, a->swsData[i].enPt);
    }
  }

  a->MakeSweepSrcData (false);
  a->MakeSweepDestData (false);

  return (done_something? 0 : shape_nothing_to_do);
}

.

[EDITS]

@Simon Mourier - 出色的工作.代码甚至干净可读!干得好,先生.不过,我确实有几个问题要问你.

首先,金额的正数代表什么？我认为对于Offset方法,正面将是"开始"而负面将是"插入",但你的例子似乎正好相反.

其次,我做了一些基本的测试(只是扩展你的样本),发现了一些奇怪的东西.

当偏移量增加时,"酷"中的"l"会发生什么(对于这么简单的字母,肯定会引起问题!).

...以及重现那个的代码:

    private void Form1_Paint(object sender, PaintEventArgs e)
    {
            GraphicsPath path = new GraphicsPath();

            path.AddString("cool", new FontFamily("Arial"), 0, 200, new PointF(), StringFormat.GenericDefault);

            GraphicsPath offset1 = path.Offset(32);

            e.Graphics.DrawPath(new Pen(Color.Black, 1), path);
            e.Graphics.DrawPath(new Pen(Color.Red, 1), offset1);
    }

最后,有点不同.这是来自Wingdings的"S"角色(看起来像泪滴):

这是代码:

    private void Form1_Paint(object sender, PaintEventArgs e)
    {
        GraphicsPath path = new GraphicsPath();
        path.AddString("S", new FontFamily("Wingdings"), 0, 200, new PointF(), StringFormat.GenericDefault);
        GraphicsPath offset1 = path.Offset(20);

        e.Graphics.DrawPath(new Pen(Color.Black, 1), path);
        e.Graphics.DrawPath(new Pen(Color.Red, 1), offset1);
    }

男人,这是如此接近,它让我想哭.但它仍然不起作用.

我认为解决这个问题的方法是看插入向量何时相交,并停止插入该点.如果插入量太大(或路径太小)以至于没有剩余,则路径应该消失(变为空),而不是反转自身并重新展开.

再说一遍,我并没有以任何方式敲击你所做的事情,但我想知道你是否知道这些例子可能会发生什么.

(PS - 我添加了'this'关键字使其成为扩展方法,因此您可能需要使用方法(参数)表示法调用代码才能运行这些示例)

.

@RAN Ran通过重新使用GraphicsPath本机方法得出了类似的输出.伙计,这很难.两者都非常接近.

这是两个例子的屏幕截图,使用Wingdings中的字符"S":

@Simon在左边,@ Ran在右边.

在Inkscape中执行"插入"之后,这是相同的泪滴"S"字符.插图很干净:

顺便说一句,这是@ Ran测试的代码:

    private void Form1_Paint(object sender, PaintEventArgs e)
    {
        GraphicsPath path = new GraphicsPath();
        path.AddString("S", new FontFamily("Wingdings"), 0, 200, new PointF(), StringFormat.GenericDefault);
        e.Graphics.DrawPath(new Pen(Color.Black, 1), path);

        GraphicsPath offset1 = path.Shrink(20);
        e.Graphics.DrawPath(new Pen(Color.Red, 1), offset1);
    }

Answer 1

我仍然会发布我的新解决方案,即使它并不完美,还有一些需要修复的问题列表.也许你会想要采取它的一部分并改进它们,或者也许它有一些学习价值.

首先,图片 - 我最好的插图泪珠符号:

我做了什么

1. 我曾经GraphicsPath.Widen生成给定图形的"内"和"外"边.

2. 我扫描了结果的点GraphicsPath,去除了外边缘,只保留了内边缘.

3. 我使用内边缘展平GraphicsPath.Flatten,使得图形仅由线段(无曲线)组成.

4. 然后,我扫描了内部路径上的所有点,以及每个当前段:

   4.1.如果当前点p在原始路径之外,或者太靠近原始路径上的一个段,我会在当前边缘计算一个新点,该点与原始路径之间的距离是合适的,我接受这个指向而不是p,并将其连接到我已经扫描过的部分.

   4.2.解决方案中的当前限制:我从计算点继续,向前扫描.这意味着对具有孔的形状(例如Arial"o")没有很好的支持.要解决此问题,必须维护一个"断开连接"的数字列表,并重新连接在同一点(或"彼此足够接近"的端点)的数字.

问题

首先,我将指出最主要的问题和限制,然后我将发布代码本身.

1. 似乎GraphicsPath.Widen不会产生干净的形状.我得到的内在形象很小(但几乎看不见)"锯齿状".其重要性在于A)我的剔除算法产生更多噪声,而B)该图有更多的点,因此性能下降.

2. 在这一点上,如果有的话,性能几乎是不可接受的.我的解决方案目前以非常幼稚的方式(在O(n ^ n)中)进行扫描,以找到"太靠近"内边缘上的候选点的线段.这导致算法非常慢.可以通过维护一些数据结构来改进,其中段由x排序,从而显着减少距离计算的数量.

3. 我没有费心去优化要使用的代码,structs并且还有很多其他地方可以优化代码以便更快.

4. 没有支持带孔的形状,其中内部图形必须"分裂"成几个图形(如Arial"o").我知道如何实现它,但它需要更多的时间:)

5. 我会考虑采用Simon的方法来移动现有的点来获得内在的数字,用我的方法来清理这条路径.(但是由于Simon的解决方案中的一个错误,我现在无法做到这一点,例如,导致Tear符号的尖端移动到形状内的有效位置.我的算法认为这个位置是有效的,不清理它).

代码

我无法避免想出一些我自己的数学/几何实用工具.所以这是代码......

就个人而言,我认为这可能值得赏金,即使它不是一个完美的解决方案...... :)

public class LineSegment
{
    private readonly LineEquation line;
    private RectangleF bindingRectangle;

    public PointF A { get; private set; }
    public PointF B { get; private set; }

    public LineSegment(PointF a, PointF b)
    {
        A = a;
        B = b;

        line = new LineEquation(a, b);
        bindingRectangle = new RectangleF(
            Math.Min(a.X, b.X), Math.Min(a.Y, b.Y), 
            Math.Abs(a.X - b.X), Math.Abs(a.Y - b.Y));
    }

    public PointF? Intersect(LineSegment other)
    {
        var p = line.Intersect(other.line);
        if (p == null) return null;

        if (bindingRectangle.Contains(p.Value) &&
            other.bindingRectangle.Contains(p.Value))
        {
            return p;
        }
        return null;
    }

    public float Distance(PointF p)
    {
        if (LineEquation.IsBetween(line.GetNormalAt(A), p, line.GetNormalAt(B)))
        {
            return line.Distance(p);
        }
        return Math.Min(Distance(A, p), Distance(B, p));

    }

    static float Distance(PointF p1, PointF p2)
    {
        var x = p1.X - p2.X;
        var y = p1.Y - p2.Y;
        return (float) Math.Sqrt(x*x + y*y);
    }

    public PointF? IntersectAtDistance(LineSegment segmentToCut, float width)
    {
        // always assuming other.A is the farthest end
        var distance = width* (line.IsAboveOrRightOf(segmentToCut.A) ? 1 : -1);
        var parallelLine = line.GetParallelLine(distance);

        var p = parallelLine.Intersect(segmentToCut.line);
        if (p.HasValue)
        {
            if (LineEquation.IsBetween(line.GetNormalAt(A), p.Value, line.GetNormalAt(B)) &&
                segmentToCut.bindingRectangle.Contains(p.Value))
            {
                return p;
            }
        }

        List<PointF> points = new List<PointF>();
        points.AddRange(segmentToCut.line.Intersect(new CircleEquation(width, A)));
        points.AddRange(segmentToCut.line.Intersect(new CircleEquation(width, B)));

        return GetNearestPoint(segmentToCut.A, points);
    }

    public static PointF GetNearestPoint(PointF p, IEnumerable<PointF> points)
    {
        float minDistance = float.MaxValue;
        PointF nearestPoint = p;
        foreach (var point in points)
        {
            var d = Distance(p, point);
            if (d < minDistance)
            {
                minDistance = d;
                nearestPoint = point;
            }
        }
        return nearestPoint;
    }
}

public class LineEquation
{
    private readonly float a;
    private readonly float b;

    private readonly bool isVertical;
    private readonly float xConstForVertical;

    public LineEquation(float a, float b)
    {
        this.a = a;
        this.b = b;
        isVertical = false;
    }

    public LineEquation(float xConstant)
    {
        isVertical = true;
        xConstForVertical = xConstant;
    }

    public LineEquation(float a, PointF p)
    {
        this.a = a;
        b = p.Y - a*p.X;
        isVertical = false;
    }

    public LineEquation(PointF p1, PointF p2)
    {
        if (p1.X == p2.X)
        {
            isVertical = true;
            xConstForVertical = p1.X;
            return;
        }

        a = (p1.Y - p2.Y)/(p1.X - p2.X);
        b = p1.Y - a * p1.X;
        isVertical = false;
    }

    public PointF? Intersect(float x)
    {
        if (isVertical)
        {
            return null;
        }
        return new PointF(x, a*x + b);
    }

    public PointF? Intersect(LineEquation other)
    {
        if (isVertical && other.isVertical) return null;
        if (a == other.a) return null;

        if (isVertical) return other.Intersect(xConstForVertical);
        if (other.isVertical) return Intersect(other.xConstForVertical);

        // both have slopes and are not parallel
        var x = (b - other.b) / (other.a - a);
        return Intersect(x);
    }

    public float Distance(PointF p)
    {
        if (isVertical)
        {
            return Math.Abs(p.X - xConstForVertical);
        }
        var p1 = Intersect(0).Value;
        var p2 = Intersect(100).Value;

        var x1 = p.X - p1.X;
        var y1 = p.Y - p1.Y;
        var x2 = p2.X - p1.X;
        var y2 = p2.Y - p1.Y;

        return (float) (Math.Abs(x1*y2 - x2*y1) / Math.Sqrt(x2*x2 + y2*y2));
    }

    public bool IsAboveOrRightOf(PointF p)
    {
        return isVertical ? 
            xConstForVertical > p.X : 
            a*p.X + b > p.Y;
    }

    public static bool IsBetween(LineEquation l1, PointF p, LineEquation l2)
    {
        return l1.IsAboveOrRightOf(p) ^ l2.IsAboveOrRightOf(p);
    }

    public LineEquation GetParallelLine(float distance)
    {
        if (isVertical) return new LineEquation(xConstForVertical + distance);

        var angle = Math.Atan(a);
        float dy = (float) (distance/Math.Sin(angle));
        return new LineEquation(a, b - dy);
    }

    public LineEquation GetNormalAt(PointF p)
    {
        if (isVertical) return new LineEquation(p.X);

        var newA = -1/a;
        var newB = (a + 1/a)*p.X + b;
        return new LineEquation(newA, newB);
    }

    public PointF[] Intersect(CircleEquation circle)
    {
        var cx = circle.Center.X;
        var cy = circle.Center.Y;
        var r = circle.Radius;

        if (isVertical)
        {
            var distance = Math.Abs(cx - xConstForVertical);
            if (distance > r) return new PointF[0];
            if (distance == r) return new[] {new PointF(xConstForVertical, cy) };

            // two intersections
            var dx = cx - xConstForVertical;

            var qe = new QuadraticEquation(
                1,
                -2 * cy,
                r * r - dx * dx);

            return qe.Solve();
        }

        var t = b - cy;
        var q = new QuadraticEquation(
            1 + a*a,
            2*a*t - 2*cx,
            cx*cx + t*t - r*r);

        var solutions = q.Solve();
        for (var i = 0; i < solutions.Length; i++) 
           solutions[i] = Intersect(solutions[i].X).Value;
        return solutions;
    }
}

public class CircleEquation
{
    public float Radius { get; private set; }
    public PointF Center { get; private set; }

    public CircleEquation(float radius, PointF center)
    {
        Radius = radius;
        Center = center;
    }
}

public class QuadraticEquation
{
    public float A { get; private set; }
    public float B { get; private set; }
    public float C { get; private set; }

    public QuadraticEquation(float a, float b, float c)
    {
        A = a;
        B = b;
        C = c;
    }

    public PointF Intersect(float x)
    {
        return new PointF(x, A*x*x + B*x + C);
    }
    public PointF[] Solve()
    {
        var d = B*B - 4*A*C;
        if (d < 0) return new PointF[0];
        if (d == 0)
        {
            var x = -B / (2*A);
            return new[] { Intersect(x) };
        }

        var sd = Math.Sqrt(d);
        var x1 = (float) ((-B - sd) / (2f*A));
        var x2 = (float) ((-B + sd) / (2*A));
        return new[] { Intersect(x1), Intersect(x2) };
    }
}

public static class GraphicsPathExtension
{
    public static GraphicsPath Shrink(this GraphicsPath originalPath, float width)
    {
        originalPath.CloseAllFigures();
        originalPath.Flatten();
        var parts = originalPath.SplitFigures();
        var shrunkPaths = new List<GraphicsPath>();

        foreach (var part in parts)
        {
            using (var widePath = new GraphicsPath(part.PathPoints, part.PathTypes))
            {
                // widen the figure
                widePath.Widen(new Pen(Color.Black, width * 2));

                // pick the inner edge
                var innerEdge = widePath.SplitFigures()[1];
                var fixedPath = CleanPath(innerEdge, part, width);
                if (fixedPath.PointCount > 0)
                    shrunkPaths.Add(fixedPath);
            }
        }

        // build the result
        originalPath.Reset();
        foreach (var p in shrunkPaths)
        {
            originalPath.AddPath(p, false);
        }
        return originalPath;
    }

    public static IList<GraphicsPath> SplitFigures(this GraphicsPath path)
    {
        var paths = new List<GraphicsPath>();
        var position = 0;
        while (position < path.PointCount)
        {
            var figureCount = CountNextFigure(path.PathData, position);

            var points = new PointF[figureCount];
            var types = new byte[figureCount];

            Array.Copy(path.PathPoints, position, points, 0, figureCount);
            Array.Copy(path.PathTypes, position, types, 0, figureCount);
            position += figureCount;

            paths.Add(new GraphicsPath(points, types));
        }
        return paths;
    }

    static int CountNextFigure(PathData data, int position)
    {
        var count = 0;
        for (var i = position; i < data.Types.Length; i++)
        {
            count++;
            if (0 != (data.Types[i] & (int)PathPointType.CloseSubpath))
            {
                return count;
            }
        }
        return count;
    }

    static GraphicsPath CleanPath(GraphicsPath innerPath, GraphicsPath originalPath, float width)
    {
        var points = new List<PointF>();
        Region originalRegion = new Region(originalPath);

        // find first valid point
        int firstValidPoint = 0;
        IEnumerable<LineSegment> segs;

        while (IsPointTooClose(
                   innerPath.PathPoints[firstValidPoint], 
                   originalPath, originalRegion, width, out segs))
        {
            firstValidPoint++;
            if (firstValidPoint == innerPath.PointCount) return new GraphicsPath();
        }

        var prevP = innerPath.PathPoints[firstValidPoint];
        points.Add(prevP);

        for (int i = 1; i < innerPath.PointCount; i++)
        {
            var p = innerPath.PathPoints[(firstValidPoint + i) % innerPath.PointCount];

            if (!IsPointTooClose(p, originalPath, originalRegion, width, out segs))
            {
                prevP = p;
                points.Add(p);
                continue;
            }

            var invalidSegment = new LineSegment(prevP, p);

            // found invalid point (too close or external to original figure)
            IEnumerable<PointF> cutPoints = 
                segs.Select(seg => seg.IntersectAtDistance(invalidSegment, width).Value);
            var cutPoint = LineSegment.GetNearestPoint(prevP, cutPoints);

            // now add the cutPoint instead of 'p'.
            points.Add(cutPoint);
            prevP = cutPoint;
        }

        var types = new List<byte>();
        for (int i = 0; i < points.Count - 1; i++)
        {
            types.Add(1);
        }
        types.Add(129);

        return points.Count == 0 ?
            new GraphicsPath() :
            new GraphicsPath(points.ToArray(), types.ToArray());
    }

    static bool IsPointTooClose(
        PointF p, GraphicsPath path, Region region, 
        float distance, out IEnumerable<LineSegment> breakingSegments)
    {
        if (!region.IsVisible(p))
        {
            breakingSegments = new LineSegment[0];
            return true;
        }

        var segs = new List<LineSegment>();
        foreach (var seg in GetSegments(path))
        {
            if (seg.Distance(p) < distance)
            {
                segs.Add(seg);
            }
        }
        breakingSegments = segs;
        return segs.Count > 0;
    }

    static public IEnumerable<LineSegment> GetSegments(GraphicsPath path)
    {
        for (var i = 0; i < path.PointCount; i++)
        {
            yield return 
                new LineSegment(path.PathPoints[i], path.PathPoints[(i + 1) % path.PointCount]);
        }
    }
}

Answer 2

这是一个不错的选择.它不像@Simon那样复杂,但它提供了很好的结果(可以进一步改进),代码更简单.

我们的想法是重用现有的功能GraphicsPath.Widen以获得积分.

当我们调用Widen上GraphicsPath是由ñ封闭图形,所产生的路径具有2N边缘.每个原始图形的外边缘和内边缘.

因此,我创建一个临时路径,加宽它,并仅复制内边缘.

这是代码:

public static GraphicsPath Shrink(this GraphicsPath path, float width)
{
    using (var p = new GraphicsPath())
    {
        p.AddPath(path, false);
        p.CloseAllFigures();
        p.Widen(new Pen(Color.Black, width*2));

        var position = 0;
        var result = new GraphicsPath();
        while (position < p.PointCount)
        {
            // skip outer edge
            position += CountNextFigure(p.PathData, position);
            // count inner edge
            var figureCount = CountNextFigure(p.PathData, position);
            var points = new PointF[figureCount];
            var types = new byte[figureCount];

            Array.Copy(p.PathPoints, position, points, 0, figureCount);
            Array.Copy(p.PathTypes, position, types, 0, figureCount);
            position += figureCount;
            result.AddPath(new GraphicsPath(points, types), false);
        }
        path.Reset();
        path.AddPath(result, false);
        return path;
    }
}

static int CountNextFigure(PathData data, int position)
{
    int count = 0;
    for (var i = position; i < data.Types.Length; i++)
    {
        count++;
        if (0 != (data.Types[i] & (int) PathPointType.CloseSubpath))
        {
            return count;
        }
    }
    return count;
}

这是一个例子:

GraphicsPath path = new GraphicsPath();
path.AddString("cool", new FontFamily("Times New Roman"), 0, 300, 
    new PointF(), StringFormat.GenericDefault);
e.Graphics.DrawPath(new Pen(Color.Black, 1), path); 
path.Shrink(3);
e.Graphics.DrawPath(new Pen(Color.Red), path);

不可否认,当偏移量足够大以使形状与自身相交时,我的解决方案也会产生不希望的伪影.

编辑:

我可以很容易地检测O(n ^ 2)中的所有交点,或者用一些努力 - 使用扫描线算法(n是点数)在O(n logn)中检测它们.

但是一旦我找到了交叉点,我不知道如何确定要删除的路径的哪些部分.有人有想法吗？:)

编辑2:

实际上,我们并不需要找到数字的交叉点.

我们能做的就是扫描图上的所有点.一旦我们发现一个点在原始图形之外,或者太靠近原始图形的边缘,那么我们必须修复它.

为了固定一个点,我们看一下这个点和前一个点之间的边缘,我们必须切割这个边缘,使它现在以一个新的点结束,与原始图形保持正确的距离.

我做了一些近似于这个算法的实验(粗略但简单的算法,我完全删除了"关闭"点而不是移动它们以缩短它们的边缘,我检查了原始图形上的点的距离而不是它上面的边缘).这有一些很好的结果,删除大多数不需要的工件.

实施完整的解决方案可能需要几个小时......

编辑3:

虽然还远非完美,但我在一个单独的答案中发布了我的改进解决方案.