.Net Напротив GraphicsPath.Widen()

Question

мне нужна противоположность методу GraphicsPath.Widen() в .Net:

public GraphicsPath Widen() 

Метод Widen() не принимает отрицательный параметр, поэтому необходимо установить эквивалент Inset метода :

public GraphicsPath Inset() 

Вы можете сделать это с открытым исходным кодом Inkscape приложения (www.Inkscape.org), перейдя в меню и выбрав пункт «Path/Врезка» (сумма Врезка хранится в диалоге Inkscape Properties). Поскольку Inkscape является открытым исходным кодом, это должно быть возможно сделать в C# .Net, но я не могу следить за источником Inkscape C++ для жизни меня (и мне просто нужна эта одна функция, поэтому я не могу оправдать изучение C++ для этого).

В принципе, мне нужен метод GraphicsPath расширения с этой подписью:

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

В подписи государств, это займет GraphicsPath объект и .Inset() путь на пройденную сумму ... так же, как Inkscape делает сегодня , Если это упрощает какие-либо вопросы, все рассматриваемые GraphicsPaths создаются из метода .PolyBezier (и ничего больше), поэтому нет необходимости регистрировать прямоугольники, эллипсы или любые другие фигуры, если вы не хотите сделать это для полноты.

К сожалению, у меня нет опыта работы с кодом на C++, поэтому для меня почти невозможно следовать логике C++, содержащейся в Inkscape.

.

[EDIT:] В соответствии с запросом здесь приведен код Inkscape «MakeOffset». Второй параметр (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); 
} 

.

[редактирует]

@Simon Mourier - Удивительная работа. Код был даже чистым и читаемым! Хорошая работа, сэр. Тем не менее, у меня было несколько вопросов.

Во-первых, что представляет собой положительное число для суммы? Я думал, что для метода Offset положительный будет «начальным», а отрицательным будет «вставка», но ваш пример, похоже, делает обратное.

Во-вторых, я провел некоторое базовое тестирование (просто расширив ваш образец) и нашел некоторые странности.

Вот что происходит с «л» в прохладе, когда смещение растет (для такого простого письма ему очень нравится создавать проблемы!).

...и код для его воспроизведения:

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

И, наконец, что-то совсем другое. Вот «S» символ из Wingdings (появляется как капля слезы):

Вот код:

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 - я добавил «это» ключевое слово, чтобы сделать его метод расширения, так что вам может понадобиться для вызова кода с помощью метода (параметры) нотацию, чтобы получить эти образцы для запуска)

.

@RAN Ran придумал аналогичный вывод, повторно используя собственные методы GraphicsPath. Человек, это сложно. Оба они так близки.

Вот снимок экрана обоих примеров, с помощью символа "S" от Wingdings:

@Simon находится на левой стороне, @Ran справа.

Вот такой же символ «S» с отрывным следом после выполнения «Вставки» в Inkscape. Врезка чистый:

Кстати, вот код для теста @ Ран:

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»). Чтобы исправить это, нужно было бы сохранить список «отключенных» фигур и повторно подключить цифры, которые заканчиваются в одной и той же точке (или заканчиваются «достаточно близко» друг к другу).

Проблемы

Сначала я specifiy самые основные проблемы и ограничения, а потом я выложу сам код.

1. Похоже, что GraphicsPath.Widen не производит чистую форму. Внутренняя фигура, которую я получаю, имеет небольшую (но в основном невидимую) «зубчатость». Значимость этого заключается в том, что A) мой алгоритм отбраковки генерирует больше шума, а B) у фигуры больше точек, поэтому производительность ухудшается.

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

Хорошо, я думаю, что есть зацепка для вас, ребята ... но его в совершенно другом направлении.

В любом случае, я понял, что «подпуть» большого пути фактически сжимается (вставки) во время операции .Widen, поэтому я решил посмотреть, было ли что-то плодотворное по этому пути (каламбур не предназначен).

Действительно, идея здесь - .Widen путь ... снаружи!

Что делать, если мы взяли оригинальную GraphicsPath и «обернут» это в большей Rectangle (делать в Inflate из 10 на .GetBounds в GraphicsPath должны получить нам легкую обертку).

Затем сначала добавляется обертка, а реальная GraphicsPath добавляется как подпуть к ней.Все, что потом получает .Widen, и, наконец, новый GraphicsPath создаются с нуля, используя .PathPoints и .PathTypes из расширенного пути, который удаляет ненужную оболочку (к счастью, то GraphicsPath принимает PathPoints и PathTypes в одном из конструктора перегрузок) ,

Я останусь в офисе до конца дня, так что я не вижу этого до конца, но вот впереди.

Просто поместите этот код в виде регулярного Ol»:

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

Из этого простого эксперимента, вы увидите, что целевой путь (круг) теперь имеет неуловимое Inset (в красном)!

Существует также некоторые другие дерьмо, что я не очень понимаю там (который также появляется на прямоугольнике обертке), но из PathPoints и PathTypes, она должна быть обеспечена возможность перебирать массивов и удалите мусор, когда создается девственная GraphicsPath (или узнайте, откуда этот хлам и предотвратит его). Затем верните новый, чистый GraphicsPath.

Этот метод позволяет избежать всей сложной математики, но ее немного длинный снимок.

Answer 3

Вот код, который, кажется, работает. Он поддерживает закрытые & открытые фигуры (это сложная часть ...), положительная & отрицательные смещения.

В принципе, в каждой точке пути он вычисляет точку смещения. Точка смещения определяется с использованием нормального вектора, но на самом деле она вычисляется с использованием пересечения двух линий смещения (что эквивалентно). Есть некоторые случаи, когда он не будет отображаться красиво (если фрагменты пути слишком близки, ближе к смещению, например).

Обратите внимание, что он не объединяет смещения/смещения для пересекающихся фигур, но это уже другая история. Теоретическую статью можно найти здесь: An offset algorithm for polyline curves.

Вы можете попробовать этот пример:

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

Вот хорошая альтернатива. Это не так сложно, как @ 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); 

Правда, мое решение также нежелательными артефактами, когда смещение достаточно велико, чтобы вызвать форму пересекающийся с сам.

EDIT:

можно легко обнаружить все точки пересечения в O (п^2), или с некоторым усилием - обнаружить их в O (п LOGN), используя алгоритм развертки линии (n - количество точек).

Но как только я нашел точки пересечения, я не уверен, как решить, какие части пути удалить. У кого-то есть идея? :)

EDIT 2:

На самом деле, мы на самом деле не нужно, чтобы найти пересечение фигур.

Что мы можем сделать, это сканировать все точки на рисунке. Как только мы нашли точку, которая находится либо за пределами исходного рисунка, либо слишком близко к краю на исходной фигуре, тогда мы должны ее исправить.

Для того, чтобы исправить точку, мы смотрим на грань между этой точкой и предыдущей, и мы должны разрезать этот край так, чтобы он теперь заканчивался в новой точке, на правильном расстоянии от исходного рисунка ,

Я провел несколько экспериментов с приблизительным алгоритмом (с грубым, но легким алгоритмом, где я полностью удалял «выключенные» точки, вместо того, чтобы перемещать их, чтобы сократить их край, и я проверил расстояния до точек на оригинале фигура вместо краев на нем). Это привело к хорошим результатам устранения большинства нежелательных артефактов.

Для реализации полного решения, вероятно, займет несколько часов ...

EDIT 3:

Хотя все еще далеко от совершенства, я отправил свое усовершенствованное решение в отдельном ответе.