How to clip non-closed geometry

Question

Intro

I noticed an issue while implementing clipping (see this).

It looks like UIElement.Clip still render invisible parts

Rendering relatively small geometry (lines to only fill 1920x1200 area ~ 2000 vertical lines) take a lot of time. When using Clip and moving that geometry offscreen (so that clipping should remove significant part of it) it is still take same time (around 1 sec).

Ok, I found what using Geometry.Combine will do a clip (render time is reduced proportionally to removed after clipping geometry). Perfect!

Problem

Geometry.Combine doesn't work with non-closed geometry properly. It produce closed geometry. And it looks ugly, connecting first and last point:

Question

How can I perform clipping (reducing amount of geometry to be rendered) for non-closed figures?

Edit

Here is geometry before (small peace of shown on picture)

{M0;50L0;50L1;53,1395259764657L2;56,2666616782152L3;59,3690657292862L4;62,4344943582427L5;65,4508497187474L6;68,4062276342339L7;71,2889645782536L8; ...

and after

{F1M54,9999923706055;34,5491371154785L53,9999885559082;37,5655174255371 53,0000114440918;40,6309471130371 52,0000076293945;43,7333335876465 ...

Notice change at beginning, was M 0;50 L ..., become F 1 M 55;34 L ...

F1 means NonZero filling

Rule that determines whether a point is in the fill region of the path by drawing a ray from that point to infinity in any direction and then examining the places where a segment of the shape crosses the ray. Starting with a count of zero, add one each time a segment crosses the ray from left to right and subtract one each time a path segment crosses the ray from right to left. After counting the crossings, if the result is zero then the point is outside the path. Otherwise, it is inside.

And I have absolutely no clue what that means. But maybe it is important?

Edit

I should have been looking at the end of strings. There is z at the end of Path.Data, which means figure is closed.

Strangely enough, trying to remove z (by using Geometry.ToString()/Geometry.Parse() combo) doesn't works. After some investigation I found what Combine produces physically enclosing figures (commands L x;y, where x;y is the leftmost point). And the worst thing is what it's not always the last point, so simply removing last L x;y before parsing doesn't works either. =(

Edit

Sample to demonstrate problem:

Xaml:

<Path x:Name="path" Stroke="Red"/>

Code:

var geometry1 = new RectangleGeometry(new Rect(100, 100, 100, 100));
var geometry2 = new PathGeometry(new[] { new PathFigure(new Point(0,0), new[] {
    new LineSegment(new Point(300, 300), true),
    new LineSegment(new Point(300, 0), true),
}, false) });

//path.Data = geometry1;
//path.Data = geometry2;
//path.Data = Geometry.Combine(geometry1, geometry2, GeometryCombineMode.Intersect, null);

Pictures of geometry1 and geometry2:

Resulting Combine:

As you can see 2 lines become 3 after clipping, debugging proves it:

{F1M100;100L200;100 200;200 100;100z}

Notice, it's not only z, but also 100;100 point at the end, connecting starting point.

Answer 1

I attempted to implement a clipping solutions for non closed geometry based on this line intersection algorithm

Code

    public static PathGeometry ClipGeometry(PathGeometry geom, Rect clipRect)
    {
        PathGeometry clipped = new PathGeometry();
        foreach (var fig in geom.Figures)
        {
            PathSegmentCollection segments = new PathSegmentCollection();
            Point lastPoint = fig.StartPoint;
            foreach (LineSegment seg in fig.Segments)
            {
                List<Point> points;
                if (LineIntersectsRect(lastPoint, seg.Point, clipRect, out points))
                {
                    LineSegment newSeg = new LineSegment(points[1], true);
                    PathFigure newFig = new PathFigure(points[0], new[] { newSeg }, false);
                    clipped.Figures.Add(newFig);
                }
                lastPoint = seg.Point;
            }
        }
        return clipped;
    }

    static bool LineIntersectsRect(Point lineStart, Point lineEnd, Rect rect, out List<Point> points)
    {
        points = new List<Point>();

        if (rect.Contains(lineStart) && rect.Contains(lineEnd))
        {
            points.Add(lineStart);
            points.Add(lineEnd);
            return true;
        }

        Point outPoint;
        if (Intersects(lineStart, lineEnd, rect.TopLeft, rect.TopRight, out outPoint))
        {
            points.Add(outPoint);
        }

        if (Intersects(lineStart, lineEnd, rect.BottomLeft, rect.BottomRight, out outPoint))
        {
            points.Add(outPoint);
        }

        if (Intersects(lineStart, lineEnd, rect.TopLeft, rect.BottomLeft, out outPoint))
        {
            points.Add(outPoint);
        }

        if (Intersects(lineStart, lineEnd, rect.TopRight, rect.BottomRight, out outPoint))
        {
            points.Add(outPoint);
        }

        if (points.Count == 1)
        {
            if (rect.Contains(lineStart))
                points.Add(lineStart);
            else
                points.Add(lineEnd);
        }

        return points.Count > 0;
    }

    static bool Intersects(Point a1, Point a2, Point b1, Point b2, out Point intersection)
    {
        intersection = new Point(0, 0);

        Vector b = a2 - a1;
        Vector d = b2 - b1;
        double bDotDPerp = b.X * d.Y - b.Y * d.X;

        if (bDotDPerp == 0)
            return false;

        Vector c = b1 - a1;
        double t = (c.X * d.Y - c.Y * d.X) / bDotDPerp;
        if (t < 0 || t > 1)
            return false;

        double u = (c.X * b.Y - c.Y * b.X) / bDotDPerp;
        if (u < 0 || u > 1)
            return false;

        intersection = a1 + t * b;

        return true;
    }

currently solution works for line based geometry, other types perhaps need to be included if needed.

test xaml

<UniformGrid Columns="2"
             Margin="250,250,0,0">
    <Grid>
        <Path x:Name="pathClip"
              Fill="#22ff0000" />
        <Path x:Name="path"
              Stroke="Black" />

    </Grid>
    <Path x:Name="path2"
          Margin="100,0,0,0"
          Stroke="Black" />
</UniformGrid>

test code 1

    void test()
    {
        var geometry = new PathGeometry(new[] { new PathFigure(new Point(0,0), new[] {
                                                    new LineSegment(new Point(300, 300), true),
                                                    new LineSegment(new Point(300, 0), true),
                                                }, false) });

        Rect clipRect= new Rect(10, 10, 180, 180);
        path.Data = ClipGeometry(geometry, clipRect);
        path2.Data = geometry;
        pathClip.Data = new RectangleGeometry(clipRect);
    }

result

test code 2

    void test()
    {
        var radius = 1.0;
        var figures = new List<LineSegment>();
        for (int i = 0; i < 2000; i++, radius += 0.1)
        {
            var segment = new LineSegment(new Point(radius * Math.Sin(i), radius * Math.Cos(i)), true);
            segment.Freeze();
            figures.Add(segment);
        }
        var geometry = new PathGeometry(new[] { new PathFigure(figures[0].Point, figures, false) });

        Rect clipRect= new Rect(10, 10, 180, 180);
        path.Data = ClipGeometry(geometry, clipRect);
        path2.Data = geometry;
        pathClip.Data = new RectangleGeometry(clipRect);
    }

result

give it a try and see how close it is.

Answer 2

If i am right your mainquestion is:"How do i improve the performance of drawing many shapes?"

To get this working you have to understand Geometry Math.

Geometric objects can only merged/combined if they connect or overlap. And there is a big difference between path-geometry and shape-geometry.

As example if two circle overlap you can combine them in WPF

• to get the overlapping region: Intersect
• to get the difference: Xor
• to get the combined surface: Union
• to get the difference of only one shape: Exclude

For path-geometry it's a little different, because a path has no surface a path cannot Intersect | Xor | Union | Exclude another path or shape.

But WPF thinks you just forgot to close the path and is doing that for you, which result in the given result in your question.

so to achieve a performanceboost you have to filter all the geometry first for shapes and paths.

foreach(Shape geometryObj in ControlsOrWhatEver)
{
    if(geometryObj  is Line || geometryObj  is Path || geometryObj  is Polypath)
    {
        pathList.Add(geometryObj);
    } 
    else
    {
        shapeList.Add(geometryObj);
    }
}

for the shapeList you can use Geometry.Combine, but for the pathList you have to do some other work. You have to check if the connect at some point, doesnt matter if beginningPoint, endPoint or somwhere inbetween. If you have done that you can Merge not Combine the path by yourself like:

public Polyline mergePaths(Shape line1, Shape line2)
{
     if(!checkLineType(line1) || !checkLineType(line2))
     {
         return null;
     }

     if(hitTest(line1, line2))
     {
         //here you have to do some math to determine the overlapping points
         //on these points you can do something like this:

         foreach(Point p in Overlapping Points)
         {
              //add the first line until p then add line2 and go on to add lin 1 until another p
         }
     }
     else
     {
         return null;
     }         
}