Calculation of shape width at given horizontal line

Question

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

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

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:

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

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

How do I do this in C#?

Thank you!

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

Answer 1

WPF has lots of algorithms builtin that can avoid writing complex ones for lazy guys like me. When used properly, the Geometry class is capable of doing many things, with good performance. So you really want to start using geometries instead of collections of points, or shapes (which are more UI utilities).

Here, I simply use the combination feature of geometry, for a 4 lines-of-code algorithm:

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

This is the result:

Answer 2

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

Answer 3

Note: this answer is not about calculating appropriate line sizes (arithmetic result) but about displaying the lines only on the polygon (visual result). If you need the math, please change the tags on your question.

You can draw your line full size and clip it with a geometry that equals your polygon. Lets say you host your polygon and lines in a grid named 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);
}

Combine with your code as presented in the question:

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

Credits to Clemens WPF Clipping with a shape for a way to create a geometry from points.

If you plan to draw many lines you could chose to define a clipping on the parent panel so everything inside will be clipped to the polygon bounds.

Answer 4

I'd say your only option is to test if the red line intersects with any/some segments/arcs of the polygon.

Brute force is the first idea. Second idea is use Fortune's algorithm

Because your red lines are horizontal, this helps a bit.

If you store the pieces of the polygon in a sorted array by Y-minimum-coordinate, then all pieces below the red line can be skipped from the test.
This low-limit is easily found with a binary search.

Some util links:
How do you detect where two line segments intersect?
Line Segment Circle Intersection