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 };
	}
}

// Cell grid instead of a clipper - every authored footprint is a union of axis-aligned rectangles.
public static class ArchFootprint
{
	const float Grain = 0.02f;

	// Eight sides is a round enough shaft to read as one and few enough faces to weld cleanly; the
	// author raises it when a lift core wants to look turned rather than cut.
	public const int LeastSegments = 8;

	// Turned about a point, in one place: a shape and everything filed under it have to swing through the
	// same angle about the same centre, and two callers doing their own trigonometry is two centres.
	public static List<Vector2> Turned( IReadOnlyList<Vector2> loop, Vector2 about, float degrees )
	{
		var turned = new List<Vector2>( loop.Count );
		var radians = degrees.DegreeToRadian();
		var cos = MathF.Cos( radians );
		var sin = MathF.Sin( radians );

		foreach ( var point in loop )
		{
			var local = point - about;

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

		return turned;
	}

	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 ) };
	}

	// One answer to "what does this part read as": its authored loop when it has one, otherwise the rect
	// its bounds describe. Platforms, roofs and cutouts all ask this, so a shape dragged as a loop is
	// never re-derived per consumer - the way ArchCutSegment.Outline answers for a cut's own legs.
	public static List<Vector2> OrRect( IReadOnlyList<Vector2> loop, Vector2 min, Vector2 max )
	{
		return loop is { Count: >= 4 } ? new List<Vector2>( loop ) : Rect( min, max );
	}

	// A closed n-gon inscribed in the box, so a circle is authored as the bounds that were dragged plus
	// a segment count - the vertices are DERIVED, which is what keeps a round shape round while the drag
	// itself still snaps. Never closed with a repeated first point: a duplicate corner is a degenerate
	// edge, and a degenerate edge is where a mesh stops being manifold.
	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 );

		// Started half a step round so an eight-sided shaft presents flats to the axes rather than points,
		// which is how an octagonal core sits against a wall instead of poking a corner through it.
		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 )
	{
		if ( loop is null || loop.Count < 4 )
		{
			return false;
		}

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

			if ( MathF.Abs( span.x ) > Grain && MathF.Abs( span.y ) > Grain )
			{
				return false;
			}
		}

		return true;
	}

	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;
	}

	// One answer to "what does a drag become": repaired to a simple loop, wound to the canonical
	// direction, and its bounds read off. Platforms, roofs and rooms all author their footprint this
	// way, so a part's stored shape can never disagree with the outline it draws.
	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 ) );
		}
	}

	// Which side of a CCW loop the floor stands on, as a sign on the edge's outward normal: void left,
	// floor right is -1, the mirror is +1. Well trims and rail guards all ask this before probing an
	// edge, so a hole and the guard round it can never disagree about which way the floor is.
	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 - clip each loop against what is covered to keep the set disjoint.
	public static List<List<Vector2>> Union( IEnumerable<IReadOnlyList<Vector2>> loops )
	{
		var filled = loops.Where( loop => loop is { Count: >= 3 } ).ToList();

		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 ) );
	}

	// What the loops and the outline BOTH cover. Both sides donate coordinates, so the outline's boundary lands
	// on a cell line rather than slicing one - a clamp to the outline's bounds fills a notch straight back in.
	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 ( 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 ( Slanted( filled ) || Slanted( holes ) )
		{
			return Carved( filled, holes );
		}

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

	// The cell grid is exact while every edge lies on an axis, and squares off any edge that does not - which
	// is how a circular bool came back as a stepped cross under its own round trim. ArchCarve's arrangement
	// already splits along a slanted edge and walks its own boundary, so anything diagonal is answered there.
	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 );
	}

	// Dilation distributes over union, so reflex corners square off with no join rule.
	//
	// That only holds while every edge lies on an axis. A cell grid squares a slanted edge off, so a turned loop
	// came back as an axis-aligned stair of boxes - which is a shaft ring standing square while the hole it lines
	// is at thirty degrees. A lone slanted loop is therefore OFFSET instead: each edge moved off the material and
	// the corners mitred where the moved edges meet, which is the mitre the ring was always documented to have.
	public static List<List<Vector2>> Grow( IEnumerable<IReadOnlyList<Vector2>> loops, float amount )
	{
		var filled = loops.Where( loop => loop is { Count: >= 3 } ).ToList();

		if ( amount > Grain && filled.Count == 1 && !IsRectilinear( filled[0] ) )
		{
			return Offset( filled[0], amount );
		}

		var cells = Cells( filled, null );

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

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

	// Off the MATERIAL, not outward in world terms: an outer loop is wound with what it covers on its left, so
	// the right-hand normal already points away from it, and a hole wound the other way points into itself -
	// which is the same dilation, closing the hole rather than opening it.
	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 );

		// A dilation that turned the loop inside out is a hole narrower than twice the amount, and it is gone.
		return offset.Count >= 3 && SignedArea( offset ) * SignedArea( loop ) > 0f
			? new List<List<Vector2>> { offset }
			: new List<List<Vector2>>();
	}

	// Where the two moved edge lines cross. A corner sharp enough to throw the mitre out to nothing useful is
	// bevelled instead - taken back to the nearer of the two moved ends.
	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;
	}

	// Four times the offset is a corner sharper than any authored shape needs a point on.
	const float MitreReach = 4f;

	// Erode by growing what surrounds it and subtracting - keeps reflex corners square, no self-intersection.
	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 ) );
	}

	// Traced regions are outers plus holes wound the other way - solids want the outers only.
	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;
	}

	// The cheap bounds question: do these two boxes overlap, grain tolerance included. Culls, porch
	// drops and roof reaches all ask it - a room that merely touches a roof's box from outside must not
	// seal it, so the test is strict past the grain rather than inclusive at the edge.
	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;
	}

	// Both sides donate coordinates, so a hole's boundary lands on a cell line, not slicing one.
	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;
	}

	// The one copy of the crossing count - it was written out five times over.
	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;
	}

	// One answer to "is this point solid": inside the region and inside none of its holes. Slab cells
	// and plank lanes both ask it, so a hole that opens the slab opens the boards over it the same way.
	public static bool Covered(
		IReadOnlyList<IReadOnlyList<Vector2>> region,
		IReadOnlyList<ArchFloorCutout> cutouts,
		Vector2 point )
	{
		return Encloses( region, point ) && !cutouts.Any( cutout => cutout.Contains( point ) );
	}

	// Even-odd across the whole set, so an outer plus a hole reads as a ring, not a solid.
	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; an ALONG-edge segment reports no crossing.
	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;
			}
		}
	}

	// The stretches of a segment that lie INSIDE a loop, as parameters along it. Split at the crossings and
	// keep the spans whose midpoint is enclosed - the same walk the board lanes do, asked of one loop, which
	// is what "how much of this wall is standing in that hole" means.
	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 );
	}

	// Wound with covered on the left - outers CCW, holes clockwise, the winding the tool assumes.
	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( Snap ).Distinct().OrderBy( value => value ).ToList();
	}

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

		return found < 0 ? ~found : found;
	}

	static float Snap( float value ) => ArchGridService.Fine( value );
}