source: OniSplit/Akira/Polygon2Clipper.cs@ 1148

using System;
using System.Collections.Generic;

namespace Oni.Akira
{
    internal struct Polygon2Clipper
    {
        private readonly List<Polygon2> result;
        private readonly RoomBspNode bspTree;

        #region private struct Line

        private struct Line
        {
            private float a, c, d;

            public Line(Plane plane)
            {
                a = plane.Normal.X;
                c = plane.Normal.Z;
                d = plane.D;
            }

            public int RelativePosition(Vector2 point)
            {
                float r = a * point.X + c * point.Y + d;

                if (r < -0.00001f)
                    return -1;
                else if (r > 0.00001f)
                    return 1;
                else
                    return 0;
            }

            public Vector2 Intersect(Vector2 p0, Vector2 p1)
            {
                if (p0.X == p1.X)
                {
                    float x = p0.X;
                    float y = (d + a * x) / -c;
                    return new Vector2(x, y);
                }
                else if (p0.Y == p1.Y)
                {
                    float x = (-c * p0.Y - d) / a;
                    float y = p0.Y;
                    return new Vector2(x, y);
                }
                else
                {
                    float m = (p1.Y - p0.Y) / (p1.X - p0.X);
                    float x = (c * m * p0.X - c * p0.Y - d) / (a + c * m);
                    float y = m * (x - p0.X) + p0.Y;
                    return new Vector2(x, y);
                }
            }
        }

        #endregion

        public Polygon2Clipper(RoomBspNode bspTree)
        {
            this.result = new List<Polygon2>();
            this.bspTree = bspTree;
        }

        public IEnumerable<Polygon2> Clip(Polygon2 polygon)
        {
            result.Clear();
            Clip(new[] { polygon }, bspTree);
            return result;
        }

        private void Clip(IEnumerable<Polygon2> polygons, RoomBspNode node)
        {
            var negative = new List<Polygon2>();
            var positive = new List<Polygon2>();

            var plane = node.Plane;

            if (Math.Abs(plane.Normal.Y) > 0.001f)
            {
                negative.AddRange(polygons);
                positive.AddRange(polygons);
            }
            else
            {
                var line = new Line(plane);

                foreach (Polygon2 polygon in polygons)
                    Clip(polygon, line, negative, positive);
            }

            if (node.FrontChild != null)
                Clip(positive, node.FrontChild);

            if (node.BackChild != null)
                Clip(negative, node.BackChild);
            else
                result.AddRange(negative);
        }

        private static void Clip(Polygon2 polygon, Line line, List<Polygon2> negative, List<Polygon2> positive)
        {
            var signs = new int[polygon.Length];
            int positiveCount = 0, negativeCount = 0;

            for (int i = 0; i < polygon.Length; i++)
            {
                signs[i] = line.RelativePosition(polygon[i]);

                if (signs[i] >= 0)
                    positiveCount++;

                if (signs[i] <= 0)
                    negativeCount++;
            }

            if (negativeCount == polygon.Length)
            {
                //
                // All points are in the negative half plane, nothing to clip.
                //

                negative.Add(polygon);
                return;
            }

            if (positiveCount == polygon.Length)
            {
                //
                // All points are in the positive half plane, nothing to clip.
                //

                positive.Add(polygon);
                return;
            }

            var negativePoints = new List<Vector2>();
            var positivePoints = new List<Vector2>();

            int start = 0;
            Vector2 p0;
            int s0;

            do
            {
                p0 = polygon[start];
                s0 = signs[start];
                start++;

                //
                // do not start right on the clip line
                //

            } while (s0 == 0);

            var intersections = new Vector2[2];
            int intersectionCount = 0;

            for (int i = 0; i < polygon.Length; i++)
            {
                Vector2 p1 = polygon[(i + start) % polygon.Length];
                int s1 = signs[(i + start) % polygon.Length];

                if (s0 == s1)
                {
                    //
                    // Same half plane, no intersection, add the existing edge.
                    //

                    if (s0 < 0)
                        negativePoints.Add(p0);
                    else
                        positivePoints.Add(p0);
                }
                else if (s0 == 0)
                {
                    //
                    // If the previous point was on the clip line then we need
                    // to use the current point sign to figure out the destination polygon.
                    //

                    if (s1 < 0)
                        negativePoints.Add(p0);
                    else
                        positivePoints.Add(p0);
                }
                else
                {
                    //
                    // Different half plane, split the edge in two.
                    //

                    Vector2 intersection;

                    if (s1 == 0)
                        intersection = p1;
                    else
                        intersection = line.Intersect(p0, p1);

                    intersections[intersectionCount++] = intersection;

                    if (s0 < 0)
                    {
                        // the negative polygon needs to be closed
                        // the positive polygon needs to have an edge added from the previous intersection to the new one

                        negativePoints.Add(p0);

                        if (intersectionCount == 2)
                        {
                            negativePoints.Add(intersection);
                            positivePoints.Add(intersections[0]);
                        }

                        if (s1 != 0)
                            positivePoints.Add(intersection);
                    }
                    else
                    {
                        // the positive polygon needs to be closed
                        // the negative polygon needs to have an edge added from the previous intersection to the new one

                        positivePoints.Add(p0);

                        if (intersectionCount == 2)
                        {
                            positivePoints.Add(intersection);
                            negativePoints.Add(intersections[0]);
                        }

                        if (s1 != 0)
                            negativePoints.Add(intersection);
                    }
                }

                p0 = p1;
                s0 = s1;
            }

            negative.Add(new Polygon2(negativePoints.ToArray()));
            positive.Add(new Polygon2(positivePoints.ToArray()));
        }
    }
}