/* -*-C-*- ******************************************************************************** * * File:        seam.c  (Formerly seam.c) * Description: * Author:       Mark Seaman, OCR Technology * Created:      Fri Oct 16 14:37:00 1987 * Modified:     Fri May 17 16:30:13 1991 (Mark Seaman) marks@hpgrlt * Language:     C * Package:      N/A * Status:       Reusable Software Component * * (c) Copyright 1987, Hewlett-Packard Company. ** Licensed under the Apache License, Version 2.0 (the "License"); ** you may not use this file except in compliance with the License. ** You may obtain a copy of the License at ** http://www.apache.org/licenses/LICENSE-2.0 ** Unless required by applicable law or agreed to in writing, software ** distributed under the License is distributed on an "AS IS" BASIS, ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. ** See the License for the specific language governing permissions and ** limitations under the License. * *********************************************************************************//*----------------------------------------------------------------------              I n c l u d e s----------------------------------------------------------------------*/#include "seam.h"#include "callcpp.h"#include "structures.h"#include "makechop.h"#ifdef __UNIX__#include <assert.h>#endif/*----------------------------------------------------------------------              V a r i a b l e s----------------------------------------------------------------------*/#define NUM_STARTING_SEAMS  20#define SEAMBLOCK 100            /* Cells per block */makestructure (newseam, free_seam, printseam, SEAM,freeseam, SEAMBLOCK, "SEAM", seamcount);/*----------------------------------------------------------------------        Public Function Code----------------------------------------------------------------------*//********************************************************************** * point_in_split * * Check to see if either of these points are present in the current * split.  Return TRUE if one of them is. **********************************************************************/bool point_in_split(SPLIT *split, EDGEPT *point1, EDGEPT *point2) {  return ((split) ?    ((exact_point (split->point1, point1) ||    exact_point (split->point1, point2) ||    exact_point (split->point2, point1) ||    exact_point (split->point2, point2)) ? TRUE : FALSE) : FALSE);}/********************************************************************** * point_in_seam * * Check to see if either of these points are present in the current * seam.  Return TRUE if one of them is. **********************************************************************/bool point_in_seam(SEAM *seam, SPLIT *split) {  return (point_in_split (seam->split1, split->point1, split->point2) ||    point_in_split (seam->split2, split->point1, split->point2) ||    point_in_split (seam->split3, split->point1, split->point2));}/********************************************************************** * add_seam * * Add another seam to a collection of seams. **********************************************************************/SEAMS add_seam(SEAMS seam_list, SEAM *seam) {  return (array_push (seam_list, seam));}/********************************************************************** * combine_seam * * Combine two seam records into a single seam.  Move the split * references from the second seam to the first one.  The argument * convention is patterned after strcpy. **********************************************************************/void combine_seams(SEAM *dest_seam, SEAM *source_seam) {  dest_seam->priority += source_seam->priority;  dest_seam->location += source_seam->location;  dest_seam->location /= 2;  if (source_seam->split1) {    if (!dest_seam->split1)      dest_seam->split1 = source_seam->split1;    else if (!dest_seam->split2)      dest_seam->split2 = source_seam->split1;    else if (!dest_seam->split3)      dest_seam->split3 = source_seam->split1;    else      cprintf ("combine_seam: Seam is too crowded, can't be combined !\n");  }  if (source_seam->split2) {    if (!dest_seam->split2)      dest_seam->split2 = source_seam->split2;    else if (!dest_seam->split3)      dest_seam->split3 = source_seam->split2;    else      cprintf ("combine_seam: Seam is too crowded, can't be combined !\n");  }  if (source_seam->split3) {    if (!dest_seam->split3)      dest_seam->split3 = source_seam->split3;    else      cprintf ("combine_seam: Seam is too crowded, can't be combined !\n");  }  free_seam(source_seam);}/********************************************************************** * delete_seam * * Free this seam record and the splits that are attached to it. **********************************************************************/void delete_seam(void *arg) {  //SEAM  *seam)  SEAM *seam = (SEAM *) arg;  if (seam) {    if (seam->split1)      delete_split (seam->split1);    if (seam->split2)      delete_split (seam->split2);    if (seam->split3)      delete_split (seam->split3);    free_seam(seam);  }}/********************************************************************** * free_seam_list * * Free all the seams that have been allocated in this list.  Reclaim * the memory for each of the splits as well. **********************************************************************/void free_seam_list(SEAMS seam_list) {  int x;  array_loop (seam_list, x) delete_seam (array_value (seam_list, x));  array_free(seam_list);}/********************************************************************** * test_insert_seam * * Return true if insert_seam will succeed. **********************************************************************/bool test_insert_seam(SEAMS seam_list,                      int index,                      TBLOB *left_blob,                      TBLOB *first_blob) {  SEAM *test_seam;  TBLOB *blob;  int test_index;  int list_length;  list_length = array_count (seam_list);  for (test_index = 0, blob = first_blob->next;  test_index < index; test_index++, blob = blob->next) {    test_seam = (SEAM *) array_value (seam_list, test_index);    if (test_index + test_seam->widthp < index &&        test_seam->widthp + test_index == index - 1 &&        account_splits_right(test_seam, blob) < 0)      return false;  }  for (test_index = index, blob = left_blob->next;  test_index < list_length; test_index++, blob = blob->next) {    test_seam = (SEAM *) array_value (seam_list, test_index);    if (test_index - test_seam->widthn >= index &&        test_index - test_seam->widthn == index &&        account_splits_left(test_seam, first_blob, blob) < 0)      return false;  }  return true;}/********************************************************************** * insert_seam * * Add another seam to a collection of seams at a particular location * in the seam array. **********************************************************************/SEAMS insert_seam(SEAMS seam_list,                  int index,                  SEAM *seam,                  TBLOB *left_blob,                  TBLOB *first_blob) {  SEAM *test_seam;  TBLOB *blob;  int test_index;  int list_length;  list_length = array_count (seam_list);  for (test_index = 0, blob = first_blob->next;  test_index < index; test_index++, blob = blob->next) {    test_seam = (SEAM *) array_value (seam_list, test_index);    if (test_index + test_seam->widthp >= index) {      test_seam->widthp++;       /*got in the way */    }    else if (test_seam->widthp + test_index == index - 1) {      test_seam->widthp = account_splits_right(test_seam, blob);      if (test_seam->widthp < 0) {        cprintf ("Failed to find any right blob for a split!\n");        print_seam("New dud seam", seam);        print_seam("Failed seam", test_seam);      }    }  }  for (test_index = index, blob = left_blob->next;  test_index < list_length; test_index++, blob = blob->next) {    test_seam = (SEAM *) array_value (seam_list, test_index);    if (test_index - test_seam->widthn < index) {      test_seam->widthn++;       /*got in the way */    }    else if (test_index - test_seam->widthn == index) {      test_seam->widthn = account_splits_left(test_seam, first_blob, blob);      if (test_seam->widthn < 0) {        cprintf ("Failed to find any left blob for a split!\n");        print_seam("New dud seam", seam);        print_seam("Failed seam", test_seam);      }    }  }  return (array_insert (seam_list, index, seam));}/********************************************************************** * account_splits_right * * Account for all the splits by looking to the right. * in the blob list. **********************************************************************/int account_splits_right(SEAM *seam, TBLOB *blob) {  inT8 found_em[3];  inT8 width;  found_em[0] = seam->split1 == NULL;  found_em[1] = seam->split2 == NULL;  found_em[2] = seam->split3 == NULL;  if (found_em[0] && found_em[1] && found_em[2])    return 0;  width = 0;  do {    if (!found_em[0])      found_em[0] = find_split_in_blob (seam->split1, blob);    if (!found_em[1])      found_em[1] = find_split_in_blob (seam->split2, blob);    if (!found_em[2])      found_em[2] = find_split_in_blob (seam->split3, blob);    if (found_em[0] && found_em[1] && found_em[2]) {      return width;    }    width++;    blob = blob->next;  }  while (blob != NULL);  return -1;}/********************************************************************** * account_splits_left * * Account for all the splits by looking to the left. * in the blob list. **********************************************************************/int account_splits_left(SEAM *seam, TBLOB *blob, TBLOB *end_blob) {  static inT32 depth = 0;  static inT8 width;  static inT8 found_em[3];  if (blob != end_blob) {    depth++;    account_splits_left (seam, blob->next, end_blob);    depth--;  }  else {    found_em[0] = seam->split1 == NULL;    found_em[1] = seam->split2 == NULL;    found_em[2] = seam->split3 == NULL;    width = 0;  }  if (!found_em[0])    found_em[0] = find_split_in_blob (seam->split1, blob);  if (!found_em[1])    found_em[1] = find_split_in_blob (seam->split2, blob);  if (!found_em[2])    found_em[2] = find_split_in_blob (seam->split3, blob);  if (!found_em[0] || !found_em[1] || !found_em[2]) {    width++;    if (depth == 0) {      width = -1;    }  }  return width;}/********************************************************************** * find_split_in_blob * * Return TRUE if the split is somewhere in this blob. **********************************************************************/bool find_split_in_blob(SPLIT *split, TBLOB *blob) {  TESSLINE *outline;#if 0  for (outline = blob->outlines; outline != NULL; outline = outline->next)    if (is_split_outline (outline, split))      return TRUE;  return FALSE;#endif  for (outline = blob->outlines; outline != NULL; outline = outline->next)    if (point_in_outline(split->point1, outline))      break;  if (outline == NULL)    return FALSE;  for (outline = blob->outlines; outline != NULL; outline = outline->next)    if (point_in_outline(split->point2, outline))      return TRUE;  return FALSE;}/********************************************************************** * join_two_seams * * Merge these two seams into a new seam.  Duplicate the split records * in both of the input seams.  Return the resultant seam. **********************************************************************/SEAM *join_two_seams(SEAM *seam1, SEAM *seam2) {  SEAM *result = NULL;  SEAM *temp;  assert(seam1 &&seam2);  if (((seam1->split3 == NULL && seam2->split2 == NULL) ||    (seam1->split2 == NULL && seam2->split3 == NULL) ||    seam1->split1 == NULL ||  seam2->split1 == NULL) && (!shared_split_points (seam1, seam2))) {    clone_seam(result, seam1);    clone_seam(temp, seam2);    combine_seams(result, temp);  }  return (result);}/********************************************************************** * new_seam * * Create a structure for a "seam" between two blobs.  This data * structure may actually hold up to three different splits. * Initailization of this record is done by this routine. **********************************************************************/SEAM *new_seam(PRIORITY priority,               int x_location,               SPLIT *split1,               SPLIT *split2,               SPLIT *split3) {  SEAM *seam;  seam = newseam ();  seam->priority = priority;  seam->location = x_location;  seam->widthp = 0;  seam->widthn = 0;  seam->split1 = split1;  seam->split2 = split2;  seam->split3 = split3;  return (seam);}/********************************************************************** * new_seam_list * * Create a collection of seam records in an array. **********************************************************************/SEAMS new_seam_list() {  return (array_new (NUM_STARTING_SEAMS));}/********************************************************************** * print_seam * * Print a list of splits.  Show the coordinates of both points in * each split. **********************************************************************/void print_seam(const char *label, SEAM *seam) {  if (seam) {    cprintf(label);    cprintf (" %6.2f @ %5d, p=%d, n=%d ",      seam->priority, seam->location, seam->widthp, seam->widthn);    print_split (seam->split1);    if (seam->split2) {      cprintf (",   ");      print_split (seam->split2);      if (seam->split3) {        cprintf (",   ");        print_split (seam->split3);      }    }    cprintf ("\n");  }}/********************************************************************** * print_seams * * Print a list of splits.  Show the coordinates of both points in * each split. **********************************************************************/void print_seams(const char *label, SEAMS seams) {  int x;  char number[CHARS_PER_LINE];  if (seams) {    cprintf ("%s\n", label);    array_loop(seams, x) {      sprintf (number, "%2d:   ", x);      print_seam (number, (SEAM *) array_value (seams, x));    }    cprintf ("\n");  }}/********************************************************************** * shared_split_points * * Check these two seams to make sure that neither of them have two * points in common. Return TRUE if any of the same points are present * in any of the splits of both seams. **********************************************************************/int shared_split_points(SEAM *seam1, SEAM *seam2) {  if (seam1 == NULL || seam2 == NULL)    return (FALSE);  if (seam2->split1 == NULL)    return (FALSE);  if (point_in_seam (seam1, seam2->split1))    return (TRUE);  if (seam2->split2 == NULL)    return (FALSE);  if (point_in_seam (seam1, seam2->split2))    return (TRUE);  if (seam2->split3 == NULL)    return (FALSE);  if (point_in_seam (seam1, seam2->split3))    return (TRUE);  return (FALSE);}