diff options
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model')
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 |