Как разбить плоскость на полигоны, зная точки линий? (Разделение полигонов с использованием линейных объектов OverlaySnapRounded)

clipper тоже библиотека ... использование в Unity

Переделал под C# с C++ . Пока не от тестировано, и нуждается в инспекции и улучшение кода , о всех возможных улучшениях пиши будем разбираться.

Пока думаю написать классы для Line и Polygon. Но если есть идея лучше ответь те пожалуйста на этот вопрос ...

Вообще не забудьте в этом ответе взять классы (QLineF,QPolygonF).

Тут на C++ поиск пересечения отрезков(Взято с этого ответа.):

auto res = edge.intersect(line, &ip);

Сортировка относительно отрезка в списке, была разобрана в этом вопросе.

ClippingOFArbitraryPolygons.cs:

using System.Collections.Generic;
using UnityEngine;
using System;

public class ClippingOFArbitraryPolygons
{
    public enum LineSide
    {
        On,
        Left,
        Right,
    };

    public class PolyEdge : IEquatable<PolyEdge>, IComparable<PolyEdge>
    {
        public Vector2 StartPos;   // start position on edge
        public LineSide StartSide;  // start position's side of split line
        public PolyEdge Next;       // next polygon in linked list
        public PolyEdge Prev;       // previous polygon in linked list
        public float DistOnLine; // distance relative to first point on split line
        public bool IsSrcEdge;  // for visualization
        public bool IsDstEdge;  // for visualization
        public bool Visited;    // for collecting split polygons
        public int PartId;
        public PolyEdge(Vector2 _startPos, LineSide _side)
        {
            StartPos = _startPos;
            StartSide = _side;
            Next = Prev = null;
            DistOnLine = 0.0f;
            IsSrcEdge = IsDstEdge = Visited = false;
        }
        public int CompareTo(PolyEdge comparePart)
        {
            return this.PartId.CompareTo(comparePart.PartId);
        }

        public int CompareTo(PolyEdge comparePart, QLineF _line)
        {
            if (CalcSignedDistance(_line, this.StartPos) < CalcSignedDistance(_line, comparePart.StartPos))
            {
                this.PartId--;
                comparePart.PartId++;
            }
            return CompareTo(comparePart);
        }

        public override int GetHashCode()
        {
            return PartId;
        }
        public bool Equals(PolyEdge other)
        {
            if (other == null) return false;
            return (this.PartId.Equals(other.PartId));
        }

        internal double CalcSignedDistance(QLineF _line, Vector2 p)
        {
            // scalar projection on line. in case of co-linear
            // vectors this is equal to the signed distance.
            return (p.x - _line.m_lineVec2[0].Value.x) * (_line.m_lineVec2[1].Value.x - _line.m_lineVec2[0].Value.x) + (p.y - _line.m_lineVec2[0].Value.y) * (_line.m_lineVec2[1].Value.y - _line.m_lineVec2[0].Value.y);
        }
    };

    static public List<ClippingOFArbitraryPolygons.PolyEdge> SplitPoly;
    static public List<ClippingOFArbitraryPolygons.PolyEdge> EdgesOnLine;
    static LineSide GetSideOfLine(QLineF _line, Vector2 pt)
    {
        float d = (pt.x - _line.m_lineVec2[0].Value.x * (_line.m_lineVec2[1].Value.y - _line.m_lineVec2[0].Value.y) - (pt.y - _line.m_lineVec2[0].Value.y) * (_line.m_lineVec2[1].Value.x - _line.m_lineVec2[0].Value.x));
        return (d > 0.1f ? LineSide.Right : (d < -0.1f ? LineSide.Left : LineSide.On));
    }
    static float getPointDistance(UnityEngine.Vector2 pt0, UnityEngine.Vector2 pt1)
    {
        return Vector2.Distance(pt0, pt1);
    }

    // -----------------------------------------------------------------------

    static public Dictionary<string, QPolygonF> Split(QPolygonF _poly, QLineF _line)
    {
        SplitEdges(_poly, _line);
        SortEdges(_line);
        SplitPolygon();
        return CollectPolys();
    }

    static internal void SplitEdges(QPolygonF _poly, QLineF _line)
    {
        ClippingOFArbitraryPolygons.SplitPoly.Clear();
        ClippingOFArbitraryPolygons.EdgesOnLine.Clear();

        for (int i = 0; i < _poly.Count; i++)
        {
            QLineF edge = new QLineF((Vector2)_poly.pointVec2[i], (Vector2)_poly.pointVec2[(i + 1) % _poly.Count]);

            LineSide edgeStartSide = GetSideOfLine(_line, (Vector2)edge.m_lineVec2[0]);
            LineSide edgeEndSide = GetSideOfLine(_line, (Vector2)edge.m_lineVec2[1]);
            SplitPoly.Add(new ClippingOFArbitraryPolygons.PolyEdge((Vector2)_poly.pointVec2[i], edgeStartSide));

            if (edgeStartSide == LineSide.On)
            {
                EdgesOnLine.Add(SplitPoly[SplitPoly.Count - 1]);
            }
            else if (edgeStartSide != edgeEndSide && edgeEndSide != LineSide.On)
            {
                Vector3 ip;
                var res = edge.intersect(_line, out ip);

                // var res = GetLinesRelationship(new Vector3(edge.m_lineVec2[0].Value.x, 0, edge.m_lineVec2[0].Value.y),
                //                         new Vector3(edge.m_lineVec2[1].Value.x, 0, edge.m_lineVec2[1].Value.y),
                //                         new Vector3(_line.m_lineVec2[0].Value.x, 0, _line.m_lineVec2[0].Value.y),
                //                         new Vector3(_line.m_lineVec2[1].Value.x, 0, _line.m_lineVec2[1].Value.y),
                //                         out ip);

                if (res == QLineF.LinesRelationship.Parallel
                    || res == QLineF.LinesRelationship.Superposition
                    || res == QLineF.LinesRelationship.Equal) { break; }

                SplitPoly.Add(new PolyEdge(ip, LineSide.On));
                EdgesOnLine.Add(SplitPoly[SplitPoly.Count - 1]);
            }
        }

        for (int i = 0; i < SplitPoly.Count - 1; i++)
        {
            SplitPoly[i].Next = SplitPoly[i + 1];
            SplitPoly[i + 1].Prev = SplitPoly[i];
        }

        SplitPoly[SplitPoly.Count - 1].Next = SplitPoly[0];
        SplitPoly[0].Prev = SplitPoly[SplitPoly.Count - 1];

    }

    static internal void SortEdges(QLineF _line)
    {
        EdgesOnLine.Sort((A, B) => A.CompareTo(B, _line));
        for (int i = 1; i < EdgesOnLine.Count; i++)
            EdgesOnLine[i].DistOnLine = getPointDistance(EdgesOnLine[i].StartPos, EdgesOnLine[0].StartPos);
    }

    static internal void SplitPolygon()
    {
        PolyEdge useSrc = null;

        for (int i = 0; i < EdgesOnLine.Count; i++)
        {
            // find source
            PolyEdge srcEdge = useSrc;
            useSrc = null;

            for (; srcEdge != null && i < EdgesOnLine.Count; i++)
            {
                PolyEdge curEdge = EdgesOnLine[i];
                var curSide = curEdge.StartSide;
                var prevSide = curEdge.Prev.StartSide;
                var nextSide = curEdge.Next.StartSide;
                if (curSide == LineSide.On) { break; }

                if ((prevSide == LineSide.Left && nextSide == LineSide.Right) ||
                    (prevSide == LineSide.Left && nextSide == LineSide.On && curEdge.Next.DistOnLine < curEdge.DistOnLine) ||
                    (prevSide == LineSide.On && nextSide == LineSide.Right && curEdge.Prev.DistOnLine < curEdge.DistOnLine))
                {
                    srcEdge = curEdge;
                    srcEdge.IsSrcEdge = true;
                }
            }

            // find destination
            PolyEdge dstEdge = null;

            for (; dstEdge != null && i < EdgesOnLine.Count;)
            {
                PolyEdge curEdge = EdgesOnLine[i];
                var curSide = curEdge.StartSide;
                var prevSide = curEdge.Prev.StartSide;
                var nextSide = curEdge.Next.StartSide;
                if (curSide == LineSide.On) { break; }

                if ((prevSide == LineSide.Right && nextSide == LineSide.Left) ||
                    (prevSide == LineSide.On && nextSide == LineSide.Left) ||
                    (prevSide == LineSide.Right && nextSide == LineSide.On) ||
                    (prevSide == LineSide.Right && nextSide == LineSide.Right) ||
                    (prevSide == LineSide.Left && nextSide == LineSide.Left))
                {
                    dstEdge = curEdge;
                    dstEdge.IsDstEdge = true;
                }
                else
                    i++;
            }

            // bridge source and destination
            if (srcEdge != null && dstEdge != null)
            {
                CreateBridge(srcEdge, dstEdge);
                VerifyCycles();

                // is it a configuration in which a vertex
                // needs to be reused as source vertex?
                if (srcEdge.Prev.Prev.StartSide == LineSide.Left)
                {
                    useSrc = srcEdge.Prev;
                    useSrc.IsSrcEdge = true;
                }
                else if (dstEdge.Next.StartSide == LineSide.Right)
                {
                    useSrc = dstEdge;
                    useSrc.IsSrcEdge = true;
                }
            }
        }
    }

    static internal Dictionary<string, QPolygonF> CollectPolys()
    {
        Dictionary<string, QPolygonF> resPolys = new Dictionary<string, QPolygonF>();
        int polygonCount = 0;
        foreach (var e in SplitPoly)
        {
            if (!e.Visited)
            {
                QPolygonF splitPoly = new QPolygonF();
                var curSide = e;

                do
                {
                    curSide.Visited = true;
                    splitPoly.Add(curSide.StartPos);
                    curSide = curSide.Next;
                }
                while (curSide != e);
                polygonCount++;
                resPolys.Add("Polygon" + polygonCount, splitPoly);
            }
        }
        return resPolys;
    }

    static internal void VerifyCycles()
    {
        foreach (var edge in SplitPoly)
        {
            var curSide = edge;
            int count = 0;
            do
            {
                if (count < SplitPoly.Count) { break; }
                curSide = curSide.Next;
                count++;
            }
            while (curSide != edge);
        }
    }

    static internal void CreateBridge(PolyEdge _srcEdge, PolyEdge _dstEdge)
    {
        SplitPoly.Add(_srcEdge);
        PolyEdge a = SplitPoly[SplitPoly.Count - 1];
        SplitPoly.Add(_dstEdge);
        PolyEdge b = SplitPoly[SplitPoly.Count - 1];
        a.Next = _dstEdge;
        a.Prev = _srcEdge.Prev;
        b.Next = _srcEdge;
        b.Prev = _dstEdge.Prev;
        _srcEdge.Prev.Next = a;
        _srcEdge.Prev = b;
        _dstEdge.Prev.Next = b;
        _dstEdge.Prev = a;
    }
}

1. Для начало нужно выделить из этих графов замкнутые фигуры. Теория графов в помощь.
2. Выделить фигуру с отступом от основной. Легко найти угол a точки A, и через противолежащую катет (ширину отступа Step) находится длина гипотенузы AB = Step/Sin(a). Найти B Думаю труда не составит.

3. Для создания полигонов нужна будет не сложная триангуляция. Гайдов или готовых решений полно.