计算给定水平线处的形状宽度
Calculation of shape width at given horizontal line
假设我有这样一个多边形
public partial class Window2 : Window
{
public Window2()
{
InitializeComponent();
var myPolygon = new Polygon();
myPolygon.Stroke = Brushes.Black;
myPolygon.Fill = Brushes.LightSeaGreen;
myPolygon.StrokeThickness = 2;
myPolygon.Points = new PointCollection(new Point[] {
new Point(50,50),
new Point(50,165),
new Point(140,165),
new Point(140,120),
new Point(70,120),
new Point(80,70),
new Point(140,70),
new Point(140,50)
});
this.Content = myPolygon;
}
}
假设我想绘制从一边到另一边穿过多边形的红线,如下图所示:
我只知道这条线应该站在哪个垂直位置,但是我怎么知道我应该从哪个水平点开始这条线,从哪个水平点结束这条线呢?
我的主要目标是知道这条线在哪个水平点开始,在哪个水平点结束,以便在这条线上排列文本。
如果线在多个地方穿过形状(如下图),我想得到所有线的数组:
请注意,形状可以由直线和拱形组成。
以下是 Adobe Illustrator 排列文本的方式:
如何在 C# 中执行此操作?
谢谢!
注意:如需悬赏,请附上 C# 示例。
注意:此答案不是关于计算适当的线大小(算术结果),而是关于仅在多边形上显示线(视觉结果)。如果您需要数学,请更改问题上的标签。
您可以绘制完整尺寸的线条,并使用与多边形相等的几何形状对其进行剪裁。假设您将多边形和线托管在名为 grid1
:
的网格中
private void DrawLine(Polygon myPolygon, int linePos)
{
var clip = new StreamGeometry();
using (var context = clip.Open())
{
context.BeginFigure(myPolygon.Points.First(), true, true);
context.PolyLineTo(myPolygon.Points.Skip(1).ToList(), true, false);
}
var line = new Line()
{
X1 = 0,
X2 = Width,
Y1 = linePos,
Y2 = linePos,
Stroke = Brushes.Red,
StrokeThickness = 2,
Clip = clip
};
grid1.Children.Add(line);
}
结合问题中的代码:
var myPolygon = new Polygon();
myPolygon.Stroke = Brushes.Black;
myPolygon.Fill = Brushes.LightSeaGreen;
myPolygon.StrokeThickness = 2;
myPolygon.Points = new PointCollection(new Point[]
{
new Point(50,50),
new Point(50,165),
new Point(140,165),
new Point(140,120),
new Point(70,120),
new Point(80,70),
new Point(140,70),
new Point(140,50)
});
grid1.Children.Add(myPolygon);
DrawLine(myPolygon, 80);
DrawLine(myPolygon, 150);
感谢 Clemens WPF Clipping with a shape 从点创建几何的方法。
如果您计划绘制多条线,您可以选择在父面板上定义一个剪裁,这样内部的所有内容都将被剪裁到多边形边界。
我会说你唯一的选择是测试红线是否与多边形的 any/some segments/arcs 相交。
蛮力是第一个想法。第二个想法是使用 Fortune's algorithm
因为你的红线是水平的,这有点帮助。
如果将多边形的片段存储在按 Y 最小坐标排序的数组中,则可以从测试中跳过红线以下的所有片段。
这个下限很容易通过二分查找找到。
一些实用链接:
How do you detect where two line segments intersect?
Line Segment Circle Intersection
- 你要把形状分成直线和曲线
- 检查下面提供的代码,了解这些与您的红线相交的直线/曲线
- 最后你会得到至少两条相交的直线/曲线,这样你就会知道红线的宽度。
检查线相交的代码:
public static Point GetLineLineIntersections(
Point start1, Point end1,
Point start2, Point end2)
{
return GetLineLineIntersections(start1.X, start1.Y,
end1.X, end1.Y,
start2.X, start2.Y,
end2.X, end2.Y);
}
public static Point GetLineLineIntersections(
double x1, double y1,
double x2, double y2,
double x3, double y3,
double x4, double y4)
{
double px = ((x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4)) /
((x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4));
double py = ((x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4)) /
((x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4));
return new Point(px, py);
}
检查线与曲线相交的代码:
public static List<Point> GetLineCurveIntersections(
Point curve1, Point curve2, Point curve3, Point curve4,
Point lineStart, Point lineEnd)
{
var res = new List<Point>();
var points = new List<Point>(new Point[] { curve1, curve2, curve3, curve4 });
Rect rect = pointsBoundingRect(points);
var rectData = new Tuple<Rect, List<Point>>(rect, points);
var rectsData = new Queue<Tuple<Rect, List<Point>>>();
rectsData.Enqueue(rectData);
while (rectsData.Count != 0)
{
rectData = rectsData.Dequeue();
rect = rectData.Item1;
var controlPoints = rectData.Item2;
if (!lineIntersectsRect(lineStart, lineEnd, rect))
continue;
if (isRectSmallEnough(rect))
{
res.Add(rect.Location);
continue;
}
var pointsLeft = controlPointsForCurveInRange(0, 0.5, controlPoints);
var pointsRight = controlPointsForCurveInRange(0.501, 1, controlPoints);
var rectLeft = pointsBoundingRect(pointsLeft);
var rectRight = pointsBoundingRect(pointsRight);
rectsData.Enqueue(new Tuple<Rect, List<Point>>(rectLeft, pointsLeft));
rectsData.Enqueue(new Tuple<Rect, List<Point>>(rectRight, pointsRight));
}
return res;
}
static Rect pointsBoundingRect(List<Point> points)
{
var xMin = points[0].X;
var yMin = points[0].Y;
var xMax = xMin;
var yMax = yMin;
for (var i = 0; i < points.Count; ++i)
{
var x = points[i].X;
var y = points[i].Y;
if (x < xMin)
xMin = x;
if (x > xMax)
xMax = x;
if (y < yMin)
yMin = y;
if (y > yMax)
yMax = y;
}
return new Rect(new Point(xMax, yMax), new Point(xMin, yMin));
}
static bool lineIntersectsRect(Point lineStart, Point lineEnd, Rect rect)
{
var lineXmin = lineStart.X;
var lineXmax = lineEnd.X;
if (lineXmin > lineXmax)
{
lineXmin = lineEnd.X;
lineXmax = lineStart.X;
}
if (lineXmax > rect.BottomRight.X)
lineXmax = rect.BottomRight.X;
if (lineXmin < rect.Location.X)
lineXmin = rect.Location.X;
if (lineXmin > lineXmax)
return false;
var minY = lineStart.Y;
var maxY = lineEnd.Y;
var dx = lineEnd.X - lineStart.X;
if (Math.Abs(dx) > 0.000001)
{
//line equation
var a = (lineEnd.Y - lineStart.Y) / dx;
var b = lineStart.Y - a * lineStart.X;
minY = a * lineXmin + b;
maxY = a * lineXmax + b;
}
if (minY > maxY)
{
var tmp = minY;
minY = maxY;
maxY = tmp;
}
if (maxY > rect.BottomRight.Y)
maxY = rect.BottomRight.Y;
if (minY < rect.Location.Y)
minY = rect.Location.Y;
if (minY > maxY)
return false;
return true;
}
static bool isRectSmallEnough(Rect rect)
{
return rect.Width * rect.Height <= 1;
}
static Point calculatePointForParameters(double[] parameters, List<Point> controlPoints)
{
//De Casteljau's algorithm
if (parameters.Length != (controlPoints.Count - 1))
{
throw new Exception("Invalid input(calculate curve point)");
}
if (controlPoints.Count == 1)
return controlPoints[0];
var points = controlPoints;
var iteration = 0;
while (points.Count != 1)
{
var t = parameters[iteration];
var newPoints = new List<Point>();
for (var i = 1; i < points.Count; ++i)
{
var x = (1 - t) * points[i - 1].X + t * points[i].X;
var y = (1 - t) * points[i - 1].Y + t * points[i].Y;
newPoints.Add(new Point(x, y));
}
++iteration;
points = newPoints;
}
return points[0];
}
static List<Point> controlPointsForCurveInRange(double tMin, double tMax, List<Point> points)
{
var controlPoints = new List<Point>();
var pointsCount = points.Count;
var parameters = new double[pointsCount - 1];
for (var i = 0; i < pointsCount; ++i)
{
parameters.Fill(tMin, 0, parameters.Length - i);
parameters.Fill(tMax, parameters.Length - i, pointsCount);
var newPoint = calculatePointForParameters(parameters, points);
controlPoints.Add(newPoint);
}
return controlPoints;
}
public static class Ex
{
public static void Fill<T>(this IList<T> list, T value, int start, int end)
{
end = Math.Min(list.Count, end);
for (int i = start; i < end; ++i)
{
list[i] = value;
}
}
}
WPF内置了很多算法,可以避免为像我这样的懒人编写复杂的算法。如果使用得当,Geometry class 可以做很多事情,而且性能很好。所以你真的想开始使用几何而不是点或形状的集合(它们更多 UI 实用程序)。
在这里,我简单地使用了几何学的combination特性,一个4行代码的算法:
public static IEnumerable<Rect> ComputeIntersectingSegments(Geometry geometry, double y, double width)
{
// Add a geometry line to compute intersections.
// A geometry must not be 0 thickness for combination to be meaningful.
// So we widen the line by a very small size
var line = new LineGeometry(new Point(0, y), new Point(width, y)).GetWidenedPathGeometry(new Pen(null, 0.01));
// Intersect the line with input geometry and compute intersections
var combined = Geometry.Combine(line, geometry, GeometryCombineMode.Intersect, null);
foreach (var figure in combined.Figures)
{
// the resulting figure can be a complex thing
// we just want the bounding box
yield return new PathGeometry(new PathFigure[] { figure }).Bounds;
}
}
public partial class MainWindow : Window
{
public MainWindow()
{
InitializeComponent();
// use a canvas to display shape and intersections
var canvas = new Canvas();
Content = canvas;
// your polygon can be built as a geometry for example like this:
// var myPolygon = Geometry.Parse("M50,50 L50,165 L140,165 L140,120 L70,120 L80,70 L140,70 L140,50");
// build a 'o' shape for testing, add it to the canvas
var circle1 = new EllipseGeometry(new Point(100, 100), 70, 70);
var circle2 = new EllipseGeometry(new Point(100, 100), 40, 40);
// exclude mode will compute the 'o' shape ...
var oGeometry = new CombinedGeometry(GeometryCombineMode.Exclude, circle1, circle2);
var oPath = new Path();
oPath.Stroke = Brushes.Black;
oPath.Fill = Brushes.LightSeaGreen;
oPath.StrokeThickness = 2;
oPath.Data = oGeometry;
canvas.Children.Add(oPath);
// test many heights
for (int y = 0; y < Height; y += 25)
{
foreach (var segment in ComputeIntersectingSegments(oGeometry, y, Width))
{
// for our sample, we add each segment to the canvas
// Height is irrelevant, we use 2 for tests
var line = new Rectangle();
Canvas.SetLeft(line, segment.X);
Canvas.SetTop(line, segment.Y);
line.Width = segment.Width;
line.Height = 2;
line.Stroke = Brushes.Red;
line.StrokeThickness = 1;
canvas.Children.Add(line);
}
}
}
}
这是结果:
假设我有这样一个多边形
public partial class Window2 : Window
{
public Window2()
{
InitializeComponent();
var myPolygon = new Polygon();
myPolygon.Stroke = Brushes.Black;
myPolygon.Fill = Brushes.LightSeaGreen;
myPolygon.StrokeThickness = 2;
myPolygon.Points = new PointCollection(new Point[] {
new Point(50,50),
new Point(50,165),
new Point(140,165),
new Point(140,120),
new Point(70,120),
new Point(80,70),
new Point(140,70),
new Point(140,50)
});
this.Content = myPolygon;
}
}
假设我想绘制从一边到另一边穿过多边形的红线,如下图所示:
我只知道这条线应该站在哪个垂直位置,但是我怎么知道我应该从哪个水平点开始这条线,从哪个水平点结束这条线呢?
我的主要目标是知道这条线在哪个水平点开始,在哪个水平点结束,以便在这条线上排列文本。
如果线在多个地方穿过形状(如下图),我想得到所有线的数组:
请注意,形状可以由直线和拱形组成。
以下是 Adobe Illustrator 排列文本的方式:
如何在 C# 中执行此操作?
谢谢!
注意:如需悬赏,请附上 C# 示例。
注意:此答案不是关于计算适当的线大小(算术结果),而是关于仅在多边形上显示线(视觉结果)。如果您需要数学,请更改问题上的标签。
您可以绘制完整尺寸的线条,并使用与多边形相等的几何形状对其进行剪裁。假设您将多边形和线托管在名为 grid1
:
private void DrawLine(Polygon myPolygon, int linePos)
{
var clip = new StreamGeometry();
using (var context = clip.Open())
{
context.BeginFigure(myPolygon.Points.First(), true, true);
context.PolyLineTo(myPolygon.Points.Skip(1).ToList(), true, false);
}
var line = new Line()
{
X1 = 0,
X2 = Width,
Y1 = linePos,
Y2 = linePos,
Stroke = Brushes.Red,
StrokeThickness = 2,
Clip = clip
};
grid1.Children.Add(line);
}
结合问题中的代码:
var myPolygon = new Polygon();
myPolygon.Stroke = Brushes.Black;
myPolygon.Fill = Brushes.LightSeaGreen;
myPolygon.StrokeThickness = 2;
myPolygon.Points = new PointCollection(new Point[]
{
new Point(50,50),
new Point(50,165),
new Point(140,165),
new Point(140,120),
new Point(70,120),
new Point(80,70),
new Point(140,70),
new Point(140,50)
});
grid1.Children.Add(myPolygon);
DrawLine(myPolygon, 80);
DrawLine(myPolygon, 150);
感谢 Clemens WPF Clipping with a shape 从点创建几何的方法。
如果您计划绘制多条线,您可以选择在父面板上定义一个剪裁,这样内部的所有内容都将被剪裁到多边形边界。
我会说你唯一的选择是测试红线是否与多边形的 any/some segments/arcs 相交。
蛮力是第一个想法。第二个想法是使用 Fortune's algorithm
因为你的红线是水平的,这有点帮助。
如果将多边形的片段存储在按 Y 最小坐标排序的数组中,则可以从测试中跳过红线以下的所有片段。
这个下限很容易通过二分查找找到。
一些实用链接:
How do you detect where two line segments intersect?
Line Segment Circle Intersection
- 你要把形状分成直线和曲线
- 检查下面提供的代码,了解这些与您的红线相交的直线/曲线
- 最后你会得到至少两条相交的直线/曲线,这样你就会知道红线的宽度。
检查线相交的代码:
public static Point GetLineLineIntersections(
Point start1, Point end1,
Point start2, Point end2)
{
return GetLineLineIntersections(start1.X, start1.Y,
end1.X, end1.Y,
start2.X, start2.Y,
end2.X, end2.Y);
}
public static Point GetLineLineIntersections(
double x1, double y1,
double x2, double y2,
double x3, double y3,
double x4, double y4)
{
double px = ((x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4)) /
((x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4));
double py = ((x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4)) /
((x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4));
return new Point(px, py);
}
检查线与曲线相交的代码:
public static List<Point> GetLineCurveIntersections(
Point curve1, Point curve2, Point curve3, Point curve4,
Point lineStart, Point lineEnd)
{
var res = new List<Point>();
var points = new List<Point>(new Point[] { curve1, curve2, curve3, curve4 });
Rect rect = pointsBoundingRect(points);
var rectData = new Tuple<Rect, List<Point>>(rect, points);
var rectsData = new Queue<Tuple<Rect, List<Point>>>();
rectsData.Enqueue(rectData);
while (rectsData.Count != 0)
{
rectData = rectsData.Dequeue();
rect = rectData.Item1;
var controlPoints = rectData.Item2;
if (!lineIntersectsRect(lineStart, lineEnd, rect))
continue;
if (isRectSmallEnough(rect))
{
res.Add(rect.Location);
continue;
}
var pointsLeft = controlPointsForCurveInRange(0, 0.5, controlPoints);
var pointsRight = controlPointsForCurveInRange(0.501, 1, controlPoints);
var rectLeft = pointsBoundingRect(pointsLeft);
var rectRight = pointsBoundingRect(pointsRight);
rectsData.Enqueue(new Tuple<Rect, List<Point>>(rectLeft, pointsLeft));
rectsData.Enqueue(new Tuple<Rect, List<Point>>(rectRight, pointsRight));
}
return res;
}
static Rect pointsBoundingRect(List<Point> points)
{
var xMin = points[0].X;
var yMin = points[0].Y;
var xMax = xMin;
var yMax = yMin;
for (var i = 0; i < points.Count; ++i)
{
var x = points[i].X;
var y = points[i].Y;
if (x < xMin)
xMin = x;
if (x > xMax)
xMax = x;
if (y < yMin)
yMin = y;
if (y > yMax)
yMax = y;
}
return new Rect(new Point(xMax, yMax), new Point(xMin, yMin));
}
static bool lineIntersectsRect(Point lineStart, Point lineEnd, Rect rect)
{
var lineXmin = lineStart.X;
var lineXmax = lineEnd.X;
if (lineXmin > lineXmax)
{
lineXmin = lineEnd.X;
lineXmax = lineStart.X;
}
if (lineXmax > rect.BottomRight.X)
lineXmax = rect.BottomRight.X;
if (lineXmin < rect.Location.X)
lineXmin = rect.Location.X;
if (lineXmin > lineXmax)
return false;
var minY = lineStart.Y;
var maxY = lineEnd.Y;
var dx = lineEnd.X - lineStart.X;
if (Math.Abs(dx) > 0.000001)
{
//line equation
var a = (lineEnd.Y - lineStart.Y) / dx;
var b = lineStart.Y - a * lineStart.X;
minY = a * lineXmin + b;
maxY = a * lineXmax + b;
}
if (minY > maxY)
{
var tmp = minY;
minY = maxY;
maxY = tmp;
}
if (maxY > rect.BottomRight.Y)
maxY = rect.BottomRight.Y;
if (minY < rect.Location.Y)
minY = rect.Location.Y;
if (minY > maxY)
return false;
return true;
}
static bool isRectSmallEnough(Rect rect)
{
return rect.Width * rect.Height <= 1;
}
static Point calculatePointForParameters(double[] parameters, List<Point> controlPoints)
{
//De Casteljau's algorithm
if (parameters.Length != (controlPoints.Count - 1))
{
throw new Exception("Invalid input(calculate curve point)");
}
if (controlPoints.Count == 1)
return controlPoints[0];
var points = controlPoints;
var iteration = 0;
while (points.Count != 1)
{
var t = parameters[iteration];
var newPoints = new List<Point>();
for (var i = 1; i < points.Count; ++i)
{
var x = (1 - t) * points[i - 1].X + t * points[i].X;
var y = (1 - t) * points[i - 1].Y + t * points[i].Y;
newPoints.Add(new Point(x, y));
}
++iteration;
points = newPoints;
}
return points[0];
}
static List<Point> controlPointsForCurveInRange(double tMin, double tMax, List<Point> points)
{
var controlPoints = new List<Point>();
var pointsCount = points.Count;
var parameters = new double[pointsCount - 1];
for (var i = 0; i < pointsCount; ++i)
{
parameters.Fill(tMin, 0, parameters.Length - i);
parameters.Fill(tMax, parameters.Length - i, pointsCount);
var newPoint = calculatePointForParameters(parameters, points);
controlPoints.Add(newPoint);
}
return controlPoints;
}
public static class Ex
{
public static void Fill<T>(this IList<T> list, T value, int start, int end)
{
end = Math.Min(list.Count, end);
for (int i = start; i < end; ++i)
{
list[i] = value;
}
}
}
WPF内置了很多算法,可以避免为像我这样的懒人编写复杂的算法。如果使用得当,Geometry class 可以做很多事情,而且性能很好。所以你真的想开始使用几何而不是点或形状的集合(它们更多 UI 实用程序)。
在这里,我简单地使用了几何学的combination特性,一个4行代码的算法:
public static IEnumerable<Rect> ComputeIntersectingSegments(Geometry geometry, double y, double width)
{
// Add a geometry line to compute intersections.
// A geometry must not be 0 thickness for combination to be meaningful.
// So we widen the line by a very small size
var line = new LineGeometry(new Point(0, y), new Point(width, y)).GetWidenedPathGeometry(new Pen(null, 0.01));
// Intersect the line with input geometry and compute intersections
var combined = Geometry.Combine(line, geometry, GeometryCombineMode.Intersect, null);
foreach (var figure in combined.Figures)
{
// the resulting figure can be a complex thing
// we just want the bounding box
yield return new PathGeometry(new PathFigure[] { figure }).Bounds;
}
}
public partial class MainWindow : Window
{
public MainWindow()
{
InitializeComponent();
// use a canvas to display shape and intersections
var canvas = new Canvas();
Content = canvas;
// your polygon can be built as a geometry for example like this:
// var myPolygon = Geometry.Parse("M50,50 L50,165 L140,165 L140,120 L70,120 L80,70 L140,70 L140,50");
// build a 'o' shape for testing, add it to the canvas
var circle1 = new EllipseGeometry(new Point(100, 100), 70, 70);
var circle2 = new EllipseGeometry(new Point(100, 100), 40, 40);
// exclude mode will compute the 'o' shape ...
var oGeometry = new CombinedGeometry(GeometryCombineMode.Exclude, circle1, circle2);
var oPath = new Path();
oPath.Stroke = Brushes.Black;
oPath.Fill = Brushes.LightSeaGreen;
oPath.StrokeThickness = 2;
oPath.Data = oGeometry;
canvas.Children.Add(oPath);
// test many heights
for (int y = 0; y < Height; y += 25)
{
foreach (var segment in ComputeIntersectingSegments(oGeometry, y, Width))
{
// for our sample, we add each segment to the canvas
// Height is irrelevant, we use 2 for tests
var line = new Rectangle();
Canvas.SetLeft(line, segment.X);
Canvas.SetTop(line, segment.Y);
line.Width = segment.Width;
line.Height = 2;
line.Stroke = Brushes.Red;
line.StrokeThickness = 1;
canvas.Children.Add(line);
}
}
}
}
这是结果: