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

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

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