c# - .Net GraphicsPath.Widen() の反対

Question

GraphicsPath.Widen().Net のメソッドの反対が必要です。

public GraphicsPath Widen()

Widen()メソッドは負のパラメーターを受け入れないため、メソッドに相当するものが必要ですInset。

public GraphicsPath Inset()

オープン ソースの Inkscape アプリケーション (www.Inkscape.org) でこれを行うには、メニューに移動して [パス / インセット] を選択します (インセット量は [Inkscape プロパティ] ダイアログに保存されます)。Inkscape はオープン ソースであるため、C#.Net でこれを実行できるはずですが、一生 Inkscape C++ ソースをたどることはできません (必要なのはこの 1 つの関数だけなので、C++ の学習を正当化することはできません)。これを完了するために）。

基本的に、次のシグネチャを持つ GraphicsPath 拡張メソッドが必要です。

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

署名が述べているように、渡された量だけGraphicsPathオブジェクトと.Inset()パスを受け取ります... Inkscapeが今日行っているように。問題を単純化すると、問題の GraphicsPaths はすべて.PolyBezierメソッドから作成されます (他には何もありません)。したがって、完全を期す場合を除き、四角形、楕円形、またはその他の形状を考慮する必要はありません。

残念ながら、私は C++ コードの経験がないので、Inkscape に含まれる C++ ロジックに従うことはほぼ不可能です。

.

[編集:] リクエストに応じて、「MakeOffset」Inkscape コードを次に示します。2 番目のパラメーター (double dec) は Inset の負の値であり、そのパラメーターの絶対値は形状を取り込む量です。

ここには多くの依存関係があることを知っています。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);
}

.

[編集]

@Simon Mourier - すばらしい仕事です。コードもきれいで読みやすいものでした! よくやった、サー。ただし、いくつか質問があります。

まず、Amount の正の数は何を表しているのでしょうか。Offset メソッドの場合、正は「アウトセット」、負は「インセット」になると考えていましたが、あなたの例は逆のようです。

次に、いくつかの基本的なテスト (サンプルを拡張するだけ) を行ったところ、奇妙な点がいくつか見つかりました。

オフセットが大きくなると、cool の "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);
    }

ほら、近すぎて泣きたくなる。しかし、それでもうまくいきません。

挿入ベクトルがいつ交差するかを確認し、その時点を過ぎて挿入を停止することで修正できると思います。Inset の量が非常に大きい (またはパスが非常に小さい) ために何も残っていない場合、パス自体を元に戻して再度拡張するのではなく、パスが消える (null になる) 必要があります。

繰り返しますが、私はあなたが行ったことを決して非難しているわけではありませんが、これらの例で何が起こっているのか知っているかどうか疑問に思っていました.

(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) Figure に多くのポイントがあるため、パフォーマンスが低下することです。

2. この時点で、パフォーマンスは許容範囲内であるとしても、ほとんど許容範囲内ではありません。私のソリューションは現在、非常に単純な方法 ( O(n^n) ) でスキャンして、内側のエッジの候補点に「近すぎる」線分を見つけます。これにより、アルゴリズムが非常に遅くなります。これは、セグメントがxでソートされたデータ構造を維持することで改善できるため、距離計算の数が大幅に削減されます。

3. 使用するコードを最適化することは気にしませんでした。コードをstructs最適化してはるかに高速化できる場所は他にもたくさんあります。

4. 内部の図形がいくつかの図形に「分割」されなければならない穴のある形状 (Arial の「o」など) はサポートされていません。私はそれを実装する方法を知っていますが、もっと時間が必要です:)

5. 既存のポイントを移動して内側の図を取得するというサイモンのアプローチを、そのパスをクリーンアップする私のアプローチに適応させることを検討します。(しかし、サイモンのソリューションのバグのため、この時点では実行できませんでした。たとえば、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、ポイントを取得するために の既存の機能を再利用することです。

n 個の閉じた図形で構成されるWidenaを呼び出すと、結果のパスには2n 個のエッジがあります。元の各図形の外側と内側のエッジ。GraphicsPath

そこで、一時的なパスを作成して広げ、内側のエッジだけをコピーします。

コードは次のとおりです。

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：

まだ完璧にはほど遠いですが、改善されたソリューションを別の回答に投稿しました。

Answer 3

ここに動作するように見えるコードがあります。閉じた図形と開いた図形 (これは難しい部分です...)、正と負のオフセットをサポートします。

基本的に、パスの各ポイントでオフセット ポイントを計算します。オフセット ポイントは法線ベクトルを使用して決定されますが、実際には、2 つのオフセット ラインの交点を使用して計算されます (これは同等です)。うまく表示されない場合があります (パス チャンクが近すぎる場合、たとえばオフセットよりも近い場合)。

交差する図形のオフセットを結合/マージしないことに注意してください。ただし、これは別の話です。理論的な記事はここにあります:ポリライン カーブのオフセット アルゴリズム。

次の例で試すことができます。

protected override void OnPaint(PaintEventArgs e)
{
    GraphicsPath path = new GraphicsPath();

    path.AddString("cool", new FontFamily("Arial"), 0, 200, new PointF(), StringFormat.GenericDefault);
    path.AddEllipse(150, 50, 80, 80);
    path.AddEllipse(150 + 100, 50 + 100, 80 + 100, 80 + 100);

    GraphicsPath offset1 = Offset(path, -5);
    GraphicsPath offset2 = Offset(path, 5);

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

完全なコード:

public static GraphicsPath Offset(GraphicsPath path, float offset)
{
    if (path == null)
        throw new ArgumentNullException("path");

    // death from natural causes
    if (path.PointCount < 2)
        throw new ArgumentException(null, "path");

    PointF[] points = new PointF[path.PointCount];

    for (int i = 0; i < path.PointCount; i++)
    {
        PointF current = path.PathPoints[i];
        PointF prev = GetPreviousPoint(path, i);
        PointF next = GetNextPoint(path, i);

        PointF offsetPoint = Offset(prev, current, next, offset);
        points[i] = offsetPoint;
    }

    GraphicsPath newPath = new GraphicsPath(points, path.PathTypes);
    return newPath;
}

// get the closing point for a figure or null if none was found
private static PointF? GetClosingPoint(GraphicsPath path, ref int index)
{
    for (int i = index + 1; i < path.PointCount; i++)
    {
        if (IsClosingPoint(path, i))
        {
            index = i;
            return path.PathPoints[i];
        }
    }
    return null;
}

// get the starting point for a figure or null if none was found
private static PointF? GetStartingPoint(GraphicsPath path, ref int index)
{
    for (int i = index - 1; i >= 0; i--)
    {
        if (IsStartingPoint(path, i))
        {
            index = i;
            return path.PathPoints[i];
        }
    }
    return null;
}

// get a previous point to compute normal vector at specified index
private static PointF GetPreviousPoint(GraphicsPath path, int index)
{
    if (IsStartingPoint(path, index))
    {
        int closingIndex = index;
        PointF? closing = GetClosingPoint(path, index, ref closingIndex);
        if (closing.HasValue)
        {
            if (closing.Value != path.PathPoints[index])
                return closing.Value;

            return GetPreviousPoint(path, closingIndex);
        }
    }
    else
    {
        return path.PathPoints[index - 1];
    }

    // we are on an unclosed end point, emulate a prev point on the same line using next point
    PointF point = path.PathPoints[index];
    PointF next = path.PathPoints[index + 1];
    return VectorF.Add(point, VectorF.Substract(point, next));
}

// get a next point to compute normal vector at specified index
private static PointF GetNextPoint(GraphicsPath path, int index)
{
    if (IsClosingPoint(path, index))
    {
        int startingIndex = index;
        PointF? starting = GetStartingPoint(path, ref startingIndex);
        if (starting.HasValue)
        {
            // some figures (Ellipse) are closed with the same point as the starting point
            // in this case, we need the starting point's next point
            if (starting.Value != path.PathPoints[index])
                return starting.Value;

            return GetNextPoint(path, startingIndex);
        }
    }
    else if ((index != (path.PointCount - 1)) && (!IsStartingPoint(path, index + 1)))
    {
        return path.PathPoints[index + 1];
    }

    // we are on an unclosed end point, emulate a next point on the same line using previous point
    PointF point = path.PathPoints[index];
    PointF prev = path.PathPoints[index - 1];
    return VectorF.Add(point, VectorF.Substract(point, prev));
}

// determine if a point is a closing point
private static bool IsClosingPoint(GraphicsPath path, int index)
{
    return (path.PathTypes[index] & (byte)PathPointType.CloseSubpath) == (byte)PathPointType.CloseSubpath;
}

// determine if a point is a starting point
private static bool IsStartingPoint(GraphicsPath path, int index)
{
    return (path.PathTypes[index] == (byte)PathPointType.Start);
}

// offsets a Point using the normal vector (actually computed using intersection or 90° rotated vectors)
private static PointF Offset(PointF prev, PointF current, PointF next, float offset)
{
    VectorF vnext = VectorF.Substract(next, current);
    vnext = vnext.DegreeRotate(Math.Sign(offset) * 90);
    vnext = vnext.Normalize() * Math.Abs(offset);
    PointF pnext1 = current + vnext;
    PointF pnext2 = next + vnext;

    VectorF vprev = VectorF.Substract(prev, current);
    vprev = vprev.DegreeRotate(-Math.Sign(offset) * 90);
    vprev = vprev.Normalize() * Math.Abs(offset);
    PointF pprev1 = current + vprev;
    PointF pprev2 = prev + vprev;

    PointF ix = VectorF.GetIntersection(pnext1, pnext2, pprev1, pprev2);
    if (ix.IsEmpty)
    {
        // 3 points on the same line, just translate (both vectors are identical)
        ix = current + vnext;
    }
    return ix;
}

// a useful Vector class (does not exists in GDI+, why?)
[Serializable, StructLayout(LayoutKind.Sequential)]
public struct VectorF : IFormattable, IEquatable<VectorF>
{
    private float _x;
    private float _y;

    public VectorF(float x, float y)
    {
        _x = x;
        _y = y;
    }

    public float X
    {
        get
        {
            return _x;
        }
        set
        {
            _x = value;
        }
    }

    public float Y
    {
        get
        {
            return _y;
        }
        set
        {
            _y = value;
        }
    }

    public double Length
    {
        get
        {
            return Math.Sqrt(_x * _x + _y * _y);
        }
    }

    public VectorF Rotate(double angle)
    {
        float cos = (float)Math.Cos(angle);
        float sin = (float)Math.Sin(angle);
        return new VectorF(_x * cos - _y * sin, _x * sin + _y * cos);
    }

    public VectorF DegreeRotate(double angle)
    {
        return Rotate(DegreeToGradiant(angle));
    }

    public static PointF GetIntersection(PointF start1, PointF end1, PointF start2, PointF end2)
    {
        float denominator = ((end1.X - start1.X) * (end2.Y - start2.Y)) - ((end1.Y - start1.Y) * (end2.X - start2.X));
        if (denominator == 0) // parallel
            return PointF.Empty;

        float numerator = ((start1.Y - start2.Y) * (end2.X - start2.X)) - ((start1.X - start2.X) * (end2.Y - start2.Y));
        float r = numerator / denominator;

        PointF result = new PointF();
        result.X = start1.X + (r * (end1.X - start1.X));
        result.Y = start1.Y + (r * (end1.Y - start1.Y));
        return result;
    }

    public static PointF Add(PointF point, VectorF vector)
    {
        return new PointF(point.X + vector._x, point.Y + vector._y);
    }

    public static VectorF Add(VectorF vector1, VectorF vector2)
    {
        return new VectorF(vector1._x + vector2._x, vector1._y + vector2._y);
    }

    public static VectorF Divide(VectorF vector, float scalar)
    {
        return vector * (1.0f / scalar);
    }

    public static VectorF Multiply(float scalar, VectorF vector)
    {
        return new VectorF(vector._x * scalar, vector._y * scalar);
    }

    public static VectorF Multiply(VectorF vector, float scalar)
    {
        return Multiply(scalar, vector);
    }

    public static VectorF operator *(float scalar, VectorF vector)
    {
        return Multiply(scalar, vector);
    }

    public static VectorF operator *(VectorF vector, float scalar)
    {
        return Multiply(scalar, vector);
    }

    public static PointF operator -(PointF point, VectorF vector)
    {
        return Substract(point, vector);
    }

    public static PointF operator +(VectorF vector, PointF point)
    {
        return Add(point, vector);
    }

    public static PointF operator +(PointF point, VectorF vector)
    {
        return Add(point, vector);
    }

    public static VectorF operator +(VectorF vector1, VectorF vector2)
    {
        return Add(vector1, vector2);
    }

    public static VectorF operator /(VectorF vector, float scalar)
    {
        return Divide(vector, scalar);
    }

    public static VectorF Substract(PointF point1, PointF point2)
    {
        return new VectorF(point1.X - point2.X, point1.Y - point2.Y);
    }

    public static PointF Substract(PointF point, VectorF vector)
    {
        return new PointF(point.X - vector._x, point.Y - vector._y);
    }

    public static double AngleBetween(VectorF vector1, VectorF vector2)
    {
        double y = (vector1._x * vector2._y) - (vector2._x * vector1._y);
        double x = (vector1._x * vector2._x) + (vector1._y * vector2._y);
        return Math.Atan2(y, x);
    }

    private static double GradiantToDegree(double angle)
    {
        return (angle * 180) / Math.PI;
    }

    private static double DegreeToGradiant(double angle)
    {
        return (angle * Math.PI) / 180;
    }

    public static double DegreeAngleBetween(VectorF vector1, VectorF vector2)
    {
        return GradiantToDegree(AngleBetween(vector1, vector2));
    }

    public VectorF Normalize()
    {
        if (Length == 0)
            return this;

        VectorF vector = this / (float)Length;
        return vector;
    }

    public override string ToString()
    {
        return ToString(null, null);
    }

    public string ToString(string format, IFormatProvider provider)
    {
        return string.Format(provider, "{0:" + format + "};{1:" + format + "}", _x, _y);
    }

    public override int GetHashCode()
    {
        return _x.GetHashCode() ^ _y.GetHashCode();
    }

    public override bool Equals(object obj)
    {
        if ((obj == null) || !(obj is VectorF))
            return false;

        return Equals(this, (VectorF)obj);
    }

    public bool Equals(VectorF value)
    {
        return Equals(this, value);
    }

    public static bool Equals(VectorF vector1, VectorF vector2)
    {
        return (vector1._x.Equals(vector2._x) && vector1._y.Equals(vector2._y));
    }
}

Answer 4

OK、手がかりはあると思いますが、それはまったく別の方向に進んでいます。

とにかく、より大きなパスの「サブパス」が.Widen操作中に実際に縮小 (インセット) することに気付きました。

本当に、ここでのアイデア.Widenはパスへの... 外からです!

オリジナルGraphicsPathをより大きなものに「ラップ」するとどうなるでしょうかRectangle( のInflateで 10 を実行する.GetBoundsとGraphicsPath、簡単なラッパーが得られるはずです)。

次に、最初にラッパーが追加GraphicsPathされ、そのサブパスとして real が追加されます。次に、全体が を取得し、最後に、拡張されたパスのandを使用して、ゼロから.Widen新しいGraphicsPathものが作成されます。.PathPoints.PathTypesGraphicsPathPathPointsPathTypes

残りの時間はオフィスにいないので、完成までは見えませんが、ここにリードがあります。

このコードを通常の古い形式にドロップするだけです:

        private void Form1_Paint(object sender, PaintEventArgs e)
        {
            GraphicsPath g = new GraphicsPath();
            g.AddRectangle(new Rectangle(0, 0, 200, 200));
            g.AddEllipse(50, 50, 100, 100);

            //Original path
            e.Graphics.DrawPath(new Pen(Color.Black,2), g);

            //"Inset" path
            g.Widen(new Pen(Color.Black, 10));
            e.Graphics.DrawPath(new Pen(Color.Red, 2), g);
        }

この簡単な実験から、ターゲット パス (円) にとらえどころのないインセット (赤) があることがわかります。

そこには私が本当に理解していない他のがらくたもあります（これは長方形ラッパーにも表示されます）が、PathPointsとからPathTypes、バージンGraphicsPathが作成されたときに配列を反復してジャンクを削除できるはずです（またはそのジャンクがどこから来ているかを見つけて、それが起こらないようにします)。次に、新しい clean を返しGraphicsPathます。

この手法は、複雑な計算をすべて回避しますが、少し遠回りです。