答案1
更新:收敛检测以限制迭代次数和动画长度
该解决方案实现了上述引用,重新规范化新的多边形顶点坐标,以防止多边形坍塌为一个点。
实现是在 LaTeX3 中完成的,并l3fparray
使用 s 作为多边形的容器X和是坐标。绘图由 Ti 完成钾z。
在收敛状态下,多边形顶点在边缘中心和上一次迭代后的位置之间来回跳跃。因此,为了测试收敛,需要进行两次连续迭代和随后的规范化,然后评估顶点坐标的变化。此收敛测试在每个动画帧结束时进行。
n=50 多边形示例;单击运行SVG动画片 (11.3 MB) 在浏览器中:
\documentclass{standalone} % lualatex
%\documentclass[dvisvgm,autoplay]{standalone} % dvilualatex + dvisvgm
%\documentclass[export]{standalone} % lualatex + imagemagick (PDF to animated GIF)
\usepackage{animate}
\usepackage{tikz}
%%%%%%%%%%%%%%%%%%%%%%%
\def\n{50} % #vertices
\def\animationStepsMax{10000}% hard limit of #animation frames
\def\iterationsPerFrame{2} % #iterations per animation step; must be >= 2
\def\maxnorm{5.0e-5} % max norm of vertex coordinate change vectors between iterations
% tikzpicture properties
\def\bboxLowerLeft{-0.4,-0.4}% bounding box coords
\def\bboxUpperRight{0.4,0.4}
\def\scalePicture{6} % factor for scaling
%%%%%%%%%%%%%%%%%%%%%%%
\ExplSyntaxOn
% computes the edge centres; takes two fparrays of same length with polygon x and
% y coordinates and modifies them in place
\cs_new_protected_nopar:Npn\computeEdgeCentres#1#2{{
\fp_set:Nn\l_tmpa_fp{\fparray_item:Nn#1{1}}
\fp_set:Nn\l_tmpb_fp{\fparray_item:Nn#2{1}}
\int_step_inline:nn{\fparray_count:N#1-1}{
\fparray_gset:Nnn#1{##1}{(\fparray_item:Nn#1{##1}+\fparray_item:Nn#1{##1+1})/2}
\fparray_gset:Nnn#2{##1}{(\fparray_item:Nn#2{##1}+\fparray_item:Nn#2{##1+1})/2}
}
\fparray_gset:Nnn#1{\fparray_count:N#1}{(\fparray_item:Nn#1{\fparray_count:N#1}+\l_tmpa_fp)/2}
\fparray_gset:Nnn#2{\fparray_count:N#2}{(\fparray_item:Nn#2{\fparray_count:N#2}+\l_tmpb_fp)/2}
}}
% normalises polygon vertex coordinates in place;
% arguments: 2 fparrays of same length, each having unit 2-norm afterwards
\cs_new_protected_nopar:Npn\normalisePolygon#1#2{{
\computeTwoNorm\l_tmpa_tl#1
\computeTwoNorm\l_tmpb_tl#2
\int_step_inline:nn{\fparray_count:N#1}{
\fparray_gset:Nnn#1{##1}{\fparray_item:Nn#1{##1}/\l_tmpa_tl}
\fparray_gset:Nnn#2{##1}{\fparray_item:Nn#2{##1}/\l_tmpb_tl}
}
}}
% re-centres about (0,0) polygon coordinates (two fparrays)
\cs_new_protected_nopar:Npn\recentrePolygon#1#2{{
\fp_zero:N\l_tmpa_fp
\fp_zero:N\l_tmpb_fp
\int_set:Nn\l_tmpa_int{\fparray_count:N#1}
\int_step_inline:nn{\l_tmpa_int}{
\fp_add:Nn\l_tmpa_fp{\fparray_item:Nn#1{##1}}
\fp_add:Nn\l_tmpb_fp{\fparray_item:Nn#2{##1}}
}
\fp_set:Nn\l_tmpa_fp{\l_tmpa_fp/\l_tmpa_int}
\fp_set:Nn\l_tmpb_fp{\l_tmpb_fp/\l_tmpa_int}
\int_step_inline:nn{\n}{
\fparray_gset:Nnn#1{##1}{\fparray_item:Nn#1{##1}-\l_tmpa_fp}
\fparray_gset:Nnn#2{##1}{\fparray_item:Nn#2{##1}-\l_tmpb_fp}
}
}}
% computes 2-norm of vector argument (arg #2, fparray) and places result
% in tl variable (arg #1)
\cs_new_protected_nopar:Npn\computeTwoNorm#1#2{
\tl_set:Nn#1{0}
\int_step_inline:nn{\fparray_count:N#2}{
\tl_set:Nx#1{\fp_to_tl:n{#1+\fparray_item:Nn#2{##1}*\fparray_item:Nn#2{##1}}}
}
\tl_set:Nx#1{\fp_to_tl:n{sqrt(#1)}}
}
% sorts elements of fparray in place
\cs_new_protected_nopar:Npn\bubbleSort#1{{
\int_set:Nn\l_tmpa_int{\fparray_count:N#1}
\int_do_while:nn{\l_tmpb_int=\c_one_int}{
\int_zero:N\l_tmpb_int
\int_step_inline:nnn{1}{\l_tmpa_int-1}{
\fp_compare:nT{\fparray_item:Nn#1{##1}>\fparray_item:Nn#1{##1+1}}{
\fp_set:Nn\l_tmpa_fp{\fparray_item:Nn#1{##1}}
\fparray_gset:Nnn#1{##1}{\fparray_item:Nn#1{##1+1}}
\fparray_gset:Nnn#1{##1+1}{\l_tmpa_fp}
\int_set_eq:NN\l_tmpb_int\c_one_int
}
}
\int_decr:N\l_tmpa_int
}
}}
% subtracts second from first fparray argument, changing the first in place
\cs_new_protected_nopar:Npn\subtractSecondFromFirst#1#2{
\int_step_inline:nn{\fparray_count:N#1}{
\fparray_gset:Nnn#1{##1}{\fparray_item:Nn#1{##1}-\fparray_item:Nn#2{##1}}
}
}
% copies elements of second into elements of first fparray argument
\cs_new_protected_nopar:Npn\copySecondToFirst#1#2{
\int_step_inline:nn{\fparray_count:N#1}{
\fparray_gset:Nnn#1{##1}{\fparray_item:Nn#2{##1}}
}
}
% returns polygon vertex coordinate out of two fparray arguments by index;
% arg #1: vertex index (integer),
% arg #2, #3: x and y fparrays with vertex coordinates
\cs_new_nopar:Npn\getVertexCoord#1#2#3{
\fparray_item_to_tl:Nn#2{#1},\fparray_item_to_tl:Nn#3{#1}
}
\let\fpCompareTrue\fp_compare:nT % alias for use outside of ExplSyntax
\let\intStepInline\int_step_inline:nn
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% initialise starting random polygon
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% allocate fparrays for polygon x and y coordinates
\fparray_new:Nn\polyX{\n}
\fparray_new:Nn\polyY{\n}
% initialise coordinates with random values
\sys_gset_rand_seed:n{691422}
\int_step_inline:nn{\n}{
\fparray_gset:Nnn\polyX{#1}{rand()}
\fparray_gset:Nnn\polyY{#1}{rand()}
}
% centre polygon around (0,0)
\recentrePolygon\polyX\polyY
% normalise polygon coordinates
\normalisePolygon\polyX\polyY
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\fparray_new:Nn\polyXCurr{\n} % for convergence test
\fparray_new:Nn\polyYCurr{\n}
\fparray_new:Nn\polyXPrev{\n}
\fparray_new:Nn\polyYPrev{\n}
\ExplSyntaxOff
\begin{document}
\gdef\isConverged{0}%
\begin{animateinline}[controls]{25}
\multiframe{\inteval{\animationStepsMax+1}}{i=0+\iterationsPerFrame}{
\begin{tikzpicture}[scale=\scalePicture]
\useasboundingbox (\bboxLowerLeft) rectangle (\bboxUpperRight);
\draw[line join=bevel,every node/.style={circle,draw,fill=white,inner sep=0pt,minimum size=2pt}]
(\getVertexCoord{1}\polyX\polyY) node {}
foreach \i in {2,...,\inteval{\n}} {--(\getVertexCoord{\i}\polyX\polyY) node {}} --cycle;
\node [anchor=south west] at (current bounding box.south west) {Step \i};
\node [label={[inner sep=0pt]left:\scriptsize O},inner sep=0pt] at (0,0) {\tiny$\times$};
\end{tikzpicture}%
\ifnum\isConverged>0\multiframebreak\fi% stop frame generation if converged
% core algorithm
\intStepInline{\iterationsPerFrame-2}{%
\computeEdgeCentres\polyX\polyY% new polygon vertices on edge centres
\ifnum\inteval{\iterationsPerFrame-2}=#1
\normalisePolygon\polyX\polyY% after last iteration, normalise new coordinates
\fi%
}%
% convergence testing
\copySecondToFirst\polyXPrev\polyX%
\copySecondToFirst\polyYPrev\polyY%
\computeEdgeCentres\polyX\polyY% two more iterations
\computeEdgeCentres\polyX\polyY%
\normalisePolygon\polyX\polyY% ... and normalisation
\copySecondToFirst\polyXCurr\polyX%
\copySecondToFirst\polyYCurr\polyY%
\bubbleSort\polyXPrev%
\bubbleSort\polyYPrev%
\bubbleSort\polyXCurr%
\bubbleSort\polyYCurr%
\subtractSecondFromFirst\polyXPrev\polyXCurr%
\subtractSecondFromFirst\polyYPrev\polyYCurr%
\computeTwoNorm\tmpa\polyXPrev%
\computeTwoNorm\tmpb\polyYPrev%
\typeout{coord change vectors: ||dx||=\tmpa, ||dy||=\tmpb}%
\fpCompareTrue{\tmpa<\maxnorm && \tmpb<\maxnorm}{\gdef\isConverged{1}}
}
\end{animateinline}
\end{document}
答案2
这是渐近线代码。请注意,多边形在向椭圆迭代时会缩小。如果您愿意,可以取消注释 5 行注释,以随着迭代的进行而扩大路径大小。
我编译此代码以asy solution -noV -f pdf
创建多页 PDF 文件。将您的 PDF 查看器设置为查看单页,然后您可以使用键盘上的“Page Down”进行“动画”。
unitsize(1inch);
int numPoints = 20;
int numIterations = 100;
path updateToMidpoints(path pin)
{
path p;
for (int i = 0; i < length(pin); ++i)
{
p = p--(0.5*(point(pin, i) + point(pin, i+1)));
}
real scaleFactor = 1.0;
// pair startingDimensions = max(pin) - min(pin);
// pair endingDimensions = max(p) - min(p);
// real xscale = startingDimensions.x / endingDimensions.x;
// real yscale = startingDimensions.y / endingDimensions.y;
// real scaleFactor = xscale < yscale ? xscale : yscale;
p = scale(scaleFactor)*(p--cycle); // scale
return p;
}
path p = (unitrand(), unitrand());
for (int i = 1; i < numPoints; ++i) { p = p--(unitrand(), unitrand()); }
p = scale(3)*shift(-0.5,-0.5)*(p--cycle);
for (int i = 0; i < numIterations; ++i)
{
draw(p);
dot(p, 3+red);
dot((0,0), 3+black);
newpage();
p = updateToMidpoints(p);
}
答案3
由于 PGF/TikZ 并不关心引用的坐标/节点是否真的在另一张图片中(除非remember picture
设置),我们可以简单地循环遍历所有顶点并将新顶点放置在它们之间的中点。每个顶点都存在两次,因为我们不能简单地覆盖它们,因为每个顶点也用于计算新位置两次。
可用于仅显示每个only every = k
钾图。这个实现起来非常简单,并且需要一个偶数(由于后缀的交换)。只计算中间点的部分在 PGF 中,并且还使用了一个实例,\pgfmathloop
这应该比完整\foreach
构造更快。(实际上所有这些\foreach
循环都非常简单。)
宏\tikzrptedo
只是输出每一个钾第一张图,包括放置顶点的第一个实例的第 0 张图。
各种样式允许我们根据图表的数量或步骤等更改可视化效果……
可以进一步优化灵活性。(可以使用 plotmark 代替节点。)
代码
\documentclass[tikz]{standalone}
\usetikzlibrary{calc, graphs}
\newcommand*\tikzrpteset{\pgfqkeys{/tikz/rpte}}% Random Polygon To Ellipse = rpte
\tikzrpteset{
n/.initial=10,
steps/.initial=10,
@vertex/.style={draw, shape=circle, inner sep=+0pt, minimum size=+.5mm},
vertex/.style=rpte/@vertex,
edge/.style=draw,
only every/.initial=1,
every diagram/.style={
x=+5cm, y=+5cm,
execute at begin picture={% consistent bounding box
\node foreach \p in {(0,0), (1,1)} [rpte/@vertex, path only] at \p {};}}}
\newcommand*\tikzrpteswap{\let\temp\rpteSuffixA\global\let\rpteSuffixA\rpteSuffixB\global\let\rpteSuffixB\temp}
\newcommand*\tikzrptedo[1][]{%
\begingroup
\tikzrpteset{#1}%
\pgfmathtruncatemacro\rpteN{\pgfkeysvalueof{/tikz/rpte/n}}%
\pgfmathtruncatemacro\rpteEvery{\pgfkeysvalueof{/tikz/rpte/only every}}%
\pgfmathtruncatemacro\rpteSteps{\pgfkeysvalueof{/tikz/rpte/steps}}%
\pgfmathtruncatemacro\rpteEach{\rpteSteps/\rpteEvery}%
\gdef\rpteSuffixA{'}\gdef\rpteSuffixB{}%
\def\rpteStep{0}\def\rpteDiagram{0}%
\begin{tikzpicture}[
rpte/every diagram,
rpte/diagram \rpteDiagram/.try,
rpte/step \rpteStep/.try]
\node foreach \rpteEach in {1, ..., \rpteN}
[rpte/vertex, rpte/vertex \rpteEach/.try] at (rnd, rnd) (rpteV\rpteEach) {};
\pgfnodealias{rpteV0}{rpteV\rpteN};
\graph[use existing nodes, cycle, edges=rpte/edge]{
\foreach\rpteEach in {1, ..., \rpteN}{rpteV\rpteEach}};
\end{tikzpicture}%
\foreach \rpteDiagram in {1, ..., \rpteEach}{%
\edef\rpteStep{\pgfinteval{\rpteDiagram*\rpteEvery}}%
\begin{tikzpicture}[
rpte/every diagram,
rpte/diagram \rpteDiagram/.try,
rpte/step \rpteStep/.try]
\foreach\rpteIter in {1, ..., \pgfinteval{\rpteEvery-1}}{
\pgfmathloop
\pgfcoordinate
{rpteV\pgfmathcounter\rpteSuffixA}
{\pgfpointlineattime{.5}
{\pgfpointanchor{rpteV\pgfinteval{\pgfmathcounter-1}\rpteSuffixB}{center}}
{\pgfpointanchor{rpteV\pgfmathcounter\rpteSuffixB}{center}}}%
\ifnum\pgfmathcounter<\rpteN
\repeatpgfmathloop
\pgfnodealias{rpteV0\rpteSuffixA}{rpteV\rpteN\rpteSuffixA}%
\tikzrpteswap
}
\node foreach \rpteIter in {1, ..., \rpteN}
[rpte/vertex, rpte/vertex \rpteIter/.try,
at={($(rpteV\pgfinteval{\rpteIter-1}')!.5!(rpteV\rpteIter')$)},
name=rpteV\rpteIter] {};
\pgfnodealias{rpteV0}{rpteV\rpteN}
\graph[use existing nodes, cycle, edges=rpte/edge]{\foreach\rpteIter in {1, ..., \rpteN}{rpteV\rpteIter}};
\end{tikzpicture}%
}%
\endgroup}
\begin{document}
\pgfmathsetseed{691422}
\tikzrptedo
\pgfmathsetseed{691422}
\tikzrptedo[
steps=1000, n=50, only every=20,
vertex/.append code={\ifnum\rpteStep>200 \tikzset{shape=coordinate}\fi},
every diagram/.append style={
execute at end picture={
\node[above right] {Step: \rpteStep};}}]
\end{document}