google fan google fan - 3 years ago 214
C# Question

Calculation of shape width at given horizontal line

Let's say I have such a polygon

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


enter image description here

And Let's say I want to draw the red lines that cross the polygon from side to side, as in the next picture:

enter image description here

I only know the vertical position where the line should stand, but how can I know which horizontal point I should start the line and which horizontal point to end the line?

My main goal is to know at which horizontal point the line starts and at which point it ends, for arrange an text on this line.

If the line crosses the shape in several places (as in the following picture), I want to get an array of all the lines:

enter image description here

Note that the shape can be composed of straight lines and arches.

Here's how Adobe Illustrator arranges the text in a shape:

enter image description here

How do I do this in C#?

Thank you!

NOTE: For a bounty please attach an example in C#.

Answer Source
  1. You have to divide the shape into lines and curves
  2. Check with the code provided below for these lines / curves intersecting with your red line
  3. Finally you will get at least two lines / curves intersecting and so you will know the width of the red line.

Code for checking line intersections:

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

Code for checking line intersection with curve:

    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;
        }
    }
}
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download