kdtree/kdtree.html at master · code-compGeom-class/kdtree · 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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">


<style type="text/css">
body { margin:1em;}
pre { background-color:#ddd; padding:10px; margin:20px;}
h1 { font-size=5;color:black}
h2 { font-s1ize=4; color:blue}
h3 { font-size=3; color:green;}
</style>

<html> <head>
<title></title>
</head>

<body>
<h2>Building a 2d-tree</h2>


In this assignment the goal is to build and visualize a
two-dimensional kd-tree for a set of points in the plane.
<ol>
<li>Part 1: build the kd-tree.
<li>Part 2: render/visualize the kd-tree, and make it look like a Mondrian painting.
</ol>


<h2>Representing the kd-tree</h2>

<p>For this asignment, make your <tt>point2D</tt> store the coordinates as doubles, not ints.

<p>You will need to define a data structure to encode a kd-tree
such as below --- feel free to refine as needed.

<pre>
typedef struct _treeNode {
     point2D p; /* If this is a leaf node,  p represents the point stored in this leaf.
                  If this is not a leaf node,  p represents the horizontal or vertical line
                  stored in this node. For a vertical line, p.y is
                  ignored. For a horizontal line, p.x is ignored
                */
     char type; / * this can be 'h' (horizontal) or 'v' (vertical), or 'l' (leaf)
                    depending whether the node splits with a horizontal line or  vertical line.
                    Technically this should be an enum.
                */
     treeNode  *left, *right; /* left/below and right/above children. */
} treeNode;

typedef struct _kdtree{
   treeNode* root;

   int count; //number of nodes  in the tree

   int height; //height of tree
} kdtree;
</pre>


In c++, it will look more like this:

<pre>
class TreeNode {
  private:
     point2D* p;
     char type;
     TreeNode *left, *rigt;
  public:
     TreeNode(Point2D*);
     ~TreeNode();
};

class Kdtree {
  private:
     TreeNode* root;
     int count ; //number of leaves in the tree
     int height;  //height of the tree

     //build the kd-tree
     TreeNode* buildKdtree(Point2D* sortedbyx, Point* sortedbyy, int n, int cuttype);

  public:
     Kdtree(Point2D* p, int n );
     ~Kdtree();
     ...
};
</pre>


<p><b>Note: Feel free to use Vectors instead of arrays everywhere. </b>


<p>You'll need to write the basic primitives for operating on a treeNode and
on a kdtree, such as creating a node and creating an empty tree, printing a
node, and printing a tree.


<p> For example, include a function that prints some basic info about the kd-tree,
such as number of nodes, and height. Call this function in the main
functin so that we can see its output.


<h2>Building a kd-tree</h2>

<p>The function will take as argument an array of points and returns the kd-tree.

<p>In C it might look like this:

<pre>
/* Build a kd-tree for the set of n points, where each leaf cell
   contains  1 point.
   Return a pointer to the root.
*/
kdtree*  buildkdtree(point2D* points, int n)
</pre>

In cpp write a constructor that looks like this:

<pre>
  public:
     Kdtree(Point2D p[], int n );
</pre>


<p>Note: Since your coordinates are doubles and you generate the
points randomly, its unlikely that you'll get coincident points in
your set of points. If your coordinates are ints, you'll need to
consider this issue. Below we assume that the points are
<b>distinct</b>.


<p>The generic constructor should first sort the points by
Sort <tt>points</tt> by x-coord and by y-coord using system
<tt>qsort</tt> (or a different sort).

<pre>
point2D *points-by-x, *points-by-y;
//allocate them, copy data from points then sort them
</pre>

<p>You need to use system qsort and define appropriate comparison
functions.

Points that have same x-coordinate or same y-coordinate can cause
issues with the partition (for example...). To handle these cases
elegantly think of using comparison functions that uniquely order the
points:


<pre>
//orders the points by x, and for same x in y-order
int leftToRightCmp(Point2D a, Point2D* b) {
    ...
}

//orders the points by y, and for same y in x-order
int bottomToTopCmp(Point2D a, Point2D* b) {
   ...
}
</pre>


<p>After sorting the points, the function should call a helper
function that takes more arguments and is recursive. In C it may look
like this:


<pre>
treeNode* kdtree_build_rec(point2D* points-sorted-by-x, point2D* points-sorted-by-y, int n, ...)
 </pre>

In cpp it may look like this:
<pre>
TreeNode* Kdtree::buildKdtree(Point2D* points-sortedbyx, Point* points-sortedbyy, int n, int cuttype);
</pre>

This helper function should build the kd-tree recursively. It should
probably take the depth of the current node as a parameter and use it to
decide whether to split vertically or horizontally.


<h2>The median and degenerate cases</h2>


<p>The main challenge in this function will be make sure the recursion
stops.

<p> Stop the recursion when the node contains 1 point (and possibly
earlier if necessary, depending on how you handle degenerate cases).


<p>The median is the value in the middle index of the sorted array
(sorted by x or by y, depending on the type of node).  One way to set
up the recursive calls is to put all points with x-coord smaller or
equal to the median to the left, and the others on the right.  Think
of what happens when you have points with same coordinates, for
example consider the case of points on the same vertical line. All
x-coordinates are the same, and if you distribute all the points with
x-coord smaller or equal to the median to the left, all points end up
on the left side. You need to think if its possible to generate
infinite recursion.

<p>For e.g. consider the points <tt>(2,6), (3,6), (3,5)</tt> examined
in the x-coordinate. Middle point is (3,6). But the third's point
x-value is also 3, so it will go on the left side. Thus this passes
the entire array to the next level. Then we examine them in the
y-coordinate: <tt>(3,5), (3,6), (2,6)</tt> Middle point is (3,6). But
the third point has same y-coord as the median, which means it will
also go on the left side. Thus this passes entire array to next level
again, i.e. infinite recursion. These points are not coincident but
are collinear in just the wrong way to cause infinite recursion.

<p>There are other ways to handle this, but an elegent way is to use
the <tt>leftToRightCmp()</tt> instead of just comparing by
x. In <tt>leftToRight</tt> order, no two points are equal (unless
there are duplicate points, which we assume there aren't).  All points
before the median are strictly smaller than the median <tt>in
leftToRight</tt> order. Put differently, a point <tt>p</tt> goes to
the left of the median if <tt>p</tt> is smaller than the median
in <tt>leftToRight()</tt> order, and goes to the right of the median
otherwise. This way points are distributed evenly left and right and
there is no infinite loop. It all works simply, when using the right
comparator.


<h2>Maintaining <tt>points-by-x</tt> and <tt>points-by-y</tt> through
the recursive calls</h2>

Allocate the sorted arrays for the recursive calls

<pre>
P1-sorted-by-x, P1-sorted-by-y
P2-sorted-by-x, P2-sorted-by-y
</pre>

(you know their sizes), then do a pass through
<tt>points-sorted-by-x</tt> and <tt>points-sorted-by-y</tt> and put
them on the correct side.
<pre>
 if leftToRight(p, median) == -1: p goes to P1
 else p goes to P2
</pre>

<p>In case you allocate the arrays (as opposed to using Vectors):
Don't forget to free the arrays that you are done with, as there is no
garbage collection in c/cpp.


<h2>Testing</h2>

It goes without saying that you need to throroughly test your code.
The goal of testing is to find bugs.  Try to break your code. Once you
find a bug, try to reproduce it on the smallest possible input ----
it's no fun debugging on an input of half a million points.

<p>Once it works on small inputs, run on sets of random points with
values for various <tt>n</tt>. Make it so that when you press the
space bar you get a different set of random points.


<p>Teams shoud generate special initializers and everyone should include
everyone's test cases in their code.


<hr>
<h2>Part 2: Rendering the kd-tree</h2>

Write a function that renders the kd-tree in OpenGL.
Use the code for the previous assignments.  The OpenGL part  is
pretty easy --- basically you need  to draw a filled rectangle/polygon for each leaf node, corresponding to the regionof that leaf.

<p>This means you shoud probably store regions in nodes.

<p>The input points are generated in the range [0,WINDOWSIZE] x [0,
WINDOWSIZE]. This is the region fo the root.


<p>Render your kd-tree so that it looks similar to a Mondrian
painting. Below are some examples.

 <center>

<a href="mondrian1.png"><img src="mondrian1.png" border="0" height="300" align="middle"></a>
<a href="mondrian2.png"><img src="mondrian2.png" border="0" height="300" align="middle"></a>
<a href="mondrian3.png"><img src="mondrian3.png" border="0" height="300" align="middle"></a>
<a href="mondrian4.png"><img src="mondrian4.png" border="0" height="300" align="middle"></a>

<a href="painting.png"><img src="painting.png" border="0" height="300"
align="middle"></a>
<a href="painting2.png"><img src="painting2.png" border="0" height="300" align="middle"></a>
</center>


<h3>Team work</h3>

You are encouraged to do pair-programming, but feel free to work
alone.


<h3>What to turn in</h3>

<ul>

  <li> Check in your code on GitHub.

  <li>Provide a README that describes
the state of your code (how to run it, does it work on all test cases, do you know of
any bugs, did you impemnent any extra features, etc). Basically what
  you want people to know about your code.

  <li>Fill in the <a href="./selfreport-kdtrees.pdf">self-reflection report</a> and get it to me (either hard
  copy in class or DM on slack).

  </ul>


<h2>Enjoy!</h2>


</body> </html>