24 #include "hough_transform.h"
55 __root =
new Node(
this, num_dims);
57 __num_dims = num_dims;
59 __reuse_head =
new Node(
this);
60 __reuse_cur = __reuse_head;
61 __reuse_tail = __reuse_head;
64 __max_values =
new int[num_dims];
70 while (__reuse_head) {
71 Node *n = __reuse_head;
72 __reuse_head = __reuse_head->__reuse_next;
76 delete[] __max_values;
89 for (
unsigned int i = 0; i < num_values; ++i) {
90 unsigned int count = __root->insert(values[i]);
91 if (count > __max_count) {
93 for (
unsigned int d = 0; d < __num_dims; ++d) {
94 __max_values[d] = values[i][d];
110 for (
unsigned int d = 0; d < __num_dims; ++d) {
111 values[d] = __max_values[d];
129 return __root->filter(values, min_count);
137 HoughTransform::Node *
148 __reuse_cur = __reuse_head;
151 for (
unsigned int d = 0; d < __num_dims; ++d) {
175 HoughTransform::Node::Node(
HoughTransform *ht,
unsigned int dims,
int value)
182 __left = __right = __dim_next = __filter_next = __reuse_next = 0;
191 Node *parent,
unsigned int dims,
int value)
198 __left = __right = __dim_next = __filter_next = __reuse_next = 0;
209 __left = __right = __dim_next = __filter_next = __reuse_next = 0;
213 HoughTransform::Node::~Node()
225 HoughTransform::Node::insert(
int *values)
227 if (values[0] == __value) {
230 __dim_next = __ht->
create_node(
this, __dims - 1, values[1]);
233 return __dim_next->insert(&(values[1]));
237 }
else if (values[0] < __value) {
239 __left = __ht->create_node(__parent, __dims, values[0]);
241 return __left->insert(values);
244 __right = __ht->create_node(__parent, __dims, values[0]);
246 return __right->insert(values);
255 HoughTransform::Node::num_nodes()
258 if (__left) rv += __left->num_nodes();
259 if (__right) rv += __right->num_nodes();
260 if (__dim_next) rv += __dim_next->num_nodes();
269 HoughTransform::Node::depth()
272 if (__left) d = std::max(d, __left->depth());
273 if (__right) d = std::max(d, __right->depth());
274 if (__dim_next) d = std::max(d, __dim_next->depth());
283 HoughTransform::Node::filtered_length()
288 while (t->__filter_next) {
290 t = t->__filter_next;
306 HoughTransform::Node::filter(
int **values,
unsigned int min_count)
308 Node *filtered_root =
new Node();
309 filter(filtered_root, min_count);
310 unsigned int flen = filtered_root->filtered_length();
312 int *fvals = (
int *)calloc(flen, __dims *
sizeof(
int));
313 Node *t = filtered_root;
315 while ((t = t->__filter_next) != NULL) {
317 for (
unsigned int i = 1; i <= __dims; ++i) {
318 fvals[ __dims * (f + 1) - i ] = s->__value;
324 delete filtered_root;
336 HoughTransform::Node *
337 HoughTransform::Node::filter(Node *tail,
unsigned int min_count)
340 if (__count >= min_count) {
342 this->__filter_next = NULL;
343 tail->__filter_next =
this;
346 if (__left) tail = __left->filter(tail, min_count);
347 if (__right) tail = __right->filter(tail, min_count);
350 if (__dim_next) tail = __dim_next->filter(tail, min_count);
351 if (__left) tail = __left->filter(tail, min_count);
352 if (__right) tail = __right->filter(tail, min_count);