using System;
using System.Collections.Generic;
using System.Linq;
using Sandbox;

namespace Sunless.Architecture;

public readonly struct ArchBox {
	public Vector2 Min { get; init; }
	public Vector2 Max { get; init; }

	public ArchBox Grown( float amount ) {
		var margin = new Vector2( amount, amount );

		return new ArchBox { Min = Min - margin, Max = Max + margin };
	}
}

public static class ArchFootprint {
	const float Grain = 0.02f;

	public const int LeastSegments = 8;

	public static List<Vector2> Turned( IReadOnlyList<Vector2> loop, Vector2 about, float degrees ) {
		var turned = new List<Vector2>( loop.Count );

		foreach ( var point in loop ) {
			turned.Add( Turned( point, about, degrees ) );
		}

		return turned;
	}

	public static List<List<Vector2>> Turned( IEnumerable<IReadOnlyList<Vector2>> loops, Vector2 about, float degrees ) {
		return loops.Select( loop => Turned( loop, about, degrees ) ).ToList();
	}

	public static Vector2 Turned( Vector2 point, Vector2 about, float degrees ) {
		var radians = degrees.DegreeToRadian();
		var local = point - about;
		var cos = MathF.Cos( radians );
		var sin = MathF.Sin( radians );

		return about + new Vector2( local.x * cos - local.y * sin, local.x * sin + local.y * cos );
	}

	public static List<Vector2> Rect( Vector2 min, Vector2 max ) {
		return new List<Vector2> { min, new( max.x, min.y ), max, new( min.x, max.y ) };
	}

	public static List<Vector2> OrRect( IReadOnlyList<Vector2> loop, Vector2 min, Vector2 max ) {
		return loop is { Count: >= 4 } ? new List<Vector2>( loop ) : Rect( min, max );
	}

	public static List<Vector2> Ellipse( Vector2 min, Vector2 max, int segments ) {
		var sides = Math.Max( 3, segments );
		var centre = (min + max) * 0.5f;
		var radius = (max - min) * 0.5f;
		var loop = new List<Vector2>( sides );

		// Half-step offset so flats face the axes, not points.
		var lead = MathF.PI / sides;

		for ( var index = 0; index < sides; index++ ) {
			var angle = lead + index * MathF.Tau / sides;

			loop.Add( centre + new Vector2( MathF.Cos( angle ) * radius.x, MathF.Sin( angle ) * radius.y ) );
		}

		return Wind( loop );
	}

	public static bool IsRectilinear( IReadOnlyList<Vector2> loop ) => IsRectilinear( loop, 0f );

	public static bool IsRectilinear( IReadOnlyList<Vector2> loop, float degrees ) {
		if ( loop is null || loop.Count < 4 ) {
			return false;
		}

		var radians = degrees.DegreeToRadian();
		var along = new Vector2( MathF.Cos( radians ), MathF.Sin( radians ) );
		var across = new Vector2( -along.y, along.x );

		for ( var index = 0; index < loop.Count; index++ ) {
			var span = loop[(index + 1) % loop.Count] - loop[index];

			if ( MathF.Abs( Vector2.Dot( span, along ) ) > Grain && MathF.Abs( Vector2.Dot( span, across ) ) > Grain ) {
				return false;
			}
		}

		return true;
	}

	public static bool Bearing( IEnumerable<IReadOnlyList<Vector2>> loops, out float degrees ) {
		degrees = 0f;

		var filled = loops?.Where( loop => loop is { Count: >= 3 } ).ToList();

		if ( filled is not { Count: > 0 } || filled.All( loop => IsRectilinear( loop, 0f ) ) ) {
			return true;
		}

		var turned = Longest( filled );

		if ( !filled.All( loop => IsRectilinear( loop, turned ) ) ) {
			return false;
		}

		degrees = turned;

		return true;
	}

	public static bool Bearing( IReadOnlyList<Vector2> loop, out float degrees ) {
		return Bearing( new[] { loop }, out degrees );
	}

	// Longest edge names the frame, folded into [0, 90) — a stub must not speak for the whole plan.
	static float Longest( IReadOnlyList<IReadOnlyList<Vector2>> loops ) {
		var reach = 0f;
		var degrees = 0f;

		foreach ( var loop in loops ) {
			for ( var index = 0; index < loop.Count; index++ ) {
				var span = loop[(index + 1) % loop.Count] - loop[index];

				if ( span.Length <= reach ) {
					continue;
				}

				reach = span.Length;
				degrees = MathF.Atan2( span.y, span.x ).RadianToDegree();
			}
		}

		return degrees % 90f;
	}

	public static Vector2 Pivot( IEnumerable<IReadOnlyList<Vector2>> loops ) {
		return loops?.FirstOrDefault( loop => loop is { Count: >= 1 } )?[0] ?? Vector2.Zero;
	}

	static bool Framed( IEnumerable<IReadOnlyList<Vector2>> loops, out Vector2 pivot, out float degrees ) {
		var filled = loops?.Where( loop => loop is { Count: >= 3 } ).ToList() ?? new List<IReadOnlyList<Vector2>>();

		pivot = Pivot( filled );

		return Bearing( filled, out degrees ) && MathF.Abs( degrees ) > 0.001f;
	}

	public static bool IsSimple( IReadOnlyList<Vector2> loop ) {
		if ( loop is null || loop.Count < 4 || loop.Distinct().Count() != loop.Count ) {
			return false;
		}

		for ( var first = 0; first < loop.Count; first++ ) {
			var firstEnd = (first + 1) % loop.Count;

			for ( var second = first + 1; second < loop.Count; second++ ) {
				var secondEnd = (second + 1) % loop.Count;

				if ( first == second || firstEnd == second || secondEnd == first ) {
					continue;
				}

				if ( Intersects( loop[first], loop[firstEnd], loop[second], loop[secondEnd] ) ) {
					return false;
				}
			}
		}

		return true;
	}

	// Repairs, winds, and bounds — the canonical footprint from a drag.
	public static (List<Vector2> Loop, Vector2 Min, Vector2 Max) Authored( IReadOnlyList<Vector2> outline ) {
		var loop = Wind( Repair( outline ) );

		Bounds( loop, out var min, out var max );

		return (loop, min, max);
	}

	public static List<Vector2> Repair( IReadOnlyList<Vector2> loop ) {
		if ( loop is not { Count: >= 3 } ) {
			return new List<Vector2>();
		}

		if ( IsSimple( loop ) ) {
			return loop.ToList();
		}

		Bounds( loop, out var min, out var max );

		return Rect( min, max );
	}

	public static void Bounds( IReadOnlyList<Vector2> loop, out Vector2 min, out Vector2 max ) {
		min = new Vector2( float.MaxValue, float.MaxValue );
		max = new Vector2( float.MinValue, float.MinValue );

		foreach ( var point in loop ) {
			min = new Vector2( MathF.Min( min.x, point.x ), MathF.Min( min.y, point.y ) );
			max = new Vector2( MathF.Max( max.x, point.x ), MathF.Max( max.y, point.y ) );
		}
	}

	// Floor side as a sign: -1 = floor on right (outer), +1 = floor on left (hole).
	public static float FloorSide( IReadOnlyList<Vector2> loop ) {
		return SignedArea( loop ) > 0f ? -1f : 1f;
	}

	public static float SignedArea( IReadOnlyList<Vector2> loop ) {
		var total = 0f;

		for ( var index = 0; index < loop.Count; index++ ) {
			var current = loop[index];
			var next = loop[(index + 1) % loop.Count];

			total += current.x * next.y - next.x * current.y;
		}

		return total * 0.5f;
	}

	static bool Intersects( Vector2 a, Vector2 b, Vector2 c, Vector2 d ) {
		return MathF.Max( MathF.Min( a.x, b.x ), MathF.Min( c.x, d.x ) ) <= MathF.Min( MathF.Max( a.x, b.x ), MathF.Max( c.x, d.x ) ) + Grain
			&& MathF.Max( MathF.Min( a.y, b.y ), MathF.Min( c.y, d.y ) ) <= MathF.Min( MathF.Max( a.y, b.y ), MathF.Max( c.y, d.y ) ) + Grain
			&& Side( a, b, c ) * Side( a, b, d ) <= Grain
			&& Side( c, d, a ) * Side( c, d, b ) <= Grain;
	}

	static float Side( Vector2 a, Vector2 b, Vector2 point ) => (b.x - a.x) * (point.y - a.y) - (b.y - a.y) * (point.x - a.x);

	static bool ProperlyCrosses( Vector2 a, Vector2 b, Vector2 c, Vector2 d ) {
		var first = Side( a, b, c );
		var second = Side( a, b, d );
		var third = Side( c, d, a );
		var fourth = Side( c, d, b );

		return (first > Grain && second < -Grain || first < -Grain && second > Grain)
			&& (third > Grain && fourth < -Grain || third < -Grain && fourth > Grain);
	}

	public static List<Vector2> Wind( List<Vector2> loop ) {
		if ( loop.Count < 3 || SignedArea( loop ) >= 0f ) {
			return loop;
		}

		loop.Reverse();

		return loop;
	}

	// Even-odd coverage cancels overlaps.
	public static List<List<Vector2>> Union( IEnumerable<IReadOnlyList<Vector2>> loops ) {
		var filled = Distinct( loops.Where( loop => loop is { Count: >= 3 } ).ToList() );

		// Rotated into the set's own frame where the cell grid is exact.
		if ( Framed( filled, out var pivot, out var bearing ) ) {
			return Turned( Union( Turned( filled, pivot, -bearing ) ), pivot, bearing );
		}

		if ( Slanted( filled ) ) {
			return Carved( filled, null );
		}

		var region = new List<IReadOnlyList<Vector2>>();

		foreach ( var loop in filled ) {
			region.AddRange( Subtract( new[] { loop }, region ) );
		}

		return Trace( Cells( region, null ) );
	}

	public static List<List<Vector2>> Intersect( IEnumerable<IReadOnlyList<Vector2>> loops, IReadOnlyList<Vector2> outline ) {
		var filled = loops.Where( loop => loop is { Count: >= 3 } ).ToList();

		if ( outline is not { Count: >= 3 } || filled.Count == 0 ) {
			return filled.Select( loop => loop.ToList() ).ToList();
		}

		if ( Framed( filled.Append( outline ), out var pivot, out var bearing ) ) {
			return Turned(
				Intersect( Turned( filled, pivot, -bearing ), Turned( outline, pivot, -bearing ) ),
				pivot, bearing );
		}

		if ( Slanted( filled ) || !IsRectilinear( outline ) ) {
			var spill = Subtract( filled, new[] { outline } )
				.Select( loop => (IReadOnlyList<Vector2>)loop )
				.ToList();

			return Subtract( filled, spill );
		}

		var donors = filled.SelectMany( loop => loop ).Concat( outline ).ToList();
		var xs = Axis( donors.Select( point => point.x ) );
		var ys = Axis( donors.Select( point => point.y ) );
		var cells = new List<ArchBox>();

		for ( var ix = 0; ix + 1 < xs.Count; ix++ ) {
			for ( var iy = 0; iy + 1 < ys.Count; iy++ ) {
				var min = new Vector2( xs[ix], ys[iy] );
				var max = new Vector2( xs[ix + 1], ys[iy + 1] );
				var centre = (min + max) * 0.5f;

				if ( Encloses( filled, centre ) && Contains( outline, centre ) ) {
					cells.Add( new ArchBox { Min = min, Max = max } );
				}
			}
		}

		return Trace( cells );
	}

	public static List<List<Vector2>> Subtract( IEnumerable<IReadOnlyList<Vector2>> loops, IReadOnlyList<IReadOnlyList<Vector2>> holes ) {
		var filled = loops.Where( loop => loop is { Count: >= 3 } ).ToList();

		if ( holes is not { Count: > 0 } ) {
			return filled.Select( loop => loop.ToList() ).ToList();
		}

		if ( Framed( filled.Concat( holes ), out var pivot, out var bearing ) ) {
			return Turned(
				Subtract( Turned( filled, pivot, -bearing ), Turned( holes, pivot, -bearing ) ),
				pivot, bearing );
		}

		if ( Slanted( filled ) || Slanted( holes ) ) {
			return Carved( filled, holes );
		}

		return Trace( Cells( filled, holes ) );
	}

	// Duplicate loops are dropped — coincident slanted rings break the carve's boundary walk.
	static List<IReadOnlyList<Vector2>> Distinct( List<IReadOnlyList<Vector2>> filled ) {
		var kept = new List<IReadOnlyList<Vector2>>();

		foreach ( var loop in filled ) {
			if ( !kept.Any( standing => Coincident( standing, loop ) ) ) {
				kept.Add( loop );
			}
		}

		return kept;
	}

	static bool Coincident( IReadOnlyList<Vector2> first, IReadOnlyList<Vector2> second ) {
		if ( first.Count != second.Count ) {
			return false;
		}

		for ( var index = 0; index < first.Count; index++ ) {
			if ( (first[index] - second[index]).Length > Grain ) {
				return false;
			}
		}

		return true;
	}

	// Diagonal edges fall through to ArchCarve — cell grid only handles axis-aligned.
	static bool Slanted( IEnumerable<IReadOnlyList<Vector2>> loops ) {
		return loops.Any( loop => loop is { Count: >= 3 } && !IsRectilinear( loop ) );
	}

	static List<List<Vector2>> Carved( IReadOnlyList<IReadOnlyList<Vector2>> filled, IReadOnlyList<IReadOnlyList<Vector2>> holes ) {
		var carve = new ArchCarve();

		foreach ( var loop in filled ) {
			carve.Plus( ArchCarveVolume.Over( loop, 0f, 1f ) );
		}

		foreach ( var loop in holes ?? Array.Empty<IReadOnlyList<Vector2>>() ) {
			carve.Less( ArchCarveVolume.Over( loop, -1f, 2f ) );
		}

		return carve.Resolve().Outline( 0.5f );
	}

	// Axis-aligned: cell dilation. Slanted: per-edge offset with mitred corners.
	public static List<List<Vector2>> Grow( IEnumerable<IReadOnlyList<Vector2>> loops, float amount ) {
		var filled = loops.Where( loop => loop is { Count: >= 3 } ).ToList();

		if ( filled.Count == 1 && !IsRectilinear( filled[0] ) ) {
			// Zero grow must return untouched — cell decomposition would square off diagonal edges.
			return amount <= Grain
				? new List<List<Vector2>> { filled[0].ToList() }
				: Offset( filled[0], amount );
		}

		if ( Framed( filled, out var pivot, out var bearing ) ) {
			return Turned( Grow( Turned( filled, pivot, -bearing ), amount ), pivot, bearing );
		}

		var cells = Cells( filled, null );

		if ( amount <= Grain ) {
			return Trace( cells );
		}

		return Trace( cells.Select( cell => cell.Grown( amount ) ).ToList() );
	}

	// Offset direction is off the material — outers grow outward, holes shrink inward.
	static List<List<Vector2>> Offset( IReadOnlyList<Vector2> loop, float amount ) {
		var moved = new List<Vector2>( loop.Count );

		for ( var index = 0; index < loop.Count; index++ ) {
			var behind = loop[(index - 1 + loop.Count) % loop.Count];
			var here = loop[index];
			var ahead = loop[(index + 1) % loop.Count];

			moved.Add( Mitred( behind, here, ahead, amount ) );
		}

		var offset = Simplify( moved );

		return offset.Count >= 3 && SignedArea( offset ) * SignedArea( loop ) > 0f
			? new List<List<Vector2>> { offset }
			: new List<List<Vector2>>();
	}

	// Mitre at the intersection of two offset edges; bevelled if too sharp.
	static Vector2 Mitred( Vector2 behind, Vector2 here, Vector2 ahead, float amount ) {
		var into = ArchRegion.Outward( behind, here ) * amount;
		var away = ArchRegion.Outward( here, ahead ) * amount;
		var turn = (here - behind).Normal;
		var next = (ahead - here).Normal;
		var cross = turn.x * next.y - turn.y * next.x;

		if ( MathF.Abs( cross ) < 0.0001f ) {
			return here + into;
		}

		var reach = ((here + away) - (here + into)).x * next.y - ((here + away) - (here + into)).y * next.x;
		var mitre = here + into + turn * (reach / cross);

		return (mitre - here).Length > amount * MitreReach ? here + (into + away) * 0.5f : mitre;
	}

	const float MitreReach = 4f;

	public static List<List<Vector2>> Shrink( IEnumerable<IReadOnlyList<Vector2>> loops, float amount ) {
		var filled = loops.Where( loop => loop is { Count: >= 3 } ).ToList();

		if ( filled.Count == 0 || amount <= Grain ) {
			return filled.Select( loop => loop.ToList() ).ToList();
		}

		Bounds( filled.SelectMany( loop => loop ).ToList(), out var min, out var max );

		var margin = new Vector2( amount * 3f, amount * 3f );
		var around = Subtract( new[] { Rect( min - margin, max + margin ) }, filled );

		return Subtract( filled, Grow( around, amount ) );
	}

	public static IEnumerable<List<Vector2>> Outer( IEnumerable<List<Vector2>> region ) {
		return region.Where( loop => loop.Count >= 3 && SignedArea( loop ) > 0f );
	}

	public static List<Vector2> Merge( IReadOnlyList<Vector2> outline, IReadOnlyList<Vector2> addition ) {
		var merged = Union( new[] { outline, addition } );
		var outer = Outer( merged ).Where( IsSimple ).ToList();

		if ( outer.Count == 1 ) {
			return outer[0];
		}

		return null;
	}

	public static bool Overlaps( ArchBox first, ArchBox second ) {
		return first.Min.x < second.Max.x - Grain && first.Max.x > second.Min.x + Grain
			&& first.Min.y < second.Max.y - Grain && first.Max.y > second.Min.y + Grain;
	}

	public static bool Overlaps( IReadOnlyList<Vector2> first, IReadOnlyList<Vector2> second ) {
		if ( first is not { Count: >= 3 } || second is not { Count: >= 3 } ) {
			return false;
		}

		Bounds( first, out var firstMin, out var firstMax );
		Bounds( second, out var secondMin, out var secondMax );

		if ( firstMax.x <= secondMin.x + Grain || secondMax.x <= firstMin.x + Grain
			|| firstMax.y <= secondMin.y + Grain || secondMax.y <= firstMin.y + Grain ) {
			return false;
		}

		if ( first.Any( point => Contains( second, point ) ) || second.Any( point => Contains( first, point ) ) ) {
			return true;
		}

		for ( var firstIndex = 0; firstIndex < first.Count; firstIndex++ ) {
			var firstFrom = first[firstIndex];
			var firstTo = first[(firstIndex + 1) % first.Count];

			for ( var secondIndex = 0; secondIndex < second.Count; secondIndex++ ) {
				var secondFrom = second[secondIndex];
				var secondTo = second[(secondIndex + 1) % second.Count];

				if ( ProperlyCrosses( firstFrom, firstTo, secondFrom, secondTo ) ) {
					return true;
				}
			}
		}

		return false;
	}

	public static List<ArchBox> Cells( IEnumerable<IReadOnlyList<Vector2>> loops, IReadOnlyList<IReadOnlyList<Vector2>> holes ) {
		var filled = loops.Where( loop => loop is { Count: >= 3 } ).ToList();
		var removed = (holes ?? Array.Empty<IReadOnlyList<Vector2>>()).Where( loop => loop is { Count: >= 3 } ).ToList();
		var cells = new List<ArchBox>();

		if ( filled.Count == 0 ) {
			return cells;
		}

		var donors = filled.Concat( removed ).SelectMany( loop => loop ).ToList();
		var xs = Axis( donors.Select( point => point.x ) );
		var ys = Axis( donors.Select( point => point.y ) );

		for ( var ix = 0; ix + 1 < xs.Count; ix++ ) {
			for ( var iy = 0; iy + 1 < ys.Count; iy++ ) {
				var min = new Vector2( xs[ix], ys[iy] );
				var max = new Vector2( xs[ix + 1], ys[iy + 1] );
				var centre = (min + max) * 0.5f;

				if ( Encloses( filled, centre ) && !Encloses( removed, centre ) ) {
					cells.Add( new ArchBox { Min = min, Max = max } );
				}
			}
		}

		return cells;
	}

	public static bool Contains( IReadOnlyList<Vector2> loop, Vector2 point ) {
		if ( loop is not { Count: >= 3 } ) {
			return false;
		}

		var inside = false;

		for ( int index = 0, previous = loop.Count - 1; index < loop.Count; previous = index++ ) {
			var a = loop[index];
			var b = loop[previous];

			if ( a.y > point.y != b.y > point.y
				&& point.x < (b.x - a.x) * (point.y - a.y) / (b.y - a.y) + a.x ) {
				inside = !inside;
			}
		}

		return inside;
	}

	public static bool Covered(
		IReadOnlyList<IReadOnlyList<Vector2>> region,
		IReadOnlyList<ArchFloorCutout> cutouts,
		Vector2 point ) {
		return Encloses( region, point ) && !cutouts.Any( cutout => cutout.Contains( point ) );
	}

	public static bool Encloses( IReadOnlyList<IReadOnlyList<Vector2>> loops, Vector2 point ) {
		var inside = false;

		foreach ( var loop in loops ) {
			if ( Contains( loop, point ) ) {
				inside = !inside;
			}
		}

		return inside;
	}

	// Solved, not sampled — stepping quantises boundaries.
	public static IEnumerable<float> Crossings( IReadOnlyList<Vector2> loop, Vector2 from, Vector2 to ) {
		var span = to - from;

		for ( var index = 0; index < loop.Count; index++ ) {
			var corner = loop[index];
			var edge = loop[(index + 1) % loop.Count] - corner;
			var turn = span.x * edge.y - span.y * edge.x;

			if ( MathF.Abs( turn ) < 1e-6f ) {
				continue;
			}

			var offset = corner - from;
			var alongSpan = (offset.x * edge.y - offset.y * edge.x) / turn;
			var alongEdge = (offset.x * span.y - offset.y * span.x) / turn;

			if ( alongSpan > 0f && alongSpan < 1f && alongEdge >= 0f && alongEdge <= 1f ) {
				yield return alongSpan;
			}
		}
	}

	public static IEnumerable<(float From, float To)> Inside( IReadOnlyList<Vector2> loop, Vector2 from, Vector2 to ) {
		if ( loop is not { Count: >= 3 } ) {
			yield break;
		}

		var cuts = new List<float> { 0f, 1f };

		cuts.AddRange( Crossings( loop, from, to ) );
		cuts.Sort();

		for ( var index = 0; index + 1 < cuts.Count; index++ ) {
			var start = cuts[index];
			var end = cuts[index + 1];

			if ( end - start > Grain && Contains( loop, Vector2.Lerp( from, to, (start + end) * 0.5f ) ) ) {
				yield return (start, end);
			}
		}
	}

	public static List<List<Vector2>> Trace( IReadOnlyList<ArchBox> boxes ) {
		if ( boxes.Count == 0 ) {
			return new List<List<Vector2>>();
		}

		var xs = Axis( boxes.SelectMany( box => new[] { box.Min.x, box.Max.x } ) );
		var ys = Axis( boxes.SelectMany( box => new[] { box.Min.y, box.Max.y } ) );
		var columns = xs.Count - 1;
		var covered = new bool[columns * (ys.Count - 1)];

		foreach ( var box in boxes ) {
			var fromX = Index( xs, box.Min.x );
			var toX = Index( xs, box.Max.x );
			var fromY = Index( ys, box.Min.y );
			var toY = Index( ys, box.Max.y );

			for ( var ix = fromX; ix < toX; ix++ ) {
				for ( var iy = fromY; iy < toY; iy++ ) {
					covered[iy * columns + ix] = true;
				}
			}
		}

		return Trace( xs, ys, covered );
	}

	public static List<List<Vector2>> Trace( List<float> xs, List<float> ys, bool[] covered ) {
		var columns = xs.Count - 1;
		var rows = ys.Count - 1;
		var segments = new Dictionary<int, List<int>>();

		bool Covered( int ix, int iy ) {
			return ix >= 0 && iy >= 0 && ix < columns && iy < rows && covered[iy * columns + ix];
		}

		int Node( int ix, int iy ) => iy * (columns + 1) + ix;

		void Segment( int fromX, int fromY, int toX, int toY ) {
			var key = Node( fromX, fromY );

			if ( !segments.TryGetValue( key, out var ends ) ) {
				ends = new List<int>();
				segments[key] = ends;
			}

			ends.Add( Node( toX, toY ) );
		}

		for ( var ix = 0; ix < columns; ix++ ) {
			for ( var iy = 0; iy < rows; iy++ ) {
				if ( !Covered( ix, iy ) ) {
					continue;
				}

				if ( !Covered( ix, iy - 1 ) ) Segment( ix, iy, ix + 1, iy );
				if ( !Covered( ix + 1, iy ) ) Segment( ix + 1, iy, ix + 1, iy + 1 );
				if ( !Covered( ix, iy + 1 ) ) Segment( ix + 1, iy + 1, ix, iy + 1 );
				if ( !Covered( ix - 1, iy ) ) Segment( ix, iy + 1, ix, iy );
			}
		}

		var loops = new List<List<Vector2>>();

		while ( segments.Count > 0 ) {
			var start = segments.Keys.First();
			var nodes = new List<int>();
			var at = start;

			while ( segments.TryGetValue( at, out var ends ) && ends.Count > 0 ) {
				var next = ends[0];
				ends.RemoveAt( 0 );

				if ( ends.Count == 0 ) {
					segments.Remove( at );
				}

				nodes.Add( at );
				at = next;

				if ( at == start ) {
					break;
				}
			}

			var loop = Simplify( nodes.Select( node => new Vector2( xs[node % (columns + 1)], ys[node / (columns + 1)] ) ).ToList() );

			if ( loop.Count >= 4 ) {
				loops.Add( loop );
			}
		}

		return loops;
	}

	static List<Vector2> Simplify( List<Vector2> loop ) {
		var kept = new List<Vector2>();

		for ( var index = 0; index < loop.Count; index++ ) {
			var previous = loop[(index - 1 + loop.Count) % loop.Count];
			var current = loop[index];
			var next = loop[(index + 1) % loop.Count];

			var into = current - previous;
			var outOf = next - current;

			if ( MathF.Abs( into.x * outOf.y - into.y * outOf.x ) > Grain ) {
				kept.Add( current );
			}
		}

		return kept;
	}

	static List<float> Axis( IEnumerable<float> values ) {
		return values.Select( ArchGridService.Fine ).Distinct().OrderBy( value => value ).ToList();
	}

	static int Index( List<float> axis, float value ) {
		var found = axis.BinarySearch( ArchGridService.Fine( value ) );

		return found < 0 ? ~found : found;
	}
}