From: Maxime Chupin (escudo) Date: Tue, 29 Nov 2016 16:11:34 +0000 (+0100) Subject: Première version Voronoi avec MetaPost X-Git-Url: https://melusine.eu.org/syracuse/G/git/?p=delaunay.git;a=commitdiff_plain;h=a00e38bda1dd258080ec6a649d61b1f577ccb71a Première version Voronoi avec MetaPost --- diff --git a/luamesh.lua b/luamesh.lua index 26a3cbf..4d255a1 100644 --- a/luamesh.lua +++ b/luamesh.lua @@ -207,6 +207,81 @@ function circoncircle(M, N, P) return Out, rad -- (center [Point], R [float]) end +-- compute the list of the circumcircle of a triangulation +function listCircumCenter(listPoints,triangulation) + list = {} + for j=1,#triangulation do + A = listPoints[triangulation[j][1]] + B = listPoints[triangulation[j][2]] + C = listPoints[triangulation[j][3]] + center, radius = circoncircle(A,B,C) + table.insert(list,{x=center.x,y=center.y,r=radius}) + end + return list +end + +-- find the three neighbour triangles of T +function findNeighbour(T,i,triangulation) + -- T : triangle + -- i : index of T in triangualation + -- triangulation + + list = {} + -- define the three edge + e1 = {T[1],T[2]} + e2 = {T[2],T[3]} + e3 = {T[3],T[1]} + for j=1,#triangulation do + if j~= i then + if(edgeInTriangle(e1,triangulation[j])) then + table.insert(list,j) + end + if(edgeInTriangle(e2,triangulation[j])) then + table.insert(list,j) + end + if(edgeInTriangle(e3,triangulation[j])) then + table.insert(list,j) + end + end + end + return list +end + +-- test if edge are the same (reverse) +function equalEdge(e1,e2) + if(((e1[1] == e2[1]) and (e1[2] == e2[2])) or ((e1[1] == e2[2]) and (e1[2] == e2[1]))) then + return true + else + return false + end +end + +-- test if the edge belongs to the list +function edgeInList(e,listE) + output = false + for i=1,#listE do + if(equalEdge(e,listE[i])) then + output = true + end + end + return output +end + +-- build the edges of the Voronoi diagram with a given triangulation +function buildVoronoi(listPoints, triangulation) + listCircumCircle = listCircumCenter(listPoints, triangulation) + listVoronoi = {} + for i=1,#listCircumCircle do + listN = findNeighbour(triangulation[i],i,triangulation) + for j=1,#listN do + edge = {i,listN[j]} + if( not edgeInList(edge, listVoronoi)) then + table.insert(listVoronoi, edge) + end + end + end + return listVoronoi +end -------------------------- TeX -- build the list of points @@ -252,6 +327,81 @@ function rectangleList(a,b,nbrA,nbrB) return listPoints end + +-- trace Voronoi with MP +function traceVoronoiMP(listPoints, triangulation,listVoronoi, points, tri) + listCircumC = listCircumCenter(listPoints,triangulation) + output = ""; + output = output .. " pair MeshPoints[];" + for i=1,#listPoints do + output = output .. "MeshPoints[".. i .. "] = (" .. listPoints[i].x .. "," .. listPoints[i].y .. ")*u;" + end + output = output .. " pair CircumCenters[];" + for i=1,#listCircumC do + output = output .. "CircumCenters[".. i .. "] = (" .. listCircumC[i].x .. "," .. listCircumC[i].y .. ")*u;" + end + if(tri=="show") then + for i=1,#triangulation do + PointI = listPoints[triangulation[i][1]] + PointJ = listPoints[triangulation[i][2]] + PointK = listPoints[triangulation[i][3]] + if(triangulation[i].type == "bbox") then + output = output .. "draw (".. PointI.x ..",".. PointI.y ..")*u--("..PointJ.x..",".. PointJ.y ..")*u--("..PointK.x..",".. PointK.y ..")*u--cycle withcolor \\luameshmpcolorBbox;" + else + output = output .. "draw (".. PointI.x ..",".. PointI.y ..")*u--("..PointJ.x..",".. PointJ.y ..")*u--("..PointK.x..",".. PointK.y ..")*u--cycle withcolor \\luameshmpcolor;" + end + end + end + for i=1,#listVoronoi do + PointI = listCircumC[listVoronoi[i][1]] + PointJ = listCircumC[listVoronoi[i][2]] + output = output .. "draw (".. PointI.x ..",".. PointI.y ..")*u--("..PointJ.x..",".. PointJ.y ..")*u withcolor \\luameshmpcolorVoronoi;" + end + if(points=="points") then + j=1 + for i=1,#listPoints do + if(listPoints[i].type == "bbox") then + output = output .. "dotlabel.llft (btex $\\MeshPoint^{*}_{"..j.."}$ etex, (" .. listPoints[i].x ..",".. listPoints[i].y .. ")*u ) withcolor \\luameshmpcolorBbox ;" + j=j+1 + else + output = output .. "dotlabel.llft (btex $\\MeshPoint_{" .. i .. "}$ etex, (" .. listPoints[i].x ..",".. listPoints[i].y .. ")*u ) withcolor \\luameshmpcolor ;" + end + end + for i=1,#listCircumC do + output = output .. "dotlabel.llft (btex $\\CircumPoint_{" .. i .. "}$ etex, (" .. listCircumC[i].x ..",".. listCircumC[i].y .. ")*u ) withcolor \\luameshmpcolorVoronoi ;" + end + else + j=1 + for i=1,#listPoints do + if(listPoints[i].type == "bbox") then + output = output .. "drawdot (" .. listPoints[i].x ..",".. listPoints[i].y .. ")*u withcolor \\luameshmpcolorBbox withpen pencircle scaled 3;" + j=j+1 + else + output = output .. "drawdot (" .. listPoints[i].x ..",".. listPoints[i].y .. ")*u withcolor \\luameshmpcolor withpen pencircle scaled 3;" + end + end + for i=1,#listCircumC do + output = output .. "drawdot (" .. listCircumC[i].x ..",".. listCircumC[i].y .. ")*u withcolor \\luameshmpcolorVoronoi withpen pencircle scaled 3;" + end + end + + return output +end + + + +-- buildVoronoi with MP +function buildVoronoiMPBW(chaine,mode,points,bbox,scale,tri) + listPoints = buildList(chaine, mode) + triangulation = BowyerWatson(listPoints,bbox) + listVoronoi = buildVoronoi(listPoints, triangulation) + output = traceVoronoiMP(listPoints,triangulation,listVoronoi,points,tri) + output = "\\leavevmode\\begin{mplibcode}beginfig(0);u:="..scale.. ";" .. output .."endfig;\\end{mplibcode}" + tex.sprint(output) +end + + + -- trace a triangulation with TikZ function traceMeshTikZ(listPoints, triangulation,points,color,colorBbox) output = "" diff --git a/luamesh.sty b/luamesh.sty index ae3db83..de6d9e7 100644 --- a/luamesh.sty +++ b/luamesh.sty @@ -153,6 +153,138 @@ % \fi% }% +%%%%%%%%%%%%%%%% the buildVoronoi command +%% the user can write code (tikz or MP) +%% before and after the generated code +\define@boolkey{buildVoronoiInc}{tikz}[true]{}% +%% show the bounding box for delaunay +\define@choicekey*{buildVoronoiInc}{bbox}[\val\nr]{none, show}{% + \ifcase\nr\relax% + \def\luameshval@bvi@bbox{none}% + \or% + \def\luameshval@bvi@bbox{bbox}% + \fi% +}% +%% the scale +\define@key{buildVoronoiInc}{scale}[1cm]{\def\luameshval@bvi@scale{#1}}% +%% print ponits ? +\define@choicekey*{buildVoronoiInc}{print}[\val\nr]{none, points}{% + \ifcase\nr\relax% + \def\luameshval@bvi@print{none}% + \or% + \def\luameshval@bvi@print{points}% + \fi% +}% +%% the name of the point +\define@key{buildVoronoiInc}{meshpoint}[P]{\def\luameshval@bvi@meshpoint{#1}}% +%% the mode for reading the points +\define@choicekey*{buildVoronoiInc}{mode}[\val\nr]{int, ext}{% + \ifcase\nr\relax% + \def\luameshval@bvi@mode{int}% + \or% + \def\luameshval@bvi@mode{ext}% + \fi% +}% +%% the name of the color of drawing +\define@key{buildVoronoiInc}{color}[black]{\def\luameshval@bvi@color{#1}}% +%% the name of the color of drawing the bbox +\define@key{buildVoronoiInc}{colorBbox}[black]{\def\luameshval@bvi@colorbbox{#1}}% +% +\presetkeys{buildVoronoiInc}{tikz=false,bbox=none,scale, meshpoint,mode=int,print=none,color,colorBbox}{}% +% +\newcommand*{\buildVoronoiBWinc}[4][]{% + % #1 : optionnal arguments + % #2 : the string containing the list of points + % (x1,y1);(x2,y2);... or the name file containing the points + % #3 : the code to place before the generated one + % #4 : the code to place after the generated one + \setkeys{buildVoronoiInc}{#1} % + \def\MeshPoint{\luameshval@bvi@meshpoint}% + \ifKV@buildVoronoiInc@tikz% if we are using tikz + \directlua{% + buildVoronoiTikZBWinc("#2","\luaescapestring{\unexpanded{#3}}","\luaescapestring{\unexpanded{#4}}","\luameshval@bvi@mode","\luameshval@bvi@print","\luameshval@bvi@bbox","\luameshval@bvi@scale","\luameshval@bvi@color","\luameshval@bvi@colorbbox")% + }% + \else % we are using MP + \mplibcolor{\luameshmpcolor}{\luameshval@bvi@color}% + \mplibcolor{\luameshmpcolorBbox}{\luameshval@bvi@colorbbox}% + \directlua{% + buildVoronoiMPBWinc("#2","\luaescapestring{\unexpanded{#3}}","\luaescapestring{\unexpanded{#4}}","\luameshval@bvi@mode","\luameshval@bvi@print","\luameshval@bvi@bbox","\luameshval@bvi@scale")% + }% + % + \fi% +}% +% +%%%%%%%%%%%%%%%% the buildVoronoiBW command +%% the code is complete and we don't have any callbacks +\define@boolkey{buildVoronoi}{tikz}[true]{}% +%% show the bounding box for delaunay +\define@choicekey*{buildVoronoi}{bbox}[\val\nr]{none, show}{% + \ifcase\nr\relax% + \def\luameshval@bv@bbox{none}% + \or% + \def\luameshval@bv@bbox{bbox}% + \fi% +}% +%% the scale +\define@key{buildVoronoi}{scale}[1cm]{\def\luameshval@bv@scale{#1}}% +%% print points +\define@choicekey*{buildVoronoi}{print}[\val\nr]{none, points}{% + \ifcase\nr\relax% + \def\luameshval@bv@print{none}% + \or% + \def\luameshval@bv@print{points}% + \fi% +}% +%% the name of the point +\define@key{buildVoronoi}{meshpoint}[P]{\def\luameshval@bv@meshpoint{#1}}% +%% the name of the circum point +\define@key{buildVoronoi}{circumpoint}[P]{\def\luameshval@bv@circumpoint{#1}}% +%% the mode for reading the points +\define@choicekey*{buildVoronoi}{mode}[\val\nr]{int, ext}{% + \ifcase\nr\relax% + \def\luameshval@bv@mode{int}% + \or% + \def\luameshval@bv@mode{ext}% + \fi% +}% +%% the mode for reading the points +\define@choicekey*{buildVoronoi}{delaunay}[\val\nr]{none, show}{% + \ifcase\nr\relax% + \def\luameshval@bv@delaunay{none}% + \or% + \def\luameshval@bv@delaunay{show}% + \fi% +}% +%% the name of the color of drawing +\define@key{buildVoronoi}{color}[black]{\def\luameshval@bv@color{#1}}% +%% the name of the color of drawing Voronoi +\define@key{buildVoronoi}{colorVoronoi}[red]{\def\luameshval@bv@colorVoronoi{#1}}% +%% the name of the color of drawing the bbox +\define@key{buildVoronoi}{colorBbox}[black]{\def\luameshval@bv@colorbbox{#1}}% +% +\presetkeys{buildVoronoi}{tikz=false,bbox=none,scale, meshpoint,circumpoint,mode=int,print=none,color,colorVoronoi,colorBbox,delaunay=none}{}% +% +\newcommand{\buildVoronoiBW}[2][]{% + % #1 : optionnal arguments + % #2 : the string containing the list of points + % (x1,y1);(x2,y2);... or the name file containing the points + \setkeys{buildVoronoi}{#1} % + \def\MeshPoint{\luameshval@bv@meshpoint}% + \def\CircumPoint{\luameshval@bv@circumpoint}% + \ifKV@buildVoronoi@tikz% if we are using tikz + \directlua{% + buildVoronoiTikZBW("#2","\luameshval@bv@mode","\luameshval@bv@print","\luameshval@bv@bbox","\luameshval@bv@scale","\luameshval@bv@color","\luameshval@bv@colorbbox")% + }% + \else % we are using MP + \mplibcolor{\luameshmpcolor}{\luameshval@bv@color}% + \mplibcolor{\luameshmpcolorBbox}{\luameshval@bv@colorbbox}% + \mplibcolor{\luameshmpcolorVoronoi}{\luameshval@bv@colorVoronoi}% + \directlua{% + buildVoronoiMPBW("#2","\luameshval@bv@mode","\luameshval@bv@print","\luameshval@bv@bbox","\luameshval@bv@scale","\luameshval@bv@delaunay")% + }% + % + \fi% +}% % % %%%%%%%%%%%%%%%%% the draw Points macro diff --git a/test/delaunay.pdf b/test/delaunay.pdf index 33fcbbe..f208943 100644 Binary files a/test/delaunay.pdf and b/test/delaunay.pdf differ diff --git a/test/delaunay.tex b/test/delaunay.tex index 3229ba1..d79b5b7 100644 --- a/test/delaunay.tex +++ b/test/delaunay.tex @@ -139,4 +139,14 @@ colorBbox = black ] {(0,0);(3.5,3);(7,0);(7.5,5);(1.61,3.14);(6,4)}{(3,1)} + +% \def\CircumPoint{y} +% \luampcolor +% \directlua{ +% buildVoronoiMP("mesh.txt","ext","points","","1cm","show") +% } +\buildVoronoiBW[mode=ext]{mesh.txt} +\buildVoronoiBW[mode=ext,delaunay=show]{mesh.txt}\par +\buildVoronoiBW[mode=ext,print=points,delaunay=show,bbox=show]{mesh.txt} + \end{document} diff --git a/test/test.lua b/test/test.lua new file mode 100644 index 0000000..e4e9a91 --- /dev/null +++ b/test/test.lua @@ -0,0 +1,20 @@ +dofile('luamesh.lua') + +listPoints = {{x=0, y=0},{x=1,y=1},{x=1.7,y=0.8},{x=0.6, y=2},{x=3,y=0},{x=1.9,y=2.7}} +print("list of Points") + +for i=1,#listPoints do + print(listPoints[i].x,listPoints[i].y) +end + +triangulation = BowyerWatson(listPoints, "") +print("triangualiton") +for i=1,#triangulation do + print(triangulation[i][1],triangulation[i][2],triangulation[i][3]) +end + +listVoronoi = buildVoronoi(listPoints, triangulation) +print("Voronoi") +for i=1,#listVoronoi do + print(listVoronoi[i][1],listVoronoi[i][2]) +end