~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

Linux Cross Reference
Tina4/src/vision/line2/linearprox.c

Version: ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /**@(#)
  2 **/
  3 #include <math.h>
  4 #include <stdio.h>
  5 #include <tina/sys.h>
  6 #include <tina/sysfuncs.h>
  7 #include <tina/math.h>
  8 #include <tina/mathfuncs.h>
  9 #include <tina/vision.h>
 10 #include <tina/visionfuncs.h>
 11 
 12 #define INIT_SAMPLE 12
 13 
 14 static double line_sqrdist(Vec2 q, Vec2 p, Vec2 v)      /* point q to line (p v) */
 15 
 16 {
 17     Vec2    dq = {Vec2_id};
 18 
 19     dq = vec2_projperp(vec2_diff(q, p), v);
 20     return (vec2_sqrmod(dq));
 21 }
 22 
 23 static Bool line_check(Vec2 p, Vec2 v, List * start, List * end, int max_diverge, double thres)
 24 {
 25     Vec2    pos = {Vec2_id};
 26     List *dptr;
 27     int     misses = 0;
 28     double  thres2 = 2 * thres;
 29 
 30     for (dptr = start;; dptr = dptr->next)
 31     {
 32         double  sep;
 33 
 34         DD_GET_POS2(dptr, pos);
 35         sep = line_sqrdist(pos, p, v);
 36         if (sep > thres2)
 37             break;
 38         if (sep > thres)
 39             ++misses;
 40         else
 41             misses = 0;
 42         if (misses > max_diverge)
 43             return (false);
 44         if (dptr == end)
 45             break;
 46     }
 47     return (true);
 48 }
 49 
 50 static int line_count(Vec2 p, Vec2 v, List * start, List * end, int sample, double thres)
 51 {
 52     Vec2    q = {Vec2_id};
 53     int     i, count = 0;
 54     List *dptr;
 55 
 56     for (dptr = start;;)
 57     {
 58         DD_GET_POS2(dptr, q);
 59         if (line_sqrdist(q, p, v) < thres)
 60             ++count;
 61 
 62         if (dptr == end)
 63             break;
 64 
 65         for (i = 0; i < sample; ++i, dptr = dptr->next)
 66             if (dptr == end)
 67                 break;
 68     }
 69     return (count);
 70 }
 71 
 72 static void line_grow(Vec2 p, Vec2 v, List * start, List * end, List ** p1, List ** p2, int max_diverge, double thres)
 73 {
 74     List *m1 = *p1;
 75     List *m2 = *p2;
 76     List *ptr;
 77     Vec2    pos = {Vec2_id};
 78     int     misses;
 79 
 80     misses = 0;
 81     for (ptr = m1; ptr != start;)
 82     {
 83         ptr = ptr->last;
 84         DD_GET_POS2(ptr, pos);
 85         if (line_sqrdist(pos, p, v) < thres)
 86         {
 87             misses = 0;
 88             m1 = ptr;
 89         } else
 90             ++misses;
 91         if (misses > max_diverge)
 92             break;
 93     }
 94 
 95     misses = 0;
 96     for (ptr = m2; ptr != end;)
 97     {
 98         ptr = ptr->next;
 99         DD_GET_POS2(ptr, pos);
100         if (line_sqrdist(pos, p, v) < thres)
101         {
102             misses = 0;
103             m2 = ptr;
104         } else
105             ++misses;
106         if (misses > max_diverge)
107             break;
108     }
109 
110     *p1 = m1;
111     *p2 = m2;
112 }
113 
114 List *linear_prox(List * start, List * end, float thres, int sample)
115 {
116     List *p1;
117     List *p2;
118     List *pm;
119     List *m1;
120     List *m2;
121     List *list1 = NULL;
122     List *list2 = NULL;
123     Line2  *line = NULL;
124     double  thres_sqr = thres * thres;
125     Vec2    q = {Vec2_id};
126     Vec2    p = {Vec2_id};
127     Vec2    v = {Vec2_id};
128     int     i, max_diverge, maxcount = 0;
129 
130     if (start == NULL || end == NULL || start == end)
131         return (NULL);
132 
133     if (ddstr_count(start, end) < 5)
134         return (poly_prox(start, end, thres));
135 
136     p1 = start;
137     p2 = ddstr_nth_point(start, end, 2 * sample + 1);
138     if (p2 == NULL)
139         p2 = end;
140     pm = ddstr_mid_point(p1, p2);
141     max_diverge = sample / 3;
142     if (max_diverge == 0)
143         max_diverge = 1;
144 
145     while (1)
146     {
147         DD_GET_POS2(p1, p);
148         DD_GET_POS2(p2, q);
149         v = vec2_unit(vec2_diff(q, p));
150         DD_GET_POS2(pm, q);
151 
152         if (line_sqrdist(q, p, v) < thres_sqr &&
153             line_check(p, v, p1, p2, max_diverge, thres_sqr))
154         {
155             int     count = line_count(p, v, start, end, sample / 2, thres_sqr);
156 
157             if (count > maxcount)
158             {
159                 maxcount = count;
160                 m1 = p1;
161                 m2 = p2;
162             }
163         }
164         if (p2 == end)
165             break;
166 
167         for (i = 0; i < sample; ++i)
168         {
169             p1 = p1->next;
170             pm = pm->next;
171             p2 = p2->next;
172             if (p2 == end)
173                 break;
174         }
175     }
176 
177     if (maxcount > 2)
178     {
179         DD_GET_POS2(m1, p);
180         DD_GET_POS2(m2, q);
181         v = vec2_unit(vec2_diff(q, p));
182         line_grow(p, v, start, end, &m1, &m2, max_diverge, thres_sqr);
183         line = line2_fit_and_grow(&m1, &m2, start, end, thres);
184     }
185     if (line == NULL)           /* failed */
186     {
187         sample /= 2;
188         if (sample >= 3)
189             return (linear_prox(start, end, thres, sample));
190         return (poly_prox(start, end, thres));
191     }
192     if (start->last == end && end->next == start)       /* A LOOP */
193     {
194         line2_free(line);       /* ignore this line and start again */
195         if (ddstr_length(start, m1) < ddstr_length(m2, end))
196             return (linear_prox(m2->next, m2->last, thres, sample));
197         else
198             return (linear_prox(m1->next, m1->last, thres, sample));
199     }
200     if (m1 != start)
201         list1 = linear_prox(start, m1, thres, sample);
202 
203     if (m2 != end)
204         list2 = linear_prox(m2, end, thres, sample);
205 
206     return (dd_append(list1, dd_append(dd_link_alloc((void *) line, LINE2), list2)));
207 }
208 
209 Tstring *linear_string(Tstring * string, double thres)
210 {
211     List *linear;
212 
213     if (string == NULL)
214         return (NULL);
215 
216     linear = linear_prox(string->start, string->end, (float)thres, INIT_SAMPLE);
217 
218     if (linear == NULL)
219         return (NULL);
220 
221     return (str_make(STRING, linear, dd_get_end(linear)));
222 }
223 
224 List   *linear_strings(List * strings, double thres)
225 {
226     List   *sptr;
227     List   *splist = NULL;
228 
229     for (sptr = strings; sptr != NULL; sptr = sptr->next)
230     {
231         Tstring *string = linear_string((Tstring *) sptr->to, thres);
232 
233         splist = ref_addtostart((List *) splist, (void *) string, STRING);
234     }
235     return (splist);
236 }
237 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

This page was automatically generated by the LXR engine.
Visit the LXR main site for more information.