diff options
author | Norbert Preining <norbert@preining.info> | 2023-01-16 03:03:27 +0000 |
---|---|---|
committer | Norbert Preining <norbert@preining.info> | 2023-01-16 03:03:27 +0000 |
commit | 6f9e1680085e7bb4d258f6f8116369d122e196e1 (patch) | |
tree | 9ac0ecb239240d1d672b188f29c1479de215074b /graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model | |
parent | b8345f39630408bb198e7636381ce4240154ca9b (diff) |
CTAN sync 202301160303
Diffstat (limited to 'graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model')
10 files changed, 4186 insertions, 0 deletions
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Arc.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Arc.lua new file mode 100644 index 0000000000..e007e9b59b --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Arc.lua @@ -0,0 +1,653 @@ +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header$ + + +--- +-- 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. +-- +-- 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. +-- +-- 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. +-- +-- Between any two vertices of a graph there can be only one arc, so +-- all digraphs are always simple graphs. However, in the +-- specification of a graph (the syntactic digraph), there might +-- 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. +-- +-- 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 +-- the |declare_parameter_sequence| function for the syntax. Similar +-- to the |path| field below, the options set in this table are +-- written back to the syntactic edges during a sync. +-- +-- Finally, there is also an |animations| field, which, similarly to +-- the |generated_options|, gets written back during a sync when it is +-- not |nil|. +-- +-- In detail, the following happens: Even though an arc has a |path|, +-- |generated_options|, and |animations| fields, setting these fields does +-- not immediately set the paths of the syntactic edges nor does it +-- generate options. Indeed, you will normally want to setup and +-- modify the |path| field of an arc during your algorithm and only at +-- the very end, ``write it back'' to the multiple syntactic edges +-- underlying the graph. For this purpose, the method |sync| is used, +-- which is called automatically for the |ugraph| and |digraph| of a +-- scope as well as for spanning trees. +-- +-- The bottom line concerning the |path| field is the following: If +-- you just want a straight line along an arc, just leave the field as +-- it is (namely, |nil|). If you want to have all edges along a path +-- to follow a certain path, set the |path| field of the arc to the +-- path you desire (typically, using the |setPolylinePath| or a +-- similar method). This will cause all syntactic edges underlying the +-- arc to be set to the specified path. In the event that you want to +-- set different paths for the edges underlying a single arc +-- differently, set the |path| fields of these edges and set the +-- |path| field of the arc to |nil|. This will disable the syncing for +-- the arc and will cause the edge |paths| to remain untouched. +-- +-- @field tail The tail vertex of the arc. +-- @field head The head vertex of the arc. May be the same as the tail +-- in case of a loop. +-- @field path If non-nil, the path of the arc. See the description +-- above. +-- @field generated_options If non-nil, some options to be passed back +-- to the original syntactic edges, see the description above. +-- @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 +-- 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|. +-- +local Arc = {} +Arc.__index = Arc + + +-- Namespace + +require("pgf.gd.model").Arc = Arc + + +-- Imports + +local Path = require 'pgf.gd.model.Path' +local lib = require 'pgf.gd.lib' + + +--- +-- Get an array of options of the syntactic edges corresponding to an arc. +-- +-- An arc in a digraph is typically (but not always) present because +-- there are one or more edges in the syntactic digraph between the +-- tail and the head of the arc or between the head and the tail. +-- +-- Since for every arc there can be several edges present in the +-- syntactic digraph, an option like |length| may have +-- been given multiple times for the edges corresponding to the arc. +-- +-- 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. +-- +-- @param option A string option like |"length"|. +-- +-- @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: +-- % +--\begin{codeexample}[code only] +--graph { +-- tail -- [length=1] head, % multi edge 1 +-- tail -- [length=3] head, % mulit edge 2 +-- head -- [length=8] tail, % multi edge 3 +-- tail -- head, % multi edge 4 +-- head -- [length=7] tail, % multi edge 5 +-- 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: +-- % +--\begin{codeexample}[code only, tikz syntax=false] +--local a = g:arc(tail.head) -- some arc +--local opt = a:optionsArray('length') +--local sum = 0 +--for i=1,#opt.aligned do +-- 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} +-- +function Arc:optionsArray(option) + + local cache = self.option_cache + local t = cache[option] + if t then + return t + end + + -- Accumulate the edges for which the option is set: + local tail = self.tail + local head = self.head + local s_graph = self.syntactic_digraph + + local arc = s_graph:arc(tail, head) + local aligned = {} + if arc then + for _,m in ipairs(arc.syntactic_edges) do + if m.options[option] ~= nil then + 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 + 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 + t[i] = aligned[i].options[option] + end + for i=1,#anti_aligned do + t[#t+1] = anti_aligned[i].options[option] + end + cache[option] = t + + return t +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. +-- +-- @param option An option +-- @param only_aligned If true, only aligned syntactic edges will be +-- considered. +-- @return The first entry of the |optionsArray| +function Arc:options(option, only_aligned) + if only_aligned then + local opt = self:optionsArray(option) + if #opt.aligned > 0 then + return opt[1] + end + else + return self:optionsArray(option)[1] + end +end + + + + +--- +-- Get an accumulated value of an option of the syntactic edges +-- corresponding to an arc. +-- +-- @param option The option of interest +-- @param accumulator A function taking two values. When there are +-- more than one syntactic edges corresponding to |self| for which the +-- |option| is set, this function will be called repeatedly for the +-- different values. The first time it will be called for the first +-- two values. Next, it will be called for the result of this call and +-- the third value, and so on. +-- @param only_aligned A boolean. If true, only the aligned syntactic +-- 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 +-- edge, the value of this edge is returned. Otherwise, the result of +-- repeatedly applying the |accumulator| function as described +-- above. +-- +-- The result is cached, repeated calls will not invoke the +-- |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} +-- +function Arc:optionsAccumulated(option, accumulator, only_aligned) + local opt = self:options(option) + if only_aligned then + local aligned = opt.aligned + local v = aligned[accumulator] + if v == nil then + v = opt[1] + for i=2,#aligned do + v = accumulator(v, opt[i]) + end + align[accumulator] = v + end + return v + else + local v = opt[accumulator] + if v == nil then + v = opt[1] + for i=2,#opt do + v = accumulator(v, opt[i]) + end + opt[accumulator] = v + end + return v + end +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 +-- 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, +-- |nil| is returned. +-- +-- @return The syntactic tail +-- @return The syntactic head + +function Arc:syntacticTailAndHead () + local s_graph = self.syntactic_digraph + local tail = self.tail + local head = self.head + if s_graph:arc(tail, head) then + return tail, head + elseif s_graph:arc(head, tail) then + return head, tail + end +end + + +--- +-- Compute the point cloud. +-- +-- @return This method will return the ``point cloud'' of an arc, +-- which is an array of all points that must be rotated and shifted +-- along with the endpoints of an edge. +-- +function Arc:pointCloud () + if self.cached_point_cloud then + return self.cached_point_cloud -- cached + end + local cloud = {} + local a = self.syntactic_digraph:arc(self.tail,self.head) + 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 + end + end + end + self.cached_point_cloud = cloud + return cloud +end + + + +--- +-- Compute an event index for the arc. +-- +-- @return The lowest event index of any edge involved +-- in the arc (or nil, if there is no syntactic edge). +-- +function Arc:eventIndex () + if self.cached_event_index then + return self.cached_event_index + end + local head = self.head + local tail = self.tail + local e = math.huge + local a = self.syntactic_digraph:arc(tail,head) + if a then + for _,m in ipairs(a.syntactic_edges) do + e = math.min(e, m.event.index) + end + end + local a = head ~= tail and self.syntactic_digraph:arc(head,tail) + if a then + for _,m in ipairs(a.syntactic_edges) do + e = math.min(e, m.event.index) + end + end + self.cached_event_index = e + return e +end + + + + +--- +-- The span collector +-- +-- This method returns the top (that is, smallest) priority of any +-- 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. +-- \end{enumerate} +-- +-- @return The priority of the arc, as described above. +-- +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 + local g = self.syntactic_digraph + + local a = g:arc(tail,head) + 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) + + min = math.min(p or 5, min or math.huge) + end + end + + local a = head ~= tail and g:arc(head,tail) + 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) + + min = math.min(p or 5, min or math.huge) + end + end + + self.cached_span_priority = min or 5 + + return min or 5 +end + + + + + + +--- +-- Sync an |Arc| with its syntactic edges with respect to the path and +-- generated options. It causes the following to happen: +-- If the |path| field of the arc is |nil|, nothing +-- happens with respect to the path. Otherwise, a copy of the |path| +-- is created. However, for every path element that is a function, +-- this function is invoked with the syntactic edge as its +-- parameter. The result of this call should now be a |Coordinate|, +-- 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) +--arc:setPolylinePath { Coordinate.new(x,y), Coordinate.new(x1,y1) } +--... +--arc:sync() +--\end{codeexample} +-- +-- Next, similar to the path, the field |generated_options| is +-- considered. If it is not |nil|, then all options listed in this +-- field are appended to all syntactic edges underlying the arc. +-- +-- Note that this function will automatically be called for all arcs +-- of the |ugraph|, the |digraph|, and the |spanning_tree| of an +-- algorithm by the rendering pipeline. +-- +function Arc:sync() + if self.path then + local path = self.path + local head = self.head + local tail = self.tail + 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 + 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 + end + end + if self.generated_options then + local head = self.head + local tail = self.tail + 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 + 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 + end + end + end + if self.animations then + local head = self.head + local tail = self.tail + 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 + 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 + end + end + end +end + + +--- +-- This method returns a ``coordinate factory'' that can be used as +-- the coordinate of a |moveto| at the beginning of a path starting at +-- the |tail| of the arc. Suppose you want to create a path starting +-- at the tail vertex, going to the coordinate $(10,10)$ and ending at +-- the head vertex. The trouble is that when you create the path +-- corresponding to this route, you typically do not know where the +-- tail vertex is going to be. Even if that \emph{has} already been +-- settled, you will still have the problem that different edges +-- underlying the arc may wish to start their paths at different +-- anchors inside the tail vertex. In such cases, you use this +-- 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: +-- % +--\begin{codeexample}[code only, tikz syntax=false] +--local a = g:connect(tail,head) +--... +--arc.path = Path.new() +--arc.path:appendMoveto(arc:tailAnchorForArcPath()) +--arc.path:appendLineto(10, 10) +--arc.path:appendLineto(arc:headAnchorForArcPath()) +--\end{codeexample} +-- +-- 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 +end + +--- +-- See |Arc:tailAnchorForArcPath|. + +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 +end + + + +--- +-- Setup the |path| field of an arc in such a way that it corresponds +-- to a sequence of straight line segments starting at the tail's +-- anchor and ending at the head's anchor. +-- +-- @param coordinates An array of |Coordinates| through which the line +-- will go through. + +function Arc:setPolylinePath(coordinates) + local p = Path.new () + + p:appendMoveto(self:tailAnchorForArcPath()) + + for _,c in ipairs(coordinates) do + p:appendLineto(c) + end + + p:appendLineto(self:headAnchorForArcPath()) + + self.path = p +end + + + + +-- Returns a string representation of an arc. This is mainly for debugging +-- +-- @return The Arc as string. +-- +function Arc:__tostring() + return tostring(self.tail) .. "->" .. tostring(self.head) +end + + +-- Done + +return Arc diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Collection.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Collection.lua new file mode 100644 index 0000000000..abc454b7db --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Collection.lua @@ -0,0 +1,208 @@ +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header$ + + +--- +-- A collection is essentially a subgraph of a graph, that is, a +-- ``collection'' of some nodes and some edges of the graph. The name +-- ``collection'' was chosen over ``subgraph'' since the latter are +-- often thought of as parts of a graph that are rendered in a special +-- way (such as being surrounded by a rectangle), while collections +-- are used to model such diverse things as hyperedges, sets of +-- 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 +-- 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. +-- +-- Collections serve two purposes: First, they can be seen as ``hints'' +-- to graph drawing algorithms that certain nodes and/or edges ``belong +-- together''. For instance, collections of kind |same layer| are used +-- by the Sugiyama algorithm to group together nodes that should appear +-- at the same height of the output. Second, since collections are also +-- passed back to the display layer in a postprocessing step, they can be +-- used to render complicated concepts such as hyperedges (which are +-- just collections of nodes, after all) or subgraphs. +-- +-- @field kind The ``kind'' of the collection. +-- +-- @field vertices A lookup table of vertices (that is, both an array +-- with the vertices in the order in which they appear as well as a +-- table such that |vertices[vertex] == true| whenever |vertex| is +-- present in the table. +-- +-- @field edges A lookup table of edges (not arcs!). +-- +-- @field options An options table. This is the table of options that +-- 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, +-- 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. +-- +-- @field event An |Event| object that was create for this +-- collection. Its |kind| will be |"collection"| while its |parameter| +-- will be the collection kind. + +local Collection = {} +Collection.__index = Collection + + +-- Namespace + +require("pgf.gd.model").Collection = Collection + + +-- Imports +local Storage = require "pgf.gd.lib.Storage" + + + +--- +-- Creates a new collection. You should not call this function +-- directly, it is called by the interface classes. +-- +-- @param t A table of initial values. The field |t.kind| must be a +-- nonempty string. +-- +-- @return The new collection +-- +function Collection.new(t) + assert (type(t.kind) == "string" and t.kind ~= "", "collection kind not set") + + return setmetatable( + { + vertices = t.vertices or {}, + edges = t.edges or {}, + options = t.options or {}, + generated_options = t.generated_options or {}, + kind = t.kind, + event = t.event, + child_collections = t.child_collections or {}, + }, Collection) +end + + + + +-- +-- An internal function for registering a collection as child of +-- another collection. The collection |self| will be made a child +-- collection of |parent|. +-- +-- @param parent A collection. + +function Collection:registerAsChildOf(parent) + self.parent = parent + if parent then + assert (getmetatable(parent) == Collection, "parent must be a collection") + parent.child_collections[#parent.child_collections+1] = self + end +end + + + +--- +-- A collection can have any number of \emph{child collections}, which +-- are collections nested inside the collection. You can access the +-- array of these children through this method. You may not modify +-- the array returned by this function. +-- +-- @return The array of children of |self|. +-- +function Collection:children() + return self.child_collections +end + + +--- +-- This method works like the |children| method. However, the tree of +-- collections is, conceptually, contracted by considering only these +-- collections that have the |kind| given as parameter. For instance, +-- if |self| has a child collection of a kind different from |kind|, +-- but this child collection has, in turn, a child collection of kind +-- |kind|, this latter child collection will be included in the array +-- -- but not any of its child collections. +-- +-- @param kind The collection kind to which the tree of collections +-- should be restricted. +-- +-- @return The array of children of |self| in this contracted tree. +-- +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 + else + rec (d, a) + end + end + return a + end + return rec(self, {}) +end + + +--- +-- The descendants of a collection are its children, plus their +-- children, plus their children, and so on. +-- +-- @return An array of all descendants of |self|. It will be in +-- preorder. + +function Collection:descendants() + local function rec (c, a) + for _,d in ipairs(c.child_collections) do + a[#a + 1] = d + rec (d, a) + end + return a + end + return rec(self, {}) +end + + + +--- +-- The descendants of a collection of the given |kind|. +-- +-- @param kind A collection 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 + end + rec (d, a) + end + return a + end + return rec(self, {}) +end + + + +-- Done + +return Collection diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Coordinate.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Coordinate.lua new file mode 100644 index 0000000000..3a4448ab08 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Coordinate.lua @@ -0,0 +1,306 @@ +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @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 y +-- +-- There is also a static field called |origin| that is always equal to the origin. + +local Coordinate = {} +Coordinate.__index = Coordinate + + +-- Namespace + +require("pgf.gd.model").Coordinate = Coordinate + + + + +--- Creates a new coordinate. +-- +-- @param x The $x$ value +-- @param y The $y$ value +-- +-- @return A coordinate +-- +function Coordinate.new(x,y) + return setmetatable( {x=x, y=y}, Coordinate) +end + + +Coordinate.origin = Coordinate.new(0,0) + + +--- Creates a new coordinate that is a copy of an existing one. +-- +-- @return A new coordinate at the same location as |self| +-- +function Coordinate:clone() + return setmetatable( { x = self.x, y = self.y }, Coordinate) +end + + + +--- Apply a transformation matrix to a coordinate, +-- see |pgf.gd.lib.Transform| for details. +-- +-- @param t A transformation. + +function Coordinate:apply(t) + local x = self.x + local y = self.y + self.x = t[1]*x + t[2]*y + t[5] + self.y = t[3]*x + t[4]*y + t[6] +end + + +--- Shift a coordinate +-- +-- @param a An $x$ offset +-- @param b A $y$ offset + +function Coordinate:shift(a,b) + self.x = self.x + a + self.y = self.y + b +end + + +--- +-- ``Unshift'' a coordinate (which is the same as shifting by the +-- inversed coordinate; only faster). +-- +-- @param a An $x$ offset +-- @param b A $y$ offset + +function Coordinate:unshift(a,b) + self.x = self.x - a + self.y = self.y - b +end + + +--- +-- Like |shift|, only for coordinate parameters. +-- +-- @param c Another coordinate. The $x$- and $y$-values of |self| are +-- increased by the $x$- and $y$-values of this coordinate. + +function Coordinate:shiftByCoordinate(c) + self.x = self.x + c.x + self.y = self.y + c.y +end + + +--- +-- Like |unshift|, only for coordinate parameters. +-- +-- @param c Another coordinate. + +function Coordinate:unshiftByCoordinate(c) + self.x = self.x - c.x + self.y = self.y - c.y +end + + +--- +-- Moves the coordinate a fraction of |f| along a straight line to |c|. +-- +-- @param c Another coordinate +-- @param f A fraction + +function Coordinate:moveTowards(c,f) + self.x = self.x + f*(c.x-self.x) + self.y = self.y + f*(c.y-self.y) +end + + + +--- Scale a coordinate by a factor +-- +-- @param s A factor. + +function Coordinate:scale(s) + self.x = s*self.x + self.y = s*self.y +end + + + + +--- +-- Add two coordinates, yielding a new coordinate. Note that it will +-- be a lot faster to call shift, whenever this is possible. +-- +-- @param a A coordinate +-- @param b A coordinate + +function Coordinate.__add(a,b) + return setmetatable({ x = a.x + b.x, y = a.y + b.y }, Coordinate) +end + + +--- +-- Subtract two coordinates, yielding a new coordinate. Note that it will +-- be a lot faster to call unshift, whenever this is possible. +-- +-- @param a A coordinate +-- @param b A coordinate + +function Coordinate.__sub(a,b) + return setmetatable({ x = a.x - b.x, y = a.y - b.y }, Coordinate) +end + + +--- +-- The unary minus (mirror the coordinate against the origin). +-- +-- @param a A coordinate + +function Coordinate.__unm(a) + return setmetatable({ x = - a.x, y = - a.y }, Coordinate) +end + + +--- +-- The multiplication operator. Its effect depends on the parameters: +-- If both are coordinates, their dot-product is returned. If exactly +-- one of them is a coordinate and the other is a number, the scalar +-- multiple of this coordinate is returned. +-- +-- @param a A coordinate or a scalar +-- @param b A coordinate or a scalar +-- @return The dot product or scalar product. + +function Coordinate.__mul(a,b) + if getmetatable(a) == Coordinate then + if getmetatable(b) == Coordinate then + return a.x * b.x + a.y * b.y + else + return setmetatable({ x = a.x * b, y = a.y *b }, Coordinate) + end + else + return setmetatable({ x = a * b.x, y = a * b.y }, Coordinate) + end +end + +--- +-- The division operator. Returns the scalar division of a coordinate +-- by a scalar. +-- +-- @param a A coordinate +-- @param b A scalar (not equal to zero). +-- @return The scalar product or a * (1/b). + +function Coordinate.__div(a,b) + return setmetatable({ x = a.x / b, y = a.y / b }, Coordinate) +end + + +--- +-- The norm function. Returns the norm of a coordinate. +-- +-- @param a A coordinate +-- @return The norm of the coordinate + +function Coordinate:norm() + return math.sqrt(self.x * self.x + self.y * self.y) +end + + +--- +-- Normalize a vector: Ensure that it has length 1. If the vector used +-- to be the 0-vector, it gets replaced by (1,0). +-- + +function Coordinate:normalize() + local x, y = self.x, self.y + if x == 0 and y == 0 then + self.x = 1 + else + local norm = math.sqrt(x*x+y*y) + self.x = x / norm + self.y = y / norm + end +end + + +--- +-- Normalized version of a vector: Like |normalize|, only the result is +-- returned in a new vector. +-- +-- @return Normalized version of |self| + +function Coordinate:normalized() + local x, y = self.x, self.y + if x == 0 and y == 0 then + return setmetatable({ x = 1, y = 0 }, Coordinate) + else + local norm = math.sqrt(x*x+y*y) + return setmetatable({ x = x/norm, y = y/norm }, Coordinate) + end +end + + + +--- +-- Compute a bounding box around an array of coordinates +-- +-- @param array An array of coordinates +-- +-- @return |min_x| The minimum $x$ value of the bounding box of the array +-- @return |min_y| The minimum $y$ value +-- @return |max_x| +-- @return |max_y| +-- @return |center_x| The center of the bounding box +-- @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 + 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 + + return min_x, min_y, max_x, max_y, (min_x+max_x) / 2, (min_y+max_y) / 2 + end +end + + + + +-- Returns a string representation of an arc. This is mainly for debugging +-- +-- @return The Arc as string. +-- +function Coordinate:__tostring() + return "(" .. self.x .. "pt," .. self.y .. "pt)" +end + + +-- Done + +return Coordinate
\ No newline at end of file diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Digraph.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Digraph.lua new file mode 100644 index 0000000000..30b600e308 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Digraph.lua @@ -0,0 +1,849 @@ +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header$ + + + + +--- +-- 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, +-- 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 +-- ``end'' (the head). The class modeling ``nodes'' is actually called +-- |Vertex|, just to stress that this is not a direct model of a +-- \tikzname\ |node|, but can represent a arbitrary vertex of a graph, +-- independently of whether it is an actual |node| in \tikzname. +-- +-- \medskip +-- \noindent\emph{Time Bounds.} +-- 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. +-- \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 +-- number of arcs between the to-be-deleted nodes and the remaining +-- nodes. Note that this time bound in independent of~$k$. In +-- particular, it will be much faster to delete many vertices by once +-- calling the |remove| function instead of calling it repeatedly. +-- \item Deleting an arc takes time $O(t_o+h_i)$ where $t_o$ is the +-- 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 +-- 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 +-- \emph{stable} in the following sense: The ordering of the elements +-- 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. +-- +-- @field vertices This array contains the vertices that are part of +-- the digraph. Internally, this array +-- is an object of type |LookupTable|, but you can mostly treat it as +-- if it were an array. In particular, you can iterate over its +-- elements using |ipairs|, but you may not modify the array; use the +-- |add| and |remove| methods, instead. +-- +-- \begin{codeexample}[code only, tikz syntax=false] +-- local g = Digraph.new {} +-- +-- g:add { v1, v2 } -- Add vertices v1 and v2 +-- g:remove { v2 } -- Get rid of v2. +-- +-- assert (g:contains(v1)) +-- assert (not g:contains(v2)) +-- \end{codeexample} +-- +-- It is important to note that although each digraph stores a +-- |vertices| array, the elements in this array are not exclusive to +-- the digraph: A vertex can be an element of any number of +-- digraphs. Whether or not a vertex is an element of digraph is not +-- stored in the vertex, only in the |vertices| array of the +-- digraph. To test whether a digraph contains a specific node, use the +-- |contains| method, which takes time $O(1)$ to perform the test (this +-- is because, as mentioned earlier, the |vertices| array is actually a +-- |LookupTable| and for each vertex |v| the field |vertices[v]| will +-- be true if, and only if, |v| is an element of the |vertices| array). +-- +-- Do not use |pairs(g.vertices)| because this may cause your graph +-- drawing algorithm to produce different outputs on different runs. +-- +-- A slightly annoying effect of vertices being able to belong to +-- several graphs at the same time is that the set of arcs incident to +-- a vertex is not a property of the vertex, but rather of the +-- graph. In other words, to get a list of all arcs whose tail is a +-- 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. +-- 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: +-- % +--\begin{codeexample}[code only, tikz syntax=false] +--for _,v in ipairs(g.vertices) do +-- for _,a in ipairs(g:outgoing(v)) do +-- ... +-- end +--end +--\end{codeexample} +-- +-- 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 +-- ... +--end +--\end{codeexample} +-- +-- @field arcs For any two vertices |t| and |h| of a graph, there may +-- 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 +-- pair of vertices. However, you can store any information you like for +-- 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. +-- +-- 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 +-- time. For this reason, while for vertices it makes sense to create +-- |Vertex| objects independently of any |Digraph| objects, it is not +-- possible to instantiate an |Arc| directly: only the |Digraph| method +-- |connect| is allowed to create new |Arc| objects and it will return +-- any existing arcs instead of creating new ones, if there is already +-- an arc present between two nodes. +-- +-- The |arcs| field of a digraph contains a |LookupTable| of all arc +-- objects present in the |Digraph|. Although you can access this field +-- normally and use it in |ipairs| to iterate over all arcs of a graph, +-- note that this array is actually ``reconstructed lazily'' whenever +-- an arc is deleted from the graph. What happens is the following: As +-- long as you just add arcs to a graph, the |arcs| array gets updated +-- normally. However, when you remove an arc from a graph, the arc does +-- not get removed from the |arcs| array (which would be an expensive +-- operation). Instead, the |arcs| array is invalidated (internally set +-- to |nil|), allowing us to perform a |disconnect| in time +-- $O(1)$. The |arcs| array is then ignored until the next time it is +-- accessed, for instance when a user says |ipairs(g.arcs)|. At this +-- 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 +-- 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| +-- field between calls. +-- +-- @field syntactic_digraph is a reference to the syntactic digraph +-- from which this graph stems ultimately. This may be a cyclic +-- reference to the graph itself. +-- @field options If present, it will be a table storing +-- the options set for the syntactic digraph. +-- +local Digraph = {} + +local function recalc_arcs (digraph) + local arcs = {} + local vertices = digraph.vertices + for i=1,#vertices do + local out = vertices[i].outgoings[digraph] + for j=1,#out do + arcs[#arcs + 1] = out[j] + end + end + digraph.arcs = arcs + return arcs +end + +Digraph.__index = + function (t, k) + if k == "arcs" then + return recalc_arcs(t) + else + return rawget(Digraph,k) + end + end + + + +-- Namespace +require("pgf.gd.model").Digraph = Digraph + +-- Imports +local Arc = require "pgf.gd.model.Arc" +local LookupTable = require "pgf.gd.lib.LookupTable" +local Vertex = require "pgf.gd.model.Vertex" + + + + + +--- +-- Graphs are created using the |new| method, which takes a table of +-- |initial| values as input (like most |new| methods in the graph +-- drawing system). It is permissible that this table of initial values +-- has a |vertices| field, in which case this array will be copied. In +-- contrast, an |arcs| field in the table will be ignored -- newly +-- 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 } +--g:connect (v1, v2) +-- +--local h = Digraph.new (g) +--assert (h:contains(v1)) +--assert (not h:arc(v1, v2)) +--\end{codeexample} +-- +-- To completely copy a graph, including all arcs, you have to write: +--\begin{codeexample}[code only, tikz syntax=false] +--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)$. +-- +-- @param initial A table of initial values. It is permissible that +-- this array contains a |vertices| field. In this +-- case, this field must be an array and its entries +-- must be nodes, which will be inserted. If initial +-- has an |arcs| field, this field will be ignored. +-- The table must contain a field |syntactic_digraph|, +-- which should normally be the syntactic digraph of +-- the graph, but may also be the string |"self"|, in +-- which case it will be set to the newly created +-- (syntactic) digraph. +-- @return A newly-allocated digraph. +-- +function Digraph.new(initial) + local digraph = {} + setmetatable(digraph, Digraph) + + if initial then + for k,v in pairs(initial or {}) do + digraph [k] = v + end + end + + local vertices = digraph.vertices + digraph.vertices = {} + digraph.arcs = {} + + if vertices then + digraph:add(vertices) + end + return digraph +end + + +--- Add vertices to a digraph. +-- +-- This operation takes time $O(|\verb!array!|)$. +-- +-- @param array An array of to-be-added vertices. +-- +function Digraph:add(array) + local vertices = self.vertices + for i=1,#array do + local v = array[i] + if not vertices[v] then + vertices[v] = true + vertices[#vertices + 1] = v + v.incomings[self] = {} + v.outgoings[self] = {} + end + end +end + + +--- Remove vertices from a digraph. +-- +-- This operation removes an array of vertices from a graph. The +-- operation takes time linear in the number of vertices, regardless of +-- how many vertices are to be removed. Thus, it will be (much) faster +-- to delete many vertices by first compiling them in an array and to +-- then delete them using one call to this method. +-- +-- This operation takes time $O(\max\{|\verb!array!|, |\verb!self.vertices!|\})$. +-- +-- @param array The to-be-removed vertices. +-- +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. +-- +-- This operation takes time $O(1)$. +-- +-- @param v The vertex to be tested. +-- +function Digraph:contains(v) + return v and self.vertices[v] == true +end + + + + +--- +-- Returns the arc between two nodes, provided it exists. Otherwise, +-- |nil| is returned. +-- +-- This operation takes time $O(1)$. +-- +-- @param tail The tail vertex +-- @param head The head vertex +-- +-- @return The arc object connecting them +-- +function Digraph:arc(tail, head) + local out = tail.outgoings[self] + if out then + return out[head] + end +end + + + +--- +-- Returns an array containing the outgoing arcs of a vertex. You may +-- only iterate over his array using ipairs, not using pairs. +-- +-- This operation takes time $O(1)$. +-- +-- @param v The vertex +-- +-- @return An array of all outgoing arcs of this vertex (all arcs +-- whose tail is the vertex) +-- +function Digraph:outgoing(v) + return assert(v.outgoings[self], "vertex not in graph") +end + + + +--- +-- Sorts the array of outgoing arcs of a vertex. This allows you to +-- later iterate over the outgoing arcs in a specific order. +-- +-- This operation takes time $O(|\verb!outgoing!| \log |\verb!outgoings!|)$. +-- +-- @param v The vertex +-- @param f A comparison function that is passed to |table.sort| +-- +function Digraph:sortOutgoing(v, f) + table.sort(assert(v.outgoings[self], "vertex not in graph"), f) +end + + +--- +-- Reorders the array of outgoing arcs of a vertex. The parameter array +-- \emph{must} contain the same set of vertices as the outgoing array, +-- but possibly in a different order. +-- +-- This operation takes time $O(|\verb!outgoing!|)$, where |outgoing| +-- is the array of |v|'s outgoing arcs in |self|. +-- +-- @param v The vertex +-- @param vertices An array containing the outgoing vertices in some order. +-- +function Digraph:orderOutgoing(v, vertices) + local outgoing = assert (v.outgoings[self], "vertex not in graph") + assert (#outgoing == #vertices) + + -- Create back hash + local lookup = {} + for i=1,#vertices do + lookup[vertices[i]] = i + end + + -- Compute ordering of the arcs + local reordered = {} + for _,arc in ipairs(outgoing) do + reordered [lookup[arc.head]] = arc + end + + -- Copy back + for i=1,#outgoing do + outgoing[i] = assert(reordered[i], "illegal vertex order") + end +end + + + +--- See |outgoing|. +-- +function Digraph:incoming(v) + return assert(v.incomings[self], "vertex not in graph") +end + + +--- +-- See |sortOutgoing|. +-- +function Digraph:sortIncoming(v, f) + table.sort(assert(v.incomings[self], "vertex not in graph"), f) +end + + +--- +-- See |orderOutgoing|. +-- +function Digraph:orderIncoming(v, vertices) + local incoming = assert (v.incomings[self], "vertex not in graph") + assert (#incoming == #vertices) + + -- Create back hash + local lookup = {} + for i=1,#vertices do + lookup[vertices[i]] = i + end + + -- Compute ordering of the arcs + local reordered = {} + for _,arc in ipairs(incoming) do + reordered [lookup[arc.head]] = arc + end + + -- Copy back + for i=1,#incoming do + incoming[i] = assert(reordered[i], "illegal vertex order") + end +end + + + + + +--- +-- Connects two nodes by an arc and returns the newly created arc +-- object. If they are already connected, the existing arc is returned. +-- +-- This operation takes time $O(1)$. +-- +-- @param s The tail vertex +-- @param t The head vertex (may be identical to |tail| in case of a +-- loop) +-- +-- @return The arc object connecting them (either newly created or +-- already existing) +-- +function Digraph:connect(s, t) + assert (s and t and self.vertices[s] and self.vertices[t], "trying connect nodes not in graph") + + local s_outgoings = s.outgoings[self] + local arc = s_outgoings[t] + + if not arc then + -- Ok, create and insert new arc object + arc = { + tail = s, + head = t, + option_cache = {}, + syntactic_digraph = self.syntactic_digraph, + syntactic_edges = {} + } + setmetatable(arc, Arc) + + -- Insert into outgoings: + s_outgoings [#s_outgoings + 1] = arc + s_outgoings [t] = arc + + local t_incomings = t.incomings[self] + -- Insert into incomings: + t_incomings [#t_incomings + 1] = arc + t_incomings [s] = arc + + -- Insert into arcs field, if it exists: + local arcs = rawget(self, "arcs") + if arcs then + arcs[#arcs + 1] = arc + end + end + + return arc +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. +-- +-- 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 +-- $v$. For a single vertex $v$, it takes time $O(\sum_{y: \text{there is some +-- arc between $v$ and $y$ or $y$ and $v$}} |I_y|)$. +-- +-- @param v The single vertex or the tail vertex +-- @param t The head vertex +-- +function Digraph:disconnect(v, t) + if t then + -- Case 2: Remove a single arc. + local s_outgoings = assert(v.outgoings[self], "tail node not in graph") + local t_incomings = assert(t.incomings[self], "head node not in graph") + + if s_outgoings[t] then + -- 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 + 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 + 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 + + 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 + end + end + + -- Step 2: Delete all outgoings arcs: + local outgoings = v.outgoings[self] + 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 + end + end + + if #incomings > 0 or #outgoings > 0 then + self.arcs = nil -- invalidate arcs field + end + + -- Step 3: Reset incomings and outgoings fields + v.incomings[self] = {} + v.outgoings[self] = {} + end +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 +-- effect. +-- +-- If there is already an arc at the new position, fields of the +-- to-be-reconnected arc overwrite fields of the original arc. This is +-- especially dangerous with a syntactic digraph, so do not reconnect +-- arcs of the syntactic digraph (which you should not do anyway). +-- +-- The |arc| object may no longer be valid after a reconnect, but the +-- operation returns the new arc object. +-- +-- This operation needs the time of a disconnect (if necessary). +-- +-- @param arc The original arc object +-- @param tail The new tail vertex +-- @param head The new head vertex +-- +-- @return The new arc object connecting them (either newly created or +-- already existing) +-- +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 + end + end + + -- Remove old arc: + self:disconnect(arc.tail, arc.head) + + return new_arc + end +end + + + +--- +-- Collapse a set of vertices into a single vertex +-- +-- Often, algorithms will wish to treat a whole set of vertices ``as a +-- single vertex''. The idea is that a new vertex is then inserted +-- into the graph, and this vertex is connected to all vertices to +-- which any of the original vertices used to be connected. +-- +-- The |collapse| method takes an array of to-be-collapsed vertices as +-- well as a vertex. First, it will store references to the +-- to-be-collapsed vertices inside the vertex. Second, we iterate over +-- all arcs of the to-be-collapsed vertices. If this arc connects a +-- to-be-collapsed vertex with a not-to-be-collapsed vertex, the +-- not-to-be-collapsed vertex is connected to the collapse +-- vertex. Additionally, the arc is stored at the vertex. +-- +-- Note that the collapse vertex will be added to the graph if it is +-- not already an element. The collapsed vertices will not be removed +-- from the graph, so you must remove them yourself, if necessary. +-- +-- 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. +-- +-- @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. +-- @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|. +-- @param arc_fun This function is called whenever a new arc is added +-- 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. + +function Digraph:collapse(collapse_vertices, collapse_vertex, vertex_fun, arc_fun) + + + -- Create and add node, if necessary. + if not collapse_vertex then + collapse_vertex = Vertex.new {} + end + self:add {collapse_vertex} + + -- Copy the collapse_vertices and create lookup + local cvs = {} + for i=1,#collapse_vertices do + local v = collapse_vertices[i] + cvs[i] = v + cvs[v] = true + end + assert (cvs[collapse_vertex] ~= true, "collapse_vertex is in collapse_vertices") + + -- 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 + 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) + end + collapsed_arcs[#collapsed_arcs + 1] = a + end + end + + -- Remember the old vertices. + collapse_vertex.collapsed_vertices = cvs + collapse_vertex.collapsed_arcs = collapsed_arcs + + return collapse_vertex +end + + + +--- +-- Expand a previously collapsed vertex. +-- +-- If you have collapsed a set of vertices in a graph using +-- |collapse|, you can expand this set once more using this method. It +-- will add all vertices that were previously removed from the graph +-- and will also reinstall the deleted arcs. The collapse vertex is +-- not removed. +-- +-- @param vertex A to-be-expanded vertex that was previously returned +-- by |collapse|. +-- @param vertex_fun A function that is called once for each +-- reinserted vertex. The parameters are the collapse vertex and the +-- reinstalled vertex. May be |nil|. +-- @param arc_fun A function that is called once for each +-- reinserted arc. The parameter is the arc and the |vertex|. May be |nil|. +-- +function Digraph:expand(vertex, vertex_fun, arc_fun) + local cvs = assert(vertex.collapsed_vertices, "no expand information stored") + + -- Add all vertices: + self:add(cvs) + if vertex_fun then + for _,v in ipairs(cvs) do + vertex_fun(vertex, v) + end + end + + -- 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 + end + end + + if arc_fun then + arc_fun(new_arc, vertex) + end + end +end + + + + + +--- +-- Invokes the |sync| method for all arcs of the graph. +-- +-- @see Arc:sync() +-- +function Digraph:sync() + for _,a in ipairs(self.arcs) do + a:sync() + end +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. +-- +-- @return |self| as string. +-- +function Digraph:__tostring() + local vstrings = {} + local astrings = {} + for i,v in ipairs(self.vertices) do + vstrings[i] = " " .. tostring(v) .. "[x=" .. math.floor(v.pos.x) .. "pt,y=" .. math.floor(v.pos.y) .. "pt]" + local out_arcs = v.outgoings[self] + if #out_arcs > 0 then + local t = {} + for j,a in ipairs(out_arcs) do + 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(astrings, ";\n") .. "\n}"; +end + + + + +-- Done + +return Digraph diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Edge.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Edge.lua new file mode 100644 index 0000000000..45cbc60f9f --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Edge.lua @@ -0,0 +1,209 @@ +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @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 +-- are present in the syntactic digraph. +-- +-- In detail, the relationship between arcs and edges is as follows: +-- If there is an |Edge| between two vertices $u$ and $v$ in the +-- syntactic digraph, there will be an |Arc| from $u$ to $v$ and the +-- array |syntactic_edges| of this |Arc| object will contain the +-- |Edge| object. In particular, if there are several edges between +-- the same vertices, all of these edges will be part of the array in +-- a single |Arc| object. +-- +-- Edges, like arcs, are always directed from a |tail| vertex to a +-- |head| vertex; this is true even for undirected vertices. The +-- |tail| vertex will always be the vertex that came first in the +-- syntactic specification of the edge, the |head| vertex is the +-- 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 |"-!-"| +-- \end{enumerate} +-- +-- +-- @field head The head vertex of this edge. +-- +-- @field tail The tail vertex of this edge. +-- +-- @field event The creation |Event| of this edge. +-- +-- @field options A table of options that contains user-defined options. +-- +-- @field direction One of the directions named above. +-- +-- @field path A |Path| object that describes the path of the +-- edge. The path's coordinates are interpreted \emph{absolutely}. +-- +-- @field generated_options This is an options array that is generated +-- by the algorithm. When the edge is rendered later on, this array +-- will be passed back to the display layer. The syntax is the same as +-- for the |declare_parameter_sequence| function, see +-- |InterfaceToAlgorithms|. +-- +-- @field animations An array of animations, see the |animations| +-- field of the |Vertex| class for the syntax. + +local Edge = {} +Edge.__index = Edge + + +-- Namespace + +require("pgf.gd.model").Edge = Edge + + +-- Imports + +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} +-- +-- @param initial Values to override defaults. -- +-- @return A new edge object. +-- +function Edge.new(values) + local new = {} + for k,v in pairs(values) do + new[k] = v + end + new.generated_options = new.generated_options or {} + new.animations = new.animations or {} + if not new.path then + local p = Path.new () + p:appendMoveto(Edge.tailAnchorForEdgePath(new)) + p:appendLineto(Edge.headAnchorForEdgePath(new)) + new.path = p + end + + return setmetatable(new, Edge) +end + + + + +--- +-- This method returns a ``coordinate factory'' that can be used as +-- the coordinate of a |moveto| at the beginning of a path starting at +-- the |tail| of the arc. Suppose you want to create a path starting +-- at the tail vertex, going to the coordinate $(10,10)$ and ending at +-- the head vertex. The trouble is that when you create the path +-- corresponding to this route, you typically do not know where the +-- tail vertex is going to be. In this case, you use this +-- method to get a function that will, later on, compute the correct +-- position of the anchor as needed. +-- +-- 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. +-- +-- 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] +--... +--e.path = Path.new() +--e.path:appendMoveto(e:tailAnchorForEdgePath()) +--e.path:appendLineto(10, 10) +--e.path:appendLineto(e:headAnchorForEdgePath()) +--\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 +end + +--- +-- See |Arc:tailAnchorForArcPath|. + +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 +end + + + +--- +-- Setup the |path| field of an edge in such a way that it corresponds +-- to a sequence of straight line segments starting at the tail's +-- anchor and ending at the head's anchor. +-- +-- @param coordinates An array of |Coordinates| through which the line +-- will go through. + +function Edge:setPolylinePath(coordinates) + local p = Path.new () + + p:appendMoveto(self:tailAnchorForEdgePath()) + + for _,c in ipairs(coordinates) do + p:appendLineto(c) + end + + p:appendLineto(self:headAnchorForEdgePath()) + + self.path = p +end + + + +-- +-- Returns a string representation of an edge. This is mainly for debugging. +-- +-- @return The Edge as a string. +-- +function Edge:__tostring() + return tostring(self.tail) .. self.direction .. tostring(self.head) +end + + +-- Done + +return Edge diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Hyperedge.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Hyperedge.lua new file mode 100644 index 0000000000..cc265023fa --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Hyperedge.lua @@ -0,0 +1,56 @@ +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header$ + + + +--- +-- @section subsection {Hyperedges} +-- +-- @end + + +-- Includes + +local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare + + +--- + +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. + "]], + documentation = [[" +\begin{codeexample}[code only] +\graph { + % The nodes: + a, b, c, d; + + % The edges: + {[hyper] a,b,c}; + {[hyper] b,c,d}; + {[hyper] a,c}; + {[hyper] d} +}; +\end{codeexample} + "]] +} + +-- Done + +return Hyperedge
\ No newline at end of file diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Path.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Path.lua new file mode 100644 index 0000000000..cbd0f079bf --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Path.lua @@ -0,0 +1,1278 @@ +-- Copyright 2014 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @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 +-- 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 +-- 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. +-- \end{itemize} +-- +-- Instead of a |Coordinate|, a |Path| may also contain a function. In +-- this case, the function, when called, must return the |Coordinate| +-- that is ``meant'' by the position. This allows algorithms to +-- add coordinates to a path that are still not fixed at the moment +-- they are added to the path. + +local Path = {} +Path.__index = Path + + +-- Namespace + +require("pgf.gd.model").Path = Path + + +-- Imports + +local Coordinate = require "pgf.gd.model.Coordinate" +local Bezier = require "pgf.gd.lib.Bezier" + +local lib = require "pgf.gd.lib" + + +-- Private function + +function Path.rigid (x) + if type(x) == "function" then + return x() + else + return x + end +end + +local rigid = Path.rigid + + +--- +-- Creates an empty path. +-- +-- @param initial A table containing an array of strings and +-- coordinates that constitute the path. Coordinates may be given as +-- tables or as a pair of numbers. In this case, each pair of numbers +-- is converted into one coordinate. If omitted, a new empty path +-- is created. +-- +-- @return A empty Path +-- +function Path.new(initial) + if initial then + local new = {} + local i = 1 + local count = 0 + 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 + 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 + 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 + else + error ("invalid object on path") + end + i = i + 1 + end + return setmetatable(new, Path) + else + return setmetatable({}, Path) + end +end + + +--- +-- Creates a copy of a path. +-- +-- @return A copy of the path + +function Path:clone() + local new = {} + for _,x in ipairs(self) do + if type(x) == "table" then + new[#new+1] = x:clone() + else + new[#new+1] = x + end + end + return setmetatable(new, Path) +end + + + +--- +-- Returns the path in reverse order. +-- +-- @return A copy of the reversed path + +function Path:reversed() + + -- First, build segments + local subpaths = {} + local subpath = {} + + local function closepath () + if subpath.start then + subpaths [#subpaths + 1] = subpath + subpath = {} + end + end + + local prev + local start + + local i = 1 + while i <= #self do + local x = self[i] + if x == "lineto" then + subpath[#subpath+1] = { + action = 'lineto', + from = prev, + to = self[i+1] + } + prev = self[i+1] + i = i + 2 + elseif x == "moveto" then + closepath() + prev = self[i+1] + start = prev + subpath.start = prev + i = i + 2 + elseif x == "closepath" then + subpath [#subpath + 1] = { + action = "closepath", + from = prev, + to = start, + } + prev = nil + start = nil + closepath() + i = i + 1 + 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, + } + prev = self[i+3] + i = i + 4 + else + error ("illegal path command '" .. x .. "'") + end + end + closepath () + + local new = Path.new () + + for _,subpath in ipairs(subpaths) do + if #subpath == 0 then + -- A subpath that consists only of a moveto: + new:appendMoveto(subpath.start) + 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 + end + + -- Append a closepath, if necessary + if subpath[#subpath].action == "closepath" then + new:appendClosepath() + end + end + end + + return new +end + + +--- +-- Transform all points on a path. +-- +-- @param t A transformation, see |pgf.gd.lib.Transform|. It is +-- applied to all |Coordinate| objects on the path. + +function Path:transform(t) + for _,c in ipairs(self) do + if type(c) == "table" then + c:apply(t) + end + end +end + + +--- +-- Shift all points on a path. +-- +-- @param x An $x$-shift +-- @param y A $y$-shift + +function Path:shift(x,y) + for _,c in ipairs(self) do + if type(c) == "table" then + c.x = c.x + x + c.y = c.y + y + end + end +end + + +--- +-- Shift by all points on a path. +-- +-- @param x A coordinate + +function Path:shiftByCoordinate(x) + for _,c in ipairs(self) do + if type(c) == "table" then + c.x = c.x + x.x + c.y = c.y + x.y + end + end +end + + +--- +-- Makes the path empty. +-- + +function Path:clear() + for i=1,#self do + self[i] = nil + end +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. +-- @param y The $y$-part of the coordinate. + +function Path:appendMoveto(x,y) + self[#self + 1] = "moveto" + self[#self + 1] = y and Coordinate.new(x,y) or x +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. +-- @param y The $y$-part of the coordinate. + +function Path:appendLineto(x,y) + self[#self + 1] = "lineto" + self[#self + 1] = y and Coordinate.new(x,y) or x +end + + + +--- +-- Appends a |closepath| to the path. + +function Path:appendClosepath() + self[#self + 1] = "closepath" +end + + +--- +-- Appends a |curveto| to the path. There can be either three +-- coordinates (or functions) as parameters (the two support points +-- and the target) or six numbers, where two consecutive numbers form a +-- |Coordinate|. Which case is meant is detected by the presence of a +-- sixth non-nil parameter. + +function Path:appendCurveto(a,b,c,d,e,f) + self[#self + 1] = "curveto" + if f then + self[#self + 1] = Coordinate.new(a,b) + self[#self + 1] = Coordinate.new(c,d) + self[#self + 1] = Coordinate.new(e,f) + else + self[#self + 1] = a + self[#self + 1] = b + self[#self + 1] = c + end +end + + + + + + +--- +-- Makes a path ``rigid'', meaning that all coordinates that are only +-- given as functions are replaced by the values these functions +-- yield. + +function Path:makeRigid() + for i=1,#self do + self[i] = rigid(self[i]) + end +end + + +--- +-- Returns an array of all coordinates that are present in a +-- path. This means, essentially, that all strings are filtered out. +-- +-- @return An array of all coordinate objects on the path. + +function Path:coordinates() + local cloud = {} + for i=1,#self do + local p = self[i] + if type(p) == "table" then + cloud[#cloud + 1] = p + elseif type(p) == "function" then + cloud[#cloud + 1] = p() + end + end + return cloud +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. +-- +-- If the path contains no coordinates, all return values are 0. +-- +-- @return |min_x| The minimum $x$ value of the bounding box of the path +-- @return |min_y| The minimum $y$ value +-- @return |max_x| +-- @return |max_y| +-- @return |center_x| The center of the bounding box +-- @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 + end + end + + if min_x ~= math.huge then + return min_x, min_y, max_x, max_y, (min_x+max_x) / 2, (min_y+max_y) / 2 + end + end + return 0, 0, 0, 0, 0, 0 +end + + +-- Forwards + +local segmentize, bb, boxes_intersect, intersect_curves + +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 +-- divide-and-conquer approach that should be reasonably fast in +-- 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. +-- \end{itemize} + +function Path:intersectionsWith(path) + + local p1 = segmentize(self) + local memo1 = prepare_memo(p1) + local p2 = segmentize(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 + local c = s2.from.x - s1.from.x + 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 + + 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) + 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) + 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) + 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 + elseif i1 == j1 then + 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) + 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) + 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) + + -- Remove duplicates + local remains = {} + remains[1] = intersections[1] + for i=2,#intersections do + local next = intersections[i] + local prev = remains[#remains] + if math.abs(next.point.x - prev.point.x) + math.abs(next.point.y - prev.point.y) > eps then + remains[#remains+1] = next + end + end + + return remains +end + + +-- Returns true if two bounding boxes intersection + +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) +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. + +function segmentize (path) + + local prev + local start + local s = {} + + 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), + } + } + prev = x + i = i + 2 + elseif x == "moveto" then + prev = rigid(path[i+1]) + start = prev + 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), + } + } + prev = nil + start = nil + i = i + 1 + 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), + } + } + prev = path[i+3] + i = i + 4 + else + error ("illegal path command '" .. x .. "'") + end + end + + return s +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 + + +-- This function computes the bounding box of all segments between i +-- and j (inclusively) + +function bb (i, j, memo) + local b = memo[memo.base*i + j] + if not b then + assert (i < j, "memorization table filled incorrectly") + + local mid = math.floor((i+j)/2) + local bb1 = bb (i, mid, memo) + local bb2 = bb (mid+1, j, memo) + b = { + min_x = math.min(bb1.min_x, bb2.min_x), + max_x = math.max(bb1.max_x, bb2.max_x), + min_y = math.min(bb1.min_y, bb2.min_y), + max_y = math.max(bb1.max_y, bb2.max_y) + } + memo[memo.base*i + j] = b + end + + return b +end + + + +-- Intersect two Bézier 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) + + -- 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) + local c1_min_y = math.min(c1_ay, c1_by, c1_cy, c1_dy) + local c1_max_y = math.max(c1_ay, c1_by, c1_cy, c1_dy) + local c2_min_x = math.min(c2_ax, c2_bx, c2_cx, c2_dx) + 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 + + -- Everything "near together"? + if c1_max_x - c1_min_x < eps and c1_max_y - c1_min_y < eps then + + -- Compute intersection of lines c1_a to c1_d and c2_a to c2_d + local a = c2_dx - c2_ax + local b = c1_ax - c1_dx + local c = c2_ax - c1_ax + 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 + elseif t>1 then + 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)) + } + 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) + 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) + 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) + 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) + end + end +end + + +--- +-- Shorten a path at the beginning. We are given the index of a +-- segment inside the path as well as a point in time along this +-- segment. The path is now shortened so that everything before this +-- segment and everything in the segment before the given time is +-- removed from the path. +-- +-- @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") + + 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 + + -- ... and copy the rest + for i=index,#self do + cut_path[#cut_path+1] = self[i] + end + elseif action == "curveto" then + + local to = rigid(self[index+3]) + local s1 = rigid(self[index+1]) + local s2 = rigid(self[index+2]) + + -- Now, compute the support vectors and the point at time: + from:moveTowards(s1, time) + s1:moveTowards(s2, time) + s2:moveTowards(to, time) + + from:moveTowards(s1, time) + s1:moveTowards(s2, time) + + from:moveTowards(s1, time) + + -- Ok, this is easy: We start with a fresh moveto ... + cut_path[1] = "moveto" + cut_path[2] = from + cut_path[3] = "curveto" + cut_path[4] = s1 + cut_path[5] = s2 + cut_path[6] = to + + -- ... and copy the rest + 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 + for i=index,1,-1 do + if self[i] == "moveto" then + -- Bingo: + found = i + break + end + end + + assert(found, "no moveto found in path") + + local to = rigid(self[found+1]) + from:moveTowards(to,time) + + cut_path[1] = "moveto" + cut_path[2] = from + cut_path[3] = "lineto" + cut_path[4] = to + + -- ... and copy the rest + for i=index+1,#self do + cut_path[#cut_path+1] = self[i] + end + else + error ("wrong path operation") + end + + -- Move cut_path back: + for i=1,#cut_path do + self[i] = cut_path[i] + end + for i=#cut_path+1,#self do + self[i] = nil + end +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 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") + + 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]) + + -- Now, compute the support vectors and the point at time: + to:moveTowards(s2, 1-time) + s2:moveTowards(s1, 1-time) + s1:moveTowards(from, 1-time) + + to:moveTowards(s2, 1-time) + s2:moveTowards(s1, 1-time) + + to:moveTowards(s2, 1-time) + + -- ... and copy the rest + for i=1,index do + cut_path[i] = self[i] + end + + 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 + for i=index,1,-1 do + if self[i] == "moveto" then + -- 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) + + for i=1,index-1 do + cut_path[i] = self[i] + end + cut_path[index] = 'lineto' + cut_path[index+1] = to + else + error ("wrong path operation") + end + + -- Move cut_path back: + for i=1,#cut_path do + self[i] = cut_path[i] + end + for i=#cut_path+1,#self do + self[i] = nil + end +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 +-- compute an approximation to this resulting path. +-- +-- The algorithm used to compute the enlarged part does not necessarily +-- compute the precise new path. It should work correctly for polyline +-- paths, but not for curved paths. +-- +-- @param padding A padding distance. +-- @return The padded path. +-- + +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] + end + subpath[#subpath + 1] = subpath[start] + subpath[#subpath + 1] = subpath[start+1] + subpaths[#subpaths + 1] = subpath + subpath = {} + end + end + + for i,p in ipairs(padded) do + if p ~= "closepath" then + if type(p) == "table" then + subpath[#subpath + 1] = p + end + else + closepath (i) + end + end + closepath(#padded) + + -- Second, iterate over the subpaths: + for _,subpath in ipairs(subpaths) do + 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 + local d2 = subpath[i+1] - subpath[i] + 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 + elseif diff > math.pi then + 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) + + orth1:normalize() + orth2:normalize() + + if count < 0 then + 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) + else + c = Coordinate.new (padding*(orth2.y-orth1.y)/det, padding*(orth1.x-orth2.x)/det) + end + + new_coordinates[i] = c+p + end + + for i=2,#subpath-1 do + local p = subpath[i] + local new_p = new_coordinates[i] + p.x = new_p.x + p.y = new_p.y + end + + if subpath.skipped then + local p = subpath[1] + local new_p = new_coordinates[#subpath-2] + p.x = new_p.x + 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 + end + end + end + + return padded +end + + + +--- +-- Appends an arc (as in the sense of ``a part of the circumference of +-- a circle'') to the path. You may optionally provide a +-- transformation matrix, which will be applied to the arc. In detail, +-- 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. +-- +-- @function Path:appendArc(start_angle,end_angle,radius,trans) +-- +-- @param start_angle The start angle of the arc. Must be specified in +-- 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 +-- matrix will be assumed. + +Path.appendArc = lib.ondemand("Path_arced", Path, "appendArc") + + + +--- +-- Appends a clockwise arc (as in the sense of ``a part of the circumference of +-- a circle'') to the path such that it ends at a given point. If a +-- transformation matrix is given, both start and end point are first +-- transformed according to the inverted transformation, then the arc +-- is computed and then transformed back. +-- +-- @function Path:appendArcTo(target,radius_or_center,clockwise,trans) +-- +-- @param target The point where the arc should end. +-- @param radius_or_center If a number, it is the radius of the circle +-- on which this arc lies. If it is a |Coordinate|, this is the center +-- 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. +-- @param trans A transformation matrix. If missing, +-- the identity matrix is assumed. + +Path.appendArcTo = lib.ondemand("Path_arced", Path, "appendArcTo") + + + + +-- +-- @return The Path as string. +-- +function Path:__tostring() + local r = {} + 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 + elseif p == "moveto" then + r [#r+1] = " " .. tostring(rigid(self[i+1]) ) + i = i + 1 + elseif p == "curveto" then + r [#r+1] = " .. controls " .. tostring(rigid(self[i+1])) .. " and " .. + tostring(rigid(self[i+2])) .. " .. " .. tostring(rigid(self[i+3])) + i = i + 3 + elseif p == "closepath" then + r [#r+1] = " -- cycle" + else + error("illegal path command") + end + i = i + 1 + end + return table.concat(r) +end + + + +-- Done + +return Path diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Path_arced.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Path_arced.lua new file mode 100644 index 0000000000..1875b8d1a5 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Path_arced.lua @@ -0,0 +1,316 @@ +-- Copyright 2014 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header$ + + +local Path = require 'pgf.gd.model.Path' + +-- Imports + +local Coordinate = require "pgf.gd.model.Coordinate" +local Transform = require "pgf.gd.lib.Transform" + + + +-- Locals + +local rigid = Path.rigid + +local tan = math.tan +local sin = math.sin +local cos = math.cos +local sqrt = math.sqrt +local atan2 = math.atan2 +local abs = math.abs + +local to_rad = math.pi/180 +local to_deg = 180/math.pi +local pi_half = math.pi/2 + +local function sin_quarter(x) + x = x % 360 + if x == 0 then + return 0 + elseif x == 90 then + return 1 + elseif x == 180 then + return 0 + else + return -1 + end +end + +local function cos_quarter(x) + x = x % 360 + if x == 0 then + return 1 + elseif x == 90 then + return 0 + elseif x == 180 then + return -1 + else + return 0 + end +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 + + if x == 0 then + if y < 0 then + return -90 + else + return 90 + end + elseif y == 0 then + if x < 0 then + return 180 + else + return 0 + end + 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 + s1, c1, s190, c190 = sin_quarter(start_angle), cos_quarter(start_angle), sin_quarter(start_angle+90), cos_quarter(start_angle+90) + else + local a1 = start_angle*to_rad + s1, c1, s190, c190 = sin(a1), cos(a1), sin(a1+pi_half), cos(a1+pi_half) + end + + if end_angle % 90 == 0 then + s2, c2, s290, c290 = sin_quarter(end_angle), cos_quarter(end_angle), sin_quarter(end_angle-90), cos_quarter(end_angle-90) + else + 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" + path[#path + 1] = Coordinate.new (startx + c190*factor, starty + s190*factor) + path[#path + 1] = Coordinate.new (lastx + c290*factor, lasty + s290*factor) + path[#path + 1] = Coordinate.new (lastx, lasty) + + if trans then + path[#path-2]:apply(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 + -- @param end_angle is given in degrees + -- @param radius is the radius + -- @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 + -- 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) + 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) + else + 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) + 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) + else + subarc(path, startx, starty, start_angle, end_angle - start_angle, radius, trans, centerx, centery) + break + end + end + + -- else, do nothing + end +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)) + end + + arc (self, start, start_angle, end_angle, radius, trans) +end + + + + +-- Doc see Path.lua + +function Path:appendArcTo (target, radius_or_center, clockwise, 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") + + 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() + local itrans = Transform.invert(trans) + start:apply(itrans) + trans_target:apply(itrans) + if centerx then + local t = radius_or_center:clone() + t:apply(itrans) + 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 + else + 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") + 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 + 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) + + if clockwise then + if end_angle > start_angle then + end_angle = end_angle - 360 + end + else + if end_angle < start_angle then + 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: + self[#self] = target +end + + + +-- Done + +return true diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Vertex.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Vertex.lua new file mode 100644 index 0000000000..677ea4fbd0 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Vertex.lua @@ -0,0 +1,296 @@ +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header$ + + +--- +-- A |Vertex| instance models a node of graphs. Each |Vertex| object can be an +-- element of any number of graphs (whereas an |Arc| object can only be an +-- element of a single graph). +-- +-- When a vertex is added to a digraph |g|, two tables are created in +-- the vertex' storage: An array of incoming arcs (with respect to +-- |g|) and an array of outgoing arcs (again, with respect to +-- |g|). The fields are managed by the |Digraph| class and should not +-- be modified directly. +-- +-- Note that a |Vertex| is an abstraction of \tikzname\ nodes; indeed +-- the objective is to ensure that, in principle, we can use them +-- independently of \TeX. For this reason, you will not find any +-- references to |tex| inside a |Vertex|; this information is only +-- available in the syntactic digraph. +-- +-- One important aspect of vertices are its anchors -- a concept well +-- familiar for users of \tikzname, but since we need to abstract from +-- \tikzname, a separate anchor management is available inside the +-- graph drawing system. It works as follows: +-- +-- First of all, every vertex has a path, which is a (typically +-- closed) line around the vertex. The display system will pass down +-- the vertex' path to the graph drawing system and this path will be +-- stored as a |Path| object in the |path| field of the vertex. This +-- 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 +-- 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 +-- 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 +-- the three letters are quite different. A solution is to shift the +-- letters (and, thus, the paths of the vertices) in such a way that +-- in all three letters the baseline of the letters is exactly at the +-- origin. Now, when a graph drawing algorithm aligns these vertices +-- along the origins, the letters will all have the same baseline. +-- +-- Apart from the origin, there may be other positions in the path +-- coordinate system that are of interest -- such as the center of +-- the vertex. As mentioned above, this need not be the origin and +-- although a graph drawing algorithm should align the origins, +-- \emph{edges} between vertices should head toward these vertex +-- centers rather that toward the origins. Other points of interest +-- might be the ``top'' of the node. +-- +-- All points of special interest are called ``anchors''. The |anchor| +-- method allows you to retrieve them. By default, you always have +-- access to the |center| anchor, but other anchors may or may not be +-- available also, see the |anchor| method for details. +-- +-- @field pos A coordinate object that stores the position where the +-- vertex should be placed on the canvas. The main objective of graph drawing +-- algorithms is to update this coordinate. +-- +-- @field name An optional string that is used as a textual representation +-- of the node. +-- +-- @field path The path of the vertex's shape. This is a path along +-- the outer line resulting from stroking the vertex's original +-- shape. For instance, if you have a quadratic shape of size 1cm and +-- you stroke the path with a pen of 2mm thickness, this |path| field +-- would store a path of a square of edge length 12mm. +-- +-- @field anchors A table of anchors (in the TikZ sense). The table is +-- indexed by the anchor names (strings) and the values are +-- |Coordinate|s. Currently, it is only guaranteed that the |center| +-- anchor is present. Note that the |center| anchor need not lie at +-- the origin: A graph drawing system should align nodes relative to +-- the origin of the path's coordinate system. However, lines going to +-- and from the node will head towards the |center| anchor. See +-- Section~\ref{section-gd-anchors} for details. +-- +-- @field options A table of options that contains user-defined options. +-- +-- @field animations An array of attribute animations for the +-- node. When an algorithm adds entries to this array, the display +-- layer should try to render these. The syntax is as follows: Each +-- element in the array is a table with a field |attribute|, which must +-- be a string like |"opacity"| or |"translate"|, a field |entries|, +-- which must be an array to be explained in a moment, and field +-- |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 +-- 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 +-- you provide a |Coordinate| and a where a path is expected you +-- provide a |Path|. +-- +-- @field shape A string describing the shape of the node (like |rectangle| +-- or |circle|). Note, however, that this is more ``informative''; the +-- actual information that is used by the graph drawing system for +-- determining the extent of a node, its bounding box, convex hull, +-- and line intersections is the |path| field. +-- +-- @field kind A string describing the kind of the node. For instance, a +-- node of type |"dummy"| does not correspond to any real node in +-- the graph but is used by the graph drawing algorithm. +-- +-- @field event The |Event| when this vertex was created (may be |nil| +-- if the vertex is not part of the syntactic digraph). +-- +-- @field incomings A table indexed by |Digraph| objects. For each +-- digraph, the table entry is an array of all vertices from which +-- there is an |Arc| to this vertex. This field is internal and may +-- not only be accessed by the |Digraph| class. +-- +-- @field outgoings Like |incomings|, but for outgoing arcs. +-- +local Vertex = {} +Vertex.__index = Vertex + + +-- Namespace + +require("pgf.gd.model").Vertex = Vertex + + +-- Imports + +local Coordinate = require "pgf.gd.model.Coordinate" +local Path = require "pgf.gd.model.Path" +local Storage = require "pgf.gd.lib.Storage" + + +--- +-- Create a new vertex. The |initial| parameter allows you to setup +-- some initial values. +-- +-- @usage +--\begin{codeexample}[code only, tikz syntax=false] +--local v = Vertex.new { name = "hello", pos = Coordinate.new(1,1) } +--\end{codeexample} +-- +-- @param initial Values to override default node settings. The +-- following are permissible: +-- \begin{description} +-- \item[|pos|] Initial position of the node. +-- \item[|name|] The name of the node. It is optional to define this. +-- \item[|path|] A |Path| object representing the vertex's hull. +-- \item[|anchors|] A table of anchors. +-- \item[|options|] An options table for the vertex. +-- \item[|animations|] An array of generated animation attributes. +-- \item[|shape|] A string describing the shape. If not given, |"none"| is used. +-- \item[|kind|] A kind like |"node"| or |"dummy"|. If not given, |"dummy"| is used. +-- \end{description} +-- +-- @return A newly allocated node. +-- +function Vertex.new(values) + local new = { + incomings = Storage.new(), + outgoings = Storage.new() + } + for k,v in pairs(values) do + new[k] = v + end + new.path = new.path or Path.new { 0, 0 } + new.shape = new.shape or "none" + new.kind = new.kind or "dummy" + new.pos = new.pos or Coordinate.new(0,0) + new.anchors = new.anchors or { center = Coordinate.new(0,0) } + new.animations = new.animations or {} + return setmetatable (new, Vertex) +end + + + + +--- +-- Returns a bounding box of a vertex. +-- +-- @return |min_x| The minimum $x$ value of the bounding box of the path +-- @return |min_y| The minimum $y$ value +-- @return |max_x| +-- @return |max_y| +-- @return |center_x| The center of the bounding box +-- @return |center_y| + +function Vertex:boundingBox() + return self.path:boundingBox() +end + + + +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, + south = function(min_x, min_y, max_x, max_y) + 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, + west = function(min_x, min_y, max_x, max_y) + 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, + ["north east"] = function(min_x, min_y, max_x, max_y) + return max_x, max_y + end, + ["south west"] = function(min_x, min_y, max_x, max_y) + return min_x, min_y + end, + ["south east"] = function(min_x, min_y, max_x, max_y) + return max_x, min_y + end, +} + +--- +-- Returns an anchor position in a vertex. First, we try to look +-- the anchor up in the vertex's |anchors| table. If it is not found +-- there, we test whether it is one of the direction strings |north|, +-- |south east|, and so on. If so, we consider a line from the center +-- of the node to the position on the bounding box that corresponds to +-- the given direction (so |south east| would be the lower right +-- corner). We intersect this line with the vertex's path and return +-- the result. Finally, if the above fails, we try to consider the +-- anchor as a number and return the intersection of a line starting +-- at the vertex's center with the number as its angle and the path of +-- the vertex. +-- +-- @param anchor An anchor as detailed above +-- @return A coordinate in the vertex's local coordinate system (so +-- add the |pos| field to arrive at the actual position). If the +-- anchor was not found, |nil| is returned + +function Vertex:anchor(anchor) + local c = self.anchors[anchor] + if not c then + local b + local d = directions [anchor] + if d then + b = Coordinate.new(d(self:boundingBox())) + 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) + end + end + if not b then + return + end + local p = Path.new {'moveto', self.anchors.center, 'lineto', b} + local intersections = p:intersectionsWith(self.path) + if #intersections > 0 then + c = intersections[1].point + end + end + self.anchors[anchor] = c + return c +end + + + +-- +-- Returns a string representation of a vertex. This is mainly for debugging +-- +-- @return The Arc as string. +-- +function Vertex:__tostring() + return self.name or tostring(self.anchors) +end + + +-- Done + +return Vertex diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/library.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/library.lua new file mode 100644 index 0000000000..ad62faa0f3 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/library.lua @@ -0,0 +1,15 @@ +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header$ + + + +-- Load declarations from: +require "pgf.gd.model.Hyperedge" |