RTP_SFPC_SUMMER20/arduino/john-withney-linear-figure/TriangleTree.h at master · murilopolese/RTP_SFPC_SUMMER20 · GitHub

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
template <class Graphics>
class TriangleTree
{
  public:
  short *v[3];
  int z;
  TriangleTree<Graphics> *left, *right;
  int depth;
  char color;

  void set(short *v0, short *v1, short *v2, char color)
  {
    v[0] = v0;
    v[1] = v1;
    v[2] = v2;
    z = v[0][2] + v[1][2] + v[2][2];
    this->color = color;
    left = right = 0;
    depth = 1;
  }

  void draw(Graphics &g)
  {
    if(left)
      left->draw(g);
    g.triangle(v[0], v[1], v[2], color);
    if(right)
      right->draw(g);
  }

  int leftDepth()
  {
    return left ? left->depth : 0;
  }

  int rightDepth()
  {
    return right ? right->depth : 0;
  }

  void recalcDepth()
  {
    int l = leftDepth();
    int r = rightDepth();
    depth = l > r ? l : r;
  }

  int add(TriangleTree **origin, TriangleTree &t)
  {
    int d = 1;
    if(t.z < z)
    {
      if(left)
        d = left->add(&left, t);
      else
        left = &t;
    }
    else
    {
      if(right)
        d = right->add(&right, t);
      else
        right = &t;
    }
    if(depth < d + 1)
      depth = d + 1;
    int l = leftDepth();
    int r = rightDepth();
    if(l > r + 1)
    {
      int ll = left->leftDepth();
      int lr = left->rightDepth();
      if(ll < lr)
      {
        TriangleTree *tl = left;
        left = tl->right;
        tl->right = left->left;
        left->left = tl;
        left->left->recalcDepth();
        left->recalcDepth();
        ll = left->leftDepth();
        lr = left->rightDepth();
        l = leftDepth();
        recalcDepth();
      }
      {
        *origin = left;
        left = left->right;
        (*origin)->right = this;
        depth = lr > r ? lr + 1 : r + 1;
        (*origin)->depth = ll > depth ? ll + 1 : depth + 1;
        return (*origin)->depth + 1;
      }
    }
    if(r > l + 1)
    {
      int rl = right->leftDepth();
      int rr = right->rightDepth();
      if(rr < rl)
      {
        TriangleTree *tr = right;
        right = tr->left;
        tr->left = right->right;
        right->right = tr;
        right->right->recalcDepth();
        right->recalcDepth();
        rr = right->rightDepth();
        rl = right->leftDepth();
        r = rightDepth();
        recalcDepth();
      }
      {
        *origin = right;
        right = right->left;
        (*origin)->left = this;
        depth = rl > l ? rl + 1 : l + 1;
        (*origin)->depth = rr > depth ? rr + 1 : depth + 1;
        return (*origin)->depth + 1;
      }
    }
    return depth;
  }
};