Splitting polygons with vertices that touch its edges

[nicophilippi]

Assuming that we have a simple polygon with a vertex that touches an edge, such as:

Is there any way in the libary to split the polygon at the edge-touching vertex? The expected result for the example above would look like that:

[aismann]

@nicophilippi
An example code can help to reproduce it easier.

[nicophilippi]

Example Code in C#

var sub = new Paths64
{
    new Path64 { new Point64(0, 0), new Point64(128, 0), new Point64(128, 128), new Point64(0, 128)},
};

var clip = new Paths64
{
    new Path64 { new Point64(0, 128), new Point64(0, 0), new Point64(128, 64)},
};

var dif = Clipper.Difference(sub, clip, FillRule.EvenOdd);
// dif contains (according to debugger): { (128, 128), (0, 128), (128, 64), (0, 0), (128, 0) }
// Expected, or rather what I would need:
//     { (128, 128), (0, 128), (128, 64) }
//     { (128, 64), (0, 0), (128, 0) }

[AngusJohnson]

Is there any way in the libary to split the polygon at the edge-touching vertex?

No. Sorry to disappoint.

[aismann]

Fair enough, then I will come up with a solution myself and post it here later

@nicophilippi
How far ist your solution?

[nicophilippi]

@aismann Not far. Many attempts to solve the problem lead to me banging my head in the wall, so I have worked on different tasks for the project that uses Clipper2. I also didn't have much time for the project last week.

[AngusJohnson]

Many attempts to solve the problem lead to me banging my head in the wall

I'm pretty sure if it was (relatively) easy I would have found a way, so I'm not surprised you've hit a wall.

[nicophilippi]

@AngusJohnson @aismann Have a solution now. I need to test it a little more to be sure it doesn't cause issues, but so far it seems promising. If I ever update and improve the code, I will update the message here accordingly.

/// <summary>Splits the contours of the polygon on single vertex connections and saves newly
/// created contours in polygon</summary>
public static void SplitSingleVertexConnected(this Paths64 polygon)
{
    polygon.InsertVertexAtIntersects();

    for (var contourI = 0; contourI < polygon.Count; contourI++)
    {
        for (var vertex1I = 0; vertex1I < polygon[contourI].Count; vertex1I++)
        {
            for (var vertex2I = 0; vertex2I < polygon[contourI].Count; vertex2I++)
            {
                if (vertex2I == vertex1I) continue;
                
                var v1 = polygon[contourI][vertex1I];
                var v2 = polygon[contourI][vertex2I];
                if (v1 != v2) continue;
                
                var v1Prev = polygon[contourI][(vertex1I - 1).PosMod(polygon[contourI].Count)];
                var v1Next = polygon[contourI][(vertex1I + 1) % polygon[contourI].Count];
                var v2Prev = polygon[contourI][(vertex2I - 1).PosMod(polygon[contourI].Count)];
                var v2Next = polygon[contourI][(vertex2I + 1) % polygon[contourI].Count];

                var v1ToPrevAngleRad = (v1Prev - v1).ToAngleRad();
                var v1ToNextAngleRad = (v1Next - v1).ToAngleRad();
                var v2ToPrevAngleRad = (v2Prev - v2).ToAngleRad();
                var v2ToNextAngleRad = (v2Next - v2).ToAngleRad();
                if (!DoAnglesTouch(v1ToPrevAngleRad, v1ToNextAngleRad, v2ToPrevAngleRad, v2ToNextAngleRad))
                    continue;

                SplitPathAt(contourI, vertex1I, vertex2I);
            }
        }
    }
    
    
    void SplitPathAt(int contourI, int vertex1I, int vertex2I)
    {
        Assert.IsTrue(vertex1I < vertex2I);
        
        var newContour = new Path64();
        polygon.Add(newContour);
        for (var i = vertex1I; i < vertex2I; i++) newContour.Add(polygon[contourI][i]);
        polygon[contourI].RemoveRange(vertex1I, vertex2I - vertex1I);
    }
}


/// <summary>An algorithm that checks if a vertex x lies between any edge,
/// and adds a vertex between the 2 edges on x's position</summary>
public static void InsertVertexAtIntersects(this Paths64 polygon)
{
    foreach (var edgeContour in polygon)
    {
        for (var vI = 0; vI < edgeContour.Count; vI++)
        {
            var edgeStart = edgeContour[vI];
            var edgeEnd = edgeContour[(vI + 1) % edgeContour.Count];
        
            foreach (var checkContour in polygon)
            {
                // checkContour could be mutated! Do not foreach
                // ReSharper disable once ForCanBeConvertedToForeach
                for (var checkVI = 0; checkVI < checkContour.Count; checkVI++)
                {
                    var vertexToCheck = checkContour[checkVI];
                    if (vertexToCheck == edgeStart || vertexToCheck == edgeEnd ||
                        !vertexToCheck.IsPointOnEdge(edgeStart, edgeEnd)) continue;

                    edgeContour.InsertOrAddOverflow(vI + 1, vertexToCheck);
                    edgeEnd = vertexToCheck;
                }
            }
        }
    }
}


public static int PosMod(this int l, int r)
{
    var o = l % r;
    return o < 0 ? o + r : o;
}


/// <summary>Returns true if p lies directly on the edge defined by edgeStart and edgeEnd</summary>
public static bool IsPointOnEdge(this Point64 p, Point64 edgeStart, Point64 edgeEnd)
{
    var crossProd = (p.Y - edgeStart.Y) * (edgeEnd.X - edgeStart.X) -
                    (p.X - edgeStart.X) * (edgeEnd.Y - edgeStart.Y);
    if (crossProd != 0) return false;
    var withinXBounds = p.X >= Math.Min(edgeStart.X, edgeEnd.X) && p.X <= Math.Max(edgeStart.X, edgeEnd.X);
    var withinYBounds = p.Y >= Math.Min(edgeStart.Y, edgeEnd.Y) && p.Y <= Math.Max(edgeStart.Y, edgeEnd.Y);
    return withinXBounds && withinYBounds;
}


// It's imperative that ToAngleRad returns an angle that is positive in CCW orientation for the algorithms correctness
public static float ToAngleRad(this Point64 p) => throw new NotImplementedException();
//Mathf.Atan2(p.Y, p.X) * -1;


public static bool DoAnglesTouch(float angle1Start, float angle1End, float angle2Start, float angle2End)
{
    return (angle1Start.IsAngleInsideOtherAngles(angle2Start, angle2End)
            || angle1End.IsAngleInsideOtherAngles(angle2Start, angle2End))
           && (angle2Start.IsAngleInsideOtherAngles(angle1Start, angle1End)
               || angle2End.IsAngleInsideOtherAngles(angle1Start, angle1End));
}


public static bool IsAngleInsideOtherAngles(this float angleToCheck, float startAngle, float endAngle)
{
    if (startAngle > endAngle) return !angleToCheck.IsAngleInsideOtherAngles(endAngle, startAngle);
    return angleToCheck >= startAngle && angleToCheck <= endAngle;
}


/// <summary>If a Paths64 contains multiple outer contours, this method splits them and assigns the correct holes to each new Paths64.
/// Mutates paths</summary>
public static List<Paths64> SplitOuterPaths(this Paths64 mutatedPaths)
{
    var o = new List<Paths64>();
    for (var i = 0; i < mutatedPaths.Count; i++)
    {
        var c = mutatedPaths[i];
#if DEBUG
        if (Clipper.Area(c) == 0) throw new Exception("Area of contour 0?");
#endif
        var isOuter = Clipper.Area(c) > 0;
        if (!isOuter) continue;
        
        o.Add(new Paths64 { c });
        mutatedPaths.RemoveAt(i);
        i--;
    }

    foreach (var c in mutatedPaths)
    {
        foreach (var polygon in o)
        {
            var isInside = Clipper.Difference(polygon, new Paths64 { c }, FillRule.NonZero).Count == 0;
            if (!isInside) continue;
            polygon.Add(c);
        }
    }

    return o;
}