chain2_piece.c

LastWave

/*..........................................................................*/
/*                                                                          */
/*      L a s t W a v e    P a c k a g e 'dwtrans2d' 2.1                    */
/*                                                                          */
/*      Copyright (C) 1998-2002  E.Bacry, J.Fraleu, J.Kalifa, E. Le Pennec, */
/*                         W.L. Hwang , S.Mallat, S.Zhong                   */
/*      emails : [e-mail]                             */
/*               [e-mail]                               */
/*               [e-mail]                               */
/*               [e-mail]                             */
/*               [e-mail]                               */
/*               [e-mail]                                   */
/*               [e-mail]                               */
/*                                                                          */
/*..........................................................................*/
/*                                                                          */
/*      This program is a free software, you can redistribute it and/or     */
/*      modify it under the terms of the GNU General Public License as      */
/*      published by the Free Software Foundation; either version 2 of the  */
/*      License, or (at your option) any later version                      */
/*                                                                          */
/*      This program is distributed in the hope that it will be useful,     */
/*      but WITHOUT ANY WARRANTY; without even the implied warranty of      */
/*      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the       */
/*      GNU General Public License for more details.                        */
/*                                                                          */
/*      You should have received a copy of the GNU General Public License   */
/*      along with this program (in a file named COPYRIGHT);                */
/*      if not, write to the Free Software Foundation, Inc.,                */
/*      59 Temple Place, Suite 330, Boston, MA  02111-1307  USA             */
/*                                                                          */
/*..........................................................................*/



#include "lastwave.h"
#include "extrema2d.h"  


/*****************************************************************/
/* partition the chains such that all the points in a chain will */
/* have the same corresponding chain in coarser scale            */
/*****************************************************************/

void W2_partition_cross_scale_chain(EXTLIS2 extlis,CHAINLIS2 chainlis)
{
  EXT2 ext, *values;
  CHAIN2 chain, newchain;
  int i, j, nrow, ncol;
  int idx;

  nrow = extlis->nrow;
  ncol = extlis->ncol;
  values = extlis->first;

  for(i = 0; i < nrow; i++)
    for( j = 0; j < ncol; j++)
      if(ext = values[i * ncol + j]) {
	if (ext->coarser) { 
	  ext->chain_index = ext->coarser->chain_index;
	  if(ext->coarser->finer != ext) Errorf("HaHa");
	}
      }

  for(i = 0; i < nrow; i++)
    for(j = 0; j < ncol; j++)
      if(ext = values[i * ncol +j])  {
	if(ext->coarser == NULL) {
	  ext->chain_index = -1; 
	}
      }


  for(chain = chainlis->first; chain; chain = chain->next) {
    idx = -1;
    for(ext = chain->first; ext; ext = ext->next) {
      if(ext->coarser) {
	idx = ext->chain_index;
	if(ext->next) {
	  if ((ext->next->chain_index != idx) && 
	      (ext->next->chain_index != -1)) {
	    newchain = NewChain2();
	    W2_chain_split_2(chain, ext->next, newchain);
	    W2_chain_append(chain, newchain);
	    break;
	  }
	}
      }
    }
  }
  W2_update_chain_pic(chainlis);
  W2_chainning_direction(chainlis);
  W2_collect_point_in_point_pic(extlis, chainlis);
  W2_remove_point_in_chain_pic(extlis, chainlis);  

}

/****************************************************************/      
/* return a chain haveing the same coarser chain as the chain1  */
/****************************************************************/

CHAIN2 W2_cross_scale_chain(CHAIN2 chain1,CHAIN2 chain2)
{
  int found = NO;
  EXT2 point1, point2;
 

  point1 = W2_first_coarser(chain1->first);
  if(point1) {
    for(chain2; chain2; chain2 = chain2->next) {
      point2 = W2_first_coarser(chain2->first);
      if(point2) {
        if(point1->coarser->chain ==  point2->coarser->chain) {
          found = YES;
          break;
        }
      }
    }
  }
    
  if(found) return(chain2); 
  else return(NULL);
}


/********************************************************************/
/* merge chains having the same coarser chain into a chain         */
/********************************************************************/
 
void W2_merge_cross_scale_chain(CHAINLIS2 chainlis)
{
  CHAIN2 chain, finger, mark,  coarse_chain, merge_chain;
  EXT2 lastpoint, mark2, ext;
  int i, NUM = 1024, first;
  CHAIN2 *score;

  score = (CHAIN2 *)Malloc(sizeof(CHAIN2) * NUM);

  for(i = 0; i < NUM; i++)
    score[i] = NULL;

  chain = chainlis->first;
  while(chain) {
    if(chain->first) {
      finger = W2_cross_scale_chain(chain, chain->next);
      while(finger) {
	mark = finger->next;
	mark2 = W2_first_coarser(finger->first);
	coarse_chain = mark2->coarser->chain;
	ext = coarse_chain->first;
	i = 0;
	while(ext != mark2->coarser)  {
	  i = i + 1;
	  if(i >= NUM) Errorf("MERGE_CROSS_SCALE_CHAIN: i > NUM");
	  ext = ext->next;
	}
	score[i] = finger;
	RemoveChain2FromChainLis2(finger, chainlis);
	finger = mark;
	finger = W2_cross_scale_chain(chain, finger);
      }
      
      mark2 = W2_first_coarser(chain->first);
      if(mark2) {
	coarse_chain = mark2->coarser->chain;
	ext = coarse_chain->first;
	i = 0;
	while(ext != mark2->coarser) {
	  i = i + 1;
	  if(i >= NUM) Errorf("MERGE_CROSS_SCALE_CHAIN: i > NUM");
	  ext = ext->next;
	}
	score[i] = chain;

	i = 0;
	first = YES;
	while(i < NUM) {
	  if(score[i] != NULL) {
	    if(first) {
	      merge_chain = score[i];
	      first= NO;
	    }
	    else {
	      lastpoint = W2_last_point(merge_chain);
	      W2_insertafter(lastpoint, score[i]->first);
	    }
	  }
	  i = i + 1;
	}
	chain->first = merge_chain->first;
      }
    }
    chain = chain->next;
    for(i = 0; i < NUM; i++)
      score[i] = NULL;
  }
  W2_update_chain_pic(chainlis);

  Free((char *)score);
}

/************************************************************/
/* to remove the zigzag in the fine scale chains            */
/************************************************************/

void W2_zigzag_off(EXTLIS2 finer_point_pic,CHAINLIS2 finer_chain_pic,EXTLIS2 extlis,CHAINLIS2 chainlis)
{
  EXT2 point1, point2, mark1, mark2;
  EXT2 finger1, finger2, lastpoint,tmp;
  EXT2 ext, finger;
  CHAIN2 chain;
  int nextflag, nb;
   
  EXT2 finer_first, finer_last;

  for(chain = chainlis->first; chain; chain = chain->next) {
    finer_first = NULL;
    finer_last = NULL;
    if(chain->first) {
      point2 = W2_first_finer_coarser_is_point(chain->first); /* 2 1 */
      if(point2) {
	finer_first = point2->finer;
	tmp = W2_last_finer_coarser_is_point(chain->first);
	finer_last = tmp->finer;

	nb = 0;
	finger = finer_first->chain->first;
	while(finger) {
	  if (finger->coarser && (finger->coarser->finer == finger))
	    nb = nb + 1;
	  finger = finger->next;
	}

	if(finer_first && finer_last && (nb > 2)) {

	  /* circle */
	  tmp = W2_last_point(finer_first->chain);
	  tmp->next = finer_first->chain->first;
	  finer_first->chain->first->previous = tmp;
	  finer_first->chain->first = finer_first;

	  /* hole */
	  if(finer_first->previous) {
	    finer_first->previous->next = NULL;
	    finer_first->previous = NULL;
	  }
	  W2_update_chain(finer_first->chain, finer_first->chain_index); 
	}
      
	point1 = W2_first_finer_coarser_is_point(point2->next);
      }
      else point1 = NULL;

      while(point2 && point1) {
	ext = point2;
	
	finger1 = point1->finer;
        finger2 = point2->finer;
	if(finger1 && finger2) {

	  W2_chain_order_reverse(finger2, finger1, &nextflag);

	  if((nextflag ==YES)&&(finger2->next != finger1)) {
	    mark2 = finger2->next;
	    mark1 = finger1->previous;
 	    lastpoint = W2_last_point(finger1->chain); 
	    if(mark2) mark2->previous = NULL;
	    if(mark1) mark1->next = NULL;
	    finger2->next = finger1;
	    finger1->previous = finger2;
	    W2_insertafter(lastpoint, mark2); 
	  }
	  if(nextflag == NO) { 
	    point2->finer->coarser = point1;
	    point1->finer->coarser = point2;
	    tmp = point2->finer;
	    point2->finer = point1->finer;
	    point1->finer = tmp;
	    point1 = point2; 
	  }
	  if(nextflag == -1) {
	  } 
	}
	point2 = point1; /* ok */
	point1 = W2_first_finer_coarser_is_point(point2->next);
      }

      if(point2 && finer_last && (nb > 2) ){
	finger = finer_last->next; 
	while(finger) {
	  mark1 = finger->next;
	  W2_delete_a_point(finger, finer_point_pic);
	  finger = mark1;
	}
      }
    }
  }
  
  W2_collect_point_in_point_pic(finer_point_pic, finer_chain_pic);
  W2_remove_point_in_chain_pic(finer_point_pic, finer_chain_pic);  
}