Discussion :

[Invité]

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++

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;
}

Et voici ce qui cloche

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

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.
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!