summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Arc.lua265
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Collection.lua32
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Coordinate.lua22
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Digraph.lua178
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Edge.lua58
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Hyperedge.lua20
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Path.lua651
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Path_arced.lua116
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Vertex.lua46
9 files changed, 691 insertions, 697 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Arc.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Arc.lua
index e007e9b59b7..997a452399f 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Arc.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Arc.lua
@@ -14,10 +14,10 @@
-- An arc is a light-weight object representing an arc from a vertex
-- in a graph to another vertex. You may not create an |Arc| by
-- yourself, which is why there is no |new| method, arc creation is
--- done by the Digraph class.
+-- done by the Digraph class.
--
-- Every arc belongs to exactly one graph. If you want the same arc in
--- another graph, you need to newly connect two vertices in the other graph.
+-- another graph, you need to newly connect two vertices in the other graph.
--
-- You may read the |head| and |tail| fields, but you may not write
-- them. In order to store data for an arc, use |Storage| objects.
@@ -28,7 +28,7 @@
-- be multiple edges between two vertices. This means, in particular,
-- that an arc has no |options| field. Rather, it has several
-- |optionsXxxx| functions, that will search for options in all of the
--- syntactic edges that ``belong'' to an edge.
+-- synactic edges that ``belong'' to an edge.
--
-- In order to \emph{set} options of the edges, you can set the
-- |generated_options| field of an arc (which is |nil| by default), see
@@ -72,7 +72,7 @@
-- @field animations If non-nil, some animations to be passed back
-- to the original syntactic edges. See the description of the
-- |animations| field for |Vertex| for details on the syntax.
--- @field syntactic_edges In case this arc is an arc in the syntactic
+-- @field syntactic_edges In case this arc is an arc in the syntatic
-- digraph (and only then), this field contains an array containing
-- syntactic edges (``real'' edges in the syntactic digraph) that
-- underly this arc. Otherwise, the field will be empty or |nil|.
@@ -106,17 +106,15 @@ local lib = require 'pgf.gd.lib'
-- If your algorithm gets confused by multiple edges, try saying
-- |a:options(your_option)|. This will always give the ``most
-- sensible'' choice of the option if there are multiple edges
--- corresponding to the same arc.
+-- corresponding to the same arc.
--
-- @param option A string option like |"length"|.
--
--- @return A table with the following contents:
--- %
+-- @return A table with the following contents:
-- \begin{enumerate}
--- \item It is an array of all values the option has for edges
--- corresponding to |self| in the syntactic digraph. Suppose, for
--- instance, you write the following:
--- %
+-- \item It is an array of all values the option has for edges
+-- corresponding to |self| in the syntactic digraph. Suppose, for
+-- instance, you write the following:
--\begin{codeexample}[code only]
--graph {
-- tail -- [length=1] head, % multi edge 1
@@ -127,32 +125,31 @@ local lib = require 'pgf.gd.lib'
-- tail -- [length=2] head, % multi edge 6
--}
--\end{codeexample}
--- %
--- Suppose, furthermore, that |length| has been setup as an edge
--- option. Now suppose that |a| is the arc from the vertex |tail| to
--- the vertex |head|. Calling |a:optionsArray('length')| will
--- yield the array part |{1,3,2,8,7}|. The reason for the ordering is
--- as follows: First come all values |length| had for syntactic edges
--- going from |self.tail| to |self.head| in the order they appear in the
--- graph description. Then come all values the options has for syntactic
--- edges going from |self.head| to |self.tail|. The reason for this
--- slightly strange behavior is that many algorithms do not really
--- care whether someone writes |a --[length=1] b| or
--- |b --[length=1] a|; in both cases they would ``just'' like to know
--- that the length is~|1|.
---
--- \item There is field called |aligned|, which is an array storing
--- the actual syntactic edge objects whose values can be found in the
--- array part of the returned table. However, |aligned| contains only
--- the syntactic edges pointing ``in the same direction'' as the arc,
--- that is, the tail and head of the syntactic edge are the same as
--- those of the arc. In the above example, this array would contain
--- the edges with the comment numbers |1|, |2|, and |6|.
---
--- Using the length of this array and the fact that the ``aligned''
--- values come first in the table, you can easily iterate over the
--- |option|'s values of only those edges that are aligned with the arc:
--- %
+-- Suppose, furthermore, that |length| has been setup as an edge
+-- option. Now suppose that |a| is the arc from the vertex |tail| to
+-- the vertex |head|. Calling |a:optionsArray('length')| will
+-- yield the array part |{1,3,2,8,7}|. The reason for the ordering is
+-- as follows: First come all values |length| had for syntactic edges
+-- going from |self.tail| to |self.head| in the order they appear in the graph
+-- description. Then come all values the options has for syntactic
+-- edges going from |self.head| to |self.tail|. The reason for this
+-- slightly strange behaviour is that many algorithms do not really
+-- care whether someone writes |a --[length=1] b| or
+-- |b --[length=1] a|; in both cases they would ``just'' like to know
+-- that the length is~|1|.
+--
+-- \item There is field called |aligned|, which is an array storing
+-- the actual syntactic edge objects whose values can be found in the
+-- array part of the returned table. However, |aligned| contains only
+-- the syntactic edges pointing ``in the same direction'' as the arc,
+-- that is, the tail and head of the syntactic edge are the same as
+-- those of the arc. In the above example, this array would contain
+-- the edges with the comment numbers |1|, |2|, and |6|.
+--
+-- Using the length of this array and the fact that the ``aligned''
+-- values come first in the table, you can easily iterate over the
+-- |option|'s values of only those edges that are aligned with the arc:
+--
--\begin{codeexample}[code only, tikz syntax=false]
--local a = g:arc(tail.head) -- some arc
--local opt = a:optionsArray('length')
@@ -161,16 +158,17 @@ local lib = require 'pgf.gd.lib'
-- sum = sum + opt[i]
--end
--\end{codeexample}
--- %
--- \item There is a field called |anti_aligned|, which is an array
--- containing exactly the edges in the array part of the table not
--- aligned with the arc. The numbering start at |1| as usual, so the
--- $i$th entry of this table corresponds to the entry at position $i +
--- \verb!#opt.aligned!$ of the table.
--- \end{enumerate}
+--
+--\item There is a field called |anti_aligned|, which is an array
+-- containing exactly the edges in the array part of the table not
+-- aligned with the arc. The numbering start at |1| as usual, so the
+-- $i$th entry of this table corresponds to the entry at position $i +
+-- \verb!#opt.aligned!$ of the table.
+--
+--\end{enumerate}
--
function Arc:optionsArray(option)
-
+
local cache = self.option_cache
local t = cache[option]
if t then
@@ -187,23 +185,23 @@ function Arc:optionsArray(option)
if arc then
for _,m in ipairs(arc.syntactic_edges) do
if m.options[option] ~= nil then
- aligned[#aligned + 1] = m
+ aligned[#aligned + 1] = m
end
end
table.sort(aligned, function (a,b) return a.event.index < b.event.index end)
end
-
+
local arc = head ~= tail and s_graph:arc(head, tail)
local anti_aligned = {}
if arc then
for _,m in ipairs(arc.syntactic_edges) do
if m.options[option] ~= nil then
- anti_aligned[#anti_aligned + 1] = m
+ anti_aligned[#anti_aligned + 1] = m
end
end
table.sort(anti_aligned, function (a,b) return a.event.index < b.event.index end)
end
-
+
-- Now merge them together
local t = { aligned = aligned, anti_aligned = anti_aligned }
for i=1,#aligned do
@@ -213,7 +211,7 @@ function Arc:optionsArray(option)
t[#t+1] = anti_aligned[i].options[option]
end
cache[option] = t
-
+
return t
end
@@ -223,11 +221,11 @@ end
-- Returns the first option, that is, the first entry of
-- |Arc:optionsArray(option)|. However, if the |only_aligned|
-- parameter is set to true and there is no option with any aligned
--- syntactic edge, |nil| is returned.
+-- synactic edge, |nil| is returned.
--
-- @param option An option
-- @param only_aligned If true, only aligned syntactic edges will be
--- considered.
+-- considered.
-- @return The first entry of the |optionsArray|
function Arc:options(option, only_aligned)
if only_aligned then
@@ -258,7 +256,7 @@ end
-- edges will be considered.
--
-- @return If the option is not set for any (aligned) syntactic edges
--- corresponding to |self|, |nil| is returned. If there is exactly one
+-- corresponding to |self|, |nil| is returned. If there is exectly one
-- edge, the value of this edge is returned. Otherwise, the result of
-- repeatedly applying the |accumulator| function as described
-- above.
@@ -267,7 +265,6 @@ end
-- |accumulator| function again.
--
-- @usage Here is typical usage:
--- %
--\begin{codeexample}[code only, tikz syntax=false]
--local total_length = a:optionsAccumulated('length', function (a,b) return a+b end) or 0
--\end{codeexample}
@@ -280,7 +277,7 @@ function Arc:optionsAccumulated(option, accumulator, only_aligned)
if v == nil then
v = opt[1]
for i=2,#aligned do
- v = accumulator(v, opt[i])
+ v = accumulator(v, opt[i])
end
align[accumulator] = v
end
@@ -290,7 +287,7 @@ function Arc:optionsAccumulated(option, accumulator, only_aligned)
if v == nil then
v = opt[1]
for i=2,#opt do
- v = accumulator(v, opt[i])
+ v = accumulator(v, opt[i])
end
opt[accumulator] = v
end
@@ -304,7 +301,7 @@ end
-- Compute the syntactic head and tail of an arc. For this, we have a
-- look at the syntactic digraph underlying the arc. If there is at
-- least once syntactic edge going from the arc's tail to the arc's
--- head, the arc's tail and head are returned. Otherwise, we test
+-- head, the arc's tail and head are returned. Otherweise, we test
-- whether there is a syntactic edge in the other direction and, if
-- so, return head and tail in reverse order. Finally, if there is no
-- syntactic edge at all corresponding to the arc in either direction,
@@ -341,15 +338,15 @@ function Arc:pointCloud ()
if a then
for _,e in ipairs(a.syntactic_edges) do
for _,p in ipairs(e.path) do
- if type(p) == "table" then
- cloud[#cloud + 1] = p
- end
+ if type(p) == "table" then
+ cloud[#cloud + 1] = p
+ end
end
end
end
self.cached_point_cloud = cloud
return cloud
-end
+end
@@ -380,7 +377,7 @@ function Arc:eventIndex ()
end
self.cached_event_index = e
return e
-end
+end
@@ -392,16 +389,21 @@ end
-- edge involved in the arc.
--
-- The priority of an edge is computed as follows:
--- %
+--
-- \begin{enumerate}
--- \item If the option |"span priority"| is set, this number
--- will be used.
--- \item If the edge has the same head as the arc, we lookup the key\\
--- |"span priority " .. edge.direction|. If set, we use this value.
--- \item If the edge has a different head from the arc (the arc is
--- ``reversed'' with respect to the syntactic edge), we lookup the key
--- |"span priority reversed " .. edge.direction|. If set, we use this value.
--- \item Otherwise, we use priority 5.
+-- \item If the option |"span priority"| is set, this number
+-- will be used.
+--
+-- \item If the edge has the same head as the arc, we lookup the key\\
+-- |"span priority " .. edge.direction|. If set, we use
+-- this value.
+--
+-- \item If the edge has a different head from the arc (the arc is
+-- ``reversed'' with respect to the syntactic edge), we lookup the key
+-- |"span priority reversed " .. edge.direction|. If set,
+-- we use this value.
+--
+-- \item Otherwise, we use priority 5.
-- \end{enumerate}
--
-- @return The priority of the arc, as described above.
@@ -410,7 +412,7 @@ function Arc:spanPriority()
if self.cached_span_priority then
return self.cached_span_priority
end
-
+
local head = self.head
local tail = self.tail
local min
@@ -420,8 +422,8 @@ function Arc:spanPriority()
if a then
for _,m in ipairs(a.syntactic_edges) do
local p =
- m.options["span priority"] or
- lib.lookup_option("span priority " .. m.direction, m, g)
+ m.options["span priority"] or
+ lib.lookup_option("span priority " .. m.direction, m, g)
min = math.min(p or 5, min or math.huge)
end
@@ -431,15 +433,15 @@ function Arc:spanPriority()
if a then
for _,m in ipairs(a.syntactic_edges) do
local p =
- m.options["span priority"] or
- lib.lookup_option("span priority reversed " .. m.direction, m, g)
-
+ m.options["span priority"] or
+ lib.lookup_option("span priority reversed " .. m.direction, m, g)
+
min = math.min(p or 5, min or math.huge)
end
end
-
+
self.cached_span_priority = min or 5
-
+
return min or 5
end
@@ -459,7 +461,6 @@ end
-- which will replace the function in the |Path|.
--
-- You use this method like this:
--- %
--\begin{codeexample}[code only, tikz syntax=false]
--...
--local arc = g:connect(s,t)
@@ -484,34 +485,34 @@ function Arc:sync()
local a = self.syntactic_digraph:arc(tail,head)
if a and #a.syntactic_edges>0 then
for _,e in ipairs(a.syntactic_edges) do
- local clone = path:clone()
- for i=1,#clone do
- local p = clone[i]
- if type(p) == "function" then
- clone[i] = p(e)
- if type(clone[i]) == "table" then
- clone[i] = clone[i]:clone()
- end
- end
- end
- e.path = clone
+ local clone = path:clone()
+ for i=1,#clone do
+ local p = clone[i]
+ if type(p) == "function" then
+ clone[i] = p(e)
+ if type(clone[i]) == "table" then
+ clone[i] = clone[i]:clone()
+ end
+ end
+ end
+ e.path = clone
end
end
local a = head ~= tail and self.syntactic_digraph:arc(head,tail)
if a and #a.syntactic_edges>0 then
for _,e in ipairs(a.syntactic_edges) do
- local clone = path:reversed()
- for i=1,#clone do
- local p = clone[i]
- if type(p) == "function" then
- clone[i] = p(e)
- if type(clone[i]) == "table" then
- clone[i] = clone[i]:clone()
- end
- end
- end
- e.path = clone
- end
+ local clone = path:reversed()
+ for i=1,#clone do
+ local p = clone[i]
+ if type(p) == "function" then
+ clone[i] = p(e)
+ if type(clone[i]) == "table" then
+ clone[i] = clone[i]:clone()
+ end
+ end
+ end
+ e.path = clone
+ end
end
end
if self.generated_options then
@@ -520,19 +521,19 @@ function Arc:sync()
local a = self.syntactic_digraph:arc(tail,head)
if a and #a.syntactic_edges>0 then
for _,e in ipairs(a.syntactic_edges) do
- for _,o in ipairs(self.generated_options) do
- e.generated_options[#e.generated_options+1] = o
- end
+ for _,o in ipairs(self.generated_options) do
+ e.generated_options[#e.generated_options+1] = o
+ end
end
end
local a = head ~= tail and self.syntactic_digraph:arc(head,tail)
if a and #a.syntactic_edges>0 then
for _,e in ipairs(a.syntactic_edges) do
- for _,o in ipairs(self.generated_options) do
- e.generated_options[#e.generated_options+1] = o
- end
+ for _,o in ipairs(self.generated_options) do
+ e.generated_options[#e.generated_options+1] = o
+ end
end
- end
+ end
end
if self.animations then
local head = self.head
@@ -540,17 +541,17 @@ function Arc:sync()
local a = self.syntactic_digraph:arc(tail,head)
if a and #a.syntactic_edges>0 then
for _,e in ipairs(a.syntactic_edges) do
- for _,o in ipairs(self.animations) do
- e.animations[#e.animations+1] = o
- end
+ for _,o in ipairs(self.animations) do
+ e.animations[#e.animations+1] = o
+ end
end
end
local a = head ~= tail and self.syntactic_digraph:arc(head,tail)
if a and #a.syntactic_edges>0 then
for _,e in ipairs(a.syntactic_edges) do
- for _,o in ipairs(self.animations) do
- e.animations[#e.animations+1] = o
- end
+ for _,o in ipairs(self.animations) do
+ e.animations[#e.animations+1] = o
+ end
end
end
end
@@ -571,8 +572,8 @@ end
-- method to get a function that will, later on, compute the correct
-- position of the anchor as needed.
--
--- Here is the code you would use to create the above-mentioned path:
--- %
+-- Here is the code you would use to create the abovementioned path:
+--
--\begin{codeexample}[code only, tikz syntax=false]
--local a = g:connect(tail,head)
--...
@@ -584,19 +585,19 @@ end
--
-- Normally, however, you will not write code as detailed as the above
-- and you would just write instead of the last three lines:
--- %
+--
--\begin{codeexample}[code only, tikz syntax=false]
--arc:setPolylinePath { Coordinate.new (10, 10) }
--\end{codeexample}
function Arc:tailAnchorForArcPath()
return function (edge)
- local a = edge.options['tail anchor']
- if a == "" then
- a = "center"
- end
- return self.tail:anchor(a) + self.tail.pos
- end
+ local a = edge.options['tail anchor']
+ if a == "" then
+ a = "center"
+ end
+ return self.tail:anchor(a) + self.tail.pos
+ end
end
---
@@ -604,12 +605,12 @@ end
function Arc:headAnchorForArcPath()
return function (edge)
- local a = edge.options['head anchor']
- if a == "" then
- a = "center"
- end
- return self.head:anchor(a) + self.head.pos
- end
+ local a = edge.options['head anchor']
+ if a == "" then
+ a = "center"
+ end
+ return self.head:anchor(a) + self.head.pos
+ end
end
@@ -632,7 +633,7 @@ function Arc:setPolylinePath(coordinates)
end
p:appendLineto(self:headAnchorForArcPath())
-
+
self.path = p
end
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Collection.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Collection.lua
index abc454b7dbb..8ebb6f144cf 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Collection.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Collection.lua
@@ -20,11 +20,11 @@
-- vertices that should be on the same level in a layered algorithm,
-- or, indeed, subgraphs that are rendered in a special way.
--
--- Collections are grouped into ``kinds''. All collections of a given
+-- Collections are grouped into ``kinds.'' All collections of a given
-- kind can be accessed by algorithms through an array whose elements
--- are the collections. On the display layer, for each kind a separate
--- key is available to indicate that a node or an edge belongs to a
--- collection.
+-- are the collections. On the displya layer, for each kind a separate
+-- key is available to indicate that a node or an edge belongs to a
+-- collection.
--
-- Collections serve two purposes: First, they can be seen as ``hints''
-- to graph drawing algorithms that certain nodes and/or edges ``belong
@@ -48,14 +48,14 @@
-- was in force when the collection was created.
--
-- @field child_collections An array of all collections that are
--- direct children of this collection (that is,
+-- direct children of this collection (that is,
-- they were defined while the current collection was the most
-- recently defined collection on the options stack). However, you
-- should use the methods |children|, |descendants|, and so to access
-- this field.
--
-- @field parent_collection The parent collection of the current
--- collection. This field may be |nil| in case a collection has no parent.
+-- colleciton. This field may be |nil| in case a collection has no parent.
--
-- @field event An |Event| object that was create for this
-- collection. Its |kind| will be |"collection"| while its |parameter|
@@ -86,7 +86,7 @@ local Storage = require "pgf.gd.lib.Storage"
--
function Collection.new(t)
assert (type(t.kind) == "string" and t.kind ~= "", "collection kind not set")
-
+
return setmetatable(
{
vertices = t.vertices or {},
@@ -111,7 +111,7 @@ end
function Collection:registerAsChildOf(parent)
self.parent = parent
- if parent then
+ if parent then
assert (getmetatable(parent) == Collection, "parent must be a collection")
parent.child_collections[#parent.child_collections+1] = self
end
@@ -149,10 +149,10 @@ end
function Collection:childrenOfKind(kind)
local function rec (c, a)
for _,d in ipairs(c.child_collections) do
- if d.kind == kind then
- a[#a + 1] = d
+ if d.kind == kind then
+ a[#a + 1] = d
else
- rec (d, a)
+ rec (d, a)
end
end
return a
@@ -163,7 +163,7 @@ end
---
-- The descendants of a collection are its children, plus their
--- children, plus their children, and so on.
+-- children, plus their children, and so on.
--
-- @return An array of all descendants of |self|. It will be in
-- preorder.
@@ -184,15 +184,15 @@ end
---
-- The descendants of a collection of the given |kind|.
--
--- @param kind A collection kind.
+-- @param kind A colleciton kind.
--
-- @return An array of all descendants of |self| of the given |kind|.
function Collection:descendantsOfKind(kind)
local function rec (c, a)
for _,d in ipairs(c.child_collections) do
- if d.kind == kind then
- a[#a + 1] = d
+ if d.kind == kind then
+ a[#a + 1] = d
end
rec (d, a)
end
@@ -205,4 +205,4 @@ end
-- Done
-return Collection
+return Collection \ No newline at end of file
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Coordinate.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Coordinate.lua
index 3a4448ab089..815544ee705 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Coordinate.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Coordinate.lua
@@ -10,17 +10,17 @@
-- @release $Header$
----
+---
-- A Coordinate models a position on the drawing canvas.
--
-- It has an |x| field and a |y| field, which are numbers that will be
-- interpreted as \TeX\ points (1/72.27th of an inch). The $x$-axis goes
-- right and the $y$-axis goes up.
--
--- @field x
+-- @field x
-- @field y
--
--- There is also a static field called |origin| that is always equal to the origin.
+-- There is also a static field called |origin| that is always equal to the origin.
local Coordinate = {}
Coordinate.__index = Coordinate
@@ -61,7 +61,7 @@ end
--- Apply a transformation matrix to a coordinate,
-- see |pgf.gd.lib.Transform| for details.
--
--- @param t A transformation.
+-- @param t A tansformation.
function Coordinate:apply(t)
local x = self.x
@@ -74,7 +74,7 @@ end
--- Shift a coordinate
--
-- @param a An $x$ offset
--- @param b A $y$ offset
+-- @param b A $y$ offset
function Coordinate:shift(a,b)
self.x = self.x + a
@@ -87,7 +87,7 @@ end
-- inversed coordinate; only faster).
--
-- @param a An $x$ offset
--- @param b A $y$ offset
+-- @param b A $y$ offset
function Coordinate:unshift(a,b)
self.x = self.x - a
@@ -110,7 +110,7 @@ end
---
-- Like |unshift|, only for coordinate parameters.
--
--- @param c Another coordinate.
+-- @param c Another coordinate.
function Coordinate:unshiftByCoordinate(c)
self.x = self.x - c.x
@@ -119,7 +119,7 @@ end
---
--- Moves the coordinate a fraction of |f| along a straight line to |c|.
+-- Moves the coordinate a fraction of |f| along a straight line to |c|.
--
-- @param c Another coordinate
-- @param f A fraction
@@ -268,13 +268,13 @@ end
-- @return |max_x|
-- @return |max_y|
-- @return |center_x| The center of the bounding box
--- @return |center_y|
+-- @return |center_y|
function Coordinate.boundingBox(array)
if #array > 0 then
local min_x, min_y = math.huge, math.huge
local max_x, max_y = -math.huge, -math.huge
-
+
for i=1,#array do
local c = array[i]
local x = c.x
@@ -284,7 +284,7 @@ function Coordinate.boundingBox(array)
if x > max_x then max_x = x end
if y > max_y then max_y = y end
end
-
+
return min_x, min_y, max_x, max_y, (min_x+max_x) / 2, (min_y+max_y) / 2
end
end
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Digraph.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Digraph.lua
index 30b600e308d..5c48059a605 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Digraph.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Digraph.lua
@@ -12,12 +12,12 @@
----
+---
-- Each |Digraph| instance models a \emph{directed, simple}
-- graph. ``Directed'' means that all edges ``point'' from a head node
-- to a tail node. ``Simple'' means that between any nodes there can be
-- (at most) one edge. Since these properties are a bit at odds with
--- the normal behavior of ``nodes'' and ``edges'' in \tikzname,
+-- the normal behaviour of ``nodes'' and ``edges'' in \tikzname,
-- different names are used for them inside the |model| namespace:
-- The class modeling ``edges'' is actually called |Arc| to stress
-- that an arc has a specific ``start'' (the tail) and a specific
@@ -31,17 +31,14 @@
-- Since digraphs are constantly created and modified inside the graph
-- drawing engine, some care was taken to ensure that all operations
-- work as quickly as possible. In particular:
--- %
-- \begin{itemize}
--- \item Adding an array of $k$ vertices using the |add| method needs
--- time $O(k)$.
--- \item Adding an arc between two vertices needs time $O(1)$.
--- \item Accessing both the |vertices| and the |arcs| fields takes time
--- $O(1)$, provided only the above operations are used.
+-- \item Adding an array of $k$ vertices using the |add| method needs
+-- time $O(k)$.
+-- \item Adding an arc between two vertices needs time $O(1)$.
+-- \item Accessing both the |vertices| and the |arcs| fields takes time
+-- $O(1)$, provided only the above operations are used.
-- \end{itemize}
--- %
-- Deleting vertices and arcs takes more time:
--- %
-- \begin{itemize}
-- \item Deleting the vertices given in an array of $k$ vertices from a
-- graph with $n$ vertices takes time $O(\max\{n,c\})$ where $c$ is the
@@ -53,12 +50,12 @@
-- number of outgoing arcs at the arc's tail and $h_i$ is the number
-- of incoming arcs at the arc's head. After a call to |disconnect|,
-- the next use of the |arcs| field will take time $O(|V| + |E|)$,
--- while subsequent accesses take time $O(1)$ -- till the
+-- while subsequent accesses take time $O(1)$ -- till the
-- next use of |disconnect|. This means that once you start deleting
-- arcs using |disconnect|, you should perform as many additional
-- |disconnect|s as possible before accessing |arcs| one more.
-- \end{itemize}
---
+--
-- \medskip
-- \noindent\emph{Stability.} The |vertices| field and the array
-- returned by |Digraph:incoming| and |Digraph:outgoing| are
@@ -66,7 +63,7 @@
-- when you use |ipairs| on the will be the ordering in which the
-- vertices or arcs were added to the graph. Even when you remove a
-- vertex or an arc, the ordering of the remaining elements stays the
--- same.
+-- same.
--
-- @field vertices This array contains the vertices that are part of
-- the digraph. Internally, this array
@@ -106,18 +103,15 @@
-- given vertex |v|, you cannot say something like |v.outgoings| or
-- perhaps |v:getOutgoings()|. Rather, you have to say |g:outgoing(v)|
-- to get this list:
--- %
--\begin{codeexample}[code only, tikz syntax=false]
---for _,a in ipairs(g:outgoing(v)) do -- g is a Digraph object.
+--for _,a in ipairs(g:outgoing(v)) do -- g is a Digraph object.
-- pgf.debug ("There is an arc leaving " .. tostring(v) ..
-- " heading to " .. tostring(a.head))
--end
--\end{codeexample}
--- %
--- Naturally, there is also a method |g:incoming()|.
---
--- To iterate over all arcs of a graph you can say:
--- %
+-- Naturally, there is also a method |g:incoming()|.
+--
+-- To iterate over all arcs of a graph you can say:
--\begin{codeexample}[code only, tikz syntax=false]
--for _,v in ipairs(g.vertices) do
-- for _,a in ipairs(g:outgoing(v)) do
@@ -128,7 +122,7 @@
--
-- However, it will often be more convenient and, in case the there
-- are far less arcs than vertices, also faster to write
---
+--
--\begin{codeexample}[code only, tikz syntax=false]
--for _,a in ipairs(g.arcs) do
-- ...
@@ -136,7 +130,7 @@
--\end{codeexample}
--
-- @field arcs For any two vertices |t| and |h| of a graph, there may
--- or may not be
+-- or may not be
-- an arc from |t| to |h|. If this is the case, there is an |Arc|
-- object that represents this arc. Note that, since |Digraph|s are
-- always simple graphs, there can be at most one such object for every
@@ -144,7 +138,7 @@
-- an |Arc| through a |Storage|, see the |Storage| class for
-- details. Each |Arc| for an edge of the syntactic digraph stores
-- an array called |syntactic_edges| of all the multiple edges that
--- are present in the user's input.
+-- are present in the user's input.
--
-- Unlike vertices, the arc objects of a graph are always local to a
-- graph; an |Arc| object can never be part of two digraphs at the same
@@ -170,7 +164,7 @@
-- point, the |arcs| array is reconstructed by adding all arcs of all
-- nodes to it.
--
--- The bottom line of the behavior of the |arcs| field is that (a) the
+-- The bottom line of the behaviour of the |arcs| field is that (a) the
-- ordering of the elements may change abruptly whenever you remove an
-- arc from a graph and (b) performing $k$ |disconnect| operations in
-- sequence takes time $O(k)$, provided you do not access the |arcs|
@@ -194,12 +188,12 @@ local function recalc_arcs (digraph)
end
end
digraph.arcs = arcs
- return arcs
+ return arcs
end
-Digraph.__index =
+Digraph.__index =
function (t, k)
- if k == "arcs" then
+ if k == "arcs" then
return recalc_arcs(t)
else
return rawget(Digraph,k)
@@ -229,7 +223,7 @@ local Vertex = require "pgf.gd.model.Vertex"
-- created graphs always have an empty arcs set. This means that
-- writing |Digraph.new(g)| where |g| is a graph creates a new graph
-- whose vertex set is the same as |g|'s, but where there are no edges:
--- %
+--
--\begin{codeexample}[code only, tikz syntax=false]
--local g = Digraph.new {}
--g:add { v1, v2, v3 }
@@ -245,8 +239,8 @@ local Vertex = require "pgf.gd.model.Vertex"
--local h = Digraph.new (g)
--for _,a in ipairs(g.arcs) do h:connect(a.tail, a.head) end
--\end{codeexample}
---
--- This operation takes time $O(1)$.
+--
+-- This operation takes time $O(1)$.
--
-- @param initial A table of initial values. It is permissible that
-- this array contains a |vertices| field. In this
@@ -274,7 +268,7 @@ function Digraph.new(initial)
digraph.vertices = {}
digraph.arcs = {}
- if vertices then
+ if vertices then
digraph:add(vertices)
end
return digraph
@@ -315,25 +309,25 @@ end
--
function Digraph:remove(array)
local vertices = self.vertices
-
+
-- Mark all to-be-deleted nodes
for i=1,#array do
local v = array[i]
assert(vertices[v], "to-be-deleted node is not in graph")
vertices[v] = false
end
-
+
-- Disconnect them
for i=1,#array do
self:disconnect(array[i])
end
-
+
LookupTable.remove(self.vertices, array)
end
---- Test, whether a graph contains a given vertex.
+--- Test, whether a graph contains a given vertex.
--
-- This operation takes time $O(1)$.
--
@@ -348,7 +342,7 @@ end
---
-- Returns the arc between two nodes, provided it exists. Otherwise,
--- |nil| is returned.
+-- |nil| is retured.
--
-- This operation takes time $O(1)$.
--
@@ -366,7 +360,7 @@ end
----
+---
-- Returns an array containing the outgoing arcs of a vertex. You may
-- only iterate over his array using ipairs, not using pairs.
--
@@ -421,7 +415,7 @@ function Digraph:orderOutgoing(v, vertices)
-- Compute ordering of the arcs
local reordered = {}
for _,arc in ipairs(outgoing) do
- reordered [lookup[arc.head]] = arc
+ reordered [lookup[arc.head]] = arc
end
-- Copy back
@@ -463,7 +457,7 @@ function Digraph:orderIncoming(v, vertices)
-- Compute ordering of the arcs
local reordered = {}
for _,arc in ipairs(incoming) do
- reordered [lookup[arc.head]] = arc
+ reordered [lookup[arc.head]] = arc
end
-- Copy back
@@ -476,9 +470,9 @@ end
----
+---
-- Connects two nodes by an arc and returns the newly created arc
--- object. If they are already connected, the existing arc is returned.
+-- object. If they are already connected, the existing arc is returned.
--
-- This operation takes time $O(1)$.
--
@@ -528,10 +522,10 @@ end
----
+---
-- Disconnect either a single vertex |v| from all its neighbors (remove all
-- incoming and outgoing arcs of this vertex) or, in case two nodes
--- are given as parameter, remove the arc between them, if it exists.
+-- are given as parameter, remove the arc between them, if it exsits.
--
-- This operation takes time $O(|I_v| + |I_t|)$, where $I_x$ is the set
-- of vertices incident to $x$, to remove the single arc between $v$ and
@@ -551,23 +545,23 @@ function Digraph:disconnect(v, t)
-- Remove:
s_outgoings[t] = nil
for i=1,#s_outgoings do
- if s_outgoings[i].head == t then
- table.remove (s_outgoings, i)
- break
- end
+ if s_outgoings[i].head == t then
+ table.remove (s_outgoings, i)
+ break
+ end
end
t_incomings[v] = nil
for i=1,#t_incomings do
- if t_incomings[i].tail == v then
- table.remove (t_incomings, i)
- break
- end
+ if t_incomings[i].tail == v then
+ table.remove (t_incomings, i)
+ break
+ end
end
self.arcs = nil -- invalidate arcs field
end
else
-- Case 1: Remove all arcs incident to v:
-
+
-- Step 1: Delete all incomings arcs:
local incomings = assert(v.incomings[self], "node not in graph")
local vertices = self.vertices
@@ -575,15 +569,15 @@ function Digraph:disconnect(v, t)
for i=1,#incomings do
local s = incomings[i].tail
if s ~= v and vertices[s] then -- skip self-loop and to-be-deleted nodes
- -- Remove this arc from s:
- local s_outgoings = s.outgoings[self]
- s_outgoings[v] = nil
- for i=1,#s_outgoings do
- if s_outgoings[i].head == v then
- table.remove (s_outgoings, i)
- break
- end
- end
+ -- Remove this arc from s:
+ local s_outgoings = s.outgoings[self]
+ s_outgoings[v] = nil
+ for i=1,#s_outgoings do
+ if s_outgoings[i].head == v then
+ table.remove (s_outgoings, i)
+ break
+ end
+ end
end
end
@@ -592,14 +586,14 @@ function Digraph:disconnect(v, t)
for i=1,#outgoings do
local t = outgoings[i].head
if t ~= v and vertices[t] then
- local t_incomings = t.incomings[self]
- t_incomings[v] = nil
- for i=1,#t_incomings do
- if t_incomings[i].tail == v then
- table.remove (t_incomings, i)
- break
- end
- end
+ local t_incomings = t.incomings[self]
+ t_incomings[v] = nil
+ for i=1,#t_incomings do
+ if t_incomings[i].tail == v then
+ table.remove (t_incomings, i)
+ break
+ end
+ end
end
end
@@ -616,12 +610,12 @@ end
----
+---
-- An arc is changed so that instead of connecting |self.tail|
-- and |self.head|, it now connects a new |head| and |tail|. The
-- difference to first disconnecting and then reconnecting is that all
-- fields of the arc (other than |head| and |tail|, of course), will
--- be ``moved along''. Reconnecting an arc in the same way as before has no
+-- be ``moved along.'' Reconnecting an arc in the same way as before has no
-- effect.
--
-- If there is already an arc at the new position, fields of the
@@ -643,16 +637,16 @@ end
--
function Digraph:reconnect(arc, tail, head)
assert (arc and tail and head, "connect with nil parameters")
-
+
if arc.head == head and arc.tail == tail then
-- Nothing to be done
return arc
else
local new_arc = self:connect(tail, head)
-
+
for k,v in pairs(arc) do
if k ~= "head" and k ~= "tail" then
- new_arc[k] = v
+ new_arc[k] = v
end
end
@@ -688,11 +682,11 @@ end
-- A collapse vertex will store the collapsed vertices so that you can
-- call |expand| later on to ``restore'' the vertices and arcs that
-- were saved during a collapse. This storage is \emph{not} local to
--- the graph in which the collapse occurred.
+-- the graph in which the collapse occured.
--
-- @param collapse_vertices An array of to-be-collapsed vertices
-- @param collapse_vertex The vertex that represents the collapse. If
--- missing, a vertex will be created automatically and added to the graph.
+-- missing, a vertex will be created automatically and added to the graph.
-- @param vertex_fun This function is called for each to-be-collapsed
-- vertex. The parameters are the collapse vertex and the
-- to-be-collapsed vertex. May be |nil|.
@@ -700,7 +694,7 @@ end
-- between |rep| and some other vertex. The arguments are the new arc
-- and the original arc. May be |nil|.
--
--- @return The new vertex that represents the collapsed vertices.
+-- @return The new vertex that represents the collapsed vertices.
function Digraph:collapse(collapse_vertices, collapse_vertex, vertex_fun, arc_fun)
@@ -710,7 +704,7 @@ function Digraph:collapse(collapse_vertices, collapse_vertex, vertex_fun, arc_fu
collapse_vertex = Vertex.new {}
end
self:add {collapse_vertex}
-
+
-- Copy the collapse_vertices and create lookup
local cvs = {}
for i=1,#collapse_vertices do
@@ -722,29 +716,29 @@ function Digraph:collapse(collapse_vertices, collapse_vertex, vertex_fun, arc_fu
-- Connected collapse_vertex appropriately
local collapsed_arcs = {}
-
+
if not arc_fun then
arc_fun = function () end
end
-
+
for _,v in ipairs(cvs) do
if vertex_fun then
vertex_fun (collapse_vertex, v)
end
for _,a in ipairs(v.outgoings[self]) do
if cvs[a.head] ~= true then
- arc_fun (self:connect(collapse_vertex, a.head), a)
- collapsed_arcs[#collapsed_arcs + 1] = a
+ arc_fun (self:connect(collapse_vertex, a.head), a)
+ collapsed_arcs[#collapsed_arcs + 1] = a
end
end
for _,a in ipairs(v.incomings[self]) do
if cvs[a.tail] ~= true then
- arc_fun (self:connect(a.tail, collapse_vertex), a)
+ arc_fun (self:connect(a.tail, collapse_vertex), a)
end
collapsed_arcs[#collapsed_arcs + 1] = a
end
end
-
+
-- Remember the old vertices.
collapse_vertex.collapsed_vertices = cvs
collapse_vertex.collapsed_arcs = collapsed_arcs
@@ -776,7 +770,7 @@ function Digraph:expand(vertex, vertex_fun, arc_fun)
-- Add all vertices:
self:add(cvs)
- if vertex_fun then
+ if vertex_fun then
for _,v in ipairs(cvs) do
vertex_fun(vertex, v)
end
@@ -785,13 +779,13 @@ function Digraph:expand(vertex, vertex_fun, arc_fun)
-- Add all arcs:
for _,arc in ipairs(vertex.collapsed_arcs) do
local new_arc = self:connect(arc.tail, arc.head)
-
+
for k,v in pairs(arc) do
if k ~= "head" and k ~= "tail" then
- new_arc[k] = v
+ new_arc[k] = v
end
end
-
+
if arc_fun then
arc_fun(new_arc, vertex)
end
@@ -815,7 +809,7 @@ end
----
+---
-- Computes a string representation of this graph including all nodes
-- and edges. The syntax of this representation is such that it can be
-- used directly in \tikzname's |graph| syntax.
@@ -831,13 +825,13 @@ function Digraph:__tostring()
if #out_arcs > 0 then
local t = {}
for j,a in ipairs(out_arcs) do
- t[j] = tostring(a.head)
+ t[j] = tostring(a.head)
end
astrings[#astrings + 1] = " " .. tostring(v) .. " -> { " .. table.concat(t,", ") .. " }"
end
end
return "graph [id=" .. tostring(self.vertices) .. "] {\n {\n" ..
- table.concat(vstrings, ",\n") .. "\n }; \n" ..
+ table.concat(vstrings, ",\n") .. "\n }; \n" ..
table.concat(astrings, ";\n") .. "\n}";
end
@@ -846,4 +840,4 @@ end
-- Done
-return Digraph
+return Digraph \ No newline at end of file
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Edge.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Edge.lua
index 45cbc60f9f7..87b06661e54 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Edge.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Edge.lua
@@ -10,12 +10,12 @@
-- @release $Header$
----
+---
-- An |Edge| is a ``syntactic'' connection between two
-- vertices that represents a connection present in the syntactic
-- digraph. Unlike an |Arc|, |Edge| objects are not controlled by the
-- |Digraph| class. Also unlike |Arc| objects, there can be several
--- edges between the same vertices, namely whenever several such edges
+-- edges betwen the same vertices, namely whenever several such edges
-- are present in the syntactic digraph.
--
-- In detail, the relationship between arcs and edges is as follows:
@@ -33,15 +33,15 @@
-- second one. Whether
-- an edge is directed or not depends on the |direction| of the edge, which
-- may be one of the following:
--- %
+--
-- \begin{enumerate}
--- \item |"->"|
--- \item |"--"|
--- \item |"<-"|
--- \item |"<->"|
--- \item |"-!-"|
+-- \item |"->"|
+-- \item |"--"|
+-- \item |"<-"|
+-- \item |"<->"|
+-- \item |"-!-"|
-- \end{enumerate}
---
+--
--
-- @field head The head vertex of this edge.
--
@@ -63,7 +63,7 @@
-- |InterfaceToAlgorithms|.
--
-- @field animations An array of animations, see the |animations|
--- field of the |Vertex| class for the syntax.
+-- field of the |Vertex| class for the syntax.
local Edge = {}
Edge.__index = Edge
@@ -79,14 +79,14 @@ require("pgf.gd.model").Edge = Edge
local Path = require "pgf.gd.model.Path"
----
+---
-- Create a new edge. The |initial| parameter allows you to setup
-- some initial values.
--
-- @usage
--\begin{codeexample}[code only, tikz syntax=false]
--local v = Edge.new { tail = v1, head = v2 }
---\end{codeexample}
+--\end{codeexample}
--
-- @param initial Values to override defaults. --
-- @return A new edge object.
@@ -125,10 +125,10 @@ end
-- Note that you typically do not use this function, but use the
-- corresponding function of the |Arc| class. Use this function only
-- if there are multiple edges between two vertices that need to be
--- routed differently.
+-- routed differently.
+--
+-- Here is the code you would use to create the abovementioned path:
--
--- Here is the code you would use to create the above-mentioned path:
--- %
--\begin{codeexample}[code only, tikz syntax=false]
--local a = g:connect(tail,head)
--local e = a.syntactic_edges[1]
@@ -140,19 +140,19 @@ end
--\end{codeexample}
--
-- As for the |Arc| class, you can also setup a polyline more easily:
--- %
+--
--\begin{codeexample}[code only, tikz syntax=false]
--e:setPolylinePath { Coordinate.new (10, 10) }
--\end{codeexample}
function Edge:tailAnchorForEdgePath()
return function ()
- local a = self.options['tail anchor']
- if a == "" then
- a = "center"
- end
- return self.tail:anchor(a) + self.tail.pos
- end
+ local a = self.options['tail anchor']
+ if a == "" then
+ a = "center"
+ end
+ return self.tail:anchor(a) + self.tail.pos
+ end
end
---
@@ -160,12 +160,12 @@ end
function Edge:headAnchorForEdgePath()
return function ()
- local a = self.options['head anchor']
- if a == "" then
- a = "center"
- end
- return self.head:anchor(a) + self.head.pos
- end
+ local a = self.options['head anchor']
+ if a == "" then
+ a = "center"
+ end
+ return self.head:anchor(a) + self.head.pos
+ end
end
@@ -188,7 +188,7 @@ function Edge:setPolylinePath(coordinates)
end
p:appendLineto(self:headAnchorForEdgePath())
-
+
self.path = p
end
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Hyperedge.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Hyperedge.lua
index cc265023fa5..3819e193689 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Hyperedge.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Hyperedge.lua
@@ -11,7 +11,7 @@
----
+---
-- @section subsection {Hyperedges}
--
-- @end
@@ -28,19 +28,19 @@ declare {
key = "hyper",
layer = -10,
- summary = [["
- A \emph{hyperedge} of a graph does not connect just two nodes, but
- is any subset of the node set (although a normal edge is also a
- hyperedge that happens to contain just two nodes). Internally, a
- collection of kind |hyper| is created. Currently, there is
- no default renderer for hyper edges.
+ summary = [["
+ A \emph{hyperedge} of a graph does not connect just two nodes, but
+ is any subset of the node set (although a normal edge is also a
+ hyperedge that happens to contain just two nodes). Internally, a
+ collection of kind |hyper| is created. Currently, there is
+ no default renderer for hyper edges.
"]],
documentation = [["
\begin{codeexample}[code only]
\graph {
% The nodes:
a, b, c, d;
-
+
% The edges:
{[hyper] a,b,c};
{[hyper] b,c,d};
@@ -50,7 +50,7 @@ declare {
\end{codeexample}
"]]
}
-
--- Done
+
+-- Done
return Hyperedge \ No newline at end of file
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Path.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Path.lua
index cbd0f079bfb..93cd44cc218 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Path.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Path.lua
@@ -10,32 +10,32 @@
-- @release $Header$
----
+---
-- A Path models a path in the plane.
--
-- Following the PostScript/\textsc{pdf}/\textsc{svg} convention, a
-- path consists of a series of path segments, each of which can be
--- closed or not. Each path segment, in turn, consists of a series of
--- Bézier curves and straight line segments; see
+-- closed or not. Each path segement, in turn, consists of a series of
+-- Bézier curvers and straight line segments; see
-- Section~\ref{section-paths} for an introduction to paths in
-- general.
--
-- A |Path| object is a table whose array part stores
--- |Coordinate| objects, |strings|, and |function|s that
--- describe the path of the edge. The following strings are allowed in
+-- |Coordinate| objects, |strings|, and |function|s that
+-- describe the path of the edge. The following strings are allowed in
-- this array:
--- %
+--
-- \begin{itemize}
--- \item |"moveto"| The line's path should stop at the current
--- position and then start anew at the next coordinate in the array.
--- \item |"lineto"| The line should continue from the current position
--- to the next coordinate in the array.
--- \item |"curveto"| The line should continue form the current
--- position with a Bézier curve that is specified by the next three
--- |Coordinate| objects (in the usual manner).
--- \item |"closepath"| The line's path should be ``closed'' in the sense
--- that the current subpath that was started with the most recent
--- moveto operation should now form a closed curve.
+-- \item |"moveto"| The line's path should stop at the current
+-- position and then start anew at the next coordinate in the array.
+-- \item |"lineto"| The line should continue from the current position
+-- to the next coordinate in the array.
+-- \item |"curveto"| The line should continue form the current
+-- position with a Bézier curve that is specified bz the next three
+-- |Coordinate| objects (in the usual manner).
+-- \item |"closepath"| The line's path should be ``closed'' in the sense
+-- that the current subpath that was started with the most recent
+-- moveto operation should now form a closed curve.
-- \end{itemize}
--
-- Instead of a |Coordinate|, a |Path| may also contain a function. In
@@ -93,36 +93,36 @@ function Path.new(initial)
while i <= #initial do
local e = initial[i]
if type(e) == "string" then
- assert (count == 0, "illformed path")
- if e == "moveto" then
- count = 1
- elseif e == "lineto" then
- count = 1
- elseif e == "closepath" then
- count = 0
- elseif e == "curveto" then
- count = 3
- else
- error ("unknown path command " .. e)
- end
- new[#new+1] = e
+ assert (count == 0, "illformed path")
+ if e == "moveto" then
+ count = 1
+ elseif e == "lineto" then
+ count = 1
+ elseif e == "closepath" then
+ count = 0
+ elseif e == "curveto" then
+ count = 3
+ else
+ error ("unknown path command " .. e)
+ end
+ new[#new+1] = e
elseif type(e) == "number" then
- if count == 0 then
- new[#new+1] = "lineto"
- else
- count = count - 1
- end
- new[#new+1] = Coordinate.new(e,initial[i+1])
- i = i + 1
+ if count == 0 then
+ new[#new+1] = "lineto"
+ else
+ count = count - 1
+ end
+ new[#new+1] = Coordinate.new(e,initial[i+1])
+ i = i + 1
elseif type(e) == "table" or type(e) == "function" then
- if count == 0 then
- new[#new+1] = "lineto"
- else
- count = count - 1
- end
- new[#new+1] = e
+ if count == 0 then
+ new[#new+1] = "lineto"
+ else
+ count = count - 1
+ end
+ new[#new+1] = e
else
- error ("invalid object on path")
+ error ("invalid object on path")
end
i = i + 1
end
@@ -158,7 +158,7 @@ end
-- @return A copy of the reversed path
function Path:reversed()
-
+
-- First, build segments
local subpaths = {}
local subpath = {}
@@ -169,7 +169,7 @@ function Path:reversed()
subpath = {}
end
end
-
+
local prev
local start
@@ -178,9 +178,9 @@ function Path:reversed()
local x = self[i]
if x == "lineto" then
subpath[#subpath+1] = {
- action = 'lineto',
- from = prev,
- to = self[i+1]
+ action = 'lineto',
+ from = prev,
+ to = self[i+1]
}
prev = self[i+1]
i = i + 2
@@ -192,9 +192,9 @@ function Path:reversed()
i = i + 2
elseif x == "closepath" then
subpath [#subpath + 1] = {
- action = "closepath",
- from = prev,
- to = start,
+ action = "closepath",
+ from = prev,
+ to = start,
}
prev = nil
start = nil
@@ -203,11 +203,11 @@ function Path:reversed()
elseif x == "curveto" then
local s1, s2, to = self[i+1], self[i+2], self[i+3]
subpath [#subpath + 1] = {
- action = "curveto",
- from = prev,
- to = to,
- support_1 = s1,
- support_2 = s2,
+ action = "curveto",
+ from = prev,
+ to = to,
+ support_1 = s1,
+ support_2 = s2,
}
prev = self[i+3]
i = i + 4
@@ -216,7 +216,7 @@ function Path:reversed()
end
end
closepath ()
-
+
local new = Path.new ()
for _,subpath in ipairs(subpaths) do
@@ -226,29 +226,29 @@ function Path:reversed()
else
-- We start with a moveto to the end point:
new:appendMoveto(subpath[#subpath].to)
-
+
-- Now walk backwards:
for i=#subpath,1,-1 do
- if subpath[i].action == "lineto" then
- new:appendLineto(subpath[i].from)
- elseif subpath[i].action == "closepath" then
- new:appendLineto(subpath[i].from)
- elseif subpath[i].action == "curveto" then
- new:appendCurveto(subpath[i].support_2,
- subpath[i].support_1,
- subpath[i].from)
- else
- error("illegal path command")
- end
+ if subpath[i].action == "lineto" then
+ new:appendLineto(subpath[i].from)
+ elseif subpath[i].action == "closepath" then
+ new:appendLineto(subpath[i].from)
+ elseif subpath[i].action == "curveto" then
+ new:appendCurveto(subpath[i].support_2,
+ subpath[i].support_1,
+ subpath[i].from)
+ else
+ error("illegal path command")
+ end
end
-- Append a closepath, if necessary
if subpath[#subpath].action == "closepath" then
- new:appendClosepath()
+ new:appendClosepath()
end
end
end
-
+
return new
end
@@ -314,7 +314,7 @@ end
-- Appends a |moveto| to the path.
--
-- @param x A |Coordinate| or |function| or, if the |y| parameter is
--- not |nil|, a number that is the $x$-part of a coordinate.
+-- not |nil|, a number that is the $x$-part of a coordiante .
-- @param y The $y$-part of the coordinate.
function Path:appendMoveto(x,y)
@@ -327,7 +327,7 @@ end
-- Appends a |lineto| to the path.
--
-- @param x A |Coordinate| or |function|, if the |y| parameter is not
--- |nil|, a number that is the $x$-part of a coordinate.
+-- |nil|, a number that is the $x$-part of a coordiante .
-- @param y The $y$-part of the coordinate.
function Path:appendLineto(x,y)
@@ -362,7 +362,7 @@ function Path:appendCurveto(a,b,c,d,e,f)
self[#self + 1] = a
self[#self + 1] = b
self[#self + 1] = c
- end
+ end
end
@@ -371,7 +371,7 @@ end
---
--- Makes a path ``rigid'', meaning that all coordinates that are only
+-- Makes a path ``rigid,'' meaning that all coordinates that are only
-- given as functions are replaced by the values these functions
-- yield.
@@ -406,7 +406,7 @@ end
-- Returns a bounding box of the path. This will not necessarily be
-- the minimal bounding box in case the path contains curves because,
-- then, the support points of the curve are used for the computation
--- rather than the actual bounding box of the path.
+-- rather than the actual boinding box of the path.
--
-- If the path contains no coordinates, all return values are 0.
--
@@ -415,22 +415,22 @@ end
-- @return |max_x|
-- @return |max_y|
-- @return |center_x| The center of the bounding box
--- @return |center_y|
+-- @return |center_y|
function Path:boundingBox()
if #self > 0 then
local min_x, min_y = math.huge, math.huge
local max_x, max_y = -math.huge, -math.huge
-
+
for i=1,#self do
local c = rigid(self[i])
if type(c) == "table" then
- local x = c.x
- local y = c.y
- if x < min_x then min_x = x end
- if y < min_y then min_y = y end
- if x > max_x then max_x = x end
- if y > max_y then max_y = y end
+ local x = c.x
+ local y = c.y
+ if x < min_x then min_x = x end
+ if y < min_y then min_y = y end
+ if x > max_x then max_x = x end
+ if y > max_y then max_y = y end
end
end
@@ -453,22 +453,21 @@ local eps = 0.0001
---
-- Computes all intersections of a path with another path and returns
-- them as an array of coordinates. The intersections will be sorted
--- ``along the path |self|''. The implementation uses a
+-- ``along the path |self|.'' The implementation uses a
-- divide-and-conquer approach that should be reasonably fast in
--- practice.
+-- practice.
--
-- @param path Another path
--
-- @return Array of all intersections of |path| with |self| in the
-- order they appear on |self|. Each entry of this array is a table
-- with the following fields:
--- %
-- \begin{itemize}
--- \item |index| The index of the segment in |self| where
--- the intersection occurs.
--- \item |time| The ``time'' at which a point traveling along the
--- segment from its start point to its end point.
--- \item |point| The point itself.
+-- \item |index| The index of the segment in |self| where
+-- the intersection occurs.
+-- \item |time| The ``time'' at which a point travelling along the
+-- segment from its start point to its end point.
+-- \item |point| The point itself.
-- \end{itemize}
function Path:intersectionsWith(path)
@@ -479,13 +478,13 @@ function Path:intersectionsWith(path)
local memo2 = prepare_memo(p2)
local intersections = {}
-
+
local function intersect_segments(i1, i2)
-
+
local s1 = p1[i1]
local s2 = p2[i2]
local r = {}
-
+
if s1.action == 'lineto' and s2.action == 'lineto' then
local a = s2.to.x - s2.from.x
local b = s1.from.x - s1.to.x
@@ -493,103 +492,103 @@ function Path:intersectionsWith(path)
local d = s2.to.y - s2.from.y
local e = s1.from.y - s1.to.y
local f = s2.from.y - s1.from.y
-
+
local det = a*e - b*d
-
+
if math.abs(det) > eps*eps then
- local t, s = (c*d - a*f)/det, (b*f - e*c)/det
+ local t, s = (c*d - a*f)/det, (b*f - e*c)/det
- if t >= 0 and t<=1 and s>=0 and s <= 1 then
- local p = s1.from:clone()
- p:moveTowards(s1.to, t)
- return { { time = t, point = p } }
- end
+ if t >= 0 and t<=1 and s>=0 and s <= 1 then
+ local p = s1.from:clone()
+ p:moveTowards(s1.to, t)
+ return { { time = t, point = p } }
+ end
end
elseif s1.action == 'lineto' and s2.action == 'curveto' then
intersect_curves (0, 1,
- s1.from.x, s1.from.y,
- s1.from.x*2/3+s1.to.x*1/3, s1.from.y*2/3+s1.to.y*1/3,
- s1.from.x*1/3+s1.to.x*2/3, s1.from.y*1/3+s1.to.y*2/3,
- s1.to.x, s1.to.y,
- s2.from.x, s2.from.y,
- s2.support_1.x, s2.support_1.y,
- s2.support_2.x, s2.support_2.y,
- s2.to.x, s2.to.y,
- r)
+ s1.from.x, s1.from.y,
+ s1.from.x*2/3+s1.to.x*1/3, s1.from.y*2/3+s1.to.y*1/3,
+ s1.from.x*1/3+s1.to.x*2/3, s1.from.y*1/3+s1.to.y*2/3,
+ s1.to.x, s1.to.y,
+ s2.from.x, s2.from.y,
+ s2.support_1.x, s2.support_1.y,
+ s2.support_2.x, s2.support_2.y,
+ s2.to.x, s2.to.y,
+ r)
elseif s1.action == 'curveto' and s2.action == 'lineto' then
intersect_curves (0, 1,
- s1.from.x, s1.from.y,
- s1.support_1.x, s1.support_1.y,
- s1.support_2.x, s1.support_2.y,
- s1.to.x, s1.to.y,
- s2.from.x, s2.from.y,
- s2.from.x*2/3+s2.to.x*1/3, s2.from.y*2/3+s2.to.y*1/3,
- s2.from.x*1/3+s2.to.x*2/3, s2.from.y*1/3+s2.to.y*2/3,
- s2.to.x, s2.to.y,
- r)
+ s1.from.x, s1.from.y,
+ s1.support_1.x, s1.support_1.y,
+ s1.support_2.x, s1.support_2.y,
+ s1.to.x, s1.to.y,
+ s2.from.x, s2.from.y,
+ s2.from.x*2/3+s2.to.x*1/3, s2.from.y*2/3+s2.to.y*1/3,
+ s2.from.x*1/3+s2.to.x*2/3, s2.from.y*1/3+s2.to.y*2/3,
+ s2.to.x, s2.to.y,
+ r)
else
intersect_curves (0, 1,
- s1.from.x, s1.from.y,
- s1.support_1.x, s1.support_1.y,
- s1.support_2.x, s1.support_2.y,
- s1.to.x, s1.to.y,
- s2.from.x, s2.from.y,
- s2.support_1.x, s2.support_1.y,
- s2.support_2.x, s2.support_2.y,
- s2.to.x, s2.to.y,
- r)
+ s1.from.x, s1.from.y,
+ s1.support_1.x, s1.support_1.y,
+ s1.support_2.x, s1.support_2.y,
+ s1.to.x, s1.to.y,
+ s2.from.x, s2.from.y,
+ s2.support_1.x, s2.support_1.y,
+ s2.support_2.x, s2.support_2.y,
+ s2.to.x, s2.to.y,
+ r)
end
return r
end
-
+
local function intersect (i1, j1, i2, j2)
if i1 > j1 or i2 > j2 then
return
end
-
+
local bb1 = bb(i1, j1, memo1)
local bb2 = bb(i2, j2, memo2)
-
+
if boxes_intersect(bb1, bb2) then
-- Ok, need to do something
if i1 == j1 and i2 == j2 then
- local intersects = intersect_segments (i1, i2)
- for _,t in ipairs(intersects) do
- intersections[#intersections+1] = {
- time = t.time,
- index = p1[i1].path_pos,
- point = t.point
- }
- end
+ local intersects = intersect_segments (i1, i2)
+ for _,t in ipairs(intersects) do
+ intersections[#intersections+1] = {
+ time = t.time,
+ index = p1[i1].path_pos,
+ point = t.point
+ }
+ end
elseif i1 == j1 then
- local m2 = math.floor((i2 + j2) / 2)
- intersect(i1, j1, i2, m2)
- intersect(i1, j1, m2+1, j2)
+ local m2 = math.floor((i2 + j2) / 2)
+ intersect(i1, j1, i2, m2)
+ intersect(i1, j1, m2+1, j2)
elseif i2 == j2 then
- local m1 = math.floor((i1 + j1) / 2)
- intersect(i1, m1, i2, j2)
- intersect(m1+1, j1, i2, j2)
+ local m1 = math.floor((i1 + j1) / 2)
+ intersect(i1, m1, i2, j2)
+ intersect(m1+1, j1, i2, j2)
else
- local m1 = math.floor((i1 + j1) / 2)
- local m2 = math.floor((i2 + j2) / 2)
- intersect(i1, m1, i2, m2)
- intersect(m1+1, j1, i2, m2)
- intersect(i1, m1, m2+1, j2)
- intersect(m1+1, j1, m2+1, j2)
+ local m1 = math.floor((i1 + j1) / 2)
+ local m2 = math.floor((i2 + j2) / 2)
+ intersect(i1, m1, i2, m2)
+ intersect(m1+1, j1, i2, m2)
+ intersect(i1, m1, m2+1, j2)
+ intersect(m1+1, j1, m2+1, j2)
end
- end
+ end
end
-
+
-- Run the recursion
intersect(1, #p1, 1, #p2)
-- Sort
table.sort(intersections, function(a,b)
- return a.index < b.index or
- a.index == b.index and a.time < b.time
- end)
-
+ return a.index < b.index or
+ a.index == b.index and a.time < b.time
+ end)
+
-- Remove duplicates
local remains = {}
remains[1] = intersections[1]
@@ -609,15 +608,15 @@ end
function boxes_intersect (bb1, bb2)
return (bb1.max_x >= bb2.min_x - eps*eps and
- bb1.min_x <= bb2.max_x + eps*eps and
- bb1.max_y >= bb2.min_y - eps*eps and
- bb1.min_y <= bb2.max_y + eps*eps)
+ bb1.min_x <= bb2.max_x + eps*eps and
+ bb1.max_y >= bb2.min_y - eps*eps and
+ bb1.min_y <= bb2.max_y + eps*eps)
end
-- Turns a path into a sequence of segments, each being either a
-- lineto or a curveto from some point to another point. It also sets
--- up a memorization array for the bounding boxes.
+-- up a memoization array for the bounding boxes.
function segmentize (path)
@@ -628,20 +627,20 @@ function segmentize (path)
local i = 1
while i <= #path do
local x = path[i]
-
+
if x == "lineto" then
x = rigid(path[i+1])
s [#s + 1] = {
- path_pos = i,
- action = "lineto",
- from = prev,
- to = x,
- bb = {
- min_x = math.min(prev.x, x.x),
- max_x = math.max(prev.x, x.x),
- min_y = math.min(prev.y, x.y),
- max_y = math.max(prev.y, x.y),
- }
+ path_pos = i,
+ action = "lineto",
+ from = prev,
+ to = x,
+ bb = {
+ min_x = math.min(prev.x, x.x),
+ max_x = math.max(prev.x, x.x),
+ min_y = math.min(prev.y, x.y),
+ max_y = math.max(prev.y, x.y),
+ }
}
prev = x
i = i + 2
@@ -651,16 +650,16 @@ function segmentize (path)
i = i + 2
elseif x == "closepath" then
s [#s + 1] = {
- path_pos = i,
- action = "lineto",
- from = prev,
- to = start,
- bb = {
- min_x = math.min(prev.x, start.x),
- max_x = math.max(prev.x, start.x),
- min_y = math.min(prev.y, start.y),
- max_y = math.max(prev.y, start.y),
- }
+ path_pos = i,
+ action = "lineto",
+ from = prev,
+ to = start,
+ bb = {
+ min_x = math.min(prev.x, start.x),
+ max_x = math.max(prev.x, start.x),
+ min_y = math.min(prev.y, start.y),
+ max_y = math.max(prev.y, start.y),
+ }
}
prev = nil
start = nil
@@ -668,18 +667,18 @@ function segmentize (path)
elseif x == "curveto" then
local s1, s2, to = rigid(path[i+1]), rigid(path[i+2]), rigid(path[i+3])
s [#s + 1] = {
- action = "curveto",
- path_pos = i,
- from = prev,
- to = to,
- support_1 = s1,
- support_2 = s2,
- bb = {
- min_x = math.min(prev.x, s1.x, s2.x, to.x),
- max_x = math.max(prev.x, s1.x, s2.x, to.x),
- min_y = math.min(prev.y, s1.y, s2.y, to.y),
- max_y = math.max(prev.y, s1.y, s2.y, to.y),
- }
+ action = "curveto",
+ path_pos = i,
+ from = prev,
+ to = to,
+ support_1 = s1,
+ support_2 = s2,
+ bb = {
+ min_x = math.min(prev.x, s1.x, s2.x, to.x),
+ max_x = math.max(prev.x, s1.x, s2.x, to.x),
+ min_y = math.min(prev.y, s1.y, s2.y, to.y),
+ max_y = math.max(prev.y, s1.y, s2.y, to.y),
+ }
}
prev = path[i+3]
i = i + 4
@@ -693,16 +692,16 @@ end
function prepare_memo (s)
-
+
local memo = {}
-
+
memo.base = #s
-
+
-- Fill memo table
for i,e in ipairs (s) do
memo[i*#s + i] = e.bb
end
-
+
return memo
end
@@ -713,8 +712,8 @@ end
function bb (i, j, memo)
local b = memo[memo.base*i + j]
if not b then
- assert (i < j, "memorization table filled incorrectly")
-
+ assert (i < j, "memoization table filled incorrectly")
+
local mid = math.floor((i+j)/2)
local bb1 = bb (i, mid, memo)
local bb2 = bb (mid+1, j, memo)
@@ -726,21 +725,21 @@ function bb (i, j, memo)
}
memo[memo.base*i + j] = b
end
-
+
return b
end
--- Intersect two Bézier curves.
+-- Intersect two Bezier curves.
function intersect_curves(t0, t1,
- c1_ax, c1_ay, c1_bx, c1_by,
- c1_cx, c1_cy, c1_dx, c1_dy,
- c2_ax, c2_ay, c2_bx, c2_by,
- c2_cx, c2_cy, c2_dx, c2_dy,
- intersections)
-
+ c1_ax, c1_ay, c1_bx, c1_by,
+ c1_cx, c1_cy, c1_dx, c1_dy,
+ c2_ax, c2_ay, c2_bx, c2_by,
+ c2_cx, c2_cy, c2_dx, c2_dy,
+ intersections)
+
-- Only do something, if the bounding boxes intersect:
local c1_min_x = math.min(c1_ax, c1_bx, c1_cx, c1_dx)
local c1_max_x = math.max(c1_ax, c1_bx, c1_cx, c1_dx)
@@ -750,12 +749,12 @@ function intersect_curves(t0, t1,
local c2_max_x = math.max(c2_ax, c2_bx, c2_cx, c2_dx)
local c2_min_y = math.min(c2_ay, c2_by, c2_cy, c2_dy)
local c2_max_y = math.max(c2_ay, c2_by, c2_cy, c2_dy)
-
+
if c1_max_x >= c2_min_x and
c1_min_x <= c2_max_x and
c1_max_y >= c2_min_y and
- c1_min_y <= c2_max_y then
-
+ c1_min_y <= c2_max_y then
+
-- Everything "near together"?
if c1_max_x - c1_min_x < eps and c1_max_y - c1_min_y < eps then
@@ -766,57 +765,57 @@ function intersect_curves(t0, t1,
local d = c2_dy - c2_ay
local e = c1_ay - c1_dy
local f = c2_ay - c1_ay
-
+
local det = a*e - b*d
local t
-
+
t = (c*d - a*f)/det
if t<0 then
- t=0
+ t=0
elseif t>1 then
- t=1
+ t=1
end
intersections [#intersections + 1] = {
- time = t0 + t*(t1-t0),
- point = Coordinate.new(c1_ax + t*(c1_dx-c1_ax), c1_ay+t*(c1_dy-c1_ay))
+ time = t0 + t*(t1-t0),
+ point = Coordinate.new(c1_ax + t*(c1_dx-c1_ax), c1_ay+t*(c1_dy-c1_ay))
}
else
-- Cut 'em in half!
local c1_ex, c1_ey = (c1_ax + c1_bx)/2, (c1_ay + c1_by)/2
local c1_fx, c1_fy = (c1_bx + c1_cx)/2, (c1_by + c1_cy)/2
local c1_gx, c1_gy = (c1_cx + c1_dx)/2, (c1_cy + c1_dy)/2
-
+
local c1_hx, c1_hy = (c1_ex + c1_fx)/2, (c1_ey + c1_fy)/2
local c1_ix, c1_iy = (c1_fx + c1_gx)/2, (c1_fy + c1_gy)/2
-
+
local c1_jx, c1_jy = (c1_hx + c1_ix)/2, (c1_hy + c1_iy)/2
-
+
local c2_ex, c2_ey = (c2_ax + c2_bx)/2, (c2_ay + c2_by)/2
local c2_fx, c2_fy = (c2_bx + c2_cx)/2, (c2_by + c2_cy)/2
local c2_gx, c2_gy = (c2_cx + c2_dx)/2, (c2_cy + c2_dy)/2
-
+
local c2_hx, c2_hy = (c2_ex + c2_fx)/2, (c2_ey + c2_fy)/2
local c2_ix, c2_iy = (c2_fx + c2_gx)/2, (c2_fy + c2_gy)/2
-
+
local c2_jx, c2_jy = (c2_hx + c2_ix)/2, (c2_hy + c2_iy)/2
intersect_curves (t0, (t0+t1)/2,
- c1_ax, c1_ay, c1_ex, c1_ey, c1_hx, c1_hy, c1_jx, c1_jy,
- c2_ax, c2_ay, c2_ex, c2_ey, c2_hx, c2_hy, c2_jx, c2_jy,
- intersections)
+ c1_ax, c1_ay, c1_ex, c1_ey, c1_hx, c1_hy, c1_jx, c1_jy,
+ c2_ax, c2_ay, c2_ex, c2_ey, c2_hx, c2_hy, c2_jx, c2_jy,
+ intersections)
intersect_curves (t0, (t0+t1)/2,
- c1_ax, c1_ay, c1_ex, c1_ey, c1_hx, c1_hy, c1_jx, c1_jy,
- c2_jx, c2_jy, c2_ix, c2_iy, c2_gx, c2_gy, c2_dx, c2_dy,
- intersections)
+ c1_ax, c1_ay, c1_ex, c1_ey, c1_hx, c1_hy, c1_jx, c1_jy,
+ c2_jx, c2_jy, c2_ix, c2_iy, c2_gx, c2_gy, c2_dx, c2_dy,
+ intersections)
intersect_curves ((t0+t1)/2, t1,
- c1_jx, c1_jy, c1_ix, c1_iy, c1_gx, c1_gy, c1_dx, c1_dy,
- c2_ax, c2_ay, c2_ex, c2_ey, c2_hx, c2_hy, c2_jx, c2_jy,
- intersections)
+ c1_jx, c1_jy, c1_ix, c1_iy, c1_gx, c1_gy, c1_dx, c1_dy,
+ c2_ax, c2_ay, c2_ex, c2_ey, c2_hx, c2_hy, c2_jx, c2_jy,
+ intersections)
intersect_curves ((t0+t1)/2, t1,
- c1_jx, c1_jy, c1_ix, c1_iy, c1_gx, c1_gy, c1_dx, c1_dy,
- c2_jx, c2_jy, c2_ix, c2_iy, c2_gx, c2_gy, c2_dx, c2_dy,
- intersections)
+ c1_jx, c1_jy, c1_ix, c1_iy, c1_gx, c1_gy, c1_dx, c1_dy,
+ c2_jx, c2_jy, c2_ix, c2_iy, c2_gx, c2_gy, c2_dx, c2_dy,
+ intersections)
end
end
end
@@ -829,30 +828,30 @@ end
-- segment and everything in the segment before the given time is
-- removed from the path.
--
--- @param index The index of a path segment.
+-- @param index The index of a path segment.
-- @param time A time along the specified path segment.
function Path:cutAtBeginning(index, time)
-
+
local cut_path = Path:new ()
-
+
-- Ok, first, we need to find the segment *before* the current
-- one. Usually, this will be a moveto or a lineto, but things could
-- be different.
assert (type(self[index-1]) == "table" or type(self[index-1]) == "function",
- "segment before intersection does not end with a coordinate")
+ "segment before intersection does not end with a coordinate")
local from = rigid(self[index-1])
local action = self[index]
-
+
-- Now, depending on the type of segment, we do different things:
if action == "lineto" then
-
+
-- Ok, compute point:
local to = rigid(self[index+1])
from:moveTowards(to, time)
-
+
-- Ok, this is easy: We start with a fresh moveto ...
cut_path[1] = "moveto"
cut_path[2] = from
@@ -889,20 +888,20 @@ function Path:cutAtBeginning(index, time)
for i=index+4,#self do
cut_path[#cut_path+1] = self[i]
end
-
+
elseif action == "closepath" then
-- Let us find the start point:
- local found
+ local found
for i=index,1,-1 do
if self[i] == "moveto" then
- -- Bingo:
- found = i
- break
+ -- Bingo:
+ found = i
+ break
end
end
assert(found, "no moveto found in path")
-
+
local to = rigid(self[found+1])
from:moveTowards(to,time)
@@ -935,36 +934,36 @@ end
-- Shorten a path at the end. This method works like |cutAtBeginning|,
-- only the path is cut at the end.
--
--- @param index The index of a path segment.
+-- @param index The index of a path segment.
-- @param time A time along the specified path segment.
function Path:cutAtEnd(index, time)
local cut_path = Path:new ()
-
+
-- Ok, first, we need to find the segment *before* the current
-- one. Usually, this will be a moveto or a lineto, but things could
-- be different.
assert (type(self[index-1]) == "table" or type(self[index-1]) == "function",
- "segment before intersection does not end with a coordinate")
+ "segment before intersection does not end with a coordinate")
local from = rigid(self[index-1])
local action = self[index]
-
+
-- Now, depending on the type of segment, we do different things:
if action == "lineto" then
-
+
-- Ok, compute point:
local to = rigid(self[index+1])
to:moveTowards(from, 1-time)
-
+
for i=1,index do
cut_path[i] = self[i]
end
cut_path[index+1] = to
-
+
elseif action == "curveto" then
-
+
local s1 = rigid(self[index+1])
local s2 = rigid(self[index+2])
local to = rigid(self[index+3])
@@ -987,20 +986,20 @@ function Path:cutAtEnd(index, time)
cut_path[index+1] = s1
cut_path[index+2] = s2
cut_path[index+3] = to
-
+
elseif action == "closepath" then
-- Let us find the start point:
- local found
+ local found
for i=index,1,-1 do
if self[i] == "moveto" then
- -- Bingo:
- found = i
- break
+ -- Bingo:
+ found = i
+ break
end
end
assert(found, "no moveto found in path")
-
+
local to = rigid(self[found+1]:clone())
to:moveTowards(from,1-time)
@@ -1029,7 +1028,7 @@ end
-- ``Pads'' the path. The idea is the following: Suppose we stroke the
-- path with a pen whose width is twice the value |padding|. The outer
-- edge of this stroked drawing is now a path by itself. The path will
--- be a bit longer and ``larger''. The present function tries to
+-- be a bit longer and ``larger.'' The present function tries to
-- compute an approximation to this resulting path.
--
-- The algorithm used to compute the enlarged part does not necessarily
@@ -1041,29 +1040,29 @@ end
--
function Path:pad(padding)
-
+
local padded = self:clone()
padded:makeRigid()
if padding == 0 then
return padded
end
-
+
-- First, decompose the path into subpaths:
local subpaths = {}
local subpath = {}
local start_index = 1
-
+
local function closepath(end_index)
if #subpath >= 1 then
subpath.start_index = start_index
subpath.end_index = end_index
start_index = end_index + 1
-
+
local start = 1
if (subpath[#subpath] - subpath[1]):norm() < 0.01 and subpath[2] then
- start = 2
- subpath.skipped = subpath[1]
+ start = 2
+ subpath.skipped = subpath[1]
end
subpath[#subpath + 1] = subpath[start]
subpath[#subpath + 1] = subpath[start+1]
@@ -1071,11 +1070,11 @@ function Path:pad(padding)
subpath = {}
end
end
-
+
for i,p in ipairs(padded) do
if p ~= "closepath" then
if type(p) == "table" then
- subpath[#subpath + 1] = p
+ subpath[#subpath + 1] = p
end
else
closepath (i)
@@ -1088,7 +1087,7 @@ function Path:pad(padding)
local new_coordinates = {}
local _,_,_,_,c_x,c_y = Coordinate.boundingBox(subpath)
local c = Coordinate.new(c_x,c_y)
-
+
-- Find out the orientation of the path
local count = 0
for i=1,#subpath-2 do
@@ -1096,19 +1095,19 @@ function Path:pad(padding)
local d1 = subpath[i+2] - subpath[i+1]
local diff = math.atan2(d2.y,d2.x) - math.atan2(d1.y,d1.x)
-
+
if diff < -math.pi then
- count = count + 1
+ count = count + 1
elseif diff > math.pi then
- count = count - 1
+ count = count - 1
end
end
-
+
for i=2,#subpath-1 do
local p = subpath[i]
local d1 = subpath[i] - subpath[i-1]
local d2 = subpath[i+1] - subpath[i]
-
+
local orth1 = Coordinate.new(-d1.y, d1.x)
local orth2 = Coordinate.new(-d2.y, d2.x)
@@ -1116,21 +1115,21 @@ function Path:pad(padding)
orth2:normalize()
if count < 0 then
- orth1:scale(-1)
- orth2:scale(-1)
+ orth1:scale(-1)
+ orth2:scale(-1)
end
-- Ok, now we want to compute the intersection of the lines
-- perpendicular to p + padding*orth1 and p + padding*orth2:
-
+
local det = orth1.x * orth2.y - orth1.y * orth2.x
local c
if math.abs(det) < 0.1 then
- c = orth1 + orth2
- c:scale(padding/2)
+ c = orth1 + orth2
+ c:scale(padding/2)
else
- c = Coordinate.new (padding*(orth2.y-orth1.y)/det, padding*(orth1.x-orth2.x)/det)
+ c = Coordinate.new (padding*(orth2.y-orth1.y)/det, padding*(orth1.x-orth2.x)/det)
end
new_coordinates[i] = c+p
@@ -1147,50 +1146,50 @@ function Path:pad(padding)
local p = subpath[1]
local new_p = new_coordinates[#subpath-2]
p.x = new_p.x
- p.y = new_p.y
+ p.y = new_p.y
end
-
+
-- Now, we need to correct the curveto fields:
for i=subpath.start_index,subpath.end_index do
if self[i] == 'curveto' then
- local from = rigid(self[i-1])
- local s1 = rigid(self[i+1])
- local s2 = rigid(self[i+2])
- local to = rigid(self[i+3])
-
- local p1x, p1y, _, _, h1x, h1y =
- Bezier.atTime(from.x, from.y, s1.x, s1.y, s2.x, s2.y,
- to.x, to.y, 1/3)
-
- local p2x, p2y, _, _, _, _, h2x, h2y =
- Bezier.atTime(from.x, from.y, s1.x, s1.y, s2.x, s2.y,
- to.x, to.y, 2/3)
-
- local orth1 = Coordinate.new (p1y - h1y, -(p1x - h1x))
- orth1:normalize()
- orth1:scale(-padding)
-
- local orth2 = Coordinate.new (p2y - h2y, -(p2x - h2x))
- orth2:normalize()
- orth2:scale(padding)
-
- if count < 0 then
- orth1:scale(-1)
- orth2:scale(-1)
- end
-
- local new_s1, new_s2 =
- Bezier.supportsForPointsAtTime(padded[i-1],
- Coordinate.new(p1x+orth1.x,p1y+orth1.y), 1/3,
- Coordinate.new(p2x+orth2.x,p2y+orth2.y), 2/3,
- padded[i+3])
-
- padded[i+1] = new_s1
- padded[i+2] = new_s2
+ local from = rigid(self[i-1])
+ local s1 = rigid(self[i+1])
+ local s2 = rigid(self[i+2])
+ local to = rigid(self[i+3])
+
+ local p1x, p1y, _, _, h1x, h1y =
+ Bezier.atTime(from.x, from.y, s1.x, s1.y, s2.x, s2.y,
+ to.x, to.y, 1/3)
+
+ local p2x, p2y, _, _, _, _, h2x, h2y =
+ Bezier.atTime(from.x, from.y, s1.x, s1.y, s2.x, s2.y,
+ to.x, to.y, 2/3)
+
+ local orth1 = Coordinate.new (p1y - h1y, -(p1x - h1x))
+ orth1:normalize()
+ orth1:scale(-padding)
+
+ local orth2 = Coordinate.new (p2y - h2y, -(p2x - h2x))
+ orth2:normalize()
+ orth2:scale(padding)
+
+ if count < 0 then
+ orth1:scale(-1)
+ orth2:scale(-1)
+ end
+
+ local new_s1, new_s2 =
+ Bezier.supportsForPointsAtTime(padded[i-1],
+ Coordinate.new(p1x+orth1.x,p1y+orth1.y), 1/3,
+ Coordinate.new(p2x+orth2.x,p2y+orth2.y), 2/3,
+ padded[i+3])
+
+ padded[i+1] = new_s1
+ padded[i+2] = new_s2
end
end
end
-
+
return padded
end
@@ -1203,12 +1202,12 @@ end
-- the following happens: We first invert the transformation
-- and apply it to the start point. Then we compute the arc
-- ``normally'', as if no transformation matrix were present. Then we
--- apply the transformation matrix to all computed points.
+-- apply the transformation matrix to all computed points.
--
-- @function Path:appendArc(start_angle,end_angle,radius,trans)
--
-- @param start_angle The start angle of the arc. Must be specified in
--- degrees.
+-- degrees.
-- @param end_angle the end angle of the arc.
-- @param radius The radius of the circle on which this arc lies.
-- @param trans A transformation matrix. If |nil|, the identity
@@ -1233,7 +1232,7 @@ Path.appendArc = lib.ondemand("Path_arced", Path, "appendArc")
-- of the circle.
-- @param clockwise If true, the arc will be clockwise. Otherwise (the
-- default, if nothing or |nil| is given), the arc will be counter
--- clockwise.
+-- clockise.
-- @param trans A transformation matrix. If missing,
-- the identity matrix is assumed.
@@ -1250,7 +1249,7 @@ function Path:__tostring()
local i = 1
while i <= #self do
local p = self[i]
-
+
if p == "lineto" then
r [#r+1] = " -- " .. tostring(rigid(self[i+1]))
i = i + 1
@@ -1275,4 +1274,4 @@ end
-- Done
-return Path
+return Path \ No newline at end of file
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Path_arced.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Path_arced.lua
index 1875b8d1a50..92dd8ad87ac 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Path_arced.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Path_arced.lua
@@ -61,7 +61,7 @@ local function cos_quarter(x)
end
local function atan2deg(y,x)
-
+
-- Works like atan2, but returns the angle in degrees and, returns
-- exactly a multiple of 90 if x or y are zero
@@ -80,14 +80,14 @@ local function atan2deg(y,x)
else
return atan2(y,x) * to_deg
end
-
+
end
local function subarc (path, startx, starty, start_angle, delta, radius, trans, center_x, center_y)
-
+
local end_angle = start_angle + delta
local factor = tan (delta*to_rad/4) * 1.333333333333333333333 * radius
-
+
local s1, c1, s190, c190, s2, c2, s290, c290
if start_angle % 90 == 0 then
@@ -103,7 +103,7 @@ local function subarc (path, startx, starty, start_angle, delta, radius, trans,
local a2 = end_angle * to_rad
s2, c2, s290, c290 = sin(a2), cos(a2), sin(a2-pi_half), cos(a2-pi_half)
end
-
+
local lastx, lasty = center_x + c2*radius, center_y + s2*radius
path[#path + 1] = "curveto"
@@ -116,14 +116,14 @@ local function subarc (path, startx, starty, start_angle, delta, radius, trans,
path[#path-1]:apply(trans)
path[#path ]:apply(trans)
end
-
+
return lastx, lasty, end_angle
end
local function arc (path, start, start_angle, end_angle, radius, trans, centerx, centery)
-
+
-- @param path is the path object
-- @param start is the start coordinate
-- @param start_angle is given in degrees
@@ -132,65 +132,65 @@ local function arc (path, start, start_angle, end_angle, radius, trans, centerx,
-- @param trans is an optional transformation matrix that gets applied to all computed points
-- @param centerx optionally: x-part of the center of the circle
-- @param centery optionally: y-part of the center of the circle
-
+
local startx, starty = start.x, start.y
-
+
-- Compute center:
centerx = centerx or startx - cos(start_angle*to_rad)*radius
centery = centery or starty - sin(start_angle*to_rad)*radius
-
+
if start_angle < end_angle then
-- First, ensure that the angles are in a reasonable range:
start_angle = start_angle % 360
end_angle = end_angle % 360
-
+
if end_angle <= start_angle then
- -- In case the modulo has inadvertently moved the end angle
+ -- In case the modulo has inadvertedly moved the end angle
-- before the start angle:
end_angle = end_angle + 360
end
-
+
-- Ok, now create a series of arcs that are at most quarter-cycles:
while start_angle < end_angle do
if start_angle + 179 < end_angle then
- -- Add a quarter cycle:
- startx, starty, start_angle = subarc(path, startx, starty, start_angle, 90, radius, trans, centerx, centery)
+ -- Add a quarter cycle:
+ startx, starty, start_angle = subarc(path, startx, starty, start_angle, 90, radius, trans, centerx, centery)
elseif start_angle + 90 < end_angle then
- -- Add 60 degrees to ensure that there are no small segments
- -- at the end
- startx, starty, start_angle = subarc(path, startx, starty, start_angle, (end_angle-start_angle)/2, radius, trans, centerx, centery)
+ -- Add 60 degrees to ensure that there are no small segments
+ -- at the end
+ startx, starty, start_angle = subarc(path, startx, starty, start_angle, (end_angle-start_angle)/2, radius, trans, centerx, centery)
else
- subarc(path, startx, starty, start_angle, end_angle - start_angle, radius, trans, centerx, centery)
- break
+ subarc(path, startx, starty, start_angle, end_angle - start_angle, radius, trans, centerx, centery)
+ break
end
end
-
+
elseif start_angle > end_angle then
-- First, ensure that the angles are in a reasonable range:
start_angle = start_angle % 360
end_angle = end_angle % 360
-
+
if end_angle >= start_angle then
-- In case the modulo has inadvertedly moved the end angle
-- before the start angle:
end_angle = end_angle - 360
end
-
+
-- Ok, now create a series of arcs that are at most quarter-cycles:
while start_angle > end_angle do
if start_angle - 179 > end_angle then
- -- Add a quarter cycle:
- startx, starty, start_angle = subarc(path, startx, starty, start_angle, -90, radius, trans, centerx, centery)
+ -- Add a quarter cycle:
+ startx, starty, start_angle = subarc(path, startx, starty, start_angle, -90, radius, trans, centerx, centery)
elseif start_angle - 90 > end_angle then
- -- Add 60 degrees to ensure that there are no small segments
- -- at the end
- startx, starty, start_angle = subarc(path, startx, starty, start_angle, (end_angle-start_angle)/2, radius, trans, centerx, centery)
+ -- Add 60 degrees to ensure that there are no small segments
+ -- at the end
+ startx, starty, start_angle = subarc(path, startx, starty, start_angle, (end_angle-start_angle)/2, radius, trans, centerx, centery)
else
- subarc(path, startx, starty, start_angle, end_angle - start_angle, radius, trans, centerx, centery)
- break
+ subarc(path, startx, starty, start_angle, end_angle - start_angle, radius, trans, centerx, centery)
+ break
end
end
-
+
-- else, do nothing
end
end
@@ -199,10 +199,10 @@ end
-- Doc see Path.lua
function Path:appendArc(start_angle,end_angle,radius, trans)
-
+
local start = rigid(self[#self])
assert(type(start) == "table", "trying to append an arc to a path that does not end with a coordinate")
-
+
if trans then
start = start:clone()
start:apply(Transform.invert(trans))
@@ -223,13 +223,13 @@ function Path:appendArcTo (target, radius_or_center, clockwise, trans)
local trans_target = target
local centerx, centery, radius
-
+
if type(radius_or_center) == "number" then
radius = radius_or_center
else
centerx, centery = radius_or_center.x, radius_or_center.y
end
-
+
if trans then
start = start:clone()
trans_target = target:clone()
@@ -242,56 +242,56 @@ function Path:appendArcTo (target, radius_or_center, clockwise, trans)
centerx, centery = t.x, t.y
end
end
-
+
if not centerx then
-- Compute center
local dx, dy = target.x - start.x, target.y - start.y
if abs(dx) == abs(dy) and abs(dx) == radius then
if (dx < 0 and dy < 0) or (dx > 0 and dy > 0) then
- centerx = start.x
- centery = trans_target.y
+ centerx = start.x
+ centery = trans_target.y
else
- centerx = trans_target.x
- centery = start.y
+ centerx = trans_target.x
+ centery = start.y
end
else
local l_sq = dx*dx + dy*dy
if l_sq >= radius*radius*4*0.999999 then
- centerx = (start.x+trans_target.x) / 2
- centery = (start.y+trans_target.y) / 2
- assert(l_sq <= radius*radius*4/0.999999, "radius too small for arc")
+ centerx = (start.x+trans_target.x) / 2
+ centery = (start.y+trans_target.y) / 2
+ assert(l_sq <= radius*radius*4/0.999999, "radius too small for arc")
else
-- Normalize
- local l = sqrt(l_sq)
- local nx = dx / l
- local ny = dy / l
-
- local e = sqrt(radius*radius - 0.25*l_sq)
-
- centerx = start.x + 0.5*dx - ny*e
- centery = start.y + 0.5*dy + nx*e
+ local l = sqrt(l_sq)
+ local nx = dx / l
+ local ny = dy / l
+
+ local e = sqrt(radius*radius - 0.25*l_sq)
+
+ centerx = start.x + 0.5*dx - ny*e
+ centery = start.y + 0.5*dy + nx*e
end
end
end
-
+
local start_dx, start_dy, target_dx, target_dy =
start.x - centerx, start.y - centery,
trans_target.x - centerx, trans_target.y - centery
-
+
if not radius then
-- Center is given, compute radius:
radius_sq = start_dx^2 + start_dy^2
-- Ensure that the circle is, indeed, centered:
assert (abs(target_dx^2 + target_dy^2 - radius_sq)/radius_sq < 1e-5, "attempting to add an arc with incorrect center")
-
+
radius = sqrt(radius_sq)
end
-- Compute start and end angle:
- local start_angle = atan2deg(start_dy, start_dx)
- local end_angle = atan2deg(target_dy, target_dx)
+ local start_angle = atan2deg(start_dy, start_dx)
+ local end_angle = atan2deg(target_dy, target_dx)
if clockwise then
if end_angle > start_angle then
@@ -302,7 +302,7 @@ function Path:appendArcTo (target, radius_or_center, clockwise, trans)
end_angle = end_angle + 360
end
end
-
+
arc (self, start, start_angle, end_angle, radius, trans, centerx, centery)
-- Patch last point to avoid rounding problems:
@@ -313,4 +313,4 @@ end
-- Done
-return true
+return true \ No newline at end of file
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Vertex.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Vertex.lua
index 677ea4fbd06..c287181992f 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Vertex.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Vertex.lua
@@ -39,12 +39,12 @@
-- path lives in a special ``local'' coordinate system, that is, all
-- coordinates of this path should actually be considered relative to
-- the vertex' |pos| field. Note that the path is typically, but not
--- always, ``centered'' on the origin. A graph drawing algorithm
+-- alwyas, ``centered'' on the origin. A graph drawing algorithm
-- should arrange the vertices in such a way that the origins in the
-- path coordinate systems are aligned.
--
-- To illustrate the difference between the origin and the vertex
--- center, consider a tree drawing algorithm in which a node |root| has
+-- center, conside a tree drawing algorithm in which a node |root| has
-- three children |a|, |b|, and |g|. Now, if we were to simply center
-- these three letters vertically and arrange them in a line, the
-- letters would appear to ``jump up and down'' since the height of
@@ -100,7 +100,7 @@
-- |options|, which must be a table of the same syntax as the
-- |options| field. For the |entries| array, each element must be
-- table with two field: |t| must be set to a number, representing a
--- time in seconds, and |value|, which must be set to a value that
+-- time in secondds, and |value|, which must be set to a value that
-- the |attribute| should have at the given time. The entries and the
-- options will then be interpreted as described in \pgfname's basic
-- layer animation system, except that where a |\pgfpoint| is expected
@@ -207,29 +207,29 @@ local anchor_cache = Storage.new ()
local directions = {
north = function(min_x, min_y, max_x, max_y)
- return (min_x+max_x)/2, max_y
- end,
+ return (min_x+max_x)/2, max_y
+ end,
south = function(min_x, min_y, max_x, max_y)
- return (min_x+max_x)/2, min_y
- end,
+ return (min_x+max_x)/2, min_y
+ end,
east = function(min_x, min_y, max_x, max_y)
- return max_x, (min_y+max_y)/2
- end,
+ return max_x, (min_y+max_y)/2
+ end,
west = function(min_x, min_y, max_x, max_y)
- return min_x, (min_y+max_y)/2
- end,
+ return min_x, (min_y+max_y)/2
+ end,
["north west"] = function(min_x, min_y, max_x, max_y)
- return min_x, max_y
- end,
+ return min_x, max_y
+ end,
["north east"] = function(min_x, min_y, max_x, max_y)
- return max_x, max_y
- end,
+ return max_x, max_y
+ end,
["south west"] = function(min_x, min_y, max_x, max_y)
- return min_x, min_y
- end,
+ return min_x, min_y
+ end,
["south east"] = function(min_x, min_y, max_x, max_y)
- return max_x, min_y
- end,
+ return max_x, min_y
+ end,
}
---
@@ -260,10 +260,10 @@ function Vertex:anchor(anchor)
else
local n = tonumber(anchor)
if n then
- local x1, y1, x2, y2 = self:boundingBox()
- local r = math.max(x2-x1, y2-y1)
- b = Coordinate.new(r*math.cos(n/180*math.pi),r*math.sin(n/180*math.pi))
- b:shiftByCoordinate(self.anchors.center)
+ local x1, y1, x2, y2 = self:boundingBox()
+ local r = math.max(x2-x1, y2-y1)
+ b = Coordinate.new(r*math.cos(n/180*math.pi),r*math.sin(n/180*math.pi))
+ b:shiftByCoordinate(self.anchors.center)
end
end
if not b then