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

namespace Sunless.Architecture;

// One shape inside another is a RING, and a ring is stitched corner to corner: each inner corner is chorded to the
// outer corner standing nearest it round the same centre, so what is left round a turned hole is four trapezoids
// rather than the strips a sweep has to cut it into. It is what a modeller draws by hand, and it holds its four
// faces however far the hole is turned.
//
// Nothing here is taken on trust. A chord across a reflex corner leaves geometry outside the solid it was carved
// from, so the stitch is MEASURED against the area it has to cover and handed back only when it tiles it exactly -
// otherwise the caller sweeps instead.
static class ArchCarveQuads
{
	const int BreakSalt = 71;

	// Twice the finest coordinate the tool has, which is past the furthest a snap can carry a corner off a
	// turned loop - under it a break would be rounding rather than damage.
	const float LeastBite = ArchGridService.FinestSize * 2f;

	// A face with more corners than a quad, cut into quads and the odd triangle using ONLY the corners it already
	// has - so every boundary edge survives and the neighbours across them still meet it edge for edge. Triangles
	// first because a triangulation is easy to be sure of, then pairs of them fused back into the squarest quads
	// available, which is how a quad mesher gets its quads without inventing vertices to hang them on.
	public static IEnumerable<List<Vector2>> Split( List<Vector2> loop )
	{
		if ( loop.Count <= 4 )
		{
			return new[] { loop };
		}

		var wedges = Wedges( loop );

		return wedges.Count == 0 ? new[] { loop } : Fused( wedges );
	}

	static List<List<Vector2>> Wedges( List<Vector2> loop )
	{
		var remaining = new List<Vector2>( loop );
		var wedges = new List<List<Vector2>>();

		while ( remaining.Count > 3 )
		{
			var clipped = Clipped( remaining );

			if ( clipped < 0 )
			{
				return new List<List<Vector2>>();
			}

			var behind = remaining[(clipped - 1 + remaining.Count) % remaining.Count];
			var ahead = remaining[(clipped + 1) % remaining.Count];

			wedges.Add( new List<Vector2> { behind, remaining[clipped], ahead } );
			remaining.RemoveAt( clipped );
		}

		wedges.Add( remaining );

		return wedges;
	}

	// The corner to take off: convex, and with none of the rest standing inside the wedge it would leave.
	static int Clipped( List<Vector2> loop )
	{
		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];

			if ( Turn( behind, here, ahead ) < ArchCarve.Grain )
			{
				continue;
			}

			var wedge = new List<Vector2> { behind, here, ahead };

			if ( loop.Where( corner => !Corner( wedge, corner ) ).Any( corner => ArchFootprint.Contains( wedge, corner ) ) )
			{
				continue;
			}

			return index;
		}

		return -1;
	}

	static bool Corner( List<Vector2> wedge, Vector2 corner ) => wedge.Any( held => (held - corner).Length < ArchCarve.Grain );

	static float Turn( Vector2 behind, Vector2 here, Vector2 ahead )
	{
		var into = here - behind;
		var away = ahead - here;

		return into.x * away.y - into.y * away.x;
	}

	// Squarest first, so the pairing spends its triangles on the quads worth having rather than on whichever two
	// happened to be adjacent. Each triangle goes into at most one quad; what is left over stays a triangle.
	static List<List<Vector2>> Fused( List<List<Vector2>> wedges )
	{
		var taken = new bool[wedges.Count];
		var quads = new List<List<Vector2>>();

		var candidates = new List<(float Cost, int Left, int Right, List<Vector2> Quad)>();

		for ( var left = 0; left < wedges.Count; left++ )
		{
			for ( var right = left + 1; right < wedges.Count; right++ )
			{
				if ( Fuse( wedges[left], wedges[right] ) is { } quad )
				{
					candidates.Add( (Skew( quad ), left, right, quad) );
				}
			}
		}

		foreach ( var (_, left, right, quad) in candidates.OrderBy( candidate => candidate.Cost ) )
		{
			if ( taken[left] || taken[right] )
			{
				continue;
			}

			taken[left] = true;
			taken[right] = true;

			quads.Add( quad );
		}

		for ( var index = 0; index < wedges.Count; index++ )
		{
			if ( !taken[index] )
			{
				quads.Add( wedges[index] );
			}
		}

		return quads;
	}

	// The quad two triangles either side of a shared edge make, or null when they share no edge or the result
	// would fold back on itself.
	static List<Vector2> Fuse( List<Vector2> left, List<Vector2> right )
	{
		for ( var index = 0; index < left.Count; index++ )
		{
			var from = left[index];
			var to = left[(index + 1) % left.Count];

			if ( !Corner( right, from ) || !Corner( right, to ) )
			{
				continue;
			}

			var beyond = right.FirstOrDefault( corner => !Corner( new List<Vector2> { from, to }, corner ) );
			var behind = left[(index + 2) % left.Count];
			var quad = new List<Vector2> { behind, from, beyond, to };

			return Convex( quad ) ? quad : null;
		}

		return null;
	}

	static bool Convex( List<Vector2> quad )
	{
		for ( var index = 0; index < quad.Count; index++ )
		{
			var behind = quad[(index - 1 + quad.Count) % quad.Count];
			var ahead = quad[(index + 1) % quad.Count];

			if ( Turn( behind, quad[index], ahead ) < ArchCarve.Grain )
			{
				return false;
			}
		}

		return true;
	}

	// How far off square its corners stand - a rectangle scores nothing, a sliver scores four.
	static float Skew( List<Vector2> quad )
	{
		var skew = 0f;

		for ( var index = 0; index < quad.Count; index++ )
		{
			var into = (quad[index] - quad[(index - 1 + quad.Count) % quad.Count]).Normal;
			var away = (quad[(index + 1) % quad.Count] - quad[index]).Normal;

			skew += MathF.Abs( Vector2.Dot( into, away ) );
		}

		return skew;
	}

	public static List<List<Vector2>> Ring( IReadOnlyList<ArchCarveVolume> volumes )
	{
		if ( volumes.Count != 2 )
		{
			return null;
		}

		var first = Wound( volumes[0].Footprint );
		var second = Wound( volumes[1].Footprint );

		if ( first is null || second is null )
		{
			return null;
		}

		var host = Holds( first, second ) ? first : Holds( second, first ) ? second : null;

		if ( host is null )
		{
			return null;
		}

		var standing = ReferenceEquals( host, first );
		var hole = Broken( host, standing ? second : first, standing ? volumes[1].Break : volumes[0].Break );
		var faces = Stitched( host, hole );

		return faces is not null && Tiles( faces, host ) ? faces : null;
	}

	static List<Vector2> Wound( IReadOnlyList<Vector2> footprint )
	{
		return footprint is { Count: >= 3 } ? ArchFootprint.Wind( footprint.ToList() ) : null;
	}

	// Strictly inside: every corner enclosed and every edge inside along its whole length, so a hole that touches
	// or crosses the boundary is no ring and is left to the sweep.
	static bool Holds( List<Vector2> outer, List<Vector2> inner )
	{
		if ( inner.Any( corner => !ArchFootprint.Contains( outer, corner ) ) )
		{
			return false;
		}

		for ( var index = 0; index < inner.Count; index++ )
		{
			var spans = ArchFootprint.Inside( outer, inner[index], inner[(index + 1) % inner.Count] ).ToList();

			if ( spans.Count != 1 || spans[0].From > 0.001f || spans[0].To < 0.999f )
			{
				return false;
			}
		}

		return true;
	}

	// Disrepair only ever subtracts. A break pulls each CONVEX corner of the hole in along its own bisector - never
	// out into material that was standing - so the loop it hands back stands inside the loop that was dragged and
	// the ring round it can only lose area. A reflex corner is left where it is: moved inward it would push the
	// edges either side of it out past the clean loop, which is the one way an inward offset could add.
	static List<Vector2> Broken( List<Vector2> host, List<Vector2> hole, ArchCarveBreak breaking )
	{
		if ( !breaking.Breaks )
		{
			return hole;
		}

		var bite = Bite( host, hole, breaking.Jitter );

		if ( bite < LeastBite )
		{
			return hole;
		}

		var broken = new List<Vector2>();

		for ( var index = 0; index < hole.Count; index++ )
		{
			var behind = hole[(index - 1 + hole.Count) % hole.Count];
			var here = hole[index];
			var ahead = hole[(index + 1) % hole.Count];
			var inward = Turn( behind, here, ahead ) < ArchCarve.Grain ? Vector2.Zero : Inward( behind, here, ahead );
			var offset = bite * ArchBarrierShape.Noise( breaking.Seed, index, BreakSalt );

			// A corner either bites or stays exactly where it was authored - never snapped on the spot. A reflex
			// corner, a spike, and a bite the grid would round away all stay: that rounding is the one thing that
			// could carry a corner back OUT of the loop it was dragged with.
			var bitten = inward.Length > 0.5f && offset >= LeastBite;

			broken.Add( bitten ? ArchGridService.Fine( here + inward * offset ) : here );
		}

		return broken;
	}

	// No further than a third of the way across the NARROWEST material standing round the hole, and no further than
	// a quarter of the hole's own narrowest span. Past the first, a ring piece's centre lands inside the cut and the
	// whole piece goes with it - which is the cut taking material nobody dragged it over. Past the second, the loop
	// folds through itself.
	static float Bite( List<Vector2> host, List<Vector2> hole, float jitter )
	{
		ArchFootprint.Bounds( hole, out var min, out var max );

		var gap = MathF.Min( Gap( host, hole ), Gap( hole, host ) );

		return MathF.Min( jitter, MathF.Min( gap / 3f, MathF.Min( max.x - min.x, max.y - min.y ) * 0.25f ) );
	}

	// Corner to boundary, both ways round: the closest the two loops come is always a corner of one against an
	// edge of the other, so the pair of scans measures the ring at its thinnest wherever that falls.
	static float Gap( List<Vector2> loop, List<Vector2> against )
	{
		var boundary = ArchRunPath.Of( loop, 0f, true );
		var gap = float.MaxValue;

		foreach ( var corner in against )
		{
			if ( boundary.Nearest( corner, out _, out var reach ) )
			{
				gap = MathF.Min( gap, reach );
			}
		}

		return gap;
	}

	// Wound by ArchFootprint.Wind, so the loop turns anticlockwise and its inside is to the LEFT of every edge.
	static Vector2 Inward( Vector2 behind, Vector2 here, Vector2 ahead )
	{
		var into = (here - behind).Normal;
		var away = (ahead - here).Normal;
		var bisector = new Vector2( -into.y, into.x ) + new Vector2( -away.y, away.x );

		return bisector.Length < 0.0001f ? Vector2.Zero : bisector.Normal;
	}

	// One face per inner edge, taking the outer edges the chords at its two ends stepped over: none and it is a
	// triangle, one and it is the quad this exists for, more and the surplus outer edges fan off the corner the
	// second chord landed on.
	static List<List<Vector2>> Stitched( List<Vector2> host, List<Vector2> hole )
	{
		var reach = Reach( host, hole );

		if ( Around( reach, host.Count ) != host.Count )
		{
			return null;
		}

		var faces = new List<List<Vector2>> { new( hole ) };

		for ( var index = 0; index < hole.Count; index++ )
		{
			var next = (index + 1) % hole.Count;
			var corner = reach[index];
			var step = Step( reach[index], reach[next], host.Count );

			if ( step == 0 )
			{
				faces.Add( new List<Vector2> { host[corner], hole[next], hole[index] } );

				continue;
			}

			faces.Add( new List<Vector2> { host[corner], host[(corner + 1) % host.Count], hole[next], hole[index] } );

			for ( var extra = 1; extra < step; extra++ )
			{
				var at = (corner + extra) % host.Count;

				faces.Add( new List<Vector2> { host[at], host[(at + 1) % host.Count], hole[next] } );
			}
		}

		return faces;
	}

	// Winding exactly once round the outer loop is what keeps the chords from crossing each other.
	static int Around( List<int> reach, int corners )
	{
		var travelled = 0;

		for ( var index = 0; index < reach.Count; index++ )
		{
			travelled += Step( reach[index], reach[(index + 1) % reach.Count], corners );
		}

		return travelled;
	}

	static int Step( int from, int to, int corners ) => (to - from + corners) % corners;

	// Which outer corner each inner corner chords to. Corner for corner when the two loops have the same number
	// of them - every offset tried and the shortest set of chords kept, because the pairing wanted is by CORNER:
	// a hole in the end of a long slab chords to the two corners beside it, which angles about the hole's own
	// centre get wrong the moment it sits off centre. That mistake spends two chords on one corner and leaves a
	// triangle and a four-corner fan where four quads were there to be had.
	static List<int> Reach( List<Vector2> host, List<Vector2> hole )
	{
		if ( host.Count == hole.Count )
		{
			return Paired( host, hole );
		}

		var centre = hole.Aggregate( Vector2.Zero, ( total, point ) => total + point ) / hole.Count;

		return hole.Select( corner => Nearest( host, centre, corner ) ).ToList();
	}

	// Both loops wind the same way, so an offset is the whole choice - there are only as many pairings as corners.
	static List<int> Paired( List<Vector2> host, List<Vector2> hole )
	{
		var best = 0;
		var shortest = float.MaxValue;

		for ( var offset = 0; offset < host.Count; offset++ )
		{
			var total = 0f;

			for ( var index = 0; index < hole.Count; index++ )
			{
				total += (host[(index + offset) % host.Count] - hole[index]).Length;
			}

			if ( total < shortest )
			{
				shortest = total;
				best = offset;
			}
		}

		return Enumerable.Range( 0, hole.Count ).Select( index => (index + best) % host.Count ).ToList();
	}

	static int Nearest( List<Vector2> host, Vector2 centre, Vector2 corner )
	{
		var wanted = MathF.Atan2( corner.y - centre.y, corner.x - centre.x );
		var best = 0;
		var closest = float.MaxValue;

		for ( var index = 0; index < host.Count; index++ )
		{
			var angle = MathF.Atan2( host[index].y - centre.y, host[index].x - centre.x ) - wanted;
			var apart = MathF.Abs( MathF.Atan2( MathF.Sin( angle ), MathF.Cos( angle ) ) );

			if ( apart < closest )
			{
				closest = apart;
				best = index;
			}
		}

		return best;
	}

	// The hole's own loop is one of the faces, so a stitch that tiles covers the whole host exactly once. Areas
	// that add up while a face hangs outside would need another face folded back over the shortfall, which the
	// per-face simplicity and containment tests rule out.
	static bool Tiles( List<List<Vector2>> faces, List<Vector2> host )
	{
		var wanted = MathF.Abs( ArchFootprint.SignedArea( host ) );
		var covered = 0f;

		foreach ( var face in faces )
		{
			var area = ArchFootprint.SignedArea( face );
			var centre = face.Aggregate( Vector2.Zero, ( total, point ) => total + point ) / face.Count;

			if ( area < ArchCarve.Grain || !ArchFootprint.Contains( host, centre ) )
			{
				return false;
			}

			if ( face.Count > 3 && !ArchFootprint.IsSimple( face ) )
			{
				return false;
			}

			covered += area;
		}

		return MathF.Abs( covered - wanted ) < MathF.Max( 1f, wanted * 0.0001f );
	}
}