using System.Text.Json.Serialization;

namespace AdvancedMappingTools;

public enum PathInterpolation
{
	Linear,
	[Title( "Catmull-Rom" )] CatmullRom,
	[Title( "Cubic Bezier" )] Bezier,
	Hermite
}

/// <summary>
/// One control point of a construction path. <see cref="TangentIn"/> points back along the curve
/// and <see cref="TangentOut"/> forward, both relative to the point. Width, height and roll
/// are read by whatever is built along the path and blend to the next point.
/// </summary>
public sealed class PathNode
{
	public Vector3 Position { get; set; }
	public Vector3 TangentIn { get; set; }
	public Vector3 TangentOut { get; set; }

	/// <summary>
	/// The two tangents move on their own, which makes a corner.
	/// </summary>
	public bool BrokenTangents { get; set; }

	public float Width { get; set; } = 1.0f;
	public float Height { get; set; } = 1.0f;

	/// <summary>
	/// Degrees around the path, positive leans the left side up.
	/// </summary>
	public float Roll { get; set; }

	/// <summary>
	/// Rise per unit of run towards the next point, set with <see cref="PathCurve.ApplySlopes"/>.
	/// </summary>
	public float? Slope { get; set; }

	public string Material { get; set; }

	public PathNode() { }

	public PathNode( Vector3 position ) => Position = position;

	public PathNode Copy() => (PathNode)MemberwiseClone();
}

/// <summary>
/// One point of a sampled path.
/// </summary>
public readonly record struct PathSample( Vector3 Position, int Segment, float T, float Width, float Height, float Roll );

/// <summary>
/// A real three dimensional construction path: open or closed, with corners or smooth, climbing
/// and turning at once. Everything that follows a line reads it through this class, so
/// stairs, ramps, roads and walls agree on where the line runs.
/// </summary>
public sealed class PathCurve
{
	const float TangentScale = 1.0f / 3.0f;
	const int LengthSteps = 16;

	public List<PathNode> Nodes { get; set; } = [];
	public bool Closed { get; set; }
	public PathInterpolation Interpolation { get; set; } = PathInterpolation.CatmullRom;

	[JsonIgnore] public int SegmentCount => Nodes.Count < 2 ? 0 : Closed ? Nodes.Count : Nodes.Count - 1;

	public static PathCurve FromPoints( IEnumerable<Vector3> points, PathInterpolation interpolation = PathInterpolation.Linear, bool closed = false ) => new()
	{
		Nodes = [.. points.Select( x => new PathNode( x ) )],
		Interpolation = interpolation,
		Closed = closed
	};

	/// <summary>
	/// A circle climbing around a centre. Cubic pieces of an eighth of a turn stay within a
	/// thousandth of the true radius, the height rises evenly.
	/// </summary>
	public static PathCurve Helix( Vector3 center, float radius, float turns, float rise, float startDegrees = 0.0f, bool clockwise = false )
	{
		var pieces = Math.Max( (int)MathF.Ceiling( MathF.Abs( turns ) * 8.0f ), 1 );
		var step = (MathF.PI * 2.0f * turns / pieces) * (clockwise ? -1.0f : 1.0f);
		var handle = 4.0f / 3.0f * MathF.Tan( step * 0.25f ) * radius;
		var climb = rise / pieces * TangentScale;
		var curve = new PathCurve { Interpolation = PathInterpolation.Bezier };
		var start = startDegrees.DegreeToRadian();

		for ( var i = 0; i <= pieces; i++ )
		{
			var angle = start + step * i;
			var outward = new Vector3( MathF.Cos( angle ), MathF.Sin( angle ), 0.0f );
			var along = new Vector3( -outward.y, outward.x, 0.0f );

			curve.Nodes.Add( new PathNode( center + outward * radius + Vector3.Up * (rise * i / pieces) )
			{
				TangentOut = along * handle + Vector3.Up * climb,
				TangentIn = along * -handle - Vector3.Up * climb
			} );
		}

		return curve;
	}

	PathNode Node( int index )
	{
		var count = Nodes.Count;

		return Closed ? Nodes[(index % count + count) % count] : Nodes[Math.Clamp( index, 0, count - 1 )];
	}

	/// <summary>
	/// Past the ends of an open path the line carries on straight.
	/// </summary>
	Vector3 Extended( int index )
	{
		var count = Nodes.Count;

		if ( Closed ) return Nodes[(index % count + count) % count].Position;
		if ( index < 0 ) return Nodes[0].Position * 2.0f - Nodes[1].Position;
		if ( index >= count ) return Nodes[count - 1].Position * 2.0f - Nodes[count - 2].Position;

		return Nodes[index].Position;
	}

	static Vector3 Cubic( Vector3 p0, Vector3 p1, Vector3 p2, Vector3 p3, float t )
	{
		var u = 1.0f - t;

		return p0 * (u * u * u) + p1 * (3.0f * u * u * t) + p2 * (3.0f * u * t * t) + p3 * (t * t * t);
	}

	/// <summary>
	/// Catmull-Rom with centripetal spacing: it passes through the same points as the uniform
	/// kind, but unevenly spaced points cannot make it loop or overshoot.
	/// </summary>
	static Vector3 Centripetal( Vector3 p0, Vector3 p1, Vector3 p2, Vector3 p3, float t )
	{
		static float Knot( Vector3 a, Vector3 b ) => MathF.Max( MathF.Sqrt( a.Distance( b ) ), 1e-4f );

		var t1 = Knot( p0, p1 );
		var t2 = t1 + Knot( p1, p2 );
		var t3 = t2 + Knot( p2, p3 );
		var x = t1 + (t2 - t1) * t;

		var a1 = p0 + (p1 - p0) * (x / t1);
		var a2 = p1 + (p2 - p1) * ((x - t1) / (t2 - t1));
		var a3 = p2 + (p3 - p2) * ((x - t2) / (t3 - t2));
		var b1 = a1 + (a2 - a1) * (x / t2);
		var b2 = a2 + (a3 - a2) * ((x - t1) / (t3 - t1));

		return b1 + (b2 - b1) * ((x - t1) / (t2 - t1));
	}

	/// <summary>
	/// A point on one segment, with t from 0 to 1.
	/// </summary>
	public Vector3 Evaluate( int segment, float t )
	{
		var a = Node( segment );
		var b = Node( segment + 1 );

		return Interpolation switch
		{
			PathInterpolation.Bezier => Cubic( a.Position, a.Position + a.TangentOut, b.Position + b.TangentIn, b.Position, t ),
			PathInterpolation.Hermite => Cubic( a.Position, a.Position + a.TangentOut * TangentScale, b.Position + b.TangentIn * TangentScale, b.Position, t ),
			PathInterpolation.CatmullRom => Centripetal( Extended( segment - 1 ), a.Position, b.Position, Extended( segment + 2 ), t ),
			_ => Vector3.Lerp( a.Position, b.Position, t )
		};
	}

	public float SegmentLength( int segment )
	{
		var length = 0.0f;
		var last = Evaluate( segment, 0.0f );

		for ( var i = 1; i <= LengthSteps; i++ )
		{
			var next = Evaluate( segment, i / (float)LengthSteps );
			length += last.Distance( next );
			last = next;
		}

		return length;
	}

	[JsonIgnore] public float Length => Enumerable.Range( 0, SegmentCount ).Sum( SegmentLength );

	bool IsStraight( int segment ) => Interpolation == PathInterpolation.Linear
		|| (Interpolation is PathInterpolation.Bezier or PathInterpolation.Hermite
			&& Node( segment ).TangentOut.IsNearZeroLength && Node( segment + 1 ).TangentIn.IsNearZeroLength);

	/// <summary>
	/// Walk the path in pieces no longer than <paramref name="maxStep"/> that turn by no more than
	/// <paramref name="maxTurn"/> degrees. Every control point is hit exactly, corners stay corners.
	/// A closed path does not repeat its first point.
	/// </summary>
	public List<PathSample> Sample( float maxStep, float maxTurn = 6.0f )
	{
		var result = new List<PathSample>();

		for ( var s = 0; s < SegmentCount; s++ )
		{
			var a = Node( s );
			var b = Node( s + 1 );
			var count = (int)MathF.Max( 1.0f, MathF.Ceiling( SegmentLength( s ) / MathF.Max( maxStep, 0.01f ) ) );

			if ( !IsStraight( s ) )
			{
				var turn = 0.0f;
				var direction = (Evaluate( s, 1.0f / LengthSteps ) - Evaluate( s, 0.0f )).Normal;

				for ( var i = 1; i < LengthSteps; i++ )
				{
					var next = (Evaluate( s, (i + 1.0f) / LengthSteps ) - Evaluate( s, i / (float)LengthSteps )).Normal;

					turn += MathF.Acos( Math.Clamp( direction.Dot( next ), -1.0f, 1.0f ) );
					direction = next;
				}

				count = (int)MathF.Max( count, MathF.Ceiling( turn.RadianToDegree() / MathF.Max( maxTurn, 0.5f ) ) );
			}

			var table = LengthTable( s );

			for ( var i = 0; i < count; i++ )
				Add( result, s, a, b, ParameterAt( table, i / (float)count ) );
		}

		if ( SegmentCount > 0 && !Closed )
			Add( result, SegmentCount - 1, Node( SegmentCount - 1 ), Node( SegmentCount ), 1.0f );

		return result;
	}

	/// <summary>
	/// Distance along a segment at evenly spaced parameters, as a share of its length.
	/// </summary>
	float[] LengthTable( int segment )
	{
		const int steps = 32;

		var table = new float[steps + 1];
		var last = Evaluate( segment, 0.0f );

		for ( var i = 1; i <= steps; i++ )
		{
			var next = Evaluate( segment, i / (float)steps );
			table[i] = table[i - 1] + last.Distance( next );
			last = next;
		}

		var total = table[steps];

		for ( var i = 0; total > 0.0f && i <= steps; i++ )
			table[i] /= total;

		return table;
	}

	/// <summary>
	/// The parameter that lies a share of the way along a segment. Curves do not run at
	/// even speed, without this pieces would be longer in the middle of a bend.
	/// </summary>
	static float ParameterAt( float[] table, float share )
	{
		var last = table.Length - 1;

		for ( var i = 1; i <= last; i++ )
		{
			if ( table[i] < share ) continue;

			var part = table[i] - table[i - 1];
			var within = part > 0.0f ? (share - table[i - 1]) / part : 0.0f;

			return (i - 1 + within) / last;
		}

		return 1.0f;
	}

	void Add( List<PathSample> list, int segment, PathNode a, PathNode b, float t )
	{
		var position = Evaluate( segment, t );

		if ( list.Count > 0 && list[^1].Position.AlmostEqual( position, 0.001f ) ) return;

		// Eased so a change of width has no kink where it starts or ends.
		var blend = t * t * (3.0f - 2.0f * t);

		list.Add( new PathSample( position, segment, t,
			a.Width + (b.Width - a.Width) * blend,
			a.Height + (b.Height - a.Height) * blend,
			a.Roll + (b.Roll - a.Roll) * blend ) );
	}

	public PathNode Add( Vector3 position )
	{
		var node = new PathNode( position );
		Nodes.Add( node );
		return node;
	}

	public PathNode Insert( int index, Vector3 position )
	{
		var node = new PathNode( position );
		Nodes.Insert( index, node );
		return node;
	}

	public void Delete( int index ) => Nodes.RemoveAt( index );

	public void Move( int index, Vector3 position ) => Nodes[index].Position = position;

	/// <summary>
	/// A copy of a point right after it, for pulling a new point out of an existing one.
	/// </summary>
	public PathNode Duplicate( int index )
	{
		var node = Nodes[index].Copy();
		Nodes.Insert( index + 1, node );
		return node;
	}

	public void SetTangentIn( int index, Vector3 tangent )
	{
		var node = Nodes[index];

		node.TangentIn = tangent;

		if ( !node.BrokenTangents ) node.TangentOut = -tangent.Normal * node.TangentOut.Length;
	}

	public void SetTangentOut( int index, Vector3 tangent )
	{
		var node = Nodes[index];

		node.TangentOut = tangent;

		if ( !node.BrokenTangents ) node.TangentIn = -tangent.Normal * node.TangentIn.Length;
	}

	public void BreakTangents( int index ) => Nodes[index].BrokenTangents = true;

	/// <summary>
	/// Put both tangents on one line, each keeping its length.
	/// </summary>
	public void AlignTangents( int index )
	{
		var node = Nodes[index];
		var direction = (node.TangentOut - node.TangentIn).Normal;

		node.BrokenTangents = false;
		node.TangentOut = direction * node.TangentOut.Length;
		node.TangentIn = -direction * node.TangentIn.Length;
	}

	/// <summary>
	/// Point the tangents of one point along the line between its neighbours.
	/// </summary>
	public void SmoothTangents( int index )
	{
		var node = Nodes[index];
		var before = Extended( index - 1 );
		var after = Extended( index + 1 );
		var direction = (after - before).Normal;

		node.BrokenTangents = false;
		node.TangentOut = direction * (node.Position.Distance( after ) * TangentScale);
		node.TangentIn = -direction * (node.Position.Distance( before ) * TangentScale);
	}

	public void SmoothAllTangents()
	{
		for ( var i = 0; i < Nodes.Count; i++ )
			SmoothTangents( i );
	}

	/// <summary>
	/// Change how points are joined. Moving to a kind with tangents gives every point smooth ones.
	/// </summary>
	public void SetInterpolation( PathInterpolation interpolation )
	{
		var hasHandles = interpolation is PathInterpolation.Bezier or PathInterpolation.Hermite;
		var hadHandles = Interpolation is PathInterpolation.Bezier or PathInterpolation.Hermite;

		if ( hasHandles && !hadHandles ) SmoothAllTangents();

		Interpolation = interpolation;
	}

	public void Close() => Closed = Nodes.Count > 2;

	public void Open() => Closed = false;

	/// <summary>
	/// Run the same line the other way.
	/// </summary>
	public void Reverse()
	{
		Nodes.Reverse();

		foreach ( var node in Nodes )
			(node.TangentIn, node.TangentOut) = (node.TangentOut, node.TangentIn);
	}

	/// <summary>
	/// Cut the path at a point. An open path gives two paths that share that point, a closed one opens there.
	/// </summary>
	public (PathCurve First, PathCurve Second) Split( int index )
	{
		if ( Closed )
		{
			var opened = new PathCurve { Interpolation = Interpolation };

			for ( var i = 0; i <= Nodes.Count; i++ )
				opened.Nodes.Add( Nodes[(index + i) % Nodes.Count].Copy() );

			return (opened, null);
		}

		return (new PathCurve { Interpolation = Interpolation, Nodes = [.. Nodes.Take( index + 1 ).Select( x => x.Copy() )] },
			new PathCurve { Interpolation = Interpolation, Nodes = [.. Nodes.Skip( index ).Select( x => x.Copy() )] });
	}

	/// <summary>
	/// Carry on with another path. Where the two meet they share one point.
	/// </summary>
	public void Join( PathCurve other )
	{
		var nodes = other.Nodes.Select( x => x.Copy() ).ToList();

		if ( Nodes.Count > 0 && nodes.Count > 0 && Nodes[^1].Position.AlmostEqual( nodes[0].Position, 0.01f ) )
		{
			Nodes[^1].TangentOut = nodes[0].TangentOut;
			nodes.RemoveAt( 0 );
		}

		Nodes.AddRange( nodes );
	}

	/// <summary>
	/// A new path of straight pieces with points every <paramref name="spacing"/> units along this one.
	/// </summary>
	public PathCurve Resampled( float spacing ) => FromPoints( Sample( spacing, 180.0f ).Select( x => x.Position ), PathInterpolation.CatmullRom, Closed );

	/// <summary>
	/// Take out points that leave the line less than <paramref name="tolerance"/> away.
	/// </summary>
	public void Simplify( float tolerance )
	{
		if ( Nodes.Count < 3 ) return;

		var keep = new bool[Nodes.Count];
		keep[0] = keep[^1] = true;

		void Check( int first, int last )
		{
			if ( last <= first + 1 ) return;

			var a = Nodes[first].Position;
			var line = Nodes[last].Position - a;
			var worst = first;
			var distance = 0.0f;

			for ( var i = first + 1; i < last; i++ )
			{
				var offset = Nodes[i].Position - a;
				var t = line.LengthSquared > 0.0f ? Math.Clamp( offset.Dot( line ) / line.LengthSquared, 0.0f, 1.0f ) : 0.0f;
				var away = (offset - line * t).Length;

				if ( away <= distance ) continue;

				distance = away;
				worst = i;
			}

			if ( distance <= tolerance ) return;

			keep[worst] = true;
			Check( first, worst );
			Check( worst, last );
		}

		Check( 0, Nodes.Count - 1 );

		Nodes = [.. Nodes.Where( ( _, i ) => keep[i] )];
	}

	/// <summary>
	/// Pull every point towards its neighbours. The ends of an open path stay where they are.
	/// </summary>
	public void Smooth( int iterations = 1, float strength = 0.5f )
	{
		for ( var pass = 0; pass < iterations; pass++ )
		{
			var moved = Nodes.Select( ( node, i ) =>
			{
				if ( !Closed && (i == 0 || i == Nodes.Count - 1) ) return node.Position;

				var middle = (Extended( i - 1 ) + Extended( i + 1 )) * 0.5f;
				return Vector3.Lerp( node.Position, middle, strength );
			} ).ToArray();

			for ( var i = 0; i < moved.Length; i++ )
				Nodes[i].Position = moved[i];
		}
	}

	public void SetWidth( int index, float width ) => Nodes[index].Width = width;

	public void SetHeight( int index, float height ) => Nodes[index].Height = height;

	public void SetRoll( int index, float degrees ) => Nodes[index].Roll = degrees;

	public void SetSlope( int index, float? slope ) => Nodes[index].Slope = slope;

	/// <summary>
	/// Move the points behind every point with a slope to the height that slope reaches.
	/// </summary>
	public void ApplySlopes()
	{
		for ( var i = 0; i < Nodes.Count - 1; i++ )
		{
			if ( Nodes[i].Slope is not float slope ) continue;

			var run = Nodes[i].Position.WithZ( 0.0f ).Distance( Nodes[i + 1].Position.WithZ( 0.0f ) );

			Nodes[i + 1].Position = Nodes[i + 1].Position.WithZ( Nodes[i].Position.z + run * slope );
		}
	}

	/// <summary>
	/// Add height evenly along the path, on top of what the points already have.
	/// </summary>
	public void AddRise( float rise )
	{
		if ( Nodes.Count < 2 ) return;

		var lengths = Enumerable.Range( 0, Nodes.Count - 1 ).Select( SegmentLength ).ToArray();
		var total = lengths.Sum();
		var walked = 0.0f;

		if ( total <= 0.0f ) return;

		for ( var i = 1; i < Nodes.Count; i++ )
		{
			walked += lengths[i - 1];
			Nodes[i].Position += Vector3.Up * (rise * walked / total);
		}
	}

	/// <summary>
	/// Lean every point into the turn it makes, by up to this many degrees at a right angle.
	/// </summary>
	public void BankIntoTurns( float degrees )
	{
		for ( var i = 0; i < Nodes.Count; i++ )
		{
			if ( !Closed && (i == 0 || i == Nodes.Count - 1) ) continue;

			var a = (Nodes[i].Position - Extended( i - 1 )).WithZ( 0.0f ).Normal;
			var b = (Extended( i + 1 ) - Nodes[i].Position).WithZ( 0.0f ).Normal;
			var turn = MathF.Atan2( a.x * b.y - a.y * b.x, a.Dot( b ) ).RadianToDegree();

			// Turning left the right side comes up, which is a negative roll.
			Nodes[i].Roll = -degrees * Math.Clamp( turn / 90.0f, -1.0f, 1.0f );
		}
	}

	/// <summary>
	/// Stations along the path with stable frames, width, height and roll applied.
	/// <paramref name="rise"/> adds height along the way, eased to start and end level if asked.
	/// </summary>
	public PathTrack Track( float maxStep, FrameMode mode = FrameMode.Upright, float maxTurn = 6.0f, float rise = 0.0f, bool ease = false )
	{
		var samples = Sample( maxStep, maxTurn );

		if ( rise != 0.0f && samples.Count > 1 )
		{
			var walked = new float[samples.Count];

			for ( var i = 1; i < samples.Count; i++ )
				walked[i] = walked[i - 1] + samples[i - 1].Position.Distance( samples[i].Position );

			for ( var i = 0; i < samples.Count; i++ )
			{
				var share = walked[i] / walked[^1];

				if ( ease ) share = share * share * (3.0f - 2.0f * share);

				samples[i] = samples[i] with { Position = samples[i].Position + Vector3.Up * (rise * share) };
			}
		}

		return new PathTrack( PathFrames.Build( samples, Closed, mode ), Closed );
	}
}

/// <summary>
/// Frames along a path and the lines running beside it. A side line is the path moved sideways.
/// On the inside of a turn tighter than that distance such a line would run backwards and
/// make a loop, and everything built on it would fold over itself. Here the stations of such
/// a stretch all meet in the point where the line crosses itself: steps turn into wedges
/// around it, and a deck turns into a fan.
/// </summary>
public sealed class PathTrack
{
	const float MaxSearch = 6.0f;
	const float PivotSpacing = 0.05f;
	const float PivotRun = 3.0f;
	const float PivotReach = 1.5f;
	const float MaxBackTurn = 200.0f;
	const float SteepLevel = 0.5f;
	const float SteepBlend = 0.25f;
	const float PinchClimb = 8.0f;

	readonly Dictionary<int, (Vector3[] Points, Vector3[] Ups)> _lines = [];

	float _reachLeft;
	float _reachRight;
	float _spacing = PivotSpacing;

	public IReadOnlyList<PathFrame> Frames { get; }
	public bool Closed { get; }
	public int Count => Frames.Count;
	public float Length => Frames[^1].Distance;

	public PathTrack( IReadOnlyList<PathFrame> frames, bool closed )
	{
		Frames = frames;
		Closed = closed;
	}

	/// <summary>
	/// Say how far everything built along this track reaches to each side. Only the outermost
	/// lines are then worked out, the ones between them lie on the straight spokes from the path.
	/// Lines worked out on their own could cross where the turn is tight, these cannot.
	/// </summary>
	public PathTrack Reach( float left, float right )
	{
		_reachLeft = left;
		_reachRight = right;
		_lines.Clear();

		return this;
	}

	/// <summary>
	/// Let stations that gather in one point stand exactly on it. A band as wide as a road then runs
	/// out in a clean point, where a hair between them would leave it a row of slivers.
	/// Steps need that hair: each of them has to keep an area of its own.
	/// </summary>
	public PathTrack Pinched()
	{
		_spacing = 0.0f;
		_lines.Clear();

		return this;
	}

	/// <summary>
	/// The same track with its sections standing straight up instead of square to a climbing path,
	/// tall enough to keep their height across the slope. A section that leans back lets its top
	/// run backward on the inside of a climbing turn, one that stands up cannot. Only near a
	/// vertical stretch does it lean with the path again.
	/// </summary>
	public PathTrack Plumbed()
	{
		var frames = Frames.Select( frame =>
		{
			var level = frame.Forward.WithZ( 0.0f ).Length;
			var share = Math.Clamp( (level - SteepLevel) / SteepBlend, 0.0f, 1.0f );

			return share > 0.0f ? frame with { Up = Vector3.Lerp( frame.Up, Vector3.Up / level, share ) } : frame;
		} ).ToList();

		return new PathTrack( frames, Closed );
	}

	/// <summary>
	/// A track along points already sampled.
	/// </summary>
	public static PathTrack Along( IReadOnlyList<Vector3> path, bool closed, FrameMode mode = FrameMode.Upright ) =>
		new( PathFrames.Build( path, closed, mode ), closed );

	/// <summary>
	/// Cut the stations into stretches of about the wanted length.
	/// </summary>
	public List<(int From, int To)> Bays( float length )
	{
		var bays = new List<(int From, int To)>();
		var start = 0;

		for ( var i = 1; i < Count; i++ )
		{
			var isLast = i == Count - 1;
			var rest = Frames[^1].Distance - Frames[i].Distance;

			// A short leftover joins the last stretch instead of standing alone.
			if ( isLast || (Frames[i].Distance - Frames[start].Distance >= length - 0.01f && rest >= length * 0.5f) )
			{
				bays.Add( (start, i) );
				start = i;
			}
		}

		return bays;
	}

	/// <summary>
	/// The point <paramref name="left"/> beside station <paramref name="index"/> and <paramref name="up"/> above it.
	/// </summary>
	public Vector3 Place( int index, float left, float up = 0.0f )
	{
		var (points, ups) = Line( left );

		return points[index] + ups[index] * up;
	}

	/// <summary>
	/// A track of its own along a side line, straight above it by <paramref name="lift"/>. Something
	/// thin that runs beside the path, like a handrail, is swept around this line, so all
	/// of it turns around the same curve. The lift is straight up: on the inside of a bend a side
	/// line can be steep, and a height along its leaning up would throw the rail around.
	/// </summary>
	public PathTrack Side( float left, float lift = 0.0f )
	{
		var points = new List<Vector3>( Count );

		for ( var i = 0; i < (Closed ? Count - 1 : Count); i++ )
			points.Add( Place( i, left ) + Vector3.Up * lift );

		return Along( points, Closed );
	}

	/// <summary>
	/// The station before a distance along the path and how far on towards the next one it lies.
	/// </summary>
	public (int Index, float T) Locate( float distance )
	{
		var low = 0;
		var high = Count - 2;

		while ( low < high )
		{
			var middle = (low + high + 1) / 2;

			if ( Frames[middle].Distance <= distance ) low = middle;
			else high = middle - 1;
		}

		var part = Frames[low + 1].Distance - Frames[low].Distance;

		return (low, part > 0.0f ? Math.Clamp( (distance - Frames[low].Distance) / part, 0.0f, 1.0f ) : 0.0f);
	}

	public Vector3 PlaceAt( float distance, float left, float up = 0.0f )
	{
		var (index, t) = Locate( distance );

		return PlaceBetween( index, t, left, up );
	}

	public Vector3 PlaceBetween( int index, float t, float left, float up = 0.0f ) =>
		Vector3.Lerp( Place( index, left, up ), Place( index + 1, left, up ), t );

	/// <summary>
	/// The frame at a distance along the path.
	/// </summary>
	public PathFrame FrameAt( float distance )
	{
		var (index, t) = Locate( distance );
		var a = Frames[index];
		var b = Frames[index + 1];
		var forward = Vector3.Lerp( a.Forward, b.Forward, t ).Normal;
		var left = Vector3.Lerp( a.Left, b.Left, t ).Normal;

		return new PathFrame( Vector3.Lerp( a.Position, b.Position, t ), forward, left, Vector3.Cross( forward, left ).Normal,
			distance, a.Stretch + (b.Stretch - a.Stretch) * t, a.Width + (b.Width - a.Width) * t, a.Height + (b.Height - a.Height) * t );
	}

	(Vector3[] Points, Vector3[] Ups) Line( float left )
	{
		var key = (int)MathF.Round( left * 100.0f );

		if ( _lines.TryGetValue( key, out var line ) ) return line;

		var reach = left > 0.0f ? _reachLeft : _reachRight;

		line = reach > 0.0f && MathF.Abs( left ) < reach - 0.001f ? OnSpokes( left, reach ) : Build( left );
		_lines[key] = line;

		return line;
	}

	(Vector3[], Vector3[]) OnSpokes( float left, float reach )
	{
		var (outer, _) = Line( left > 0.0f ? reach : -reach );
		var points = new Vector3[Count];
		var ups = new Vector3[Count];
		var share = MathF.Abs( left ) / reach;

		for ( var i = 0; i < Count; i++ )
		{
			points[i] = Vector3.Lerp( Frames[i].Position, outer[i], share );
			ups[i] = Frames[i].Up;
		}

		return (points, ups);
	}

	(Vector3[], Vector3[]) Build( float left )
	{
		var count = Frames.Count;
		var points = new Vector3[count];
		var ups = new Vector3[count];

		for ( var i = 0; i < count; i++ )
		{
			var frame = Frames[i];

			points[i] = frame.Position + frame.Left * (left * frame.Stretch * frame.Width);
			ups[i] = frame.Up;
		}

		if ( left == 0.0f || count < 3 ) return (points, ups);

		// A closed path starts its repair outside any loop, so no loop runs over the seam.
		var shift = Closed ? CalmStart( points ) : 0;

		if ( shift != 0 )
		{
			var ring = count - 1;
			var rotatedPoints = new Vector3[count];
			var rotatedUps = new Vector3[count];

			for ( var i = 0; i < count; i++ )
			{
				rotatedPoints[i] = points[(i + shift) % ring];
				rotatedUps[i] = ups[(i + shift) % ring];
			}

			Untangle( rotatedPoints, rotatedUps, shift, MathF.Abs( left ) );

			for ( var i = 0; i < ring; i++ )
			{
				points[(i + shift) % ring] = rotatedPoints[i];
				ups[(i + shift) % ring] = rotatedUps[i];
			}

			points[count - 1] = points[0];
			ups[count - 1] = ups[0];
		}
		else
		{
			Untangle( points, ups, 0, MathF.Abs( left ) );
		}

		return (points, ups);
	}

	bool RunsBack( Vector3[] points, int segment, int shift )
	{
		var ring = Count - 1;
		var a = Frames[Closed ? (segment + shift) % ring : segment];
		var b = Frames[Closed ? (segment + shift + 1) % ring : segment + 1];
		var along = (b.Position - a.Position).WithZ( 0.0f );
		var side = (points[segment + 1] - points[segment]).WithZ( 0.0f );

		return along.Length > 1e-4f && side.Dot( along ) < 0.0f;
	}

	int CalmStart( Vector3[] points )
	{
		var ring = Count - 1;

		for ( var s = 0; s < ring; s++ )
		{
			var before = (s + ring - 1) % ring;
			var along = (Frames[s + 1].Position - Frames[s].Position).WithZ( 0.0f );
			var side = (points[s + 1] - points[s]).WithZ( 0.0f );
			var alongBefore = (Frames[before + 1].Position - Frames[before].Position).WithZ( 0.0f );
			var sideBefore = (points[before + 1] - points[before]).WithZ( 0.0f );

			if ( side.Dot( along ) >= 0.0f && sideBefore.Dot( alongBefore ) >= 0.0f ) return s;
		}

		return 0;
	}

	void Untangle( Vector3[] points, Vector3[] ups, int shift, float distance )
	{
		var count = points.Length;

		for ( var pass = 0; pass < 4; pass++ )
		{
			var found = false;

			for ( var s = 0; s < count - 1; s++ )
			{
				if ( !RunsBack( points, s, shift ) ) continue;

				var end = s;
				while ( end + 1 < count - 1 && RunsBack( points, end + 1, shift ) ) end++;

				found = true;
				Collapse( points, ups, s, end, distance );
				s = end;
			}

			if ( !found ) return;
		}
	}

	/// <summary>
	/// Replace a backward stretch by the point where the line before it meets the line after it.
	/// </summary>
	void Collapse( Vector3[] points, Vector3[] ups, int first, int last, float distance )
	{
		var count = points.Length;
		var reach = distance * MaxSearch;

		// The line runs around a point instead of past a corner: a spiral tighter than the
		// section is wide. Everything meets in the middle of that spiral.
		if ( TurnOf( points, first, last ) > MaxBackTurn )
		{
			var middle = Vector3.Zero;

			for ( var i = first; i <= last + 1; i++ )
				middle += points[i];

			Pivot( points, first, last + 1, middle / (last + 2 - first) );
			return;
		}

		float Walked( int a, int b )
		{
			var sum = 0.0f;
			for ( var i = a; i < b; i++ ) sum += points[i].Distance( points[i + 1] );
			return sum;
		}

		for ( var before = first - 1; before >= 0; before-- )
		{
			if ( Walked( before, first ) > reach ) break;

			for ( var after = last + 1; after < count - 1; after++ )
			{
				if ( Walked( last + 1, after ) > reach ) break;

				if ( !Crossing( points[before], points[before + 1], points[after], points[after + 1], out var hit, out _ ) ) continue;

				Fillet( points, before, after, hit, distance );
				return;
			}
		}

		// The line never comes back: it ends inside the turn, so it stops where it started to go wrong.
		if ( first == 0 )
		{
			Pivot( points, 0, last, points[last + 1] );
			return;
		}

		if ( last >= count - 2 )
		{
			Pivot( points, first + 1, count - 1, points[first] );
			return;
		}

		// The stretches on both sides are too short to meet. They would if they carried on,
		// and whatever lies past that point on either side is part of the fold.
		var meet = (points[first] + points[last + 1]) * 0.5f;

		if ( Crossing( points[first - 1], points[first], points[last + 1], points[last + 2], out var extended, out _, true ) && extended.Distance( meet ) < reach )
			meet = extended;

		bool IsPast( int station ) => (meet - points[station]).WithZ( 0.0f ).Dot( Frames[Math.Min( station, Count - 1 )].Forward.WithZ( 0.0f ) ) < 0.0f;

		var low = first;
		var high = last + 1;

		while ( low > 0 && IsPast( low ) ) low--;
		while ( high < count - 1 && !IsPast( high ) ) high++;

		Fillet( points, low, high - 1, meet, distance );
	}

	static float TurnOf( Vector3[] points, int first, int last )
	{
		var turn = 0.0f;

		for ( var i = first; i < last; i++ )
		{
			var a = (points[i + 1] - points[i]).WithZ( 0.0f ).Normal;
			var b = (points[i + 2] - points[i + 1]).WithZ( 0.0f ).Normal;

			turn += MathF.Abs( MathF.Atan2( a.x * b.y - a.y * b.x, a.Dot( b ) ) );
		}

		return turn.RadianToDegree();
	}

	/// <summary>
	/// Run the line around a corner instead of through its loop, on a small curve that touches
	/// both straight parts. Stations keep their height, so the surface climbs along that
	/// curve. It is just long enough for the climb to stay a slope: straight up it would be a
	/// row of slivers, and on level ground a hair is all it takes.
	/// </summary>
	void Fillet( Vector3[] points, int before, int after, Vector3 corner, float distance )
	{
		var climb = MathF.Abs( points[after + 1].z - points[before].z );

		if ( _spacing == 0.0f && climb < PinchClimb )
		{
			Pinch( points, before + 1, after, corner );
			return;
		}

		var reach = MathF.Min( MathF.Max( (after - before) * _spacing, climb * PivotRun ) * 0.5f, distance * PivotReach );

		var (start, low) = Walk( points, before, -1, corner, reach );
		var (end, high) = Walk( points, after + 1, 1, corner, reach );

		var span = (float)(high - low);

		for ( var i = low + 1; i < high; i++ )
		{
			var t = (i - low) / span;
			var u = 1.0f - t;

			points[i] = (start * (u * u) + corner * (2.0f * u * t) + end * (t * t)).WithZ( points[i].z );
		}
	}

	/// <summary>
	/// From a corner along a line, going through the stations from one index in one direction.
	/// Gives the point at a distance and the station just before reaching it.
	/// </summary>
	static (Vector3 Point, int Station) Walk( Vector3[] points, int index, int direction, Vector3 corner, float distance )
	{
		var last = corner;
		var walked = 0.0f;

		for ( var i = index; i >= 0 && i < points.Length; i += direction )
		{
			var part = last.WithZ( 0.0f ).Distance( points[i].WithZ( 0.0f ) );

			if ( walked + part >= distance )
				return (Vector3.Lerp( last, points[i], (distance - walked) / MathF.Max( part, 1e-5f ) ), i);

			walked += part;
			last = points[i];
		}

		var end = direction < 0 ? 0 : points.Length - 1;

		return (points[end], end);
	}

	/// <summary>
	/// Gather stations at the end of a line that stops inside a turn. They keep their height
	/// and stand a hair apart, so every face keeps its area.
	/// </summary>
	void Pivot( Vector3[] points, int from, int to, Vector3 pivot )
	{
		if ( _spacing == 0.0f && MathF.Abs( points[to].z - points[from].z ) < PinchClimb )
		{
			Pinch( points, from, to, pivot );
			return;
		}

		var count = to - from + 1;
		var steps = new Vector3[count];

		for ( var i = 1; i < count; i++ )
			steps[i] = steps[i - 1] + Frames[Math.Min( from + i, Count - 1 )].Forward.WithZ( 0.0f ).Normal * _spacing;

		var middle = steps.Aggregate( Vector3.Zero, ( a, b ) => a + b ) / count;

		for ( var i = 0; i < count; i++ )
			points[from + i] = (pivot + steps[i] - middle).WithZ( points[from + i].z );
	}

	/// <summary>
	/// Put stations on one point, in height as well: a side that only differs in height has no area.
	/// </summary>
	static void Pinch( Vector3[] points, int from, int to, Vector3 point )
	{
		var height = 0.0f;

		for ( var i = from; i <= to; i++ )
			height += points[i].z;

		height /= MathF.Max( to - from + 1, 1 );

		for ( var i = from; i <= to; i++ )
			points[i] = point.WithZ( height );
	}

	static bool Crossing( Vector3 a, Vector3 b, Vector3 c, Vector3 d, out Vector3 hit, out float t, bool extended = false )
	{
		var r = (b - a).WithZ( 0.0f );
		var s = (d - c).WithZ( 0.0f );
		var denominator = r.x * s.y - r.y * s.x;

		hit = default;
		t = 0.0f;

		if ( MathF.Abs( denominator ) < 1e-6f ) return false;

		var ac = (c - a).WithZ( 0.0f );

		t = (ac.x * s.y - ac.y * s.x) / denominator;

		var u = (ac.x * r.y - ac.y * r.x) / denominator;

		if ( !extended && (t < 0.0f || t > 1.0f || u < 0.0f || u > 1.0f) ) return false;

		hit = a + (b - a) * t;

		return true;
	}
}