summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/Embedding.lua
diff options
context:
space:
mode:
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.lua1445
1 files changed, 722 insertions, 723 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 8d9d3b53b14..50fc3672207 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,783 +6,782 @@ 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