find_closest_node.F File Reference

#include "implicit_f.inc"
#include "com04_c.inc"

Go to the source code of this file.

Functions/Subroutines
subroutine	find_closest_node (leading_direction, n1, n2, n3, x1, x2, eps, key1, key2, id_x2, id_list)

Function/Subroutine Documentation

find_closest_node()

subroutine find_closest_node	(	integer, intent(in)	leading_direction,
		integer, intent(in)	n1,
		integer, intent(in)	n2,
		integer, intent(in)	n3,
		intent(in)	x1,
		intent(in)	x2,
		intent(in)	eps,
		integer, dimension(n1), intent(in)	key1,
		integer, dimension(n2), intent(in)	key2,
		integer, dimension(n2), intent(in)	id_x2,
		integer, dimension(n1), intent(inout)	id_list )

Definition at line 28 of file find_closest_node.F.

!---
C  Nearest Neighbor search
C  This routines returns ID_LIST and DIST such as
C  ID_LIST(I=1:N2) is the id of the closest node in X1(ID_X2(1:N2))
C
C This NNS algorithm is not optimal
C - worst case O(N1 x N2) 
C - best case O(N1 x LOG(N1)) + O(N1)
C - Expected in practice: O(N1 log(N1)) + O (N1 x (N2)^(1/3)) 
C      which is good enough for cases where N2 << N1
C-----------------------------------------------
C   I m p l i c i t   T y p e s
C-----------------------------------------------
#include "implicit_f.inc"
C-----------------------------------------------
C   C o m m o n   B l o c k s
C-----------------------------------------------
! com04 : numels/numelq/numeltg
#include "com04_c.inc"
       
! --------------------------------------
        INTEGER, INTENT(IN) :: LEADING_DIRECTION
        INTEGER, INTENT(IN)    ::  N1,N2,N3  ! N1: number if node
                                             ! N2: number of root nodes
                                             ! N3 : total number of node
        my_real, DIMENSION(3,N1), INTENT(IN)    ::  x1 ! Coordinates 
        my_real, DIMENSION(3,N3), INTENT(IN)    ::  x2 ! Coordinates 
        my_real, INTENT(IN)    ::  eps  ! Minimum distance between two distinct points
        INTEGER, DIMENSION(N1), INTENT(IN) :: KEY1
        INTEGER, DIMENSION(N2), INTENT(IN) ::  KEY2
        INTEGER, DIMENSION(N2), INTENT(IN) ::  ID_X2  ! Indexes of 'root' coordinates
        INTEGER, DIMENSION(N1),INTENT(INOUT) ::  ID_LIST! id of the closest root node
! --------------------------------------
C      LOCAL VARIABLES
        INTEGER :: I,J,ID,info,JMIN
        INTEGER :: LAST_POSITION
        my_real :: leading_size
        my_real :: delta,dx,dy,dz,dxl,dyl,dzl,dl
        integer :: ijk
! --------------------------------------
        last_position = 1 
        jmin = 1
        DO i = 1,n1
            dx =abs(x2(1,id_x2(key2(last_position))) - x1(1,key1(i)))   
            dy =abs(x2(2,id_x2(key2(last_position))) - x1(2,key1(i)))   
            dz =abs(x2(3,id_x2(key2(last_position))) - x1(3,key1(i)))   
            leading_size = abs(x2(leading_direction,id_x2(key2(last_position))) - x1(leading_direction,key1(i)))   
            delta = sqrt(dx*dx+dy*dy+dz*dz)
 
C        Avoid nodes closer than EPS
            IF (delta < eps) delta = huge(delta)
 
C        Upward search
            j = last_position + 1
            jmin = last_position
            id = key2(last_position)
            dxl = leading_size
            DO WHILE (j <= n2 .AND. (dxl <= delta .OR. delta < eps))
                dxl =abs(x2(1,id_x2(key2(j))) - x1(1,key1(i)))   
                dyl =abs(x2(2,id_x2(key2(j))) - x1(2,key1(i)))   
                dzl =abs(x2(3,id_x2(key2(j))) - x1(3,key1(i)))   
                dl = sqrt(dxl*dxl+dyl*dyl+dzl*dzl)
                IF (dl  < delta .AND. dl  > eps) THEN
                    delta = dl
                    id = key2(j)
                    jmin = j
                ENDIF
                j = j + 1
                IF (j <= n2) dxl =abs(x2(leading_direction,id_x2(key2(j)))-x1(leading_direction,key1(i)))  
            ENDDO
 
C        Backward search
            j = last_position
            dxl = leading_size
            DO WHILE (j > 0 .AND. (dxl <= delta .OR. delta < eps))
                dxl =abs(x2(1,id_x2(key2(j))) - x1(1,key1(i)))   
                dyl =abs(x2(2,id_x2(key2(j))) - x1(2,key1(i)))   
                dzl =abs(x2(3,id_x2(key2(j))) - x1(3,key1(i)))   
                dl = sqrt(dxl*dxl+dyl*dyl+dzl*dzl)
                IF (dl  < delta .AND. dl > eps) THEN
                    delta = dl
                    id = key2(j)
                    jmin = j
                ENDIF
                j = j - 1
                IF (j > 0)  dxl =abs(x2(leading_direction,id_x2(key2(j)))-x1(leading_direction,key1(i)))  
            ENDDO
            last_position = jmin 
            id_list(key1(i)) = id
        ENDDO
 
        DO i = 1,n1
            id_list(i) = id_x2(id_list(i))
        ENDDO
 
        RETURN
!---