diff options
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/Embedding.lua')
-rw-r--r-- | Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/Embedding.lua | 1445 |
1 files changed, 723 insertions, 722 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/Embedding.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/Embedding.lua index 50fc3672207..8d9d3b53b14 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/Embedding.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/Embedding.lua @@ -6,782 +6,783 @@ require("pgf.gd.planar").Embedding = E local LinkedList = require("pgf.gd.planar.LinkedList") E.vertexmetatable = { - __tostring = function(v) - if v.name then - return v.name - elseif v.inputvertex then - return v.inputvertex.name - else - return tostring(v) - end - end + __tostring = function(v) + if v.name then + return v.name + elseif v.inputvertex then + return v.inputvertex.name + else + return tostring(v) + end + end } E.halfedgemetatable = { - __tostring = function(e) - return tostring(e.twin.target) - .. " -> " - .. tostring(e.target) - end + __tostring = function(e) + return tostring(e.twin.target) + .. " -> " + .. tostring(e.target) + end } -- create class properties E.__index = E function E.new() - local t = { - vertices = {}, - } - setmetatable(t, E) - return t + local t = { + vertices = {}, + } + setmetatable(t, E) + return t end function E:add_vertex(name, inputvertex, virtual) - virtual = virtual or nil - local vertex = { - adjmat = {}, - name = name, - inputvertex = inputvertex, - virtual = virtual, - } - setmetatable(vertex, E.vertexmetatable) - table.insert(self.vertices, vertex) - return vertex + virtual = virtual or nil + local vertex = { + adjmat = {}, + name = name, + inputvertex = inputvertex, + virtual = virtual, + } + setmetatable(vertex, E.vertexmetatable) + table.insert(self.vertices, vertex) + return vertex end function E:add_edge(v1, v2, after1, after2, virtual) - assert(v1.link == nil or v1 == after1.twin.target) - assert(v2.link == nil or v2 == after2.twin.target) - assert(v1.adjmat[v2] == nil) - assert(v2.adjmat[v1] == nil) - - virtual = virtual or nil - - local halfedge1 = { - target = v2, - virtual = virtual, - links = {}, - } - local halfedge2 = { - target = v1, - virtual = virtual, - links = {}, - } - halfedge1.twin = halfedge2 - halfedge2.twin = halfedge1 - - setmetatable(halfedge1, E.halfedgemetatable) - setmetatable(halfedge2, E.halfedgemetatable) - - if v1.link == nil then - v1.link = halfedge1 - halfedge1.links[0] = halfedge1 - halfedge1.links[1] = halfedge1 - else - halfedge1.links[0] = after1.links[0] - after1.links[0].links[1] = halfedge1 - halfedge1.links[1] = after1 - after1.links[0] = halfedge1 - end - - if v2.link == nil then - v2.link = halfedge2 - halfedge2.links[0] = halfedge2 - halfedge2.links[1] = halfedge2 - else - halfedge2.links[0] = after2.links[0] - after2.links[0].links[1] = halfedge2 - halfedge2.links[1] = after2 - after2.links[0] = halfedge2 - end - - v1.adjmat[v2] = halfedge1 - v2.adjmat[v1] = halfedge2 - - return halfedge1, halfedge2 + assert(v1.link == nil or v1 == after1.twin.target) + assert(v2.link == nil or v2 == after2.twin.target) + assert(v1.adjmat[v2] == nil) + assert(v2.adjmat[v1] == nil) + + virtual = virtual or nil + + local halfedge1 = { + target = v2, + virtual = virtual, + links = {}, + } + local halfedge2 = { + target = v1, + virtual = virtual, + links = {}, + } + halfedge1.twin = halfedge2 + halfedge2.twin = halfedge1 + + setmetatable(halfedge1, E.halfedgemetatable) + setmetatable(halfedge2, E.halfedgemetatable) + + if v1.link == nil then + v1.link = halfedge1 + halfedge1.links[0] = halfedge1 + halfedge1.links[1] = halfedge1 + else + halfedge1.links[0] = after1.links[0] + after1.links[0].links[1] = halfedge1 + halfedge1.links[1] = after1 + after1.links[0] = halfedge1 + end + + if v2.link == nil then + v2.link = halfedge2 + halfedge2.links[0] = halfedge2 + halfedge2.links[1] = halfedge2 + else + halfedge2.links[0] = after2.links[0] + after2.links[0].links[1] = halfedge2 + halfedge2.links[1] = after2 + after2.links[0] = halfedge2 + end + + v1.adjmat[v2] = halfedge1 + v2.adjmat[v1] = halfedge2 + + return halfedge1, halfedge2 end function E:remove_virtual() - local virtuals = {} - for i, v in ipairs(self.vertices) do - if v.virtual then - table.insert(virtuals, i) - else - local start = v.link - local current = start - repeat - current = current.links[0] - if current.virtual then - current.links[0].links[1] = current.links[1] - current.links[1].links[0] = current.links[0] - v.adjmat[current.target] = nil - current.target.adjmat[v] = nil - end - until current == start - end - end - for i = #virtuals, 1, -1 do - self.vertices[virtuals[i]] = self.vertices[#self.vertices] - table.remove(self.vertices) - end + local virtuals = {} + for i, v in ipairs(self.vertices) do + if v.virtual then + table.insert(virtuals, i) + else + local start = v.link + local current = start + repeat + current = current.links[0] + if current.virtual then + current.links[0].links[1] = current.links[1] + current.links[1].links[0] = current.links[0] + v.adjmat[current.target] = nil + current.target.adjmat[v] = nil + end + until current == start + end + end + for i = #virtuals, 1, -1 do + self.vertices[virtuals[i]] = self.vertices[#self.vertices] + table.remove(self.vertices) + end end -- for the use in for-loops -- iterates over the adjacency list of a vertex -- given a half edge to start and a direction (0 or 1, default 0) function E.adjacency_iterator(halfedge, direction) - direction = direction or 0 - local function next_edge(startedge, prevedge) - if prevedge == nil then - return startedge - else - local nextedge = prevedge.links[direction] - if nextedge ~= startedge then - return nextedge - else - return nil - end - end - end - return next_edge, halfedge, nil + direction = direction or 0 + local function next_edge(startedge, prevedge) + if prevedge == nil then + return startedge + else + local nextedge = prevedge.links[direction] + if nextedge ~= startedge then + return nextedge + else + return nil + end + end + end + return next_edge, halfedge, nil end function E.face_iterator(halfedge, direction) - direction = direction or 0 - local function next_edge(startedge, prevedge) - if prevedge == nil then - return startedge - else - local nextedge = prevedge.twin.links[1 - direction] - if nextedge ~= startedge then - return nextedge - else - return nil - end - end - end - return next_edge, halfedge, nil + direction = direction or 0 + local function next_edge(startedge, prevedge) + if prevedge == nil then + return startedge + else + local nextedge = prevedge.twin.links[1 - direction] + if nextedge ~= startedge then + return nextedge + else + return nil + end + end + end + return next_edge, halfedge, nil end function E:triangulate() - local visited = {} - for _, vertex in ipairs(self.vertices) do - for start in E.adjacency_iterator(vertex.link) do - if not visited[start] then - local prev = start - local beforestart = start.links[0].twin - local current = start.twin.links[1] - local next = current.twin.links[1] - visited[start] = true - visited[current] = true - visited[next] = true - while next ~= beforestart do - local halfedge1, halfedge2 - if vertex ~= current.target - and not vertex.adjmat[current.target] then - halfedge1, halfedge2 = self:add_edge( - vertex, current.target, - prev, next, - true - ) - - prev = halfedge1 - current = next - next = next.twin.links[1] - elseif not prev.target.adjmat[next.target] then - halfedge1, halfedge2 = self:add_edge( - prev.target, next.target, - current, next.twin.links[1], - true - ) - - current = halfedge1 - next = halfedge2.links[1] - else - local helper = next.twin.links[1] - halfedge1, halfedge2 = self:add_edge( - current.target, helper.target, - next, helper.twin.links[1], - true - ) - - next = halfedge1 - end - - visited[next] = true - visited[halfedge1] = true - visited[halfedge2] = true - end - end - end - end + local visited = {} + for _, vertex in ipairs(self.vertices) do + for start in E.adjacency_iterator(vertex.link) do + if not visited[start] then + local prev = start + local beforestart = start.links[0].twin + local current = start.twin.links[1] + local next = current.twin.links[1] + visited[start] = true + visited[current] = true + visited[next] = true + while next ~= beforestart do + local halfedge1, halfedge2 + if vertex ~= current.target + and not vertex.adjmat[current.target] then + halfedge1, halfedge2 = self:add_edge( + vertex, current.target, + prev, next, + true + ) + + prev = halfedge1 + current = next + next = next.twin.links[1] + elseif not prev.target.adjmat[next.target] then + halfedge1, halfedge2 = self:add_edge( + prev.target, next.target, + current, next.twin.links[1], + true + ) + + current = halfedge1 + next = halfedge2.links[1] + else + local helper = next.twin.links[1] + halfedge1, halfedge2 = self:add_edge( + current.target, helper.target, + next, helper.twin.links[1], + true + ) + + next = halfedge1 + end + + visited[next] = true + visited[halfedge1] = true + visited[halfedge2] = true + end + end + end + end end function E:canonical_order(v1, v2, vn) - local n = #self.vertices - local order = { v1 } - local marks = { [v1] = "ordered", [v2] = 0 } - local visited = {} - local vk = v1 - local candidates = LinkedList.new() - local listelements = {} - for k = 1, n-2 do - for halfedge in E.adjacency_iterator(vk.link) do - local vertex = halfedge.target - if vertex ~= vn then - local twin = halfedge.twin - visited[twin] = true - if marks[vertex] == nil then - marks[vertex] = "visited" - elseif marks[vertex] ~= "ordered" then - local neighbor1 = visited[twin.links[0]] - local neighbor2 = visited[twin.links[1]] - if marks[vertex] == "visited" then - if neighbor1 or neighbor2 then - marks[vertex] = 1 - listelements[vertex] = candidates:addback(vertex) - else - marks[vertex] = 2 - end - else - if neighbor1 == neighbor2 then - if neighbor1 and neighbor2 then - marks[vertex] = marks[vertex] - 1 - else - marks[vertex] = marks[vertex] + 1 - end - if marks[vertex] == 1 then - listelements[vertex] - = candidates:addback(vertex) - elseif listelements[vertex] then - candidates:remove(listelements[vertex]) - listelements[vertex] = nil - end - end - end - end - end - end - vk = candidates:popfirst() - order[k+1] = vk - marks[vk] = "ordered" - end - order[n] = vn - return order + local n = #self.vertices + local order = { v1 } + local marks = { [v1] = "ordered", [v2] = 0 } + local visited = {} + local vk = v1 + local candidates = LinkedList.new() + local listelements = {} + for k = 1, n-2 do + for halfedge in E.adjacency_iterator(vk.link) do + local vertex = halfedge.target + if vertex ~= vn then + local twin = halfedge.twin + visited[twin] = true + if marks[vertex] == nil then + marks[vertex] = "visited" + elseif marks[vertex] ~= "ordered" then + local neighbor1 = visited[twin.links[0]] + local neighbor2 = visited[twin.links[1]] + if marks[vertex] == "visited" then + if neighbor1 or neighbor2 then + marks[vertex] = 1 + listelements[vertex] = candidates:addback(vertex) + else + marks[vertex] = 2 + end + else + if neighbor1 == neighbor2 then + if neighbor1 and neighbor2 then + marks[vertex] = marks[vertex] - 1 + else + marks[vertex] = marks[vertex] + 1 + end + if marks[vertex] == 1 then + listelements[vertex] + = candidates:addback(vertex) + elseif listelements[vertex] then + candidates:remove(listelements[vertex]) + listelements[vertex] = nil + end + end + end + end + end + end + vk = candidates:popfirst() + order[k+1] = vk + marks[vk] = "ordered" + end + order[n] = vn + return order end function E:get_biggest_face() - local number = 0 - local edge - local visited = {} - for _, vertex in ipairs(self.vertices) do - for start in E.adjacency_iterator(vertex.link) do - local count = 0 - if not visited[start] then - visited[start] = true - local current = start - repeat - count = count + 1 - current = current.twin.links[1] - until current == start - if count > number then - number = count - edge = start - end - end - end - end - return edge, number + local number = 0 + local edge + local visited = {} + for _, vertex in ipairs(self.vertices) do + for start in E.adjacency_iterator(vertex.link) do + local count = 0 + if not visited[start] then + visited[start] = true + local current = start + repeat + count = count + 1 + current = current.twin.links[1] + until current == start + if count > number then + number = count + edge = start + end + end + end + end + return edge, number end function E:surround_by_triangle(faceedge, facesize) - local divisor = 3 - if facesize > 3 then - divisor = 4 - end - local basenodes = math.floor(facesize / divisor) - local extranodes = facesize % divisor - local attachnodes = { basenodes, basenodes, basenodes } - if facesize > 3 then - attachnodes[2] = basenodes * 2 - end - for i = 1,extranodes do - attachnodes[i] = attachnodes[i] + 1 - end - - local v = { - self:add_vertex("$v_1$", nil, true), - self:add_vertex("$v_n$", nil, true), - self:add_vertex("$v_2$", nil, true) - } - for i = 1,3 do - local currentv = v[i] - local nextv = v[i % 3 + 1] - self:add_edge(currentv, nextv, currentv.link, nextv.link, true) - end - - local current = faceedge - local next = current.twin.links[1] - for i = 1,3 do - local vertex = v[i] - local otheredge = vertex.adjmat[v[i % 3 + 1]] - local previnserted = otheredge.links[1] - for count = 1, attachnodes[i] do - if not vertex.adjmat[current.target] then - previnserted, _ = self:add_edge(vertex, current.target, - previnserted, next, - true - ) - end - - current = next - next = next.twin.links[1] - end - if not vertex.adjmat[current.target] then - previnserted, _ = self:add_edge( - vertex, current.target, - previnserted, next, - true - ) - current = previnserted - end - end - return v[1], v[3], v[2] + local divisor = 3 + if facesize > 3 then + divisor = 4 + end + local basenodes = math.floor(facesize / divisor) + local extranodes = facesize % divisor + local attachnodes = { basenodes, basenodes, basenodes } + if facesize > 3 then + attachnodes[2] = basenodes * 2 + end + for i = 1,extranodes do + attachnodes[i] = attachnodes[i] + 1 + end + + local v = { + self:add_vertex("$v_1$", nil, true), + self:add_vertex("$v_n$", nil, true), + self:add_vertex("$v_2$", nil, true) + } + for i = 1,3 do + local currentv = v[i] + local nextv = v[i % 3 + 1] + self:add_edge(currentv, nextv, currentv.link, nextv.link, true) + end + + local current = faceedge + local next = current.twin.links[1] + for i = 1,3 do + local vertex = v[i] + local otheredge = vertex.adjmat[v[i % 3 + 1]] + local previnserted = otheredge.links[1] + for count = 1, attachnodes[i] do + if not vertex.adjmat[current.target] then + previnserted, _ = self:add_edge( + vertex, current.target, + previnserted, next, + true + ) + end + + current = next + next = next.twin.links[1] + end + if not vertex.adjmat[current.target] then + previnserted, _ = self:add_edge( + vertex, current.target, + previnserted, next, + true + ) + current = previnserted + end + end + return v[1], v[3], v[2] end function E:improve() - local pairdata = {} - local inpair = {} - for i, v1 in ipairs(self.vertices) do - for j = i + 1, #self.vertices do - local v2 = self.vertices[j] - local pd = self:find_pair_components(v1, v2) - if pd then - inpair[v1] = true - inpair[v2] = true - table.insert(pairdata, pd) - end - end - if not inpair[v1] then - local pd = self:find_pair_components(v1, nil) - if pd then - inpair[v1] = true - table.insert(pairdata, pd) - end - end - end - - local changed - local runs = 1 - local edgepositions = {} - repeat - changed = false - for i, pd in ipairs(pairdata) do - self:improve_separation_pair(pd) - end - -- check for changes - for i, v in ipairs(self.vertices) do - local start = v.link - local current = start - local counter = 1 - repeat - if counter ~= edgepositions[current] then - changed = true - edgepositions[current] = counter - end - counter = counter + 1 - current = current.links[0] - until current == start - end - runs = runs + 1 - until changed == false or runs > 100 + local pairdata = {} + local inpair = {} + for i, v1 in ipairs(self.vertices) do + for j = i + 1, #self.vertices do + local v2 = self.vertices[j] + local pd = self:find_pair_components(v1, v2) + if pd then + inpair[v1] = true + inpair[v2] = true + table.insert(pairdata, pd) + end + end + if not inpair[v1] then + local pd = self:find_pair_components(v1, nil) + if pd then + inpair[v1] = true + table.insert(pairdata, pd) + end + end + end + + local changed + local runs = 1 + local edgepositions = {} + repeat + changed = false + for i, pd in ipairs(pairdata) do + self:improve_separation_pair(pd) + end + -- check for changes + for i, v in ipairs(self.vertices) do + local start = v.link + local current = start + local counter = 1 + repeat + if counter ~= edgepositions[current] then + changed = true + edgepositions[current] = counter + end + counter = counter + 1 + current = current.links[0] + until current == start + end + runs = runs + 1 + until changed == false or runs > 100 end function E:find_pair_components(v1, v2) - local visited = {} - local companchors = {} - local edgecomps = {} - local compvertices = {} - local islinear = {} - local edgeindices = {} - - local pair = { v1, v2 } - local start = v1.link - local current = start - local edgeindex = 1 - -- start searches from v1 - repeat - edgeindices[current] = edgeindex - edgeindex = edgeindex + 1 - if not edgecomps[current] then - local compindex = #companchors + 1 - local ca, il - edgecomps[current] = compindex - compvertices[compindex] = {} - local target = current.target - if target == v2 then - edgecomps[current.twin] = compindex - ca = 3 - il = true - else - ca, il = self:component_dfs( - target, - pair, - visited, - edgecomps, - compvertices[compindex], - compindex - ) - end - companchors[compindex] = ca - islinear[compindex] = il - end - current = current.links[0] - until current == start - - if v2 then - start = v2.link - current = start - local lastincomp = true - local edgeindex = 1 - -- now find the remaining blocks at v2 - repeat - edgeindices[current] = edgeindex - edgeindex = edgeindex + 1 - if not edgecomps[current] then - local compindex = #companchors + 1 - edgecomps[current] = compindex - compvertices[compindex] = {} - self:component_dfs( - current.target, - pair, - visited, - edgecomps, - compvertices[compindex], - compindex - ) - companchors[compindex] = 2 - end - current = current.links[0] - until current == start - end - - -- init compedges, tricomps, twocomps - local tricomps = {} - local twocomps = {{}, {}} - for i, anchors in ipairs(companchors) do - if anchors == 3 then - table.insert(tricomps, i) - else - table.insert(twocomps[anchors], i) - end - end - - local flipimmune = #tricomps == 2 - and (islinear[tricomps[1]] or islinear[tricomps[2]]) - if (#tricomps < 2 or flipimmune) - and (v2 ~= nil or #twocomps[1] < 2) then - return nil - end - - -- order tri comps cyclic - local function sorter(a, b) - return #compvertices[a] < #compvertices[b] - end - - table.sort(tricomps, sorter) - - -- determine order of comps - local numtricomps = #tricomps - local comporder = { {}, {} } - local bottom = math.ceil(numtricomps / 2) - local top = bottom + 1 - for i, comp in ipairs(tricomps) do - if i % 2 == 1 then - comporder[1][bottom] = comp - comporder[2][numtricomps - bottom + 1] = comp - bottom = bottom - 1 - else - comporder[1][top] = comp - comporder[2][numtricomps - top + 1] = comp - top = top + 1 - end - end - - local pairdata = { - pair = pair, - companchors = companchors, - edgecomps = edgecomps, - edgeindices = edgeindices, - compvertices = compvertices, - tricomps = tricomps, - twocomps = twocomps, - comporder = comporder, - } - return pairdata + local visited = {} + local companchors = {} + local edgecomps = {} + local compvertices = {} + local islinear = {} + local edgeindices = {} + + local pair = { v1, v2 } + local start = v1.link + local current = start + local edgeindex = 1 + -- start searches from v1 + repeat + edgeindices[current] = edgeindex + edgeindex = edgeindex + 1 + if not edgecomps[current] then + local compindex = #companchors + 1 + local ca, il + edgecomps[current] = compindex + compvertices[compindex] = {} + local target = current.target + if target == v2 then + edgecomps[current.twin] = compindex + ca = 3 + il = true + else + ca, il = self:component_dfs( + target, + pair, + visited, + edgecomps, + compvertices[compindex], + compindex + ) + end + companchors[compindex] = ca + islinear[compindex] = il + end + current = current.links[0] + until current == start + + if v2 then + start = v2.link + current = start + local lastincomp = true + local edgeindex = 1 + -- now find the remaining blocks at v2 + repeat + edgeindices[current] = edgeindex + edgeindex = edgeindex + 1 + if not edgecomps[current] then + local compindex = #companchors + 1 + edgecomps[current] = compindex + compvertices[compindex] = {} + self:component_dfs( + current.target, + pair, + visited, + edgecomps, + compvertices[compindex], + compindex + ) + companchors[compindex] = 2 + end + current = current.links[0] + until current == start + end + + -- init compedges, tricomps, twocomps + local tricomps = {} + local twocomps = {{}, {}} + for i, anchors in ipairs(companchors) do + if anchors == 3 then + table.insert(tricomps, i) + else + table.insert(twocomps[anchors], i) + end + end + + local flipimmune = #tricomps == 2 + and (islinear[tricomps[1]] or islinear[tricomps[2]]) + if (#tricomps < 2 or flipimmune) + and (v2 ~= nil or #twocomps[1] < 2) then + return nil + end + + -- order tri comps cyclic + local function sorter(a, b) + return #compvertices[a] < #compvertices[b] + end + + table.sort(tricomps, sorter) + + -- determine order of comps + local numtricomps = #tricomps + local comporder = { {}, {} } + local bottom = math.ceil(numtricomps / 2) + local top = bottom + 1 + for i, comp in ipairs(tricomps) do + if i % 2 == 1 then + comporder[1][bottom] = comp + comporder[2][numtricomps - bottom + 1] = comp + bottom = bottom - 1 + else + comporder[1][top] = comp + comporder[2][numtricomps - top + 1] = comp + top = top + 1 + end + end + + local pairdata = { + pair = pair, + companchors = companchors, + edgecomps = edgecomps, + edgeindices = edgeindices, + compvertices = compvertices, + tricomps = tricomps, + twocomps = twocomps, + comporder = comporder, + } + return pairdata end function E:component_dfs(v, pair, visited, edgecomps, compvertices, compindex) - visited[v] = true - local start = v.link - local current = start - local companchors = 1 - local numedges = 0 - local islinear = true - table.insert(compvertices, v) - repeat - numedges = numedges + 1 - local target = current.target - if target == pair[1] or target == pair[2] then - edgecomps[current.twin] = compindex - if target == pair[2] then - companchors = 3 - end - elseif not visited[target] then - local ca, il = self:component_dfs( - target, - pair, - visited, - edgecomps, - compvertices, - compindex - ) - if ca == 3 then - companchors = 3 - end - islinear = islinear and il - end - current = current.links[0] - until current == start - return companchors, islinear and numedges == 2 + visited[v] = true + local start = v.link + local current = start + local companchors = 1 + local numedges = 0 + local islinear = true + table.insert(compvertices, v) + repeat + numedges = numedges + 1 + local target = current.target + if target == pair[1] or target == pair[2] then + edgecomps[current.twin] = compindex + if target == pair[2] then + companchors = 3 + end + elseif not visited[target] then + local ca, il = self:component_dfs( + target, + pair, + visited, + edgecomps, + compvertices, + compindex + ) + if ca == 3 then + companchors = 3 + end + islinear = islinear and il + end + current = current.links[0] + until current == start + return companchors, islinear and numedges == 2 end function E:improve_separation_pair(pairdata) - local pair = pairdata.pair - local companchors = pairdata.companchors - local edgecomps = pairdata.edgecomps - local edgeindices = pairdata.edgeindices - local compvertices = pairdata.compvertices - local tricomps = pairdata.tricomps - local twocomps = pairdata.twocomps - local comporder = pairdata.comporder - local v1 = pair[1] - local v2 = pair[2] - - local compedges = {} - for i = 1, #companchors do - compedges[i] = {{}, {}} - end - - local numtricomps = #tricomps - local numtwocomps = { #twocomps[1], #twocomps[2] } - - -- find compedges - for i = 1, #pair do - -- first find an edge that is the first of a triconnected component - local start2 - if v2 then - start = pair[i].link - current = start - local last - repeat - local comp = edgecomps[current] - if companchors[comp] == 3 then - if last == nil then - last = comp - elseif last ~= comp then - start2 = current - break - end - end - current = current.links[0] - until current == start - else - start2 = pair[i].link - end - -- now list the edges by components - current = start2 - repeat - table.insert(compedges[edgecomps[current]][i], current) - current = current.links[0] - until current == start2 - end - - -- count edges on each side of tri comps - local edgecount = {} - for _, comp in ipairs(tricomps) do - edgecount[comp] = {} - for i = 1, #pair do - local count = 1 - local current = compedges[comp][i][1] - local other = pair[3 - i] - while current.target ~= other do - count = count + 1 - current = current.twin.links[0] - end - edgecount[comp][i] = count - end - end - - -- determine which comps have to be flipped - local flips = {} - local numflips = 0 - local allflipped = true - for i, comp in ipairs(comporder[1]) do - local side1, side2 - if i > numtricomps / 2 then - side1 = edgecount[comp][1] - side2 = edgecount[comp][2] - else - side1 = edgecount[comp][2] - side2 = edgecount[comp][1] - end - if side1 > side2 then - numflips = numflips + 1 - flips[comp] = true - elseif side1 < side2 then - allflipped = false - end - end - - if allflipped then - for i, comp in ipairs(tricomps) do - flips[comp] = false - end - else - for i, comp in ipairs(tricomps) do - if flips[comp] then - for _, v in ipairs(compvertices[comp]) do - local start = v.link - local current = start - repeat - current.links[0], current.links[1] - = current.links[1], current.links[0] - current = current.links[1] - until current == start - end - end - end - end - - -- order edges cyclic per component (one cycle for all tri comps) - for i = 1, #pair do - if v2 then - local co - if allflipped then - co = comporder[3 - i] - else - co = comporder[i] - end - - local id = co[numtricomps] - lastedges = compedges[id][i] - if flips[id] then - lastedge = lastedges[1] - else - lastedge = lastedges[#lastedges] - end - - -- tri comps - for _, id in ipairs(co) do - local edges = compedges[id][i] - local from - local to - local step - if flips[id] then - from = #edges - to = 1 - step = -1 - else - from = 1 - to = #edges - step = 1 - end - for k = from, to, step do - local edge = edges[k] - lastedge.links[0] = edge - edge.links[1] = lastedge - lastedge = edge - end - end - end - - -- two comps - for _, id in ipairs(twocomps[i]) do - lastedges = compedges[id][i] - lastedge = lastedges[#lastedges] - for _, edge in ipairs(compedges[id][i]) do - lastedge.links[0] = edge - edge.links[1] = lastedge - lastedge = edge - end - end - end - - -- now merge the cycles - for i = 1, #pair do - local outeredges = {} - -- find the biggest face of the tri comps - if v2 then - local biggestedge - local biggestsize - local biggestindex - local start = compedges[tricomps[1]][i][1] - local current = start - repeat - local size = self:get_face_size(current) - if not biggestedge or size > biggestsize - or (size == biggestsize - and edgeindices[current] > biggestindex) then - biggestedge = current - biggestsize = size - biggestindex = edgeindices[current] - end - current = current.links[0] - until current == start - outeredges[1] = biggestedge - end - - -- now for every two comp - for _, id in ipairs(twocomps[i]) do - local biggestedge - local biggestsize - local biggestindex - local start = compedges[id][i][1] - local current = start - repeat - local size = self:get_face_size(current) - if not biggestedge or size > biggestsize - or (size == biggestsize - and edgeindices[current] > biggestindex) then - biggestedge = current - biggestsize = size - biggestindex = edgeindices[current] - end - current = current.links[0] - until current == start - table.insert(outeredges, biggestedge) - end - - -- now merge all comps at the outer edges - local lastedge = outeredges[#outeredges].links[0] - for _, edge in ipairs(outeredges) do - local nextlastedge = edge.links[0] - lastedge.links[1] = edge - edge.links[0] = lastedge - lastedge = nextlastedge - end - end + local pair = pairdata.pair + local companchors = pairdata.companchors + local edgecomps = pairdata.edgecomps + local edgeindices = pairdata.edgeindices + local compvertices = pairdata.compvertices + local tricomps = pairdata.tricomps + local twocomps = pairdata.twocomps + local comporder = pairdata.comporder + local v1 = pair[1] + local v2 = pair[2] + + local compedges = {} + for i = 1, #companchors do + compedges[i] = {{}, {}} + end + + local numtricomps = #tricomps + local numtwocomps = { #twocomps[1], #twocomps[2] } + + -- find compedges + for i = 1, #pair do + -- first find an edge that is the first of a triconnected component + local start2 + if v2 then + start = pair[i].link + current = start + local last + repeat + local comp = edgecomps[current] + if companchors[comp] == 3 then + if last == nil then + last = comp + elseif last ~= comp then + start2 = current + break + end + end + current = current.links[0] + until current == start + else + start2 = pair[i].link + end + -- now list the edges by components + current = start2 + repeat + table.insert(compedges[edgecomps[current]][i], current) + current = current.links[0] + until current == start2 + end + + -- count edges on each side of tri comps + local edgecount = {} + for _, comp in ipairs(tricomps) do + edgecount[comp] = {} + for i = 1, #pair do + local count = 1 + local current = compedges[comp][i][1] + local other = pair[3 - i] + while current.target ~= other do + count = count + 1 + current = current.twin.links[0] + end + edgecount[comp][i] = count + end + end + + -- determine which comps have to be flipped + local flips = {} + local numflips = 0 + local allflipped = true + for i, comp in ipairs(comporder[1]) do + local side1, side2 + if i > numtricomps / 2 then + side1 = edgecount[comp][1] + side2 = edgecount[comp][2] + else + side1 = edgecount[comp][2] + side2 = edgecount[comp][1] + end + if side1 > side2 then + numflips = numflips + 1 + flips[comp] = true + elseif side1 < side2 then + allflipped = false + end + end + + if allflipped then + for i, comp in ipairs(tricomps) do + flips[comp] = false + end + else + for i, comp in ipairs(tricomps) do + if flips[comp] then + for _, v in ipairs(compvertices[comp]) do + local start = v.link + local current = start + repeat + current.links[0], current.links[1] + = current.links[1], current.links[0] + current = current.links[1] + until current == start + end + end + end + end + + -- order edges cyclic per component (one cycle for all tri comps) + for i = 1, #pair do + if v2 then + local co + if allflipped then + co = comporder[3 - i] + else + co = comporder[i] + end + + local id = co[numtricomps] + lastedges = compedges[id][i] + if flips[id] then + lastedge = lastedges[1] + else + lastedge = lastedges[#lastedges] + end + + -- tri comps + for _, id in ipairs(co) do + local edges = compedges[id][i] + local from + local to + local step + if flips[id] then + from = #edges + to = 1 + step = -1 + else + from = 1 + to = #edges + step = 1 + end + for k = from, to, step do + local edge = edges[k] + lastedge.links[0] = edge + edge.links[1] = lastedge + lastedge = edge + end + end + end + + -- two comps + for _, id in ipairs(twocomps[i]) do + lastedges = compedges[id][i] + lastedge = lastedges[#lastedges] + for _, edge in ipairs(compedges[id][i]) do + lastedge.links[0] = edge + edge.links[1] = lastedge + lastedge = edge + end + end + end + + -- now merge the cycles + for i = 1, #pair do + local outeredges = {} + -- find the biggest face of the tri comps + if v2 then + local biggestedge + local biggestsize + local biggestindex + local start = compedges[tricomps[1]][i][1] + local current = start + repeat + local size = self:get_face_size(current) + if not biggestedge or size > biggestsize + or (size == biggestsize + and edgeindices[current] > biggestindex) then + biggestedge = current + biggestsize = size + biggestindex = edgeindices[current] + end + current = current.links[0] + until current == start + outeredges[1] = biggestedge + end + + -- now for every two comp + for _, id in ipairs(twocomps[i]) do + local biggestedge + local biggestsize + local biggestindex + local start = compedges[id][i][1] + local current = start + repeat + local size = self:get_face_size(current) + if not biggestedge or size > biggestsize + or (size == biggestsize + and edgeindices[current] > biggestindex) then + biggestedge = current + biggestsize = size + biggestindex = edgeindices[current] + end + current = current.links[0] + until current == start + table.insert(outeredges, biggestedge) + end + + -- now merge all comps at the outer edges + local lastedge = outeredges[#outeredges].links[0] + for _, edge in ipairs(outeredges) do + local nextlastedge = edge.links[0] + lastedge.links[1] = edge + edge.links[0] = lastedge + lastedge = nextlastedge + end + end end function E:get_face_size(halfedge) - local size = 0 - local current = halfedge - repeat - size = size + 1 - current = current.twin.links[1] - until current == halfedge - return size + local size = 0 + local current = halfedge + repeat + size = size + 1 + current = current.twin.links[1] + until current == halfedge + return size end return E |