c# - .Net Opuesto a GraphicsPath.Widen()

open-source

Question

Necesito lo contrario del método GraphicsPath.Widen() en .Net:

public GraphicsPath Widen()

El método Widen() no acepta un parámetro negativo, por lo que necesito el equivalente de un método Inset :

public GraphicsPath Inset()

Puede hacer esto en la aplicación Inkscape de código abierto (www.Inkscape.org) yendo al menú y seleccionando "Ruta / Insertar" (la cantidad de la inserción se almacena en el cuadro de diálogo Propiedades de Inkscape). Ya que Inkscape es de código abierto, debería ser posible hacer esto en C # .Net, pero no puedo seguir la fuente de Inkscape C ++ de por vida (y solo necesito esta función, por lo que no puedo justificar el aprendizaje de C ++ para completar esto).

Básicamente, necesito un método de extensión GraphicsPath con esta firma:

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

Como indica la firma, tomará un objeto GraphicsPath y .Inset() la ruta por una cantidad pasada ... tal como lo hace hoy Inkscape. Si simplifica las cuestiones, los GraphicsPaths en cuestión se crean a partir del método .PolyBezier (y nada más), por lo que no es necesario tener en cuenta los rects, los elipses o cualquier otra forma, a menos que desee hacerlo por completo.

Desafortunadamente, no tengo experiencia con el código C ++, por lo que es casi imposible para mí seguir la lógica C ++ contenida en Inkscape.

.

[EDIT:] Según lo solicitado, aquí está el código de Inkscape "MakeOffset". El segundo parámetro (doble dec) será negativo para una inserción, y el valor absoluto de ese parámetro es la cantidad a traer en la forma.

Sé que hay muchas dependencias aquí. Si necesita ver más de los archivos fuente de Inkscape, están aquí: 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);
}

.

[EDITAR]

@Simon Mourier - Increíble trabajo. ¡El código era incluso limpio y legible! Buen trabajo, señor. Sin embargo, tuve un par de preguntas para ti.

Primero, ¿qué representa un número positivo para la cantidad? Estaba pensando que para el método de compensación, lo positivo sería "inicial" y lo negativo sería "inserción", pero su ejemplo parece hacer lo contrario.

Segundo, hice algunas pruebas básicas (solo extendiendo su muestra) y encontré algunas rarezas.

Esto es lo que le sucede a la "l" en frío cuando la compensación aumenta (para una letra tan simple, ¡seguro que le causa problemas!).

... y el código para reproducir ese:

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

Finalmente, algo un poco diferente. Aquí está el carácter "S" de Wingdings (aparece como una gota de lágrima):

Aquí está el código:

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

Hombre, esto está tan cerca, me da ganas de llorar. Sin embargo, todavía no funciona.

Creo que lo que lo solucionaría es ver cuándo los vectores de inserción se intersecan y dejar de insertar más allá de ese punto. Si la cantidad del recuadro es tan grande (o el camino es tan pequeño) que no queda nada, el camino debería desaparecer (hacerse nulo), en lugar de revertirse sobre sí mismo y volver a expandirse.

Nuevamente, no estoy golpeando lo que has hecho de ninguna manera, pero me preguntaba si sabes qué podría estar pasando con estos ejemplos.

(PS: agregué la palabra clave ''this'' para convertirlo en un método de extensión, por lo que es posible que deba llamar al código usando la notación del método (parámetros) para que se ejecuten estas muestras)

.

@RAN Ran produjo un resultado similar, reutilizando los métodos nativos GraphicsPath. Hombre, esto es duro. Ambos están tan cerca.

Aquí hay una captura de pantalla de ambos ejemplos, usando el carácter "S" de Wingdings:

@Simon está a la izquierda, @Ran a la derecha.

Aquí está el mismo carácter "S" de la lágrima después de hacer una "inserción" en Inkscape. El recuadro está limpio:

Por cierto, aquí está el código para la prueba de @Rad:

 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

Aquí hay un código que parece funcionar. Admite cifras cerradas y abiertas (esa es la parte difícil ...), compensaciones positivas y negativas.

Básicamente, en cada punto de la ruta, calcula un punto de compensación. El punto de desplazamiento se determina utilizando el vector normal, pero de hecho, se calcula utilizando la intersección de las dos líneas de desplazamiento (que es equivalente). Hay algunos casos en los que no se mostrará bien (si los fragmentos de ruta están demasiado cerca, por ejemplo, más cerca que el desplazamiento).

Tenga en cuenta que no se combinan / fusionan desplazamientos para intersectar figuras, pero esta es otra historia. Un artículo teórico se puede encontrar aquí: Un algoritmo de desplazamiento para curvas de polilínea .

Puedes probarlo con este ejemplo:

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

El código completo:

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 2

Aquí hay una buena alternativa. No es tan sofisticado como el de @ Simon, pero da buenos resultados (que pueden mejorarse aún más), con un código mucho más simple.

La idea es reutilizar la funcionalidad existente de GraphicsPath.Widen para obtener los puntos.

Cuando llamamos a Widen en un GraphicsPath que consta de n figuras cerradas, la ruta resultante tiene 2n bordes. Un borde exterior e interior para cada figura original.

Por lo tanto, creo una ruta temporal, la amplío y copio solo los bordes internos.

Aquí está el código:

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

Y he aquí un ejemplo:

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

Es cierto que mi solución también tiene artefactos no deseados cuando el desplazamiento es lo suficientemente grande como para hacer que la forma se intersecte consigo misma.

EDITAR:

Puedo detectar fácilmente todos los puntos de intersección en O ( n ^ 2 ), o con algún esfuerzo, detectarlos en O ( n logn ), usando un algoritmo de línea de barrido ( n es el número de puntos).

Pero una vez que he encontrado los puntos de intersección, no estoy seguro de cómo decidir qué partes de la ruta eliminar. Alguien tiene una idea? :)

EDIT 2:

En realidad, no necesitamos encontrar intersecciones de las figuras.

Lo que podemos hacer es escanear todos los puntos en la figura. Una vez que encontramos un punto que está fuera de la figura original, o está demasiado cerca de un borde de la figura original, entonces tenemos que arreglarlo.

Para fijar un punto, miramos el borde entre este punto y el anterior, y tenemos que cortarlo para que ahora termine en un nuevo punto, a la distancia correcta de la figura original.

He realizado algunos experimentos con una aproximación de este algoritmo (con un algoritmo simple pero simple en el que eliminé los puntos de "apagado" por completo en lugar de moverlos para acortar su borde, y verifiqué las distancias a los puntos en la figura original en lugar de a bordes en ella). Esto tuvo algunos buenos resultados de eliminar la mayoría de los artefactos no deseados.

Implementar la solución completa probablemente tomaría algunas horas ...

EDITAR 3:

Aunque aún lejos de ser perfecto, publiqué mi solución mejorada en una respuesta por separado.

Answer 3

Seguiré publicando mi nueva solución, aunque no sea perfecta, con una lista de problemas que deben solucionarse. Tal vez desee tomar parte de ella y mejorarla, o tal vez tenga algo de valor de aprendizaje.

En primer lugar, la imagen, mi mejor recuadro de lágrima:

Qué he hecho

1. Utilicé GraphicsPath.Widen para generar los bordes "internos" y "externos" de la figura dada.

2. Escané los puntos de la GraphicsPath resultante, para eliminar el borde exterior y mantener solo el interior.

3. Aplané el borde interior utilizando GraphicsPath.Flatten para que las figuras consten solo de segmentos de línea (sin curvas).

4. Luego escanee todos los puntos en la ruta interna, y para cada segmento actual:

   4.1. Si el punto actual p está fuera de la ruta original, o está demasiado cerca de un segmento en la ruta original, calculo un nuevo punto, en el borde actual, que está a la distancia deseada de la ruta original, y tomo esto apunte en lugar de p , y conéctelo a la parte que ya he escaneado.

   4.2. Una limitación actual en la solución: continúo desde el punto calculado, para escanear hacia adelante. Esto significa que no hay un buen soporte para las formas con orificios (por ejemplo, la "o" Arial). Para solucionar esto, uno tendría que mantener una lista de figuras "desconectadas" y volver a conectar las figuras que tienen extremos en el mismo punto (o extremos que están "lo suficientemente cerca" entre sí).

Los problemas

Primero especificaré los problemas y limitaciones más importantes, y luego publicaré el código en sí.

1. Parece que GraphicsPath.Widen no produce una forma limpia. La figura interior que obtengo tiene "irregularidades" pequeñas (pero en su mayoría invisibles). El significado de esto es que A) mi algoritmo de selección genera más ruido y B) la figura tiene más puntos, por lo que el rendimiento se degrada.

2. El rendimiento es apenas aceptable, en todo caso, en este punto. Mi solución actualmente escanea de forma muy ingenua (en O (n ^ n) ) para encontrar segmentos de línea que están "demasiado cerca" de los puntos candidatos en el borde interior. Esto hace que el algoritmo sea muy lento. Se puede mejorar manteniendo cierta estructura de datos en la que los segmentos están ordenados por x , de modo que el número de cálculos de distancia se reduce drásticamente.

3. No me molesté en optimizar el código para usar structs y hay muchos otros lugares donde el código puede optimizarse para ser mucho más rápido.

4. No hay soporte para formas con agujeros, donde la figura interior tiene que "dividirse" en varias figuras (como la "o" Arial). Sé cómo implementarlo, pero necesita más tiempo :)

5. Consideraría adaptar el enfoque de Simon de mover los puntos existentes para obtener la figura interior, con mi enfoque para limpiar ese camino. (Pero no pude hacerlo en este momento debido a un error en la solución de Simon, que, por ejemplo, hace que el extremo puntiagudo del símbolo Tear se mueva a una ubicación válida dentro de la forma. Mi algoritmo cree que esta ubicación es válida y no lo limpia).

El código

No pude evitar tener mis propias utilidades de matemática / geometría. Así que aquí está el código ...

Personalmente, creo que esto puede ser digno de la recompensa, aunque no sea una solución perfecta ... :)

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 4

Ok, creo que tengo una ventaja para ustedes ... pero está en una dirección completamente diferente.

De todos modos, me di cuenta de que una "ruta secundaria" de un camino más grande en realidad se encoge (se inserta) durante una .Widenoperación, por lo que decidí ver si había algo fructífero en ese camino (no pretendía hacerlo).

Realmente, la idea aquí es hacia .Widenel camino ... ¡desde afuera!

¿Qué pasa si tomamos el original GraphicsPathy ''envuelto'' en una más grande Rectangle(haciendo una Inflatede 10 en la .GetBoundsde la GraphicsPathnos debe obtener una envoltura fácil).

Luego, primero se agrega la envoltura y lo real GraphicsPathse agrega como una ruta secundaria a eso. La cosa completa se obtiene una .Widen, y finalmente, GraphicsPathse crea una nueva desde cero, utilizando la ruta .PathPointsy .PathTypesde la ruta ampliada, que elimina la envoltura inútil (afortunadamente, la GraphicsPathacepta PathPointsy PathTypesen una de las sobrecargas del constructor).

Estaré fuera de la oficina por el resto del día, así que no puedo completar esto, pero aquí está la ventaja.

Simplemente suelte este código en una forma regular:

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

A partir de ese sencillo experimento, verás que la ruta de destino (el círculo) ahora tiene el Inserto difícil de alcanzar (en rojo).

También hay alguna otra mierda que realmente no entiendo allí (que también aparece en la envoltura del rectángulo), pero a partir de PathPointsy PathTypes, debería ser posible iterar los arreglos y eliminar la basura cuando se crea el GraphicsPath virgen ( o averigüe de dónde viene esa basura y evite que suceda). Luego devuelve lo nuevo, limpio GraphicsPath.

Esta técnica evita todas las matemáticas complejas, pero es un poco remota.