\ * icvFindLoop * \****************************************************************************************/
| 807 | * icvFindLoop * |
| 808 | \****************************************************************************************/ |
| 809 | static int |
| 810 | icvFindLoop( CvEMDState * state ) |
| 811 | { |
| 812 | int i, steps = 1; |
| 813 | CvNode2D *new_x; |
| 814 | CvNode2D **loop = state->loop; |
| 815 | CvNode2D *enter_x = state->enter_x, *_x = state->_x; |
| 816 | char *is_used = state->is_used; |
| 817 | |
| 818 | memset( is_used, 0, state->ssize + state->dsize ); |
| 819 | |
| 820 | new_x = loop[0] = enter_x; |
| 821 | is_used[enter_x - _x] = 1; |
| 822 | steps = 1; |
| 823 | |
| 824 | do |
| 825 | { |
| 826 | if( (steps & 1) == 1 ) |
| 827 | { |
| 828 | /* find an unused x in the row */ |
| 829 | new_x = state->rows_x[new_x->i]; |
| 830 | while( new_x != 0 && is_used[new_x - _x] ) |
| 831 | new_x = new_x->next[0]; |
| 832 | } |
| 833 | else |
| 834 | { |
| 835 | /* find an unused x in the column, or the entering x */ |
| 836 | new_x = state->cols_x[new_x->j]; |
| 837 | while( new_x != 0 && is_used[new_x - _x] && new_x != enter_x ) |
| 838 | new_x = new_x->next[1]; |
| 839 | if( new_x == enter_x ) |
| 840 | break; |
| 841 | } |
| 842 | |
| 843 | if( new_x != 0 ) /* found the next x */ |
| 844 | { |
| 845 | /* add x to the loop */ |
| 846 | loop[steps++] = new_x; |
| 847 | is_used[new_x - _x] = 1; |
| 848 | } |
| 849 | else /* didn't find the next x */ |
| 850 | { |
| 851 | /* backtrack */ |
| 852 | do |
| 853 | { |
| 854 | i = steps & 1; |
| 855 | new_x = loop[steps - 1]; |
| 856 | do |
| 857 | { |
| 858 | new_x = new_x->next[i]; |
| 859 | } |
| 860 | while( new_x != 0 && is_used[new_x - _x] ); |
| 861 | |
| 862 | if( new_x == 0 ) |
| 863 | { |
| 864 | is_used[loop[--steps] - _x] = 0; |
| 865 | } |
| 866 | } |