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

Linux Cross Reference
Tina5/tina-libs/tina/geometry/geomEdge_link.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/geomEdge_link.c,v $
 23  * Date    :  $Date: 2009/03/19 18:36:26 $
 24  * Version :  $Revision: 1.6 $
 25  * CVS Id  :  $Id: geomEdge_link.c,v 1.6 2009/03/19 18:36:26 paul Exp $
 26  *
 27  * Author  : Legacy TINA
 28  *
 29  * Notes : 
 30  *
 31  * functions to connect edge strings
 32  * 
 33  * rewriten to use static variables rather than property list for data
 34  * manipulation
 35  * 
 36  * now modified to make use of orienation information NAT 12/12/08
 37  *
 38  *********
 39 */
 40 
 41 #include "geomEdge_link.h"
 42 
 43 #if HAVE_CONFIG_H
 44   #include <config.h>
 45 #endif
 46 
 47 #include <math.h>
 48 #include <tina/sys/sysDef.h>
 49 #include <tina/sys/sysPro.h>
 50 #include <tina/math/mathDef.h>
 51 #include <tina/math/mathPro.h>
 52 #include <tina/image/imgDef.h>
 53 #include <tina/image/imgPro.h>
 54 #include <tina/geometry/geomDef.h>
 55 #include <tina/geometry/geom_EdgeDef.h>
 56 #include <tina/geometry/geomEdge_gen.h>
 57 #include <tina/geometry/geomEdge_rect.h>
 58 
 59 /* The edge linking process is very fragile due to the nature of the data
 60  * structures involved. In particular, the forward and backward linking between
 61  * edges must be self consistent in order to avoid loops and multiple indexing
 62  * of edges in strings. Error messages have therefore been added during the process
 63  * of recent modifications in order to catch broken data structures should they 
 64  * occur due to these or any future modicifatons. 
 65  *
 66  * Algorithm proceeds by linking everything, breaking bad orientations, simplifying 
 67  * junctions and finally relinking consistent end junctions, like a 1D split and merge.
 68  * It is expected that the majority of strings (> 80%) will be correctly (semantically) 
 69  * linked, but there is one last chance to fix faulty curves during the 2D fitting process. 
 70    NAT 12/12/08 */
 71 
 72 /* control parameters which determine edge grouping and linkage */
 73 #define CROSSMATCH 236
 74 #define MAX_GAP 8
 75 #define COSCONT 0.4
 76 #define OR_DIFF 0.5
 77 #define ABSDIFFOR  0.4
 78 #define SPUR_LENGTH_THRES 3
 79 #define TEE_ORIENTATION_THRES 1.0 
 80 
 81 /* lists of special edge points and strings manipulated by linking
 82  * functions */
 83 
 84 static List *junc_list = NULL;          /* static data! */
 85 static List *term_list = NULL;          /* static data! */
 86 static List *string_list = NULL;        /* static data! */
 87 
 88 static void edge_set_conn_type_on(Edgel * edge)
 89 {
 90     edge->type &= EDGE_SET_CONN_MASK;
 91     edge->type |= EDGE_CONN;
 92 }
 93 
 94 #if 0
 95 static void edge_set_conn_type_off(Edgel * edge)
 96 {
 97     edge->type &= EDGE_SET_CONN_MASK;
 98 }
 99 
100 #endif
101 
102 /* set up edge type for display with structure integrity checking NAT 12/12/08 */
103 static void edge_set_conn_type(Edgel * edge)
104 {
105     Edge_conn *econn;
106 
107     if (edge == NULL || !(edge->type & EDGE_GET_CONN_MASK))
108         return;
109 
110     edge->type &= EDGE_SET_CONN_MASK;
111     econn = (Edge_conn *) prop_get(edge->props, EDGE_CONN);
112     if (econn == NULL)
113     {
114         edge->type |= EDGE_NOLINK;
115         return;
116     }
117 
118     if ((econn->c1 == NULL && econn->c2 == NULL && econn->conns == NULL ))
119     {
120         if (econn->count!=0) 
121              format("wrong count 0 \n");
122         econn->count = 0;
123     }
124 
125     if ((econn->c1 != NULL && econn->c2 != NULL && econn->conns == NULL ))
126     {
127         if (econn->count!=2) 
128              format("wrong count 2 \n");
129         econn->count = 2;
130     }
131     if ((econn->c1 == NULL && econn->c2 == NULL && econn->conns != NULL ))
132     {
133         if (econn->count==2)
134               format("wrong count %d \n", econn->count);
135     }
136 
137     switch (econn->count)
138     {
139     case 0:
140         edge->type |= EDGE_NOLINK;
141         break;
142     case 1:
143         edge->type |= EDGE_TERMIN;
144         break;
145     case 2:
146         edge->type |= EDGE_CONN;
147         break;
148     default:
149         edge->type |= EDGE_JUNC;
150         break;
151     }
152 }
153 
154 /* test for orinetation consistency NAT */
155 static double absdifforient(double e1, double e2)
156 {
157      double   absordif;
158 
159      absordif = sin(e1 - e2);
160      return(fabs(absordif));
161 }
162 
163 /* set up initial linkage data structures and global junc and term lists with
164    built in NSEW bias to achieve consistent connetivity                     NAT */ 
165 static void edge_set_conns(Edgel * edge, int type, Imrect * er, int i, int j)
166 {
167     Edgel  *eptr;
168     Edge_conn *econn;
169     int     n = 0, e = 0, w = 0, s = 0;
170     double orient;
171 
172     if (er == NULL || edge == NULL || !(edge->type & EDGE_GET_CONN_MASK))
173         return;
174 
175     if ((econn = (Edge_conn *) prop_get(edge->props, EDGE_CONN)) == NULL)
176     {
177         econn = econn_alloc();
178         edge->props = proplist_add(edge->props, (void *) econn, EDGE_CONN, econn_free);
179     }
180     econn->c1 = NULL;
181     econn->c2 = NULL;
182     list_rm_links(econn->conns);
183     econn->conns = NULL;
184     econn->count = 0;
185     orient = edge->orient;
186 
187     if ((eptr = er_get_edge(er, i - 1, j)) != NULL && eptr->type & EDGE_GET_CONN_MASK)
188     {
189         n = 1;
190         econn->conns = link_addtostart((List *) econn->conns, link_alloc((void *) eptr, EDGE));
191         econn->count++;
192     }
193     if ((eptr = er_get_edge(er, i + 1, j)) != NULL && eptr->type & EDGE_GET_CONN_MASK)
194     {
195         s = 1;
196         econn->conns = link_addtostart((List *) econn->conns, link_alloc((void *) eptr, EDGE));
197         econn->count++;
198     }
199     if ((eptr = er_get_edge(er, i, j - 1)) != NULL && eptr->type & EDGE_GET_CONN_MASK)
200     {
201         e = 1;
202         econn->conns = link_addtostart((List *) econn->conns, link_alloc((void *) eptr, EDGE));
203         econn->count++;
204     }
205     if ((eptr = er_get_edge(er, i, j + 1)) != NULL && eptr->type & EDGE_GET_CONN_MASK)
206     {
207         w = 1;
208         econn->conns = link_addtostart((List *) econn->conns, link_alloc((void *) eptr, EDGE));
209         econn->count++;
210     }
211     if (!n && !w && (eptr = er_get_edge(er, i - 1, j + 1)) != NULL && eptr->type & EDGE_GET_CONN_MASK)
212     {
213         econn->conns = link_addtostart((List *) econn->conns, link_alloc((void *) eptr, EDGE));
214         econn->count++;
215     }
216     if (!n && !e && (eptr = er_get_edge(er, i - 1, j - 1)) != NULL && eptr->type & EDGE_GET_CONN_MASK)
217     {
218         econn->conns = link_addtostart((List *) econn->conns, link_alloc((void *) eptr, EDGE));
219         econn->count++;
220     }
221     if (!s && !w && (eptr = er_get_edge(er, i + 1, j + 1)) != NULL && eptr->type & EDGE_GET_CONN_MASK)
222     {
223         econn->conns = link_addtostart((List *) econn->conns, link_alloc((void *) eptr, EDGE));
224         econn->count++;
225     }
226     if (!s && !e && (eptr = er_get_edge(er, i + 1, j - 1)) != NULL && eptr->type & EDGE_GET_CONN_MASK)
227     {
228         econn->conns = link_addtostart((List *) econn->conns, link_alloc((void *) eptr, EDGE));
229         econn->count++;
230     }
231     switch (econn->count)
232     {
233     case 0:
234         break;
235     case 1:                     /* termination point: add to termination list */
236         term_list = ref_addtostart((List *) term_list, (void *) edge, EDGE);
237         break;
238     case 2:                     /* standard connect */
239         econn->c1 = (Edgel *) econn->conns->to;
240         econn->c2 = (Edgel *) econn->conns->next->to;
241         list_rm_links(econn->conns);
242         econn->conns = NULL;
243         break;
244     default:                    /* potential junction: add to junction list */
245         {
246             junc_list = ref_addtostart((List *) junc_list, (void *) edge, EDGE);
247             break;
248         }
249     }
250 }
251 
252 /* generic function to remove eptr from nptr->nconn data structure whilst maintaining
253 term_list and junc_list, generally must be called 2 times for consistent removal
254 NAT 12/12/08 */
255 static void editjunc(Edgel  *eptr, Edgel *nptr)
256 {
257     Edge_conn *nconn;
258 
259     nconn = (Edge_conn *) prop_get(nptr->props, EDGE_CONN);
260     switch (nconn->count)
261     {
262         case 1:
263         {
264              rfree((void *) nconn->conns);
265              nconn->conns = NULL;
266              nconn->count = 0;
267              term_list = list_rm_ref(term_list, (void *) nptr, (void (*) ()) NULL);
268              break;
269          }
270          case 2:
271          {
272               Edgel  *keep = (nconn->c1 == eptr) ? nconn->c2 : nconn->c1;
273 
274               nconn->conns = link_alloc((void *) keep, EDGE);
275               nconn->count = 1;
276               nconn->c1 = NULL;
277               nconn->c2 = NULL;
278               term_list = ref_addtostart((List *) term_list, (void *) nptr, EDGE);
279               break;
280          }
281          case 3:
282          {
283               nconn->conns = list_rm_ref(nconn->conns, (void *) eptr, (void (*) ()) NULL);
284               nconn->c1 = (Edgel *) nconn->conns->to;
285               nconn->c2 = (Edgel *) nconn->conns->next->to;
286               nconn->count = 2;
287               list_rm_links(nconn->conns);
288               nconn->conns = NULL;
289               junc_list = list_rm_ref(junc_list, (void *) nptr, (void (*) ()) NULL);
290               break;
291          }
292          case 4:
293          {
294               nconn->conns = list_rm_ref(nconn->conns, (void *) eptr, (void (*) ()) NULL);
295               nconn->count = 3;
296               break;
297          }
298          default:
299               break;    
300      }
301 }
302 
303 /* initial pruning, test for orientation consistency and remove poor links NAT 12/12/08 */
304 static void edge_break_conns(Edgel * edge, int type, Imrect * er, int i, int j)
305 {
306     Edgel *nptr1, *nptr2, *nptr3;
307     Edge_conn *econn;
308     double orient;
309 
310     if (er == NULL || edge == NULL || !(edge->type & EDGE_GET_CONN_MASK))
311         return;
312 
313     if ((econn = (Edge_conn *) prop_get(edge->props, EDGE_CONN)) == NULL)
314         return;
315 
316     orient = edge->orient;
317 
318     switch (econn->count)
319     {
320         case 1:
321         nptr1  = (Edgel *) econn->conns->to;
322         if (absdifforient(orient,nptr1->orient)>ABSDIFFOR)
323         {
324            editjunc(edge, nptr1);
325            editjunc(nptr1, edge);
326         }
327         break;
328 
329         case 2:
330         nptr1 = econn->c1;
331         nptr2 = econn->c2;
332         if (absdifforient(orient,nptr1->orient)>ABSDIFFOR)
333         {
334             editjunc(edge, nptr1);
335             editjunc(nptr1, edge);
336         }
337         if (absdifforient(orient,nptr2->orient)>ABSDIFFOR)
338         {
339            editjunc(edge, nptr2);
340            editjunc(nptr2, edge);
341         }
342         break;
343        
344         case 3:
345         nptr1  = (Edgel *) econn->conns->to;
346         nptr2  = (Edgel *) econn->conns->next->to;
347         nptr3  = (Edgel *) econn->conns->next->next->to;
348 
349         if (absdifforient(orient,nptr1->orient)>ABSDIFFOR)
350         {
351             editjunc(edge, nptr1);
352             editjunc(nptr1, edge);
353         }
354         if (absdifforient(orient,nptr2->orient)>ABSDIFFOR)
355         {
356            editjunc(edge, nptr2);
357            editjunc(nptr2, edge);
358         }
359         if (absdifforient(orient,nptr3->orient)>ABSDIFFOR)
360         {
361            editjunc(edge, nptr3);
362            editjunc(nptr3, edge);
363         }
364         break;
365     }
366 }
367 
368 /* test a candidate linkage using orientation and directionality, returns
369    value retated to perpendicular distance NAT 1/12/08 */
370 static double elink_con(Edgel *edge1, Edgel * edge2)
371 {
372     Edge_conn *conn1;
373     Edge_conn *conn2;
374     Edgel  *prev;
375     double  orient1, orient2;
376     Vec2    v1 = {Vec2_id}, v1c = {Vec2_id};
377     Vec2    v2 = {Vec2_id}, v2c = {Vec2_id};
378     Vec2    v = {Vec2_id};
379     double  diff, delta;
380 
381     v = vec2_diff(edge2->pos, edge1->pos);
382     diff = vec2_mod(v);
383     if (diff > MAX_GAP)
384               return(diff);
385 
386     orient1 = edge1->orient;
387     orient2 = edge2->orient;
388     delta = fabs(cos(orient1-orient2)); 
389     delta = absdifforient(orient1,orient2);
390     if (delta > OR_DIFF) 
391               return(MAX_GAP);
392 
393     v = vec2_unit(v);
394 
395     conn1 = (Edge_conn *) prop_get(edge1->props, EDGE_CONN);
396     prev = (Edgel *) (conn1->conns->to);
397     if (prev != NULL) 
398     {
399        v1c = vec2_diff(edge1->pos, prev->pos);
400        v1c = vec2_unit(v1c);
401        if (vec2_dot(v1c, v) < COSCONT)  
402               return(MAX_GAP);
403     }
404 
405     conn2 = (Edge_conn *) prop_get(edge2->props, EDGE_CONN);
406     prev = (Edgel *) (conn2->conns->to);
407     if (prev != NULL) 
408     {
409        v2c = vec2_diff(edge2->pos, prev->pos);
410        v2c = vec2_unit(v2c);
411        if (vec2_dot(v2c, v) > -COSCONT) 
412               return(MAX_GAP);
413     }
414 
415     v1 = vec2(cos(orient1),-sin(orient1));
416     v2 = vec2(cos(orient2),-sin(orient2));
417 
418     diff *= sqrt(1.0 - fabs(vec2_dot(v,v1)*vec2_dot(v,v2)));
419   
420     return(diff);
421 }
422 
423 static int shortspur(Edgel * spur, Edgel * last, int thres, int count)
424 {
425     Edgel  *next;
426     Edge_conn *conn;
427 
428     if (spur == NULL) return(count);
429     conn = (Edge_conn *) prop_get(spur->props, EDGE_CONN);
430     if (count > thres || conn->count > 2 )      /* another junction */
431         return (0);
432 
433     if (conn->count == 1)       /* a termination */
434         return (count);
435 
436     next = (conn->c1 == last) ? conn->c2 : conn->c1;
437 
438     return (shortspur(next, spur, thres, count + 1));
439 }
440 
441 static List *prunespurs(List * juncs)
442 {
443     List   *jptr;
444     int     count;
445 
446     for (jptr = juncs; jptr != NULL; jptr = jptr->next)
447     {
448         Edgel  *eptr = (Edgel *) jptr->to;
449         Edge_conn *econn;
450         List   *cptr;
451         List   *short_spurs = NULL;
452 
453         econn = (Edge_conn *) prop_get(eptr->props, EDGE_CONN);
454 
455         for (cptr = econn->conns; cptr != NULL; cptr = cptr->next)
456         {
457             Edgel  *spur = (Edgel *) cptr->to;
458             List   *lptr;
459             List   *link;
460             int     spur_len;
461 
462             if ((spur_len = shortspur(spur, eptr, SPUR_LENGTH_THRES, 1)))       /* short */
463             {
464                 link = link_alloc((void *) cptr, spur_len);
465                 if (short_spurs == NULL || spur_len < short_spurs->type)
466                     short_spurs = link_addtostart((List *) short_spurs, link);
467                 else
468                 {
469                     for (lptr = short_spurs; lptr->next != NULL; lptr = lptr->next)
470                         if (spur_len < lptr->next->type)
471                             break;
472                     link_addafter(lptr, link);
473                 }
474             }
475         }
476 
477         if (short_spurs == NULL)
478             continue;
479 
480         for (cptr = short_spurs, count = econn->count; cptr != NULL; cptr = cptr->next)
481         {
482             Edge_conn *sconn;
483             Edgel  *spur = (Edgel *) ((List *) cptr->to)->to;
484 
485             sconn = (Edge_conn *) prop_get(spur->props, EDGE_CONN);
486 
487             if (sconn->count == 1)      /* terminal */
488             {
489                 list_rm_links(sconn->conns);
490                 sconn->conns = NULL;
491                 sconn->count = 0;
492                 term_list = list_rm_ref(term_list, (void *) spur, (void (*) ()) NULL);
493             } else
494             {
495                 /* sconn->count==2 */
496                 if (sconn->c1 == eptr)
497                     sconn->conns = link_alloc((void *) sconn->c2, EDGE);
498                 else
499                     sconn->conns = link_alloc((void *) sconn->c1, EDGE);
500                 sconn->c1 = sconn->c2 = NULL;
501                 sconn->count = 1;
502                 term_list = ref_addtostart((List *) term_list, (void *) spur, EDGE);
503             }
504             ((List *) cptr->to)->type = REMOVE_ME;
505             if (--count == 2)   /* simple connection */
506                 break;
507         }
508         list_rm_links(short_spurs);
509         econn->conns = list_rm_links_on_type(econn->conns, REMOVE_ME);
510     }
511 
512     for (jptr = juncs; jptr != NULL; jptr = jptr->next)
513     {
514         Edgel  *eptr = (Edgel *) jptr->to;
515         Edge_conn *econn;
516         List   *cptr;
517 
518         econn = (Edge_conn *) prop_get(eptr->props, EDGE_CONN);
519         econn->count = 0;
520         for (cptr = econn->conns; cptr != NULL; cptr = cptr->next)
521             ++econn->count;
522 
523         switch (econn->count)
524         {
525         case 0:
526             jptr->type = REMOVE_ME;
527             break;
528         case 1:
529             term_list = ref_addtostart((List *) term_list, (void *) eptr, EDGE);
530             jptr->type = REMOVE_ME;
531             break;
532         case 2:
533             econn->c1 = (Edgel *) econn->conns->to;
534             econn->c2 = (Edgel *) econn->conns->next->to;
535             list_rm_links(econn->conns);
536             econn->conns = NULL;
537             jptr->type = REMOVE_ME;
538             break;
539         default:
540             break;
541         }
542     }
543     return (list_rm_links_on_type(juncs, REMOVE_ME));
544 }
545 
546 /* identify the linkage across short gaps which which minimises the orientation and projection 
547 differences, test all candidates and keep the best only if it is consistent NAT */ 
548 static List *bridge_small_gaps(List * terms)
549 /* list of termination points */
550 {
551     List   *lptr1;
552     List   *lptr2;
553     List   *lmin;
554     Edgel  *edge1;
555     Edgel  *edge2;
556     Edgel  *etest;
557     Edge_conn *conn1;
558     Edge_conn *conn2;
559     double  min_diff, diff;
560 
561     if (terms == NULL || terms->next == NULL)
562         return (terms);
563 
564     for (lptr1 = terms; lptr1->next != NULL; lptr1 = lptr1->next)
565     {
566         if (lptr1->type == REMOVE_ME)
567             continue;
568 
569         edge1 = (Edgel *) lptr1->to;
570         conn1 = (Edge_conn *) prop_get(edge1->props, EDGE_CONN);
571         lmin = NULL;
572         min_diff = MAX_GAP;
573 
574         for (lptr2 = terms; lptr2 != NULL; lptr2 = lptr2->next)
575         {
576             if (lptr2->type == REMOVE_ME)
577                 continue;
578             if (lptr2 == lptr1) continue;
579 
580             edge2 = (Edgel *) lptr2->to;
581 
582             diff = elink_con(edge1,  edge2);
583 
584             if (diff < MAX_GAP && diff < min_diff)
585             {
586                lmin = lptr2;
587                min_diff = diff;
588             }
589         }
590         if (lmin == NULL)
591             continue;
592         edge1->props = proplist_add(edge1->props, (void *)lmin, CROSSMATCH, NULL);
593     }
594     for (lptr1 = terms; lptr1->next != NULL; lptr1 = lptr1->next)
595     {
596         if (lptr1->type == REMOVE_ME)
597             continue;
598         edge1 = (Edgel *) lptr1->to;
599         lmin = prop_get(edge1->props, CROSSMATCH);
600         etest = NULL;
601 
602         if (lmin == NULL || lmin->type == REMOVE_ME)
603             continue;
604 
605         edge2 = lmin->to;
606         lptr2 = prop_get(edge2->props, CROSSMATCH);
607         if (lptr2 !=NULL) etest = lptr2->to;
608 
609         if ( etest!=NULL && etest == edge1)
610         {
611             conn1 = (Edge_conn *) prop_get(edge1->props, EDGE_CONN);
612             conn2 = (Edge_conn *) prop_get(edge2->props, EDGE_CONN);
613             conn1->c1 = conn1->conns->to;
614             conn2->c1 = conn2->conns->to;
615             conn1->c2 = edge2;
616             conn2->c2 = edge1;
617             list_rm_links(conn1->conns);
618             list_rm_links(conn2->conns);
619             conn1->conns = NULL;
620             conn2->conns = NULL;
621             if (conn1->count != 1 || conn2->count !=1)
622                  format("bad connections in termlst \n");
623             conn1->count = 2;
624             conn2->count = 2;
625             lptr1->type = REMOVE_ME;
626             lmin->type = REMOVE_ME;
627             edge2->props = proplist_rm(edge2->props, CROSSMATCH); 
628         }
629         edge1->props = proplist_rm(edge1->props, CROSSMATCH); 
630     }
631     return (list_rm_links_on_type(terms, REMOVE_ME));
632 }
633 
634 /* finished with junctions.. delete what is left NAT 12/12/08 */
635 static void rmjuncs(List * juncs)
636 {
637     List   *jptr;
638 
639     for (jptr = juncs; jptr != NULL; jptr = jptr->next)
640     {
641         Edgel  *eptr = (Edgel *) jptr->to;
642         Edge_conn *econn;
643         List   *cptr;
644 
645         econn = (Edge_conn *) prop_get(eptr->props, EDGE_CONN);
646 
647         for (cptr = econn->conns; cptr != NULL; cptr = cptr->next)
648         {
649             Edgel  *nptr = (Edgel *) cptr->to;
650             editjunc(eptr, nptr);
651         }
652         list_rm_links(econn->conns);
653         econn->conns = NULL;
654         econn->count = 0;
655         edge_set_type_remove_me(eptr);
656     }
657 }
658 
659 /* break all links between adjacent junctions */
660 static List *prunejuncs(List * juncs)
661 {
662     List   *jptr;
663 
664     for (jptr = juncs; jptr != NULL; jptr = jptr->next)
665     {
666         Edgel  *eptr = (Edgel *) jptr->to;
667         Edge_conn *econn;
668         List   *cptr;
669 
670         econn = (Edge_conn *) prop_get(eptr->props, EDGE_CONN);
671 
672         for (cptr = econn->conns; cptr != NULL; )
673         {
674             Edgel  *nptr = (Edgel *) cptr->to;
675             Edge_conn *nconn;
676 
677             nconn = (Edge_conn *) prop_get(nptr->props, EDGE_CONN);
678             if (nconn->count > 2)       /* a neighbouring junction */
679             {
680                 cptr->type = REMOVE_ME;
681             }
682             cptr = cptr->next;
683         }
684         econn->conns = list_rm_links_on_type(econn->conns, REMOVE_ME);
685     }
686 
687     for (jptr = juncs; jptr != NULL; jptr = jptr->next)
688     {
689         Edgel  *eptr = (Edgel *) jptr->to;
690         Edge_conn *econn;
691         List   *cptr;
692 
693         econn = (Edge_conn *) prop_get(eptr->props, EDGE_CONN);
694 
695         econn->count = 0;
696         for (cptr = econn->conns; cptr != NULL; cptr = cptr->next)
697             ++econn->count;
698 
699         switch (econn->count)
700         {
701         case 0:
702             jptr->type = REMOVE_ME;
703             econn->c1 = NULL;
704             econn->c2 = NULL;
705             break;
706         case 1:
707             term_list = ref_addtostart((List *) term_list, (void *) eptr, EDGE);
708             econn->c1 = NULL;
709             econn->c2 = NULL;
710             jptr->type = REMOVE_ME;
711             break;
712         case 2:
713             econn->c1 = (Edgel *) econn->conns->to;
714             econn->c2 = (Edgel *) econn->conns->next->to;
715             list_rm_links(econn->conns);
716             econn->conns = NULL;
717             jptr->type = REMOVE_ME;
718         default:
719             break;
720         }
721     }
722     return (list_rm_links_on_type(juncs, REMOVE_ME));
723 }
724 
725 static List *prunetees(List * juncs)
726 {
727     List   *jptr;
728 
729     for (jptr = juncs; jptr != NULL; jptr = jptr->next)
730     {
731         Edgel  *eptr = (Edgel *) jptr->to;
732         Edgel  *links[3];
733         Edge_conn *econn;
734         Edge_conn *lconn[3];
735         int     i, j;
736         int     c1 = 0, c2 = 0, c3;
737         float   mindif = TEE_ORIENTATION_THRES;
738 
739         econn = (Edge_conn *) prop_get(eptr->props, EDGE_CONN);
740 
741         if (econn->count != 3)  /* not a three way junction */
742             continue;
743 
744         links[0] = (Edgel *) econn->conns->to;
745         links[1] = (Edgel *) econn->conns->next->to;
746         links[2] = (Edgel *) econn->conns->next->next->to;
747 
748         for (i = 0; i < 3; ++i)
749         {
750             lconn[i] = (Edge_conn *) prop_get(links[i]->props, EDGE_CONN);
751             if (lconn[i]->count != 2)   /* not a simple continue */
752                 break;
753         }
754         if (i < 3)
755             continue;
756 
757         for (i = 0; i < 2; ++i)
758             for (j = i + 1; j < 3; ++j)
759             {
760                 double absordif;
761                 absordif = absdifforient(links[i]->orient, links[j]->orient);
762 
763                 if (absordif < mindif)
764                 {
765                     c1 = i;
766                     c2 = j;
767                     mindif = absordif;
768                 }
769             }
770 
771         if (mindif >= TEE_ORIENTATION_THRES)
772             continue;
773 
774         econn->c1 = links[c1];
775         econn->c2 = links[c2];
776 
777         list_rm_links(econn->conns);
778         econn->conns = NULL;
779         econn->count = 2;
780 
781         jptr->type = REMOVE_ME;
782 
783         c3 = 3 - c1 - c2;
784         econn = lconn[c3];      /* Edge_conn of the remaining edge */
785         econn->conns = link_alloc((void *)
786                  ((econn->c1 == eptr) ? econn->c2 : econn->c1), EDGE);
787         econn->c1 = econn->c2 = NULL;
788         econn->count = 1;
789         term_list = ref_addtostart((List *) term_list, (void *) links[c3], EDGE);       /* new term */
790     }
791     return (list_rm_links_on_type(juncs, REMOVE_ME));
792 }
793 
794 static Tstring *edge_getloop(Edgel * edge)
795 {
796     List *start = NULL;
797     List *end = NULL;
798     Edge_conn *cptr;
799     Edgel  *eptr;
800     Edgel  *from;
801 
802     if (edge == NULL || !(edge->type & EDGE_GET_CONN_MASK))
803         return (NULL);
804 
805     cptr = (Edge_conn *) prop_get(edge->props, EDGE_CONN);
806     if (cptr->count != 2)
807         return (NULL);
808     start = end = dd_link_alloc((void *) edge, EDGE);
809     from = edge;
810     edge->type |= EDGE_LOOP;
811 
812     for (eptr = cptr->c1; eptr != edge && eptr!=NULL; eptr = cptr->c1)
813     {
814         cptr = (Edge_conn *) prop_get(eptr->props, EDGE_CONN);
815         if (cptr->c2 != from && cptr->c1 == from)
816             SWAP(Edgel *, cptr->c1, cptr->c2)
817         if (cptr->count == 2 && cptr->c2 != from)
818         {
819             printf("broken list in getloop \n");
820             return(str_make(STRING, start, end));
821         }
822         eptr->type |= EDGE_LOOP;
823         end = dd_link_addtoend(end, dd_link_alloc((void *) eptr, EDGE));
824         from = eptr;
825     }
826 
827     start->last = end;          /* to complete the loop */
828     end->next = start;
829 
830     return (str_make(LOOP, start, end));
831 }
832 
833 static void edge_find_loops(Edgel * edge)
834 {
835     Tstring *string;
836 
837     if (edge == NULL || edge->type & EDGE_GET_LOOP_MASK ||
838         (edge->type & EDGE_GET_CONN_MASK) != EDGE_CONN)
839         return;
840 
841     string = edge_getloop(edge);
842     if (string != NULL)
843         string_list = ref_addtostart((List *) string_list, (void *) string, STRING);
844 }
845 
846 /* lift connected strings out of edge pointer data structure */
847 static Tstring *edge_getstring(Edgel * term)
848 {
849     List *start = NULL;
850     List *end = NULL;
851     Edge_conn *cptr;
852     Edgel  *eptr;
853     Edgel  *from;
854     Tstring *string = NULL;
855 
856 
857     if (term == NULL)
858         return (NULL);
859 
860     cptr = (Edge_conn *) prop_get(term->props, EDGE_CONN);
861     if (cptr->count != 1)
862         return (NULL);
863     start = end = dd_link_alloc((void *) term, EDGE);
864     from = term;
865     term->type |= EDGE_NOT_LOOP;
866 
867     for (eptr = (Edgel *) cptr->conns->to; eptr!=NULL; eptr = cptr->c1)
868     {
869         cptr = (Edge_conn *) prop_get(eptr->props, EDGE_CONN);
870         if (cptr->c2 != from )
871             SWAP(Edgel *, cptr->c1, cptr->c2) ;
872 
873         if (cptr->count == 0 || (cptr->count >= 2 && cptr->c2 != from))
874         {
875             printf("broken list in getstring %d\n", cptr->count);
876             break;
877         }
878         eptr->type |= EDGE_NOT_LOOP;
879         end = dd_link_addtoend(end, dd_link_alloc((void *) eptr, EDGE));
880 
881         from = eptr;
882 
883     }
884     string = str_make(STRING, start, end);
885 
886     return (string);
887 }
888 
889 static List *findstrings(List * terms)
890 {
891     List   *tptr;
892     List   *strings = NULL;
893 
894     terms = list_copy(terms, (void *(*) ()) NULL, NULL);
895 
896     tptr = terms;
897     while (tptr != NULL)
898     {
899         Tstring *sptr = edge_getstring((Edgel *) tptr->to);
900 
901         strings = link_addtostart((List *) strings, link_alloc((void *) sptr, STRING));
902         (void) list_rm_ref(tptr, sptr->end->to, (void (*) ()) NULL);
903         tptr = link_rm_el(tptr);
904     }
905 
906     return (strings);
907 }
908 
909 /* process the raw edge rect to determine a sensible connectivity */
910 void    er_find_edge_strings(Imrect * er)
911 {
912     if (er == NULL)
913         return;
914 
915 /* first set conn field of edge type to allow all possible connections */
916     er_apply_to_all_edges(er, edge_set_conn_type_on, NULL);
917     er_apply_to_all_edges(er, edge_set_conns, (void *) er);
918 /* now remove poor orientations */
919     er_apply_to_all_edges(er, edge_break_conns, (void *) er);
920 
921 /*  prune the junctions to simplify linkage */   
922     junc_list = prunetees(junc_list);
923     junc_list = prunejuncs(junc_list);
924     junc_list = prunespurs(junc_list);
925 /* throw away what we can't deal with */
926     rmjuncs(junc_list);
927     list_rm_links(junc_list);
928 
929 /* re-connect short gaps minimising orientation differences */
930     term_list = bridge_small_gaps(term_list);
931 
932 /* extract initial strings */
933     string_list = findstrings(term_list);
934     list_rm_links(term_list);
935     junc_list = term_list = NULL;
936 
937 /* finally set up edge types for data display */
938     er_apply_to_all_edges(er, edge_set_conn_type, NULL);
939 /* mop up data which was not linked to termination points */
940     er_apply_to_all_edges(er, edge_find_loops, NULL);   
941 
942     er->props = proplist_addifnp(er->props, (void *) string_list, STRING, str_rm_list, false);
943 }
944 
945 void    er_find_simple_edge_strings(Imrect * er)
946 /* edge rect */
947 {
948     if (er == NULL)
949         return;
950 
951     /* first set conn field of edge type to allow all possible
952      * connections */
953     er_apply_to_all_edges(er, edge_set_conn_type_on, NULL);
954     er_apply_to_all_edges(er, edge_set_conns, (void *) er);
955 
956     junc_list = prunespurs(junc_list);
957     rmjuncs(junc_list);
958     list_rm_links(junc_list);
959 
960     string_list = findstrings(term_list);
961     list_rm_links(term_list);
962     junc_list = term_list = NULL;
963 
964     er_apply_to_all_edges(er, edge_set_conn_type, NULL);
965     er_apply_to_all_edges(er, edge_find_loops, NULL);   /* adds to string_list */
966 
967     er->props = proplist_addifnp(er->props, (void *) string_list, STRING, str_rm_list, false);
968 }
969 
970 List   *er_specific_edge_strings(Imrect * er, void (*func) ( /* ??? */ ), void *data)
971 /* edge rect */
972 {
973     if (er == NULL)
974         return ((List *) NULL);
975 
976     /* first set conn field using function */
977     er_apply_to_all_edges(er, func, (void *) data);
978     er_apply_to_all_edges(er, edge_set_conns, (void *) er);
979 
980     junc_list = prunespurs(junc_list);
981     rmjuncs(junc_list);
982     list_rm_links(junc_list);
983 
984     string_list = findstrings(term_list);
985     list_rm_links(term_list);
986     junc_list = term_list = NULL;
987 
988     er_apply_to_all_edges(er, edge_set_conn_type, NULL);
989     er_apply_to_all_edges(er, edge_find_loops, NULL);   /* adds to string_list */
990 
991     return (string_list);
992 }
993 

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