// Last edited on 2024-07-25 18:13:12 by stolfi

#debug "!! Loading fan_monotonify.inc ...\n"

#macro fan_monotonify(V, E, Neo,Nei, oshape, subdiv)
  // Decomposes all faces of the fan into Z-monotone polygons. Parameters:
  //
  // {V}      Array of vertex coordinates {V[1..Nv]}.
  // {E}      Array of edges {E[1..Ne]}.
  // {Neo}    Number of edges in each outer chain.
  // {Nei}    Number of edges in each inner chain.
  // {oshape} Type of outer chain: 0 = convex, 1 = dented, 2 = concave.
  // {subdiv} Which sub-figure we are generating (8 or 9).
  
  // Assumes each entry {E[ke]} is a triple of integers {<kv_org,kv_dst,ty>} 
  // where {kv_org,kv_dst} are indices into {V}, and {ty} is a edge type code.
  // Entry {E[0]} is not used
  
  // Assumes that {V[1..Neo+1]} are the vertices of the outer chain of plaza [0],
  // then {V[Neo+2..Neo+Nei+2} are the inner chain vertices of the same,
  // both in incresing order of elevation;
  // and these are followed by the {Neo+Nei+2} vertices of of plaza [1].
  
  // Returns an array {D[1..Nd]} with the diagonals that define the convex tiling.
  // Each entry {D[kd]} is a triple {<kv_org,kv_dst,ty>}, like the entries of {E},
  // where the type is 0 for now. Entry {D[0]} is not used.

  #debug "!! Generating monotonic tiling edges ...\n"
  
  #if ((subdiv != 8) & (subdiv != 9)) kaboom("bad {subdiv}") #end
  
  #local Nv = dimension_size(V, 1) - 1;
  #local Ne = dimension_size(E, 1) - 1;
  #local Nf = (Neo + Nei + 2) + 2; // Inferred number of original faces.
  
  #local Nvh = int(Nv/2); // Number of vertices per plaza.
  #if (Nv != 2*Nvh) kaboom("{Nv} is not even") #end
  #if (Nvh != Neo+Nei+2) kaboom("{Neo,Nei,Nv} inconsistent") #end
  
  // Can't predict {Nd} easily...
  #local Nd_max = 2*(Nvh - 3);  // Max number of diagonals.
  
  #local D = array[Nd_max+1];
  #local D[0] = < -1, -1, -1 >;
  
  #local nd = 0;  // Count of diagonals created.
  #if (subdiv = 8)
    fan_monotonify_plazas_dumb(Neo,Nei,oshape, D,nd)
  #elseif (subdiv = 9)
    fan_monotonify_plazas_smart(Neo,Nei,oshape, D,nd)
  #else
    // Not implemented:
    kaboom("Case not applicable or implemented")
  #end
  #debug concat("!!   nd after = ", str(nd,0,0), "\n")
  #local Nd = nd;
  
  // Trim the array:
  #local D_trim = array[Nd+1]
  #for (kd,1,Nd)
    #local D_trim[kd] = D[kd];
  #end
  
  D_trim
#end

#macro fan_monotonify_plazas_dumb(Neo,Nei,oshape, D,nd)
  // Chooses diagonals that break the plazas into convex polygons, the dumb way.
  // Stores the diagonals in {D} starting at {D[nd+1]} and increments {nd}.
  
  #debug "!!   Dumb monotonification of the plazas ...\n"

  #if (mod(Neo,2) != 0) kaboom("{Neo} is not even") #end
  #if (mod(Nei,2) != 0) kaboom("{Nei} is not even") #end

  #local Nvh = Neo+Nei+2;           // Number of vertices per plaza.
  #local kvo_ini = 1;               // Index of first vertex on outer chain of plaza [0].
  #local kvo_fin = kvo_ini + Neo;   // Index of last vertex on outer chain of plaza [0].
  #local kvo_mid = kvo_ini + Neo/2; // Index of middle vertex on outer chain of plaza [0].
 
  #local kvi_ini = kvo_fin + 1;     // Index of first vertex on inner chain of plaza [0].
  #local kvi_fin = kvi_ini + Nei;   // Index of last vertex on inner chain of plaza [0].
  #local kvi_mid = kvi_ini + Nei/2; // Index of middle vertex on inner chain of plaza [0].

  #for (km,0,1)
    #if ((oshape = 0) | (oshape = 1))
      // Nothing to do.
    #elseif (oshape = 2)
      // Outer chain is concave.
      // Connect middle inner chain vertex to middle outer chain vertex:
      #local kv0 = kvi_mid + km*Nvh;
      #local kv1 = kvo_mid + km*Nvh;
      #if ((V[kv1].z >= V[kv1-1].z) | (V[kv1].z >= V[kv1+1].z)) kaboom("outer chain is not symmetric") #end
      fan_partition_one(V, kv0,kv1, D,nd)
    #elseif (oshape = 3)
      // Both chains are deeply dented.
      #if (Nei = 0)
        // Connect the inner chain vertex to every dent tip:
        #local kvir = kvi_ini + km*Nvh;
        #local kvoa = kvo_ini + 1 + km*Nvh;
        #local kvob = kvo_fin - 1 + km*Nvh;
        fan_partition_one_to_many(V, kvir, kvoa,kvob,+2, D,nd)
      #else
        // Connect every other interior inner vertex to the corresp outer one:
        #if (Nei != Neo) kaboom("{Nei,Neo} inconsistent") #end
        #local kva = kvi_ini + 1 + km*Nvh;
        #local kvb = kvi_fin - 1 + km*Nvh;
        #local kvc = kvo_ini + 1 + km*Nvh;
        #local kvd = kvo_fin - 1 + km*Nvh;
        fan_partition_zipper(V, kva,kvb,+2, kvc,kvd,+2, D,nd)  
      #end
    #else
      kaboom("Invalid {oshape}")
    #end
  #end
#end

#macro fan_monotonify_plazas_smart(Neo,Nei,oshape, D,nd)
  // Chooses diagonals that break the plazas into Z-monoone polygons, 
  // so as to minimize new edge-plane crossings.
  // Stores the diagonals in {D} starting at {D[nd+1]} and increments {nd}.

  #debug "!!   Smart monotonification of the plazas ...\n"

  #if (mod(Neo,2) != 0) kaboom("{Neo} is not even") #end
  #if (mod(Nei,2) != 0) kaboom("{Nei} is not even") #end

  #local Nvh = Neo+Nei+2;           // Number of vertices per plaza.
  #local kvo_ini = 1;               // Index of first vertex on outer chain of plaza [0].
  #local kvo_fin = kvo_ini + Neo;   // Index of last vertex on outer chain of plaza [0].
  #local kvo_mid = kvo_ini + Neo/2; // Index of middle vertex on outer chain of plaza [0].
  
  #local kvi_ini = kvo_fin + 1;     // Index of first vertex on inner chain of plaza [0].
  #local kvi_fin = kvi_ini + Nei;   // Index of last vertex on inner chain of plaza [0].
  #local kvi_mid = kvi_ini + Nei/2; // Index of middle vertex on inner chain of plaza [0].

  #for (km,0,1)
    #if ((oshape = 0) | (oshape = 1))
      // Nothing to do, plazas are already monotonic.
    #elseif (oshape = 2)
      // Concave outer strip: Same as the dumb one.
      // Connect middle inner chain vertex to middle outer chain vertex:
      #local kvom = kvo_mid + km*Nvh;
      #local kvim = kvi_mid + km*Nvh;
      #if ((V[kvom].z >= V[kvom-1].z) | (V[kvom].z >= V[kvom+1].z)) kaboom("outer chain is not symmetric") #end
      #if (Nei > 0)
        #if ((V[kvim].z <= V[kvim-1].z) | (V[kvim].z <= V[kvim+1].z)) kaboom("inner chain is not symmetric") #end
      #end
      fan_partition_one(V, kvom,kvim, D,nd)
    #elseif (oshape = 3)
      // Deeply dented outer and inner chains.

      #if (Nei != 0)
        // Cut off inner dents:
        #local kvia = kvi_ini + 1 + km*Nvh;
        #local kvib = kvi_fin - 3 + km*Nvh;
        #local kvic = kvia + 2;
        #local kvid = kvib + 2;
        fan_partition_zipper(V, kvia,kvib,+2,  kvic,kvid,+2, D,nd)
      #end

      // Connect outer dents in zigzag fashion:
      #local kvoa = kvo_ini + 1 + km*Nvh;
      #local kvob = kvo_fin - 1 + km*Nvh;
      #while (kvoa != kvob)
        #debug concat("!!      kvoa = ", str(kvoa,0,0), " kvob = ", str(kvob,0,0), "\n")
        fan_partition_one(V, kvoa, kvob, D,nd)
        #if (kvoa < kvob)
          #local kvot = kvoa + 2;
        #else
          #local kvot = kvoa - 2;
        #end
        #local kvoa = kvob;
        #local kvob = kvot;
      #end
 
      // Connnect top inner to second outer:
      #local kvi = kvi_mid + km*Nvh;
      #local kvo = kvo_ini + 1 + km*Nvh;
      fan_partition_one(V, kvi, kvo, D,nd)
    #else
      kaboom("Invalid {oshape}")
    #end
  #end
#end