summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Path.lua
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Path.lua')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Path.lua651
1 files changed, 325 insertions, 326 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Path.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Path.lua
index cbd0f079bfb..93cd44cc218 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Path.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Path.lua
@@ -10,32 +10,32 @@
-- @release $Header$
----
+---
-- A Path models a path in the plane.
--
-- Following the PostScript/\textsc{pdf}/\textsc{svg} convention, a
-- path consists of a series of path segments, each of which can be
--- closed or not. Each path segment, in turn, consists of a series of
--- Bézier curves and straight line segments; see
+-- closed or not. Each path segement, in turn, consists of a series of
+-- Bézier curvers and straight line segments; see
-- Section~\ref{section-paths} for an introduction to paths in
-- general.
--
-- A |Path| object is a table whose array part stores
--- |Coordinate| objects, |strings|, and |function|s that
--- describe the path of the edge. The following strings are allowed in
+-- |Coordinate| objects, |strings|, and |function|s that
+-- describe the path of the edge. The following strings are allowed in
-- this array:
--- %
+--
-- \begin{itemize}
--- \item |"moveto"| The line's path should stop at the current
--- position and then start anew at the next coordinate in the array.
--- \item |"lineto"| The line should continue from the current position
--- to the next coordinate in the array.
--- \item |"curveto"| The line should continue form the current
--- position with a Bézier curve that is specified by the next three
--- |Coordinate| objects (in the usual manner).
--- \item |"closepath"| The line's path should be ``closed'' in the sense
--- that the current subpath that was started with the most recent
--- moveto operation should now form a closed curve.
+-- \item |"moveto"| The line's path should stop at the current
+-- position and then start anew at the next coordinate in the array.
+-- \item |"lineto"| The line should continue from the current position
+-- to the next coordinate in the array.
+-- \item |"curveto"| The line should continue form the current
+-- position with a Bézier curve that is specified bz the next three
+-- |Coordinate| objects (in the usual manner).
+-- \item |"closepath"| The line's path should be ``closed'' in the sense
+-- that the current subpath that was started with the most recent
+-- moveto operation should now form a closed curve.
-- \end{itemize}
--
-- Instead of a |Coordinate|, a |Path| may also contain a function. In
@@ -93,36 +93,36 @@ function Path.new(initial)
while i <= #initial do
local e = initial[i]
if type(e) == "string" then
- assert (count == 0, "illformed path")
- if e == "moveto" then
- count = 1
- elseif e == "lineto" then
- count = 1
- elseif e == "closepath" then
- count = 0
- elseif e == "curveto" then
- count = 3
- else
- error ("unknown path command " .. e)
- end
- new[#new+1] = e
+ assert (count == 0, "illformed path")
+ if e == "moveto" then
+ count = 1
+ elseif e == "lineto" then
+ count = 1
+ elseif e == "closepath" then
+ count = 0
+ elseif e == "curveto" then
+ count = 3
+ else
+ error ("unknown path command " .. e)
+ end
+ new[#new+1] = e
elseif type(e) == "number" then
- if count == 0 then
- new[#new+1] = "lineto"
- else
- count = count - 1
- end
- new[#new+1] = Coordinate.new(e,initial[i+1])
- i = i + 1
+ if count == 0 then
+ new[#new+1] = "lineto"
+ else
+ count = count - 1
+ end
+ new[#new+1] = Coordinate.new(e,initial[i+1])
+ i = i + 1
elseif type(e) == "table" or type(e) == "function" then
- if count == 0 then
- new[#new+1] = "lineto"
- else
- count = count - 1
- end
- new[#new+1] = e
+ if count == 0 then
+ new[#new+1] = "lineto"
+ else
+ count = count - 1
+ end
+ new[#new+1] = e
else
- error ("invalid object on path")
+ error ("invalid object on path")
end
i = i + 1
end
@@ -158,7 +158,7 @@ end
-- @return A copy of the reversed path
function Path:reversed()
-
+
-- First, build segments
local subpaths = {}
local subpath = {}
@@ -169,7 +169,7 @@ function Path:reversed()
subpath = {}
end
end
-
+
local prev
local start
@@ -178,9 +178,9 @@ function Path:reversed()
local x = self[i]
if x == "lineto" then
subpath[#subpath+1] = {
- action = 'lineto',
- from = prev,
- to = self[i+1]
+ action = 'lineto',
+ from = prev,
+ to = self[i+1]
}
prev = self[i+1]
i = i + 2
@@ -192,9 +192,9 @@ function Path:reversed()
i = i + 2
elseif x == "closepath" then
subpath [#subpath + 1] = {
- action = "closepath",
- from = prev,
- to = start,
+ action = "closepath",
+ from = prev,
+ to = start,
}
prev = nil
start = nil
@@ -203,11 +203,11 @@ function Path:reversed()
elseif x == "curveto" then
local s1, s2, to = self[i+1], self[i+2], self[i+3]
subpath [#subpath + 1] = {
- action = "curveto",
- from = prev,
- to = to,
- support_1 = s1,
- support_2 = s2,
+ action = "curveto",
+ from = prev,
+ to = to,
+ support_1 = s1,
+ support_2 = s2,
}
prev = self[i+3]
i = i + 4
@@ -216,7 +216,7 @@ function Path:reversed()
end
end
closepath ()
-
+
local new = Path.new ()
for _,subpath in ipairs(subpaths) do
@@ -226,29 +226,29 @@ function Path:reversed()
else
-- We start with a moveto to the end point:
new:appendMoveto(subpath[#subpath].to)
-
+
-- Now walk backwards:
for i=#subpath,1,-1 do
- if subpath[i].action == "lineto" then
- new:appendLineto(subpath[i].from)
- elseif subpath[i].action == "closepath" then
- new:appendLineto(subpath[i].from)
- elseif subpath[i].action == "curveto" then
- new:appendCurveto(subpath[i].support_2,
- subpath[i].support_1,
- subpath[i].from)
- else
- error("illegal path command")
- end
+ if subpath[i].action == "lineto" then
+ new:appendLineto(subpath[i].from)
+ elseif subpath[i].action == "closepath" then
+ new:appendLineto(subpath[i].from)
+ elseif subpath[i].action == "curveto" then
+ new:appendCurveto(subpath[i].support_2,
+ subpath[i].support_1,
+ subpath[i].from)
+ else
+ error("illegal path command")
+ end
end
-- Append a closepath, if necessary
if subpath[#subpath].action == "closepath" then
- new:appendClosepath()
+ new:appendClosepath()
end
end
end
-
+
return new
end
@@ -314,7 +314,7 @@ end
-- Appends a |moveto| to the path.
--
-- @param x A |Coordinate| or |function| or, if the |y| parameter is
--- not |nil|, a number that is the $x$-part of a coordinate.
+-- not |nil|, a number that is the $x$-part of a coordiante .
-- @param y The $y$-part of the coordinate.
function Path:appendMoveto(x,y)
@@ -327,7 +327,7 @@ end
-- Appends a |lineto| to the path.
--
-- @param x A |Coordinate| or |function|, if the |y| parameter is not
--- |nil|, a number that is the $x$-part of a coordinate.
+-- |nil|, a number that is the $x$-part of a coordiante .
-- @param y The $y$-part of the coordinate.
function Path:appendLineto(x,y)
@@ -362,7 +362,7 @@ function Path:appendCurveto(a,b,c,d,e,f)
self[#self + 1] = a
self[#self + 1] = b
self[#self + 1] = c
- end
+ end
end
@@ -371,7 +371,7 @@ end
---
--- Makes a path ``rigid'', meaning that all coordinates that are only
+-- Makes a path ``rigid,'' meaning that all coordinates that are only
-- given as functions are replaced by the values these functions
-- yield.
@@ -406,7 +406,7 @@ end
-- Returns a bounding box of the path. This will not necessarily be
-- the minimal bounding box in case the path contains curves because,
-- then, the support points of the curve are used for the computation
--- rather than the actual bounding box of the path.
+-- rather than the actual boinding box of the path.
--
-- If the path contains no coordinates, all return values are 0.
--
@@ -415,22 +415,22 @@ end
-- @return |max_x|
-- @return |max_y|
-- @return |center_x| The center of the bounding box
--- @return |center_y|
+-- @return |center_y|
function Path:boundingBox()
if #self > 0 then
local min_x, min_y = math.huge, math.huge
local max_x, max_y = -math.huge, -math.huge
-
+
for i=1,#self do
local c = rigid(self[i])
if type(c) == "table" then
- local x = c.x
- local y = c.y
- if x < min_x then min_x = x end
- if y < min_y then min_y = y end
- if x > max_x then max_x = x end
- if y > max_y then max_y = y end
+ local x = c.x
+ local y = c.y
+ if x < min_x then min_x = x end
+ if y < min_y then min_y = y end
+ if x > max_x then max_x = x end
+ if y > max_y then max_y = y end
end
end
@@ -453,22 +453,21 @@ local eps = 0.0001
---
-- Computes all intersections of a path with another path and returns
-- them as an array of coordinates. The intersections will be sorted
--- ``along the path |self|''. The implementation uses a
+-- ``along the path |self|.'' The implementation uses a
-- divide-and-conquer approach that should be reasonably fast in
--- practice.
+-- practice.
--
-- @param path Another path
--
-- @return Array of all intersections of |path| with |self| in the
-- order they appear on |self|. Each entry of this array is a table
-- with the following fields:
--- %
-- \begin{itemize}
--- \item |index| The index of the segment in |self| where
--- the intersection occurs.
--- \item |time| The ``time'' at which a point traveling along the
--- segment from its start point to its end point.
--- \item |point| The point itself.
+-- \item |index| The index of the segment in |self| where
+-- the intersection occurs.
+-- \item |time| The ``time'' at which a point travelling along the
+-- segment from its start point to its end point.
+-- \item |point| The point itself.
-- \end{itemize}
function Path:intersectionsWith(path)
@@ -479,13 +478,13 @@ function Path:intersectionsWith(path)
local memo2 = prepare_memo(p2)
local intersections = {}
-
+
local function intersect_segments(i1, i2)
-
+
local s1 = p1[i1]
local s2 = p2[i2]
local r = {}
-
+
if s1.action == 'lineto' and s2.action == 'lineto' then
local a = s2.to.x - s2.from.x
local b = s1.from.x - s1.to.x
@@ -493,103 +492,103 @@ function Path:intersectionsWith(path)
local d = s2.to.y - s2.from.y
local e = s1.from.y - s1.to.y
local f = s2.from.y - s1.from.y
-
+
local det = a*e - b*d
-
+
if math.abs(det) > eps*eps then
- local t, s = (c*d - a*f)/det, (b*f - e*c)/det
+ local t, s = (c*d - a*f)/det, (b*f - e*c)/det
- if t >= 0 and t<=1 and s>=0 and s <= 1 then
- local p = s1.from:clone()
- p:moveTowards(s1.to, t)
- return { { time = t, point = p } }
- end
+ if t >= 0 and t<=1 and s>=0 and s <= 1 then
+ local p = s1.from:clone()
+ p:moveTowards(s1.to, t)
+ return { { time = t, point = p } }
+ end
end
elseif s1.action == 'lineto' and s2.action == 'curveto' then
intersect_curves (0, 1,
- s1.from.x, s1.from.y,
- s1.from.x*2/3+s1.to.x*1/3, s1.from.y*2/3+s1.to.y*1/3,
- s1.from.x*1/3+s1.to.x*2/3, s1.from.y*1/3+s1.to.y*2/3,
- s1.to.x, s1.to.y,
- s2.from.x, s2.from.y,
- s2.support_1.x, s2.support_1.y,
- s2.support_2.x, s2.support_2.y,
- s2.to.x, s2.to.y,
- r)
+ s1.from.x, s1.from.y,
+ s1.from.x*2/3+s1.to.x*1/3, s1.from.y*2/3+s1.to.y*1/3,
+ s1.from.x*1/3+s1.to.x*2/3, s1.from.y*1/3+s1.to.y*2/3,
+ s1.to.x, s1.to.y,
+ s2.from.x, s2.from.y,
+ s2.support_1.x, s2.support_1.y,
+ s2.support_2.x, s2.support_2.y,
+ s2.to.x, s2.to.y,
+ r)
elseif s1.action == 'curveto' and s2.action == 'lineto' then
intersect_curves (0, 1,
- s1.from.x, s1.from.y,
- s1.support_1.x, s1.support_1.y,
- s1.support_2.x, s1.support_2.y,
- s1.to.x, s1.to.y,
- s2.from.x, s2.from.y,
- s2.from.x*2/3+s2.to.x*1/3, s2.from.y*2/3+s2.to.y*1/3,
- s2.from.x*1/3+s2.to.x*2/3, s2.from.y*1/3+s2.to.y*2/3,
- s2.to.x, s2.to.y,
- r)
+ s1.from.x, s1.from.y,
+ s1.support_1.x, s1.support_1.y,
+ s1.support_2.x, s1.support_2.y,
+ s1.to.x, s1.to.y,
+ s2.from.x, s2.from.y,
+ s2.from.x*2/3+s2.to.x*1/3, s2.from.y*2/3+s2.to.y*1/3,
+ s2.from.x*1/3+s2.to.x*2/3, s2.from.y*1/3+s2.to.y*2/3,
+ s2.to.x, s2.to.y,
+ r)
else
intersect_curves (0, 1,
- s1.from.x, s1.from.y,
- s1.support_1.x, s1.support_1.y,
- s1.support_2.x, s1.support_2.y,
- s1.to.x, s1.to.y,
- s2.from.x, s2.from.y,
- s2.support_1.x, s2.support_1.y,
- s2.support_2.x, s2.support_2.y,
- s2.to.x, s2.to.y,
- r)
+ s1.from.x, s1.from.y,
+ s1.support_1.x, s1.support_1.y,
+ s1.support_2.x, s1.support_2.y,
+ s1.to.x, s1.to.y,
+ s2.from.x, s2.from.y,
+ s2.support_1.x, s2.support_1.y,
+ s2.support_2.x, s2.support_2.y,
+ s2.to.x, s2.to.y,
+ r)
end
return r
end
-
+
local function intersect (i1, j1, i2, j2)
if i1 > j1 or i2 > j2 then
return
end
-
+
local bb1 = bb(i1, j1, memo1)
local bb2 = bb(i2, j2, memo2)
-
+
if boxes_intersect(bb1, bb2) then
-- Ok, need to do something
if i1 == j1 and i2 == j2 then
- local intersects = intersect_segments (i1, i2)
- for _,t in ipairs(intersects) do
- intersections[#intersections+1] = {
- time = t.time,
- index = p1[i1].path_pos,
- point = t.point
- }
- end
+ local intersects = intersect_segments (i1, i2)
+ for _,t in ipairs(intersects) do
+ intersections[#intersections+1] = {
+ time = t.time,
+ index = p1[i1].path_pos,
+ point = t.point
+ }
+ end
elseif i1 == j1 then
- local m2 = math.floor((i2 + j2) / 2)
- intersect(i1, j1, i2, m2)
- intersect(i1, j1, m2+1, j2)
+ local m2 = math.floor((i2 + j2) / 2)
+ intersect(i1, j1, i2, m2)
+ intersect(i1, j1, m2+1, j2)
elseif i2 == j2 then
- local m1 = math.floor((i1 + j1) / 2)
- intersect(i1, m1, i2, j2)
- intersect(m1+1, j1, i2, j2)
+ local m1 = math.floor((i1 + j1) / 2)
+ intersect(i1, m1, i2, j2)
+ intersect(m1+1, j1, i2, j2)
else
- local m1 = math.floor((i1 + j1) / 2)
- local m2 = math.floor((i2 + j2) / 2)
- intersect(i1, m1, i2, m2)
- intersect(m1+1, j1, i2, m2)
- intersect(i1, m1, m2+1, j2)
- intersect(m1+1, j1, m2+1, j2)
+ local m1 = math.floor((i1 + j1) / 2)
+ local m2 = math.floor((i2 + j2) / 2)
+ intersect(i1, m1, i2, m2)
+ intersect(m1+1, j1, i2, m2)
+ intersect(i1, m1, m2+1, j2)
+ intersect(m1+1, j1, m2+1, j2)
end
- end
+ end
end
-
+
-- Run the recursion
intersect(1, #p1, 1, #p2)
-- Sort
table.sort(intersections, function(a,b)
- return a.index < b.index or
- a.index == b.index and a.time < b.time
- end)
-
+ return a.index < b.index or
+ a.index == b.index and a.time < b.time
+ end)
+
-- Remove duplicates
local remains = {}
remains[1] = intersections[1]
@@ -609,15 +608,15 @@ end
function boxes_intersect (bb1, bb2)
return (bb1.max_x >= bb2.min_x - eps*eps and
- bb1.min_x <= bb2.max_x + eps*eps and
- bb1.max_y >= bb2.min_y - eps*eps and
- bb1.min_y <= bb2.max_y + eps*eps)
+ bb1.min_x <= bb2.max_x + eps*eps and
+ bb1.max_y >= bb2.min_y - eps*eps and
+ bb1.min_y <= bb2.max_y + eps*eps)
end
-- Turns a path into a sequence of segments, each being either a
-- lineto or a curveto from some point to another point. It also sets
--- up a memorization array for the bounding boxes.
+-- up a memoization array for the bounding boxes.
function segmentize (path)
@@ -628,20 +627,20 @@ function segmentize (path)
local i = 1
while i <= #path do
local x = path[i]
-
+
if x == "lineto" then
x = rigid(path[i+1])
s [#s + 1] = {
- path_pos = i,
- action = "lineto",
- from = prev,
- to = x,
- bb = {
- min_x = math.min(prev.x, x.x),
- max_x = math.max(prev.x, x.x),
- min_y = math.min(prev.y, x.y),
- max_y = math.max(prev.y, x.y),
- }
+ path_pos = i,
+ action = "lineto",
+ from = prev,
+ to = x,
+ bb = {
+ min_x = math.min(prev.x, x.x),
+ max_x = math.max(prev.x, x.x),
+ min_y = math.min(prev.y, x.y),
+ max_y = math.max(prev.y, x.y),
+ }
}
prev = x
i = i + 2
@@ -651,16 +650,16 @@ function segmentize (path)
i = i + 2
elseif x == "closepath" then
s [#s + 1] = {
- path_pos = i,
- action = "lineto",
- from = prev,
- to = start,
- bb = {
- min_x = math.min(prev.x, start.x),
- max_x = math.max(prev.x, start.x),
- min_y = math.min(prev.y, start.y),
- max_y = math.max(prev.y, start.y),
- }
+ path_pos = i,
+ action = "lineto",
+ from = prev,
+ to = start,
+ bb = {
+ min_x = math.min(prev.x, start.x),
+ max_x = math.max(prev.x, start.x),
+ min_y = math.min(prev.y, start.y),
+ max_y = math.max(prev.y, start.y),
+ }
}
prev = nil
start = nil
@@ -668,18 +667,18 @@ function segmentize (path)
elseif x == "curveto" then
local s1, s2, to = rigid(path[i+1]), rigid(path[i+2]), rigid(path[i+3])
s [#s + 1] = {
- action = "curveto",
- path_pos = i,
- from = prev,
- to = to,
- support_1 = s1,
- support_2 = s2,
- bb = {
- min_x = math.min(prev.x, s1.x, s2.x, to.x),
- max_x = math.max(prev.x, s1.x, s2.x, to.x),
- min_y = math.min(prev.y, s1.y, s2.y, to.y),
- max_y = math.max(prev.y, s1.y, s2.y, to.y),
- }
+ action = "curveto",
+ path_pos = i,
+ from = prev,
+ to = to,
+ support_1 = s1,
+ support_2 = s2,
+ bb = {
+ min_x = math.min(prev.x, s1.x, s2.x, to.x),
+ max_x = math.max(prev.x, s1.x, s2.x, to.x),
+ min_y = math.min(prev.y, s1.y, s2.y, to.y),
+ max_y = math.max(prev.y, s1.y, s2.y, to.y),
+ }
}
prev = path[i+3]
i = i + 4
@@ -693,16 +692,16 @@ end
function prepare_memo (s)
-
+
local memo = {}
-
+
memo.base = #s
-
+
-- Fill memo table
for i,e in ipairs (s) do
memo[i*#s + i] = e.bb
end
-
+
return memo
end
@@ -713,8 +712,8 @@ end
function bb (i, j, memo)
local b = memo[memo.base*i + j]
if not b then
- assert (i < j, "memorization table filled incorrectly")
-
+ assert (i < j, "memoization table filled incorrectly")
+
local mid = math.floor((i+j)/2)
local bb1 = bb (i, mid, memo)
local bb2 = bb (mid+1, j, memo)
@@ -726,21 +725,21 @@ function bb (i, j, memo)
}
memo[memo.base*i + j] = b
end
-
+
return b
end
--- Intersect two Bézier curves.
+-- Intersect two Bezier curves.
function intersect_curves(t0, t1,
- c1_ax, c1_ay, c1_bx, c1_by,
- c1_cx, c1_cy, c1_dx, c1_dy,
- c2_ax, c2_ay, c2_bx, c2_by,
- c2_cx, c2_cy, c2_dx, c2_dy,
- intersections)
-
+ c1_ax, c1_ay, c1_bx, c1_by,
+ c1_cx, c1_cy, c1_dx, c1_dy,
+ c2_ax, c2_ay, c2_bx, c2_by,
+ c2_cx, c2_cy, c2_dx, c2_dy,
+ intersections)
+
-- Only do something, if the bounding boxes intersect:
local c1_min_x = math.min(c1_ax, c1_bx, c1_cx, c1_dx)
local c1_max_x = math.max(c1_ax, c1_bx, c1_cx, c1_dx)
@@ -750,12 +749,12 @@ function intersect_curves(t0, t1,
local c2_max_x = math.max(c2_ax, c2_bx, c2_cx, c2_dx)
local c2_min_y = math.min(c2_ay, c2_by, c2_cy, c2_dy)
local c2_max_y = math.max(c2_ay, c2_by, c2_cy, c2_dy)
-
+
if c1_max_x >= c2_min_x and
c1_min_x <= c2_max_x and
c1_max_y >= c2_min_y and
- c1_min_y <= c2_max_y then
-
+ c1_min_y <= c2_max_y then
+
-- Everything "near together"?
if c1_max_x - c1_min_x < eps and c1_max_y - c1_min_y < eps then
@@ -766,57 +765,57 @@ function intersect_curves(t0, t1,
local d = c2_dy - c2_ay
local e = c1_ay - c1_dy
local f = c2_ay - c1_ay
-
+
local det = a*e - b*d
local t
-
+
t = (c*d - a*f)/det
if t<0 then
- t=0
+ t=0
elseif t>1 then
- t=1
+ t=1
end
intersections [#intersections + 1] = {
- time = t0 + t*(t1-t0),
- point = Coordinate.new(c1_ax + t*(c1_dx-c1_ax), c1_ay+t*(c1_dy-c1_ay))
+ time = t0 + t*(t1-t0),
+ point = Coordinate.new(c1_ax + t*(c1_dx-c1_ax), c1_ay+t*(c1_dy-c1_ay))
}
else
-- Cut 'em in half!
local c1_ex, c1_ey = (c1_ax + c1_bx)/2, (c1_ay + c1_by)/2
local c1_fx, c1_fy = (c1_bx + c1_cx)/2, (c1_by + c1_cy)/2
local c1_gx, c1_gy = (c1_cx + c1_dx)/2, (c1_cy + c1_dy)/2
-
+
local c1_hx, c1_hy = (c1_ex + c1_fx)/2, (c1_ey + c1_fy)/2
local c1_ix, c1_iy = (c1_fx + c1_gx)/2, (c1_fy + c1_gy)/2
-
+
local c1_jx, c1_jy = (c1_hx + c1_ix)/2, (c1_hy + c1_iy)/2
-
+
local c2_ex, c2_ey = (c2_ax + c2_bx)/2, (c2_ay + c2_by)/2
local c2_fx, c2_fy = (c2_bx + c2_cx)/2, (c2_by + c2_cy)/2
local c2_gx, c2_gy = (c2_cx + c2_dx)/2, (c2_cy + c2_dy)/2
-
+
local c2_hx, c2_hy = (c2_ex + c2_fx)/2, (c2_ey + c2_fy)/2
local c2_ix, c2_iy = (c2_fx + c2_gx)/2, (c2_fy + c2_gy)/2
-
+
local c2_jx, c2_jy = (c2_hx + c2_ix)/2, (c2_hy + c2_iy)/2
intersect_curves (t0, (t0+t1)/2,
- c1_ax, c1_ay, c1_ex, c1_ey, c1_hx, c1_hy, c1_jx, c1_jy,
- c2_ax, c2_ay, c2_ex, c2_ey, c2_hx, c2_hy, c2_jx, c2_jy,
- intersections)
+ c1_ax, c1_ay, c1_ex, c1_ey, c1_hx, c1_hy, c1_jx, c1_jy,
+ c2_ax, c2_ay, c2_ex, c2_ey, c2_hx, c2_hy, c2_jx, c2_jy,
+ intersections)
intersect_curves (t0, (t0+t1)/2,
- c1_ax, c1_ay, c1_ex, c1_ey, c1_hx, c1_hy, c1_jx, c1_jy,
- c2_jx, c2_jy, c2_ix, c2_iy, c2_gx, c2_gy, c2_dx, c2_dy,
- intersections)
+ c1_ax, c1_ay, c1_ex, c1_ey, c1_hx, c1_hy, c1_jx, c1_jy,
+ c2_jx, c2_jy, c2_ix, c2_iy, c2_gx, c2_gy, c2_dx, c2_dy,
+ intersections)
intersect_curves ((t0+t1)/2, t1,
- c1_jx, c1_jy, c1_ix, c1_iy, c1_gx, c1_gy, c1_dx, c1_dy,
- c2_ax, c2_ay, c2_ex, c2_ey, c2_hx, c2_hy, c2_jx, c2_jy,
- intersections)
+ c1_jx, c1_jy, c1_ix, c1_iy, c1_gx, c1_gy, c1_dx, c1_dy,
+ c2_ax, c2_ay, c2_ex, c2_ey, c2_hx, c2_hy, c2_jx, c2_jy,
+ intersections)
intersect_curves ((t0+t1)/2, t1,
- c1_jx, c1_jy, c1_ix, c1_iy, c1_gx, c1_gy, c1_dx, c1_dy,
- c2_jx, c2_jy, c2_ix, c2_iy, c2_gx, c2_gy, c2_dx, c2_dy,
- intersections)
+ c1_jx, c1_jy, c1_ix, c1_iy, c1_gx, c1_gy, c1_dx, c1_dy,
+ c2_jx, c2_jy, c2_ix, c2_iy, c2_gx, c2_gy, c2_dx, c2_dy,
+ intersections)
end
end
end
@@ -829,30 +828,30 @@ end
-- segment and everything in the segment before the given time is
-- removed from the path.
--
--- @param index The index of a path segment.
+-- @param index The index of a path segment.
-- @param time A time along the specified path segment.
function Path:cutAtBeginning(index, time)
-
+
local cut_path = Path:new ()
-
+
-- Ok, first, we need to find the segment *before* the current
-- one. Usually, this will be a moveto or a lineto, but things could
-- be different.
assert (type(self[index-1]) == "table" or type(self[index-1]) == "function",
- "segment before intersection does not end with a coordinate")
+ "segment before intersection does not end with a coordinate")
local from = rigid(self[index-1])
local action = self[index]
-
+
-- Now, depending on the type of segment, we do different things:
if action == "lineto" then
-
+
-- Ok, compute point:
local to = rigid(self[index+1])
from:moveTowards(to, time)
-
+
-- Ok, this is easy: We start with a fresh moveto ...
cut_path[1] = "moveto"
cut_path[2] = from
@@ -889,20 +888,20 @@ function Path:cutAtBeginning(index, time)
for i=index+4,#self do
cut_path[#cut_path+1] = self[i]
end
-
+
elseif action == "closepath" then
-- Let us find the start point:
- local found
+ local found
for i=index,1,-1 do
if self[i] == "moveto" then
- -- Bingo:
- found = i
- break
+ -- Bingo:
+ found = i
+ break
end
end
assert(found, "no moveto found in path")
-
+
local to = rigid(self[found+1])
from:moveTowards(to,time)
@@ -935,36 +934,36 @@ end
-- Shorten a path at the end. This method works like |cutAtBeginning|,
-- only the path is cut at the end.
--
--- @param index The index of a path segment.
+-- @param index The index of a path segment.
-- @param time A time along the specified path segment.
function Path:cutAtEnd(index, time)
local cut_path = Path:new ()
-
+
-- Ok, first, we need to find the segment *before* the current
-- one. Usually, this will be a moveto or a lineto, but things could
-- be different.
assert (type(self[index-1]) == "table" or type(self[index-1]) == "function",
- "segment before intersection does not end with a coordinate")
+ "segment before intersection does not end with a coordinate")
local from = rigid(self[index-1])
local action = self[index]
-
+
-- Now, depending on the type of segment, we do different things:
if action == "lineto" then
-
+
-- Ok, compute point:
local to = rigid(self[index+1])
to:moveTowards(from, 1-time)
-
+
for i=1,index do
cut_path[i] = self[i]
end
cut_path[index+1] = to
-
+
elseif action == "curveto" then
-
+
local s1 = rigid(self[index+1])
local s2 = rigid(self[index+2])
local to = rigid(self[index+3])
@@ -987,20 +986,20 @@ function Path:cutAtEnd(index, time)
cut_path[index+1] = s1
cut_path[index+2] = s2
cut_path[index+3] = to
-
+
elseif action == "closepath" then
-- Let us find the start point:
- local found
+ local found
for i=index,1,-1 do
if self[i] == "moveto" then
- -- Bingo:
- found = i
- break
+ -- Bingo:
+ found = i
+ break
end
end
assert(found, "no moveto found in path")
-
+
local to = rigid(self[found+1]:clone())
to:moveTowards(from,1-time)
@@ -1029,7 +1028,7 @@ end
-- ``Pads'' the path. The idea is the following: Suppose we stroke the
-- path with a pen whose width is twice the value |padding|. The outer
-- edge of this stroked drawing is now a path by itself. The path will
--- be a bit longer and ``larger''. The present function tries to
+-- be a bit longer and ``larger.'' The present function tries to
-- compute an approximation to this resulting path.
--
-- The algorithm used to compute the enlarged part does not necessarily
@@ -1041,29 +1040,29 @@ end
--
function Path:pad(padding)
-
+
local padded = self:clone()
padded:makeRigid()
if padding == 0 then
return padded
end
-
+
-- First, decompose the path into subpaths:
local subpaths = {}
local subpath = {}
local start_index = 1
-
+
local function closepath(end_index)
if #subpath >= 1 then
subpath.start_index = start_index
subpath.end_index = end_index
start_index = end_index + 1
-
+
local start = 1
if (subpath[#subpath] - subpath[1]):norm() < 0.01 and subpath[2] then
- start = 2
- subpath.skipped = subpath[1]
+ start = 2
+ subpath.skipped = subpath[1]
end
subpath[#subpath + 1] = subpath[start]
subpath[#subpath + 1] = subpath[start+1]
@@ -1071,11 +1070,11 @@ function Path:pad(padding)
subpath = {}
end
end
-
+
for i,p in ipairs(padded) do
if p ~= "closepath" then
if type(p) == "table" then
- subpath[#subpath + 1] = p
+ subpath[#subpath + 1] = p
end
else
closepath (i)
@@ -1088,7 +1087,7 @@ function Path:pad(padding)
local new_coordinates = {}
local _,_,_,_,c_x,c_y = Coordinate.boundingBox(subpath)
local c = Coordinate.new(c_x,c_y)
-
+
-- Find out the orientation of the path
local count = 0
for i=1,#subpath-2 do
@@ -1096,19 +1095,19 @@ function Path:pad(padding)
local d1 = subpath[i+2] - subpath[i+1]
local diff = math.atan2(d2.y,d2.x) - math.atan2(d1.y,d1.x)
-
+
if diff < -math.pi then
- count = count + 1
+ count = count + 1
elseif diff > math.pi then
- count = count - 1
+ count = count - 1
end
end
-
+
for i=2,#subpath-1 do
local p = subpath[i]
local d1 = subpath[i] - subpath[i-1]
local d2 = subpath[i+1] - subpath[i]
-
+
local orth1 = Coordinate.new(-d1.y, d1.x)
local orth2 = Coordinate.new(-d2.y, d2.x)
@@ -1116,21 +1115,21 @@ function Path:pad(padding)
orth2:normalize()
if count < 0 then
- orth1:scale(-1)
- orth2:scale(-1)
+ orth1:scale(-1)
+ orth2:scale(-1)
end
-- Ok, now we want to compute the intersection of the lines
-- perpendicular to p + padding*orth1 and p + padding*orth2:
-
+
local det = orth1.x * orth2.y - orth1.y * orth2.x
local c
if math.abs(det) < 0.1 then
- c = orth1 + orth2
- c:scale(padding/2)
+ c = orth1 + orth2
+ c:scale(padding/2)
else
- c = Coordinate.new (padding*(orth2.y-orth1.y)/det, padding*(orth1.x-orth2.x)/det)
+ c = Coordinate.new (padding*(orth2.y-orth1.y)/det, padding*(orth1.x-orth2.x)/det)
end
new_coordinates[i] = c+p
@@ -1147,50 +1146,50 @@ function Path:pad(padding)
local p = subpath[1]
local new_p = new_coordinates[#subpath-2]
p.x = new_p.x
- p.y = new_p.y
+ p.y = new_p.y
end
-
+
-- Now, we need to correct the curveto fields:
for i=subpath.start_index,subpath.end_index do
if self[i] == 'curveto' then
- local from = rigid(self[i-1])
- local s1 = rigid(self[i+1])
- local s2 = rigid(self[i+2])
- local to = rigid(self[i+3])
-
- local p1x, p1y, _, _, h1x, h1y =
- Bezier.atTime(from.x, from.y, s1.x, s1.y, s2.x, s2.y,
- to.x, to.y, 1/3)
-
- local p2x, p2y, _, _, _, _, h2x, h2y =
- Bezier.atTime(from.x, from.y, s1.x, s1.y, s2.x, s2.y,
- to.x, to.y, 2/3)
-
- local orth1 = Coordinate.new (p1y - h1y, -(p1x - h1x))
- orth1:normalize()
- orth1:scale(-padding)
-
- local orth2 = Coordinate.new (p2y - h2y, -(p2x - h2x))
- orth2:normalize()
- orth2:scale(padding)
-
- if count < 0 then
- orth1:scale(-1)
- orth2:scale(-1)
- end
-
- local new_s1, new_s2 =
- Bezier.supportsForPointsAtTime(padded[i-1],
- Coordinate.new(p1x+orth1.x,p1y+orth1.y), 1/3,
- Coordinate.new(p2x+orth2.x,p2y+orth2.y), 2/3,
- padded[i+3])
-
- padded[i+1] = new_s1
- padded[i+2] = new_s2
+ local from = rigid(self[i-1])
+ local s1 = rigid(self[i+1])
+ local s2 = rigid(self[i+2])
+ local to = rigid(self[i+3])
+
+ local p1x, p1y, _, _, h1x, h1y =
+ Bezier.atTime(from.x, from.y, s1.x, s1.y, s2.x, s2.y,
+ to.x, to.y, 1/3)
+
+ local p2x, p2y, _, _, _, _, h2x, h2y =
+ Bezier.atTime(from.x, from.y, s1.x, s1.y, s2.x, s2.y,
+ to.x, to.y, 2/3)
+
+ local orth1 = Coordinate.new (p1y - h1y, -(p1x - h1x))
+ orth1:normalize()
+ orth1:scale(-padding)
+
+ local orth2 = Coordinate.new (p2y - h2y, -(p2x - h2x))
+ orth2:normalize()
+ orth2:scale(padding)
+
+ if count < 0 then
+ orth1:scale(-1)
+ orth2:scale(-1)
+ end
+
+ local new_s1, new_s2 =
+ Bezier.supportsForPointsAtTime(padded[i-1],
+ Coordinate.new(p1x+orth1.x,p1y+orth1.y), 1/3,
+ Coordinate.new(p2x+orth2.x,p2y+orth2.y), 2/3,
+ padded[i+3])
+
+ padded[i+1] = new_s1
+ padded[i+2] = new_s2
end
end
end
-
+
return padded
end
@@ -1203,12 +1202,12 @@ end
-- the following happens: We first invert the transformation
-- and apply it to the start point. Then we compute the arc
-- ``normally'', as if no transformation matrix were present. Then we
--- apply the transformation matrix to all computed points.
+-- apply the transformation matrix to all computed points.
--
-- @function Path:appendArc(start_angle,end_angle,radius,trans)
--
-- @param start_angle The start angle of the arc. Must be specified in
--- degrees.
+-- degrees.
-- @param end_angle the end angle of the arc.
-- @param radius The radius of the circle on which this arc lies.
-- @param trans A transformation matrix. If |nil|, the identity
@@ -1233,7 +1232,7 @@ Path.appendArc = lib.ondemand("Path_arced", Path, "appendArc")
-- of the circle.
-- @param clockwise If true, the arc will be clockwise. Otherwise (the
-- default, if nothing or |nil| is given), the arc will be counter
--- clockwise.
+-- clockise.
-- @param trans A transformation matrix. If missing,
-- the identity matrix is assumed.
@@ -1250,7 +1249,7 @@ function Path:__tostring()
local i = 1
while i <= #self do
local p = self[i]
-
+
if p == "lineto" then
r [#r+1] = " -- " .. tostring(rigid(self[i+1]))
i = i + 1
@@ -1275,4 +1274,4 @@ end
-- Done
-return Path
+return Path \ No newline at end of file