Triangle - 1point3acres

https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=207550&extra=&page=1题目没法描述，哪天画个图片再贴上来，和图形有关的，三角形套三角形，问怎么输出一堆点，然后用已知的画线api生成某一depth的图形，不知道以前面经里有没有这道题。然后就是一直没思路，问hint也没什么有用信息，三哥就说写个简单的情况，然后突然想出点思路，然后三哥一直抠细节，问的心烦，一会问这一会问那，根本没法思考，然后看着电脑的时间不多了，心态也不好了，最后代码就写了一点点，心里当时已经是死灰一片，最后和他repeat了一下思路，貌似之前他还没有理解我要干什么，最后问他怎么做，说我on the right track。出来后感觉三哥就是个坑，占用那么多时间说其他的

输入三个顶点和depth. check 1point3acres for more. 输出一堆点 问somehow，用这些点两两连线把depth的图画出来

画三角形那道题可不可以理解为level order traversal 的变种，bfs那种的。据我观察，每加深一层，就是把一个当前的三角形分成三个三角形（中间的倒三角形不算，这样画出的边也没有重合）写了一下代码，constructor没有详写

1. public class Point {
2.         int x, y;
3.         public Point() {}
4. }
5. public class Triangle {
6.         Point A, B, C;
7.         public Triangle(Point A, Point B, Point C){}
8. }
9. public Point getMid(Point A, Point B) {
10.         int x = (A.x + B.x) / 2, y = (A.y + B.y) / 2; //不考虑double的情况
11.         return new Point(x, y);
12. }
13. 
    
14. public void drawLine(Point A, Point B) {}
15. public void drawTri(Triangle tri) {
16.         drawLine(tri.A, tri.B);
17.         drawLine(tri.B, tri.C);
18.         drawLine(tri.A, tri.C);
19. }
20. public void drawGraph(Point A, Point B, Point C, int depth) {
21.         Triangle basic = new Triangle(A, B, C);
22.         Queue<Triangle> q = new LinkedList<Triangle>();
23.         q.offer(basic);
24.         for(int i = 0; i < depth; i++) {
25.                 int size = q.size();
26.                 for(int j = 0; j < size; j++) {
27.                         basic = q.poll();
28.                         Point mid_AB = getMid(basic.A, basic.B);
29.                         Point mid_AC = getMid(basic.A, basic.C);
30.                         Point mid_BC = getMid(basic.B, basic.C);
31.                         q.offer(new Triangle(basic.A, mid_AC, mid_AB));
32.                         q.offer(new Triangle(basic.B, mid_BC, mid_AB));
33.                         q.offer(new Triangle(basic.C, mid_BC, mid_AC));
34.                 }. check 1point3acres for more.
35.         }
36.         while(!q.isEmpty()) {. check 1point3acres for more.
37.                 drawTri(q.poll());
38.         }
39. }

1. class Point(object):
2.     def __init__(self, x, y):
3.         self.x = x
4.         self.y = y
5. 
   
6. 
   
7. def draw_line(p1, p2):
8.     ninja.penup()
9.     ninja.goto(p1.x, p1.y)
10.     ninja.pendown()
11.     ninja.goto(p2.x, p2.y)
12. 
    
13. 
    
14. def draw_trangle(p1, p2, p3):
15.     draw_line(p1, p2)
16.     draw_line(p2, p3)
17.     draw_line(p3, p1)
18. 
    
19. 
    
20. def dfs(p1, p2, p3, depth):
21.     draw_trangle(p1, p2, p3)
22.     if depth:
23.         m1 = Point((p1.x+p2.x)/2., (p1.y+p2.y)/2.)
24.         m2 = Point((p2.x+p3.x)/2., (p2.y+p3.y)/2.)
25.         m3 = Point((p3.x+p1.x)/2., (p3.y+p1.y)/2.)
26.         depth -= 1
27.         dfs(p1, m1, m3, depth)
28.         dfs(p2, m1, m2, depth)
29.         dfs(p3, m2, m3, depth)

我估计应该是这个意思：假设给定一个类似于“void drawLine(const Pt& p1, const Pt& p2)”的API，我也是用的recursion.

我想的办法是构建一个类似金字塔的点阵，depth增加的时候插入新的一层点阵并按照规律画线，不过显然层主的这个方法好多了

1. typedef pair<double,double> Pt;. check 1point3acres for more.
2. typedef vector<Pt> Tri;
3. typedef vector<Tri> Tris;
4. 
   
5. // assumed given API. check 1point3acres for more.
6. void drawLine(const Pt& p1, const Pt& p2); 
7. 
   
8. // utility function to draw a given triangle
9. void drawTri(const Tri& tri) {
10.   for (int i = 0; i < 3; i++) drawLine(tri[i%3], tri[(i+1)%3]);
11. }
12. 
    
13. // dfs routine to draw central triangle and collect 
14. // 4 smaller triangles for each big trianlges
15. Tris dfs(const Tris& tris) {
16.   Tris res;    -baidu 1point3acres
17.   for (const auto& t:tris) {
18.     drawTri(t); Tri tri;
19.     // construct and draw central triangle
20.     for (int i = 0; i < 3; i++)
21.       tri.push_back(Pt((t[i%3].first+t[(i+1)%3].first)/2.0,(t[i%3].second+t[(i+1)%3].second)/2.0));
22.     drawTri(tri);
23.     // collect all 4 smaller triangles into result
24.     res.push_back(tri);    
25.     for (int i = 0; i < 3; i++) {
26.       res.push_back({t[i], res[0][i], res[0][(i+2)%3]});
27.     }
28.   } 
29.   return res;
30. }
31. . 1point3acres
32. // main function to draw triangles with given depth
33. void drawTriangles(const Tri& tri, unsigned int depth) {
34.   Tris tris = { tri };
35.   while (depth-- > 0) tris = dfs(tris);
36. }