local sdist = function (x1, y1, x2, y2) return ((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)) end
local dist = function (x1, y1, x2, y2) return ((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)) ^ 0.5 end
local abs = math.abs
local min, max, sqrt = math.min, math.max, math.sqrt
local mf = math.floor
local segments
local edges1 = {}
local edges2 = {}
local edgeN = 1
local grit = {}
local gritN = 1

local cutters = {}
local cutterN 
local checks = {}
local checkN

for i=1,10000,1 do 
  table.insert(cutters,ffi.new("float[7]"))
end

local delaunay = require('source/libs/delaunay')
local dpoint = delaunay.Point
local dedge = delaunay.Edge
local dtri = delaunay.Triangle
local intersect 
local function clusterSort(a,b) return a[1]<b[1] end
local function sweepSort(a,b)
  return a[4]==b[4] and a[1]<b[1] or a[4]<b[4] 
end
local function matchSort(a,b) 
  if a[1]==b[1] then 
    if a[2]==b[2] then 
      if a[3]==b[3] then 
        if a[4]==a[4] then 
          return a[6]<b[6] 
        else
          return a[4]<b[4] 
        end
      else
        return a[3]<b[3] 
      end
    else
      return a[2]<b[2] 
    end
  else
    return a[1]<b[1] 
  end
end

local  classicConcat = classicConcat

local function inTable(t, v)
  for i = 1, #t, 1 do
    if t[i] == v then
      return true
    end
  end
  return false
end

local function addCutter(side,t,e,x,y1,y2)
  cutterN = cutterN +1
  cutters[cutterN] = cutters[cutterN] or ffi.new("float[7]")
  cutters[cutterN][1],
  cutters[cutterN][2],
  cutters[cutterN][3],
  cutters[cutterN][4],
  cutters[cutterN][5],
  cutters[cutterN][6] = side,t,e,x, y1,y2
end

local function addCheck(x1,y1,x2,y2,t,e)
  checkN = checkN +1
  checks[checkN] = checks[checkN] or ffi.new("float[7]")
  checks[checkN][1],
  checks[checkN][2],
  checks[checkN][3],
  checks[checkN][4],
  checks[checkN][5],
  checks[checkN][6] = x1,y1,x2,y2,t,e
end


function edgesame(p1,p2,p3,p4)
  return ((p1 == p3) and (p2 == p4))
      or ((p1 == p4) and (p2 == p3))
end

local edje = dedge(dpoint(0,0),dpoint(0,0))
local function segedge(seg,edge)
  edje.p1.x,edje.p1.y,edje.p2.x,edje.p2.y = seg[1], seg[2], seg[3], seg[4]
  return  edje:same(edge) 
end

local function edgesNear(edge1,edge2)
  return  distPointToLineSegment2(edge1.p1.x, edge1.p1.y, edge2.p1.x, edge2.p1.y, edge2.p2.x, edge2.p2.y)<0.001 
     and  distPointToLineSegment2(edge1.p2.x, edge1.p2.y, edge2.p1.x, edge2.p1.y, edge2.p2.x, edge2.p2.y)<0.001
end

local function segsNear(edge1,edge2)
  return  distPointToLineSegment2(edge1[1], edge1[2], edge2[1], edge2[2], edge2[3], edge2[4])<0.0001 
     and  distPointToLineSegment2(edge1[3], edge1[4], edge2[1], edge2[2], edge2[3], edge2[4])<0.0001
end


local function triTable(t)
  return t[0]<0 and {t[1],t[2],t[3],t[4],t[5],t[6]} or {t[1],t[2]}
end

local function triTable2(p,f)
  return f[0]<0 and {p.x,p.y,f[3],f[4],f[5],f[6]} or {p.x,p.y}
end

function pointInDTri(tri,px,py)
  return  onSameSide2(px,py,tri.p1.x,tri.p1.y,tri.p2.x,tri.p2.y, tri.p3.x,tri.p3.y) 
      and onSameSide2(px,py,tri.p2.x,tri.p2.y,tri.p1.x,tri.p1.y, tri.p3.x,tri.p3.y) 
      and onSameSide2(px,py,tri.p3.x,tri.p3.y,tri.p1.x,tri.p1.y, tri.p2.x,tri.p2.y) 
end

local function triTouchesGridSquare(tri,bbox)

  if pointInBox(tri.p1.x,tri.p1.y, bbox[1],bbox[2],bbox[3],bbox[4]) or 
     pointInBox(tri.p2.x,tri.p2.y, bbox[1],bbox[2],bbox[3],bbox[4]) or 
     pointInBox(tri.p2.x,tri.p2.y, bbox[1],bbox[2],bbox[3],bbox[4]) then 
    return true
 end

 local a,b,c = tri:getSidesLength()

  if a+b+c<bbox[5] then 
    if bbox[1] <= max(tri.p1.x, tri.p2.x, tri.p3.x) and
      min(tri.p1.x, tri.p2.x, tri.p3.x) <= bbox[3] and
      bbox[2] <= max(tri.p1.y, tri.p2.y, tri.p3.y) and
      min(tri.p1.y, tri.p2.y, tri.p3.y) < bbox[4] then
      return true 
    end
  else
    if 
      intersect(tri.e1.p1.x,tri.e1.p1.y, tri.e1.p2.x,tri.e1.p2.y, bbox[1],bbox[2],bbox[1],bbox[4]) or
      intersect(tri.e1.p1.x,tri.e1.p1.y, tri.e1.p2.x,tri.e1.p2.y, bbox[1],bbox[2],bbox[3],bbox[2]) or
      intersect(tri.e1.p1.x,tri.e1.p1.y, tri.e1.p2.x,tri.e1.p2.y, bbox[3],bbox[4],bbox[1],bbox[4]) or
      intersect(tri.e1.p1.x,tri.e1.p1.y, tri.e1.p2.x,tri.e1.p2.y, bbox[3],bbox[4],bbox[3],bbox[2]) or

      intersect(tri.e1.p1.x,tri.e1.p1.y, tri.e1.p2.x,tri.e1.p2.y, bbox[1],bbox[2],bbox[1],bbox[4]) or
      intersect(tri.e1.p1.x,tri.e1.p1.y, tri.e1.p2.x,tri.e1.p2.y, bbox[1],bbox[2],bbox[3],bbox[2]) or
      intersect(tri.e1.p1.x,tri.e1.p1.y, tri.e1.p2.x,tri.e1.p2.y, bbox[3],bbox[4],bbox[1],bbox[4]) or
      intersect(tri.e1.p1.x,tri.e1.p1.y, tri.e1.p2.x,tri.e1.p2.y, bbox[3],bbox[4],bbox[3],bbox[2]) or

      intersect(tri.e1.p1.x,tri.e1.p1.y, tri.e1.p2.x,tri.e1.p2.y, bbox[1],bbox[2],bbox[1],bbox[4]) or
      intersect(tri.e1.p1.x,tri.e1.p1.y, tri.e1.p2.x,tri.e1.p2.y, bbox[1],bbox[2],bbox[3],bbox[2]) or
      intersect(tri.e1.p1.x,tri.e1.p1.y, tri.e1.p2.x,tri.e1.p2.y, bbox[3],bbox[4],bbox[1],bbox[4]) or
      intersect(tri.e1.p1.x,tri.e1.p1.y, tri.e1.p2.x,tri.e1.p2.y, bbox[3],bbox[4],bbox[3],bbox[2]) then

      return true
    end
  end

  return false
end

local function segTouchesGridSquare(seg,bbox)
  if pointInBox(seg[1],seg[2], bbox[1],bbox[2],bbox[3],bbox[4]) or 
     pointInBox(seg[3],seg[4], bbox[1],bbox[2],bbox[3],bbox[4]) then 
    return true
 end

  if math.dist(seg[1],seg[2],seg[3],seg[4])< bbox[5] then 
   if   bbox[1] <= max(seg[1], seg[3]) and
        bbox[3] >= min(seg[1], seg[3])  and
        bbox[2] <= max(seg[2], seg[4]) and
        bbox[4] >= min(seg[2], seg[4])  then
      return true 
    end
  else
    if intersect(seg[1],seg[2],seg[3],seg[4], bbox[1],bbox[2],bbox[1],bbox[4]) or
       intersect(seg[1],seg[2],seg[3],seg[4], bbox[1],bbox[2],bbox[3],bbox[2]) or
       intersect(seg[1],seg[2],seg[3],seg[4], bbox[3],bbox[4],bbox[1],bbox[4]) or
       intersect(seg[1],seg[2],seg[3],seg[4], bbox[3],bbox[4],bbox[3],bbox[2]) then

      return true
    end
  end

  return false
end

local function killTri(trit,tris,eos,t)
  for i=1,3,1 do 
    if trit[t][i]>0 and not eos[t][i] then 
      child=trit[t][i]
      trit[t][i]=0
      table.insert(tris,t)
      killTri(trit,tris,eos,child)
    end
  end
end


local function canFill(shape,filled)
  for i=1,filled[0],1 do
    if filled[i]==0 then 
      shape[0]=1
      shape[1]=i
      return true
    end
  end
  return false
end

-- local function inTable(t, v,n)
--   for i = 1, n, 1 do
--     if t[i] == v then
--       return true
--     end
--   end
--   return false
-- end

local function max4(a,b,c,d)
  return max(max(max(a,b),c),d)
end

local function min4(a,b,c,d)
  return min(min(min(a,b),c),d)
end

local function pointSort(a,b)
  return a.x<b.x--dist(0,0,a.x,a.y)<dist(0,0,b.x,b.y)
end

local function findLoop(out,shape,edges,used)
  -- table.insert(out.paths,shape)
  local x,y = shape[#shape-1],shape[#shape]
  local addedSeg = false
  for e=#edges,1,-1 do 
    if not used[e] then 
      local isSeg = edges[e][5]~=1
      if (not used.prevSeg) and (not isSeg) and addedSeg  then 
        break
      end
      local x1,y1,x2,y2 = edges[e][1],edges[e][2],edges[e][3],edges[e][4]
      local left,right = (x==x1 and y==y1),(x==x2 and y==y2)
      local ix,iy = left and x2 or x1,left and y2 or y1
      if left or right then
        if #shape>3 then 
          for s=3,#shape-1,2 do 
            if ix==shape[s] and iy == shape[s+1] then 
              goto continue 
            end
          end
        end
        if  ix==shape[1] and iy == shape[2] then 
          local used2 = lume.clone(used) ; used2[e]=true
          -- concat(shape,{ix,iy})
          local area = polyArea(shape)
          if not out.area or area<out.area then 
            table.remove(shape)
            table.remove(shape)
            table.remove(shape)
            table.remove(shape)
            out.area=area
            out.shape=shape
            out.used=used2
          end
        else
          local used2 = lume.clone(used) ; used2[e]=true
          if isSeg then 
            addedSeg = true 
            used2.segged = true
          end
          used2.prevSeg = isSeg
          findLoop(out,lume.concat(shape,{ix,iy}),edges,used2)
        end
      end
    end
    ::continue::
  end
end

local function matchCurves(tris,ftris,trit,segments,used,cut)

  ftris[0][0][0]=#tris
  cutterN=0
  checkN=0
  local addCutters = cut==1
  for t=1,#tris,1 do
    local tri = tris[t]
    ftris[t][1][1],ftris[t][1][2] = tri.p1.x, tri.p1.y
    ftris[t][2][1],ftris[t][2][2] = tri.p2.x, tri.p2.y
    ftris[t][3][1],ftris[t][3][2] = tri.p3.x, tri.p3.y
    addCheck(
      min(tri.e1.p1.x,tri.e1.p2.x),min(tri.e1.p1.y,tri.e1.p2.y),
      max(tri.e1.p1.x,tri.e1.p2.x),max(tri.e1.p1.y,tri.e1.p2.y), 
      t,1
    ) 
    addCheck(
      min(tri.e2.p1.x,tri.e2.p2.x),min(tri.e2.p1.y,tri.e2.p2.y),
      max(tri.e2.p1.x,tri.e2.p2.x),max(tri.e2.p1.y,tri.e2.p2.y), 
      t,2
    ) 
    addCheck(
      min(tri.e3.p1.x,tri.e3.p2.x),min(tri.e3.p1.y,tri.e3.p2.y),
      max(tri.e3.p1.x,tri.e3.p2.x),max(tri.e3.p1.y,tri.e3.p2.y), 
      t,3
    )
  end

  local m = 0
  for s = 1, segments[0][0], 1 do
    local seg = segments[s]
    addCheck(
      min(seg[1],seg[3]),min(seg[2],seg[4]),
      max(seg[1],seg[3]),max(seg[2],seg[4]), 
      s,0
    )
  end

  clearTail(checks,checkN+1)
  table.sort(checks,matchSort)

  _time("prep checks ")

  -- match edges to segs and add unmatched to open table

  local shared = 0
  local ceg
  for c=1,#checks,1 do 
    local check = checks[c] 
    if check[6]==0 then 
      ceg = check
    else 
      if ceg then 
        if check[1]==ceg[1] and check[2]==ceg[2] and check[3]==ceg[3] and check[4]==ceg[4] then 
          local seg  = segments[ceg[5]]
          local t,e  = check[5],check[6]
          local tri  = tris [t]
          local ftri = ftris[t]
          local edge = e == 1 and tri.e1 or (e == 2 and tri.e2 or e == 3 and tri.e3)
          local a,b = e==1 and 1 or (e==2 and 2 or 3),e==1 and 2 or (e==2 and 3 or 1)
          if segedge(seg,edge) then
            if ceg[5]>0 and ceg[5]<segments[0][0] then
              used[ceg[5]]=1 
            end
            ftri[a][0]=math.min(-1, ftri[a][0])
            ftri[b][0]=math.min(-1, ftri[b][0])
            ftri[e][0]=math.min(-2, ftri[e][0])
            if ftri[a][1] == seg[1] then 
              --  ftri[a][1],ftri[a][2],ftri[b][1],ftri[b][2],  ftri[a][5],ftri[a][6],ftri[b][3],ftri[b][4] 
              -- = seg[1], seg[2], seg[3], seg[4], seg[5], seg[6], seg[7], seg[8] 
                ftri[a][5],ftri[a][6],ftri[b][3],ftri[b][4] 
              =  seg[5], seg[6], seg[7], seg[8] 
            else
              --   ftri[a][1],ftri[a][2],ftri[b][1],ftri[b][2],  ftri[a][5],ftri[a][6],ftri[b][3],ftri[b][4] 
              -- = seg[3], seg[4], seg[1], seg[2],  seg[7], seg[8], seg[5], seg[6]
                ftri[a][5],ftri[a][6],ftri[b][3],ftri[b][4] 
              =   seg[7], seg[8], seg[5], seg[6]
            end
            trit[t][e] = 0
          end
        else
          local p = checks[c-1]
          if p and p[6]~=0 and check[1]==p[1] and check[2]==p[2] and check[3]==p[3] and check[4]==p[4] then
            local t1,e1  = check[5],check[6]
            local t2,e2  = p[5],p[6]
            local tri1,tri2 = tris [t1],tris [t2]
            local edge1 = e1 == 1 and tri1.e1 or (e1 == 2 and tri1.e2 or e1 == 3 and tri1.e3)
            local edge2 = e2 == 1 and tri2.e1 or (e2 == 2 and tri2.e2 or e2 == 3 and tri2.e3)
            if edge1:same(edge2) then 
              trit[t1][e1] = t2
              trit[t2][e2] = t1

              if addCutters then 
                addCutter(0,t1,e1,min(edge1.p1.x,edge1.p2.x),
                  min(edge1.p1.y,edge1.p2.y),max(edge1.p1.y,edge1.p2.y))
                addCutter(1,t1,e1,max(edge1.p1.x,edge1.p2.x),0,0)

                addCutter(0,t2,e2,min(edge2.p1.x,edge2.p2.x),
                  min(edge2.p1.y,edge2.p2.y),max(edge2.p1.y,edge2.p2.y))
                addCutter(1,t2,e2,max(edge2.p1.x,edge2.p2.x),0,0)
              end
            end
          end
        end
      end
    end
  end

  fixOpenEdges(tris,trit,ftris,addCutters)
end

function fixOpenEdges(tris,trit,ftris,addCutters)
  local tofix = {}
  for t=1,#tris,1 do 
    for e=1,3,1 do 
      if trit[t][e]==-1 then 
        local a,b = e==1 and 1 or (e==2 and 2 or 3),e==1 and 2 or (e==2 and 3 or 1)
        table.insert(tofix,{ftris[t][a][1],ftris[t][a][2],ftris[t][b][1],ftris[t][b][2], t,e})
      end
    end
  end

  for f1,fix1 in ipairs(tofix) do 
    for f2,fix2 in ipairs(tofix) do 
      if f1~=f2 then 
        if segsNear(fix1,fix2) then 
          trit[fix1[5]][fix1[6]] = fix2[5]
          trit[fix2[5]][fix2[6]] = fix1[5]
          if addCutters then 
            addCutter(0,fix1[5],fix1[6],min(fix1[1],fix1[3]), 
              min(fix1[2],fix1[4]),max(fix1[2],fix1[4]) )
            addCutter(1,fix2[5],fix2[6],max(fix2[1],fix2[3]),0,0)
          end
        end
      end
    end
  end
end

function fillVector( panel,segmentBuf, bbox)  
  segments = segmentBuf
  intersect = _G.intersect
  _time("", false)
  collectgarbage("stop")
  cutterN = 0
  local divs = animationPanel.fillDivs or 1
  local testpolys = {}

  local segmentsUsed = ffi.new(VECTOR_TYPE.."[?]",segments[0][0]+1)
  local points = {dpoint(segments[1][1], segments[1][2])}
  for s = 1, segments[0][0], 1 do
    table.insert(points,dpoint(segments[s][3], segments[s][4]))
  end
  table.sort(points,pointSort)
  local co = 0
  local x,y
  for p = #points,1,-1 do
    if x==points[p].x and y==points[p].y then 
      table.remove(points,p)
      co = co+1
    else 
      x,y = points[p].x,points[p].y
    end
  end
  print("co",co)

  _time("prep")

  if not animationPanel.forceRefill and panel.pointsPrev and #points==#panel.pointsPrev then 
    local same = true
    for p = 1, #points,1 do
      if not(points[p]==panel.pointsPrev[p]) then
        same = false
        break
      end
    end
    if same then 
      print("DONT FILL, NO CHANGE")
      return panel.lastFill
    end
  end

  panel.fillsUsed = {}
  panel.cachedStrokes = {}
  panel.cachedSFills = {}

  panel.pointsPrev = lume.clone(points)

  bbox.w = (bbox.r - bbox.l)
  bbox.h = (bbox.b - bbox.t)
  
  bbox.tw = bbox.w / divs
  bbox.th = bbox.h / divs
  
  local start, tris, grid, trit
  local es = {"e1", "e2", "e3"}

  tris = delaunay.triangulate(points)
  print("triangles",#tris)

  _time("triangulate ")

  local flats = 0
  for t=#tris,1,-1 do
    local tri = tris[t]
    if tri:isFlat() or tri:getArea()==0 then 
      flats=flats+1
      table.remove(tris,t)
    end
  end

  -- for t=1,#tris,1 do 
  --   local tri = tris[t]
  --   table.insert(testpolys,{color=color,{tri.p1.x,tri.p1.y}, {tri.p2.x,tri.p2.y}, {tri.p3.x,tri.p3.y} ,
  --     {tri.p1.x,tri.p1.y}, {(tri.p1.x+tri.p2.x+tri.p3.x)/3,(tri.p1.y+tri.p2.y+tri.p3.y)/3}
  --   }) 
  -- end

  -- move tris to single float array 
  -- also add all segs and triedges to sort and check table
  local trit = ffi.new(string.format("int16_t[%i][4]",#tris+1),{{-1}})
  local ftris=ffi.new(string.format(VECTOR_TYPE.."[%i][4][7]",#tris+1))

  matchCurves(tris,ftris,trit,segments,segmentsUsed,1)

  _time("match curves") 

  -- cut out triangles with unmatched segs
  local unused = 0 
  for s=1,segments[0][0],1 do 
    local seg = segments[s]
    -- local ox,oy = math.random()*0.2,math.random()*0.2
    -- table.insert(testpolys,{color={r=math.random(),g=math.random(),b=math.random()},{seg[1]+ox,seg[2]+oy}, {seg[3]+ox,seg[4]+oy}, {seg[1]+ox,seg[2]+oy} }) 
    if segmentsUsed[s]==0 then 
      unused = unused +1
      addCutter(0,s,0,min(segments[s][1],segments[s][3]),
        min(segments[s][2],segments[s][4]),max(segments[s][2],segments[s][4]))
      addCutter(1,s,0,max(segments[s][1],segments[s][3]),0,0)
    end
  end

  clearTail(cutters,cutterN+1)

  table.sort(cutters,sweepSort)
  _time("sort cutters")

  local active = {}
  local maxActive = 0
  local total = 0
  local inters = 0
  local cutTris = {}
  for c=1,#cutters,1 do 
    -- maxActive = max (maxActive,#active)
    local check = cutters[c] 
    if check[1]==0 then 
      for a=1,#active,1 do 
        if active[a][5]<=check[6] and active[a][6]>=check[5] then
          local s = (active[a][3]==0 and active[a][2] or (check[3]==0 and check[2] or false ))
          local seg  = s and segments[s] or false
          local t = (active[a][3]>0 and active[a][2] or (check[3]>0 and check[2] or false ))
          local tri = t and tris[t] or false
          if seg and tri then 
            local e = check[3]>0 and check[3] or active[a][3]
            local edge = e == 1 and tri.e1 or (e == 2 and tri.e2 or e == 3 and tri.e3)
            local x,y = intersect2(seg[1],seg[2],seg[3],seg[4],edge.p1.x,edge.p1.y,edge.p2.x,edge.p2.y)
             -- table.insert(testpolys,{{seg[1],seg[2]}, {seg[3],seg[4]}, {seg[1],seg[2]} })
            -- table.insert(testpolys,{{edge.p1.x,edge.p1.y}, {edge.p2.x,edge.p2.y}, {edge.p1.x,edge.p1.y} })
            if x then 
                -- table.insert(testpolys,{{tri.p1.x,tri.p1.y}, {tri.p2.x,tri.p2.y}, {tri.p3.x,tri.p3.y} }) 
              inters = inters + 1
              local added = false 
              for i=1,#cutTris,1 do 
                if cutTris[i][1]==t then 
                  added = i 
                  break
                end
              end
              if not added then 
                table.insert(cutTris,{t,0,0,0})
                added = #cutTris
              end
              table.insert(cutTris[added],s)
              cutTris[added][e+1]=1
            end
          end
        end
      end
      table.insert(active,check)
    else 
      for a=1,#active,1 do 
        if active[a][2]==check[2] and active[a][3]==check[3] then 
          table.remove(active,a)
          break
        end
      end
    end
  end

  table.sort(cutTris,clusterSort)
  print("cuts",#cutTris)

  -- cluster triangles
  local clusters ={}
  local removals = {}
  local retris = {}
  while #cutTris>0 do
    local cluster = {tris={cutTris[1]},segs={}}
    for i=5,#cutTris[1],1 do 
      cluster.segs[cutTris[1][i]]=true
    end
    local tri = tris[cutTris[1][1]]
    
    table.remove(cutTris,1)
    local grow = true
    local start = 1
    while grow do 
      grow = false
      -- print("start growth",#cutTris)
      for c=start,#cluster.tris,1 do 
        local cut = cluster.tris[c]
        local t = cut[1]
        
        -- print(" tri check",t)
        for e=1,3,1 do 
          if cut[e+1]==1 then -- if an edge of a triangle has been cut then we grow 
            -- print("   edge check",e,cut[e+1])
            local low,high,mid,index = 1,#cutTris
            local tindex = trit[t][e]
            if tindex>0 then 
              if not (#cluster.tris>1 and lume.match(cluster.tris,function(v) return v[1] == tindex end)) then 
                local cutTri,index = lume.match(cutTris,function(v) return v[1]==tindex end)
                if index then 
                  table.insert(cluster.tris,cutTris[index])
                  for i=5,#cutTris[index],1 do 
                    cluster.segs[cutTris[index][i]]=true
                  end
                  table.remove(cutTris,index)
                  start=start+1
                  grow = true
                end
              end
            end
          end
        end
      end
    end
    table.insert(clusters,cluster)
  end


  -- cluster clusters to fix weird disjoint clustering
  local added =0 
  for c=1,#clusters,1 do 
    local edges = {}
    local clust = clusters[c]
    local color = {r=1,b=0,g=0}--{r=math.random()*0.6+0.1,g=math.random()*0.6+0.1,b=0.5}
    local ox,oy = math.random()*0.2,math.random()*0.2

    for k=#clusters,c+1,-1 do 
      if k~=c then 
        local common = false
        local klust = clusters[k]
        for seg,_ in pairs(clust.segs) do 
          if klust.segs[seg] then 
            common=true
            break
          end
        end
        if common then 
          concat(clust.tris,klust.tris)
          for seg,_ in pairs(klust.segs) do 
            clust.segs[seg] = true
          end
          table.remove(clusters,k)
        end
      end
    end
    -- for s,_ in pairs(clust.segs) do 
    --   local seg = segments[s]
    --   table.insert(testpolys,{color={r=math.random(),g=math.random(),b=math.random()},{seg[1]+ox,seg[2]+oy}, {seg[3]+ox,seg[4]+oy}, {seg[1]+ox,seg[2]+oy} }) 
    -- end
    local clegs = {}
    for s,there in pairs(clust.segs) do 
      if there then 
        local seg = segments[s]
        table.insert(clegs,segments[s])
        -- table.insert(testpolys,{color=color,{seg[1],seg[2]}, {seg[3],seg[4]}, {seg[1],seg[2]} })
      end
    end
    clust.segs = clegs
    for t=1,#clust.tris,1 do 
      local clutri = clust.tris[t]
      local tri = tris[clutri[1]]
      table.insert(removals,clutri[1])
      for e=1,3,1 do 
        if clutri[e+1]==0 then 
          local edge = e == 1 and tri.e1 or (e == 2 and tri.e2 or e == 3 and tri.e3)
          table.insert(edges,{edge.p1.x,edge.p1.y,edge.p2.x,edge.p2.y,1})
          -- table.insert(testpolys,{color = color,{edge.p1.x+ox,edge.p1.y+oy}, {edge.p2.x+ox,edge.p2.y+oy}, {edge.p1.x+ox,edge.p1.y+oy} })   
        end
      end
      -- table.insert(testpolys,{color=color,{tri.p1.x+ox,tri.p1.y+oy}, {tri.p2.x+ox,tri.p2.y+oy}, {tri.p3.x+ox,tri.p3.y+oy} }) 
    end

    local a,b = vec2(),vec2()
    local limit = 1000
    local i = 1 
    while #edges>0 do 
      i = i +1
      if i>limit then editor.tempTip("Failed to create fill structure :(") return panel.lastFill end
      -- print("outlining")
      local edge = edges[1]
      local shape = {edge[1],edge[2],edge[3],edge[4]}
      table.remove(edges,1)
      local out = {paths={}}
      local loopedges = {}
      concat(loopedges,edges)
      concat(loopedges,clust.segs)
      findLoop(out,shape,loopedges,{})
      if out.used then 
        out.shape.color = color
        -- table.insert(testpolys,out.shape)
        for e=#edges,1,-1 do 
          if out.used[e] then 
            table.remove(edges,e)
          end
        end
        local succ,tries = pcall(mth.triangulate,out.shape)
        if succ then 
          for t=1,#tries,1 do 
            local tri = tries[t]
            table.insert(tris,dtri(dpoint(tri[1],tri[2]),dpoint(tri[3],tri[4]),dpoint(tri[5],tri[6])))
            added = added +1
            -- tri=tris[#tris]
            -- table.insert(testpolys,{color = color,{tri.p1.x,tri.p1.y}, {tri.p2.x,tri.p2.y}, {tri.p3.x,tri.p3.y} }) 
            -- table.insert(testpolys,tri)
          end
        else 
          print("FUCKKCKCKCK")
        end
      else 
        print("FRRIICKKC")
        -- table.insert(testpolys,shape)
        -- concat(testpolys,edges)
        -- for p,path in ipairs(out.paths) do 
          -- table.insert(testpolys,path)
        -- end
      end
      -- if #shape== 3 then 
      --   table.insert(retris,dtri(dpoint(shape[1],shape[2]),dpoint(shape[3],shape[4]),dpoint(shape[5],shape[6])))
      --   table.insert(testpolys,shape)
      -- end
    end

    if c == #clusters then 
      break 
    end
  end

  _time("clusters")
  table.sort(removals)
  for r=#removals,1,-1  do 
    local rem = removals[r]
    table.remove(tris,rem) 
  end

  trit = ffi.new(string.format("int16_t[%i][4]",#tris+1),{{-1}})
  ftris = ffi.new(string.format(VECTOR_TYPE.."[%i][4][7]",#tris+1))
  matchCurves(tris,ftris,trit,segments,segmentsUsed,#tris-added+1)

  _time("rematch curves") 
  -- local color = {r=0.8,g=0.3,b=0.3}
  -- for t=1,#tris,1 do 
  --   local tri = tris[t]
  --   local cx,cy = (tri.p1.x+tri.p2.x+tri.p3.x)/3,(tri.p1.y+tri.p2.y+tri.p3.y)/3
  --   table.insert(testpolys,{color=color,
  --     {(tri.p1.x*9+cx)/10,(tri.p1.y*9+cy)/10}, 
  --     {(tri.p2.x*9+cx)/10,(tri.p2.y*9+cy)/10}, 
  --     {(tri.p3.x*9+cx)/10,(tri.p3.y*9+cy)/10},
  --     {(tri.p1.x*9+cx)/10,(tri.p1.y*9+cy)/10}
  --   })
  -- end
  -- local color = {r=0.3,g=0.6,b=1}
  -- for t=1,#tris,1 do 
  --   local ftri = ftris[t]
  --   local r = 9
  --   local cx,cy = (ftri[1][1]+ftri[2][1]+ftri[3][1])/3,(ftri[1][2]+ftri[2][2]+ftri[3][2])/3
  --   table.insert(testpolys,{color=color,
  --     {(ftri[1][1]*6+cx)/7,(ftri[1][2]*6+cy)/7}, 
  --     {(ftri[2][1]*6+cx)/7,(ftri[2][2]*6+cy)/7}, 
  --     {(ftri[3][1]*6+cx)/7,(ftri[3][2]*6+cy)/7},
  --     {(ftri[1][1]*6+cx)/7,(ftri[1][2]*6+cy)/7}
  --   }) 

  -- end

  -- group triangles into fill shapes
  local filled = ffi.new("uint16_t[?]",ftris[0][0][0]+1)
  filled[0]=ftris[0][0][0]
  local shapes = {}
  local visited = {}
  local maxCheckedTris = 0
  local shape = {}
  local tried = {}
  while canFill(shape,filled) do  
    local color = {r=math.random(),g=math.random(),b=math.random()}
    local added = {}
    local segs = {}
    local valid = true
    local grow = true
    local testpoly  = {}
    local r = 1+mf(math.random()*9)
    while grow do 
      grow = false
      local checkedTris = 0
      for s=1,shape[0],1 do 
        if not added[shape[s]] then 
          checkedTris = checkedTris +1
          local tri = tris[shape[s]]
          local ftri = ftris[shape[s]]

          local f1,f2,f3 = triTable2(tri.p1,ftri[1]),triTable2(tri.p2,ftri[2]),triTable2(tri.p3,ftri[3])
          -- table.insert(testpolys,{color = color,f1,f2,f3,f1
          --   ,{(f1[1]+f2[1]+f3[1]*r)/(3+(r-1)),(f1[2]+f2[2]+f3[2]*r)/(3+(r-1))}
          -- })

          filled[shape[s]]=1
          for e=1,3,1 do 
            local connected = trit[shape[s]][e]
              -- tried[shape[s]] = true
            if connected == 0 then --and not tried[shape[s]] then 
              -- if tri[e][0]==-2 then 
                local seg = e==1 and {f1,f2} or (e==2 and {f2,f3} or {f3,f1})
                table.insert(segs,seg) 
                table.insert(testpoly,seg)
              -- end
            end
            if connected<=ftris[0][0][0] then 
              if not visited[connected] then 
                visited[connected]=true
                if connected == -1 then
                  valid = false
                  segs={}
                  goto kill
                end
                if connected>0  then 
                  if not added[connected] then
                    -- local perimeter = 
                    --   dist(tri[1][1],tri[1][2],tri[2][1],tri[2][2])+
                    --   dist(tri[1][1],tri[1][2],tri[3][1],tri[3][2])+
                    --   dist(tri[2][1],tri[2][2],tri[3][1],tri[3][2])
                    --   print(perimeter,drawingPanel.fillGap)
                    -- if perimeter>drawingPanel.fillGap then 
                      shape[0] = shape[0]+1
                      shape[shape[0]] = connected
                      grow=true
                      
                    --   print("grow")
                    -- else
                    --   print("GAPPPPP")
                    -- end
                  end
                else 
                  
                end
              end
            end

            added[shape[s]] = true 

          end
        end
      end
      maxCheckedTris  = max(maxCheckedTris,checkedTris)
    end
    ::kill::

    if valid and #segs>=3 then 
      
      -- if duplicate, remove both

      for s1=#segs,1,-1 do 
        if segs[s1] then 
          local a1,b1 = segs[s1][1],segs[s1][2]
          for s2=#segs,1,-1 do 
            local a2,b2 = segs[s2][1],segs[s2][2]
            if s1~=s2 and (
              (a1[1] == a2[1] and b1[1] == b2[1] and a1[2] == a2[2] and b1[2] == b2[2]) or 
              (a1[1] == b2[1] and b1[1] == a2[1] and a1[2] == b2[2] and b1[2] == a2[2])) then 
              table.remove(segs,max(s1,s2))
              table.remove(segs,min(s1,s2))
              break
            end
          end
        end
      end
      
      -- for s=1,#segs,1 do 
      --   table.insert(testpolys,segs[s])
      -- end

      -- join into outline
      local failed = false
      local segz = #segs
      local outlines = {}
      local outN = 0
      while #segs>0 do 
        outN = outN+1

        local outline = {segs[1][1]}
        -- print(#outline,segs[1][1][1],segs[1][1][2])
        local used = {}
        local flipped= false
        while true do 

          ::restart::

          local added,ss, sa, sb, side = 0

          for s=1,#segs,1 do 
            local x,y,px,py
            if flipped then 
              x,y = outline[1][1],outline[1][2]
              px,py = #outline>1 and outline[2][1],
                      #outline>1 and outline[2][2] 
            else
              x,y = outline[#outline][1],outline[#outline][2]
              px,py = #outline>1 and outline[#outline-1][1],
                      #outline>1 and outline[#outline-1][2] 
            end
            local a,b = segs[s][1],segs[s][2]
            local ax,ay,bx,by = a[1],a[2], b[1],b[2]
            if     (x==ax and y==ay) then 
              if (not px) or (not (px==bx and py==by)) then 
                ss,sa,sb,side = s,a,b,1
                added = added +1 
                if added>1 or #outline==1 then break end
              end

            elseif (x==bx and y==by) then 
              if (not px) or (not (px==ax and py==ay)) then 
                ss,sa,sb,side = s,a,b,0
                added = added +1 
                if added>1 or #outline==1 then break end
              end
            end
          end

          if added == 1 then 
            if side==0 then 
              if flipped then 
                outline[1][5],outline[1][6]=sb[3],sb[4]
                table.insert(outline,1,{sa[1],sa[2],sa[5],sa[6],sa[3],sa[4]})
              else
                outline[#outline][5],outline[#outline][6]=sb[3],sb[4]
                table.insert(outline,{sa[1],sa[2],sa[5],sa[6],sa[3],sa[4]})
              end
            else
              if flipped then 
                outline[1][5],outline[1][6]=sa[5],sa[6]
                table.insert(outline,1,sb)
              else
                outline[#outline][5],outline[#outline][6]=sa[5],sa[6]
                table.insert(outline,sb)
              end
            end
            table.remove(segs,ss)
          else 
            if not flipped then 
              flipped = true
              added = 0
              goto restart
            end
          end

          if added~=1 then 
            -- print("FAILED OUTLINE",shape[0])
            -- print(#segs,#outline,outline[1][1],outline[1][2],outline[#outline][1],outline[#outline][2])
            -- table.insert(testpolys,outline)
            failed= true
            outline = false 
            break 
          end

          if outline[#outline][1]==outline[1][1] and outline[#outline][2]==outline[1][2] then 
            -- print("COMPLETED OUTLINE")
            -- table.insert(testpolys,outline)

            -- for s=#segs,1,-1 do 
            --   if used[s] then 
            --     table.remove(segs,s)
            --   end
            -- end
            break
          end
        end

        if outline and #outline>2 then 
          table.insert(outlines,outline)
          -- local succ,splits = pcall(splitPolyLine,outline)
          -- if succ then 
          --   print("successful outline")
          --   concat(outlines,splits)
          -- else
          --   print("failed",#outline,inspect(outline))
          -- end
        end
      end

      if shape[0]==1 then 
         for i=1,#testpoly,1 do 
          -- testpoly[i].color = color
          -- table.insert(testpolys,testpoly[i])
        end
        -- table.insert(testpolys,outlines[1])
      end

      if #outlines>0 then 
       
        -- calc bounding box of outlines, set largest first
        local largest = 0
        local outer = 1 
        local BBOX 
        for o=#outlines,1,-1 do 
          local outline = outlines[o]
          
          local bbox = {outline[1][1],outline[1][2],outline[1][1],outline[1][2]}
          for l=1,#outline,1 do 
            bbox[1]=min(bbox[1],outline[l][1])
            bbox[2]=min(bbox[2],outline[l][2])
            bbox[3]=max(bbox[3],outline[l][1])
            bbox[4]=max(bbox[4],outline[l][2])
          end
          local size = abs(bbox[4]-bbox[2])*abs(bbox[3]-bbox[1])
          if size>largest then 
            BBOX = bbox
            largest = size 
            outer = o
          end
        end
        outlines[outer],outlines[1]=outlines[1],outlines[outer]



        table.insert(shapes,{bbox=BBOX,line=outlines})
        -- if largest>20000 then 
          -- for o,outline in ipairs(outlines) do 
          --   table.insert(testpolys,outlines[1])
          -- end
        -- end
      end
    else
      -- tempTip("Fill Failed: \n unclosed region")
    end
  end
  print("maxcheckedTris",maxCheckedTris)
  print("shapes: ",#shapes)
  _time("fill shapes")
  

  return {
    tris=tris,
    shapes=shapes,
    count=#points,
    testpolys=testpolys
  }
end

