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

Linux Cross Reference
Tina5/tina-libs/tina/geometry/geomLine_linearprox.c

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

  1 /**********
  2  * 
  3  * This file is part of the TINA Open Source Image Analysis Environment
  4  * henceforth known as TINA
  5  *
  6  * TINA is free software; you can redistribute it and/or modify
  7  * it under the terms of the GNU Lesser General Public License as 
  8  * published by the Free Software Foundation.
  9  *
 10  * TINA is distributed in the hope that it will be useful,
 11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
 12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 13  * GNU Lesser General Public License for more details.
 14  *
 15  * You should have received a copy of the GNU Lesser General Public License
 16  * along with TINA; if not, write to the Free Software Foundation, Inc., 
 17  * 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 18  *
 19  **********
 20  * 
 21  * Program :    TINA
 22  * File    :  $Source: /home/tina/cvs/tina-libs/tina/geometry/geomLine_linearprox.c,v $
 23  * Date    :  $Date: 2002/12/09 11:51:23 $
 24  * Version :  $Revision: 1.1.1.1 $
 25  * CVS Id  :  $Id: geomLine_linearprox.c,v 1.1.1.1 2002/12/09 11:51:23 cvstina Exp $
 26  *
 27  * Notes :
 28  *
 29  *********
 30 */
 31 
 32 
 33 #include "geomLine_linearprox.h"
 34 
 35 #if HAVE_CONFIG_H
 36   #include <config.h>
 37 #endif
 38 
 39 #include <stdio.h>
 40 #include <math.h>
 41 #include <tina/sys/sysDef.h>
 42 #include <tina/sys/sysPro.h>
 43 #include <tina/math/mathDef.h>
 44 #include <tina/math/mathPro.h>
 45 #include <tina/geometry/geomDef.h>
 46 #include <tina/geometry/geom_LineDef.h>
 47 #include <tina/geometry/geom_LinePro.h>
 48 
 49 #define INIT_SAMPLE 12
 50 
 51 static double line_sqrdist(Vec2 q, Vec2 p, Vec2 v)      /* point q to line (p v) */
 52 
 53 {
 54     Vec2    dq = {Vec2_id};
 55 
 56     dq = vec2_projperp(vec2_diff(q, p), v);
 57     return (vec2_sqrmod(dq));
 58 }
 59 
 60 static Bool line_check(Vec2 p, Vec2 v, List * start, List * end, int max_diverge, double thres)
 61 {
 62     Vec2    pos = {Vec2_id};
 63     List *dptr;
 64     int     misses = 0;
 65     double  thres2 = 2 * thres;
 66 
 67     for (dptr = start;; dptr = dptr->next)
 68     {
 69         double  sep;
 70 
 71         DD_GET_POS2(dptr, pos);
 72         sep = line_sqrdist(pos, p, v);
 73         if (sep > thres2)
 74             break;
 75         if (sep > thres)
 76             ++misses;
 77         else
 78             misses = 0;
 79         if (misses > max_diverge)
 80             return (false);
 81         if (dptr == end)
 82             break;
 83     }
 84     return (true);
 85 }
 86 
 87 static int line_count(Vec2 p, Vec2 v, List * start, List * end, int sample, double thres)
 88 {
 89     Vec2    q = {Vec2_id};
 90     int     i, count = 0;
 91     List *dptr;
 92 
 93     for (dptr = start;;)
 94     {
 95         DD_GET_POS2(dptr, q);
 96         if (line_sqrdist(q, p, v) < thres)
 97             ++count;
 98 
 99         if (dptr == end)
100             break;
101 
102         for (i = 0; i < sample; ++i, dptr = dptr->next)
103             if (dptr == end)
104                 break;
105     }
106     return (count);
107 }
108 
109 static void line_grow(Vec2 p, Vec2 v, List * start, List * end, List ** p1, List ** p2, int max_diverge, double thres)
110 {
111     List *m1 = *p1;
112     List *m2 = *p2;
113     List *ptr;
114     Vec2    pos = {Vec2_id};
115     int     misses;
116 
117     misses = 0;
118     for (ptr = m1; ptr != start;)
119     {
120         ptr = ptr->last;
121         DD_GET_POS2(ptr, pos);
122         if (line_sqrdist(pos, p, v) < thres)
123         {
124             misses = 0;
125             m1 = ptr;
126         } else
127             ++misses;
128         if (misses > max_diverge)
129             break;
130     }
131 
132     misses = 0;
133     for (ptr = m2; ptr != end;)
134     {
135         ptr = ptr->next;
136         DD_GET_POS2(ptr, pos);
137         if (line_sqrdist(pos, p, v) < thres)
138         {
139             misses = 0;
140             m2 = ptr;
141         } else
142             ++misses;
143         if (misses > max_diverge)
144             break;
145     }
146 
147     *p1 = m1;
148     *p2 = m2;
149 }
150 
151 List *linear_prox(List * start, List * end, float thres, int sample)
152 {
153     List *p1;
154     List *p2;
155     List *pm;
156     List *m1;
157     List *m2;
158     List *list1 = NULL;
159     List *list2 = NULL;
160     Line2  *line = NULL;
161     double  thres_sqr = thres * thres;
162     Vec2    q = {Vec2_id};
163     Vec2    p = {Vec2_id};
164     Vec2    v = {Vec2_id};
165     int     i, max_diverge, maxcount = 0;
166 
167     if (start == NULL || end == NULL || start == end)
168         return (NULL);
169 
170     if (ddstr_count(start, end) < 5)
171         return (poly_prox(start, end, thres));
172 
173     p1 = start;
174     p2 = ddstr_nth_point(start, end, 2 * sample + 1);
175     if (p2 == NULL)
176         p2 = end;
177     pm = ddstr_mid_point(p1, p2);
178     max_diverge = sample / 3;
179     if (max_diverge == 0)
180         max_diverge = 1;
181 
182     while (1)
183     {
184         DD_GET_POS2(p1, p);
185         DD_GET_POS2(p2, q);
186         v = vec2_unit(vec2_diff(q, p));
187         DD_GET_POS2(pm, q);
188 
189         if (line_sqrdist(q, p, v) < thres_sqr &&
190             line_check(p, v, p1, p2, max_diverge, thres_sqr))
191         {
192             int     count = line_count(p, v, start, end, sample / 2, thres_sqr);
193 
194             if (count > maxcount)
195             {
196                 maxcount = count;
197                 m1 = p1;
198                 m2 = p2;
199             }
200         }
201         if (p2 == end)
202             break;
203 
204         for (i = 0; i < sample; ++i)
205         {
206             p1 = p1->next;
207             pm = pm->next;
208             p2 = p2->next;
209             if (p2 == end)
210                 break;
211         }
212     }
213 
214     if (maxcount > 2)
215     {
216         DD_GET_POS2(m1, p);
217         DD_GET_POS2(m2, q);
218         v = vec2_unit(vec2_diff(q, p));
219         line_grow(p, v, start, end, &m1, &m2, max_diverge, thres_sqr);
220         line = line2_fit_and_grow(&m1, &m2, start, end, thres);
221     }
222     if (line == NULL)           /* failed */
223     {
224         sample /= 2;
225         if (sample >= 3)
226             return (linear_prox(start, end, thres, sample));
227         return (poly_prox(start, end, thres));
228     }
229     if (start->last == end && end->next == start)       /* A LOOP */
230     {
231         line2_free(line);       /* ignore this line and start again */
232         if (ddstr_length(start, m1) < ddstr_length(m2, end))
233             return (linear_prox(m2->next, m2->last, thres, sample));
234         else
235             return (linear_prox(m1->next, m1->last, thres, sample));
236     }
237     if (m1 != start)
238         list1 = linear_prox(start, m1, thres, sample);
239 
240     if (m2 != end)
241         list2 = linear_prox(m2, end, thres, sample);
242 
243     return (dd_append(list1, dd_append(dd_link_alloc((void *) line, LINE2), list2)));
244 }
245 
246 Tstring *linear_string(Tstring * string, double thres)
247 {
248     List *linear;
249 
250     if (string == NULL)
251         return (NULL);
252 
253     linear = linear_prox(string->start, string->end, (float)thres, INIT_SAMPLE);
254 
255     if (linear == NULL)
256         return (NULL);
257 
258     return (str_make(STRING, linear, dd_get_end(linear)));
259 }
260 
261 List   *linear_strings(List * strings, double thres)
262 {
263     List   *sptr;
264     List   *splist = NULL;
265 
266     for (sptr = strings; sptr != NULL; sptr = sptr->next)
267     {
268         Tstring *string = linear_string((Tstring *) sptr->to, thres);
269 
270         splist = ref_addtostart((List *) splist, (void *) string, STRING);
271     }
272     return (splist);
273 }
274 

~ [ 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.