using System;
namespace CharacterEditor;

/// <summary>For identical skin weights, skinning is affine: only the convex hull can touch a plane.</summary>
internal static class FootContactHull
{
 internal static NativeSoleContacts.Point[] Reduce(NativeSoleContacts.Point[] points)
 {
  return points.GroupBy(p=>(p.B0,p.W0,p.B1,p.W1,p.B2,p.W2,p.B3,p.W3))
   .SelectMany(g=>Hull(g.Distinct().ToArray())).ToArray();
 }
 readonly record struct Face(int A,int B,int C,Vector3 Normal);
 static IEnumerable<NativeSoleContacts.Point> Hull(NativeSoleContacts.Point[] samples)
 {
  if(samples.Length<=4)return samples;
  var p=samples.Select(s=>s.Position).ToArray();
  int a=0,b=Enumerable.Range(1,p.Length-1).MaxBy(i=>(p[i]-p[a]).LengthSquared);
  var ab=p[b]-p[a]; if(ab.LengthSquared<1e-10f)return new[]{samples[a]};
  int c=Enumerable.Range(0,p.Length).MaxBy(i=>Vector3.Cross(ab,p[i]-p[a]).LengthSquared);
  var normal=Vector3.Cross(ab,p[c]-p[a]).Normal;
  if(normal.LengthSquared<.1f)return new[]{samples[a],samples[b]};
  int d=Enumerable.Range(0,p.Length).MaxBy(i=>MathF.Abs(Vector3.Dot(normal,p[i]-p[a])));
  if(MathF.Abs(Vector3.Dot(normal,p[d]-p[a]))<.00001f)
  {
   var axis=ab.Normal;var second=Vector3.Cross(normal,axis);
   var ordered=Enumerable.Range(0,p.Length).OrderBy(i=>Vector3.Dot(p[i],axis)).ThenBy(i=>Vector3.Dot(p[i],second)).ToArray();
   float Cross(int i,int j,int k)=>Vector3.Dot(Vector3.Cross(p[j]-p[i],p[k]-p[j]),normal);
   var lower=new List<int>();var upper=new List<int>();
   foreach(int i in ordered){while(lower.Count>=2&&Cross(lower[^2],lower[^1],i)<=0)lower.RemoveAt(lower.Count-1);lower.Add(i);}
   foreach(int i in ordered.Reverse()){while(upper.Count>=2&&Cross(upper[^2],upper[^1],i)<=0)upper.RemoveAt(upper.Count-1);upper.Add(i);}
   return lower.Concat(upper).Distinct().Select(i=>samples[i]).ToArray();
  }
  var center=(p[a]+p[b]+p[c]+p[d])*.25f;var faces=new List<Face>();
  void Add(int i,int j,int k){var n=Vector3.Cross(p[j]-p[i],p[k]-p[i]).Normal;if(Vector3.Dot(n,center-p[i])>0){(j,k)=(k,j);n=-n;}faces.Add(new(i,j,k,n));}
  Add(a,b,c);Add(a,d,b);Add(b,d,c);Add(c,d,a);
  for(int i=0;i<p.Length;i++)
  {
   var visible=faces.Where(f=>Vector3.Dot(f.Normal,p[i]-p[f.A])>.00001f).ToArray();
   if(visible.Length==0)continue;
   var edges=new Dictionary<(int,int),int>();
   void Edge(int j,int k){var key=(Math.Min(j,k),Math.Max(j,k));edges[key]=edges.GetValueOrDefault(key)+1;}
   foreach(var f in visible){Edge(f.A,f.B);Edge(f.B,f.C);Edge(f.C,f.A);faces.Remove(f);}
   foreach(var e in edges)if(e.Value==1)Add(e.Key.Item1,e.Key.Item2,i);
  }
  return faces.SelectMany(f=>new[]{f.A,f.B,f.C}).Distinct().Select(i=>samples[i]).ToArray();
 }
}