Bonjour messieurs,
Dans un elan de bonte, et ayant besoin du bouzin, je me suis mis a traduire cet algorithme de triangulation de delaunay du lua vers le C++.
Voici le bout de code en question sur lequel je bloque.
Code LUA : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101 --- Triangulates a set of given vertices -- @param ... a `vargarg` list of objects of type `Point` -- @return a set of objects of type `Triangle` -- @usage -- local Delaunay = require 'Delaunay' -- local Point = Delaunay.Point -- local p1, p2, p3, p4 = Point(), Point(2,0), Point(1,1), Point(1,-1) -- local triangles = Delaunay.triangulate(p1, p2, p3, p4) -- for i = 1, #triangles do -- print(triangles[i]) -- end -- function Delaunay.triangulate(...) local vertices = {...} local nvertices = #vertices assert(nvertices > 2, "Cannot triangulate, needs more than 3 vertices") if nvertices == 3 then return {Triangle(unpack(vertices))} end local trmax = nvertices * 4 local minX, minY = vertices[1].x, vertices[1].y local maxX, maxY = minX, minY for i = 1, #vertices do local vertex = vertices[i] vertex.id = i if vertex.x < minX then minX = vertex.x end if vertex.y < minY then minY = vertex.y end if vertex.x > maxX then maxX = vertex.x end if vertex.y > maxY then maxY = vertex.y end end local dx, dy = maxX - minX, maxY - minY local deltaMax = max(dx, dy) local midx, midy = (minX + maxX) * 0.5, (minY + maxY) * 0.5 local p1 = Point(midx - 2 * deltaMax, midy - deltaMax) local p2 = Point(midx, midy + 2 * deltaMax) local p3 = Point(midx + 2 * deltaMax, midy - deltaMax) p1.id, p2.id, p3.id = nvertices + 1, nvertices + 2, nvertices + 3 vertices[p1.id] = p1 vertices[p2.id] = p2 vertices[p3.id] = p3 local triangles = {} triangles[#triangles + 1] = Triangle(vertices[nvertices + 1], vertices[nvertices + 2], vertices[nvertices + 3] ) for i = 1, nvertices do local edges = {} local ntriangles = #triangles for j = #triangles, 1, -1 do local curTriangle = triangles[j] if curTriangle:inCircumCircle(vertices[i]) then edges[#edges + 1] = curTriangle.e1 edges[#edges + 1] = curTriangle.e2 edges[#edges + 1] = curTriangle.e3 remove(triangles, j) end end for j = #edges - 1, 1, -1 do for k = #edges, j + 1, -1 do if edges[j] and edges[k] and edges[j]:same(edges[k]) then remove(edges, j) remove(edges, k-1) end end end for j = 1, #edges do local n = #triangles assert(n <= trmax, "Generated more than needed triangles") triangles[n + 1] = Triangle(edges[j].p1, edges[j].p2, vertices[i]) end end for i = #triangles, 1, -1 do local triangle = triangles[i] if (triangle.p1.id > nvertices or triangle.p2.id > nvertices or triangle.p3.id > nvertices) then remove(triangles, i) end end for _ = 1,3 do remove(vertices) end return triangles end return Delaunay
Et voici mon code en C++
Et voici ce qui cloche
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88 std::vector<Triangle> Delaunay::triangulate(std::vector<Vec2f> points) { std::size_t npoints = points.size(); int trmax = npoints * 4; float minX = points[0].getX(); float minY = points[0].getY(); float maxX = minX; float maxY = minY; for(std::size_t i = 0; i < points.size(); ++i) { points[i].id = i; if (points[i].getX() < minX) minX = points[i].getX(); if (points[i].getY() < minY) minY = points[i].getY(); if (points[i].getX() > maxX) maxX = points[i].getX(); if (points[i].getY() > maxY) maxY = points[i].getY(); } float dx = maxX - minX; float dy = maxY - minY; float deltaMax = std::max(dx, dy); float midx = (minX + maxX) * 0.5; float midy = (minY + maxY) * 0.5; Vec2f p1(midx - 2 * deltaMax, midy - deltaMax); Vec2f p2(midx, midy + 2 * deltaMax); Vec2f p3(midx + 2 * deltaMax, midy - deltaMax); p1.id = npoints + 1; p2.id = npoints + 2; p3.id = npoints + 3; points.push_back(p1); points.push_back(p2); points.push_back(p3); std::vector<Triangle> triangles; triangles.push_back(Triangle(points[points.size() - 1], points[points.size() - 2], points[points.size() - 3])); for(int i = 0; i < static_cast<int>(npoints); ++i) { std::vector<Edge> edges; for(int j = static_cast<int>(triangles.size()); j-- > 0; ) { Triangle curTriangle = triangles[j]; if(curTriangle.inCircumCircle(points[i])) { edges.push_back(curTriangle.getE1()); edges.push_back(curTriangle.getE2()); edges.push_back(curTriangle.getE3()); triangles.erase(triangles.begin() + j); } } for(int j = static_cast<int>(edges.size()) - 1; --j > 0; ) { for(int k = edges.size(); --k > j + 1; ) { if(edges[j].equals(edges[k])) { edges.erase(edges.begin() + j); edges.erase(edges.begin() + k - 1); --k; } } } for(int j = 0; j < static_cast<int>(edges.size()); ++j) { int n = triangles.size(); std::cout << n << " " << trmax << std::endl; assert(n <= trmax && "Generated more than needed triangles"); triangles.push_back(Triangle(edges[j].getP1(), edges[j].getP2(), points[i])); } } for(int i = static_cast<int>(triangles.size()); --i > 0; ) { Triangle triangle = triangles[i]; if(triangle.getP1().id > static_cast<int>(npoints) || triangle.getP2().id > static_cast<int>(npoints) || triangle.getP3().id > static_cast<int>(npoints)) { triangles.erase(triangles.begin() + i); } } return triangles; }
D'apres le code lua, je suis sense generer 12 triangles pour un set de 10 points. Sauf que mon code C++ (en virant le assert), monte jusqu'a 60 n, et genere 1 miserable triangle.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3 pudding: delaunay.cpp:80: static std::vector<Triangle> Delaunay::triangulate(std::vector<Vec2f>): Assertion `n <= trmax && "Generated more than needed triangles"' failed. [1] 11925 abort (core dumped) ./pudding
Et j'ai aucune idee de pourquoi ni comment ca cloche.
Tous les fichier sont dans ce beau zip. Je me replonge dans mon code pour truver ce qui cloche.
Merci d'avance!
Partager