Menu
I need the opposite of the GraphicsPath.Widen() method in .Net:
public GraphicsPath Widen()
The Widen() method does not accept a negative parameter, so I need the equivalent of an Inset method:
public GraphicsPath Inset()
You can do this in the open source Inkscape application (www.Inkscape.org) by going to menu and selecting "Path / Inset" (the Inset amount is stored in the Inkscape Properties dialog). Since Inkscape is open source, it should be possible to do this in C#.Net, but I can't follow the the Inkscape C++ source for the life of me (and I just need this one function so I can't justify learning C++ to complete this).
Basically, I need a GraphicsPath extension method with this signature:
public static GraphicsPath Inset(this GraphicsPath original, float amount)
{
//implementation
}
As the signature states, it will take a GraphicsPath object and .Inset() the path by a passed amount... just like Inkscape does today. If it simplifies matters any, the GraphicsPaths in question are all created from the .PolyBezier method (and nothing else), so there is no need to account for rects, ellipses, or any other shapes unless you want to do it for completeness.
Unfortunately, I have no experience with C++ code, so its just about impossible for me to follow the C++ logic contained in Inkscape.
.
[EDIT:] As requested, here is the "MakeOffset" Inkscape code. The second parameter (double dec) will be negative for an Inset, and the absolute value of that parameter is the amount to bring in the shape.
I know that there are a lot of dependencies here. If you need to see more of the Inkscape source files, they are here: 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 - Amazing work. The code was even clean and readable! Nice work, sir. I did have a couple of questions for you, though.
First, what does a positive number for the Amount represent? I was thinking that for the Offset method, positive would be "outset" and negative would be "inset", but your example seems to do the opposite.
Second, I did some basic testing (just extending your sample), and found some oddities.
Here is what happens to the "l" in cool when the offset grows (for such a simple letter, it sure likes to cause problems!).
...and the code to reproduce that one:
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);
}
Finally, something a little different. Here is the "S" character from Wingdings (appears like a tear drop):
Here is the code:
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);
}
Man, this is so close, it makes me want to cry. It still doesn't work, though.
I think what would fix it is to see when the inset vectors intersect, and stop insetting past that point. If the Inset amount is so large (or the path so small) that there is nothing left, the path should disappear (become null), instead of reversing on itself and re-expanding.
Again, I'm not knocking what you've done in any way, but I was wondering if you know what might be going on with these examples.
(PS - I added the 'this' keyword to make it an extension method, so you might need to call the code using method(parameters) notation to get these samples to run)
.
@RAN Ran come up with a similar output, by re-using the GraphicsPath native methods. Man, this is tough. Both of them are so close.
Here is a screen shot of both examples, using the character "S" from Wingdings:
@Simon is on the left, @Ran on the right.
Here is the same tear drop "S" character after doing an "Inset" in Inkscape. The Inset is clean:
By the way, here is the code for @Ran's test:
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);
}
366
I'll still post my new solution, even though it's not perfect, with some list of problems that need to be fixed. Maybe you will want to take parts of it and improve them, or maybe there's some learning value in it.
First of all, the picture - my best inset teardrop symbol:
What I've done
I used GraphicsPath.Widen to generate the "inner" and "outer" edges of the given figure.
I scanned the points of the resulting GraphicsPath, to remove the outer edge and keep only the inner one.
I flattened the inner edge using GraphicsPath.Flatten so that the figures consist only of line segments (no curves).
I then scanned all the points on the inner path, and for each current segment:
4.1. If the current point p is outside of the original path, or is too close to a segment on the original path, I calculate a new point, on the current edge, which is in the desired distance from the original path, and I take this point instead of p, and connect it to the part I've already scanned.
4.2. A current limitation in the solution: I continue from the calculated point, to scan onward. This means that there is not good support for shapes with holes (e.g. the Arial "o"). To fix this, one would have to maintain a list of "disconnected" figures, and reconnect figures that have ends at the same point (or ends that are "close enough" to each other).
The problems
First I'll specifiy the most major problems and limitations, and then I'll post the code itself.
It seems that GraphicsPath.Widen does not produce a clean shape. The inner figure that I get has small (but mostly invisible) "jaggedness". The significance of this is that A) my culling algorithm generates more noise, and B) the figure has more points, so performance degrades.
Performance is barely acceptable, if at all, at this point. My solution currently scans in a very naive way (in O(n^n)) to find line segments that are "too near" the candidate points on the inner edge. This causes the algorithm to be very slow. It can be improved by maintaining some data structure in which segments are sorted by x, so that the number of distance calculations is dramatically reduced.
I didn't bother to optimize the code to use structs and there are a lot of other places the code can be optimized to be much much faster.
There is no support for shapes with holes, where the inner figure has to "split" into several figures (like the Arial "o"). I know how to implement it, but it needs more time :)
I would consider adapting Simon's approach of moving existing points to get the inner figure, with my approach to clean that path up. (But I couldn't do it at this point because of a bug in Simon's solution, which, for example, causes the pointed end of the Tear symbol to move to a valid location inside the shape. My algorithm thinks this location is valid and doesn't clean it up).
The code
I couldn't avoid coming up with some math/geometry utilities of my own. So here's the code...
Personally, I think this can be worthy of the bounty, even though it's not a perfect solution... :)
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]);
}
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
