duplicates - 在 Fortran 的大数组中查找所有具有容差的重复顶点的列表

Question

我正在尝试在 Fortran 中编写一个有效的子程序来查找数组中所有重复顶点的列表。容差（使用参数 固定paraEps）对应于我在其中查找重复点的每个点周围的半径。为有限元分析定义的顶点和每个组件的范围将取决于将应用这些方法的 3D 几何（我可以预期组件的值可以[-10^6,10^6]以10^-6.

目前，以下代码在大约 150k 个顶点上运行，但它将用于 1-3M 顶点数组。

例子：

顶点数组。在这里，我只使用了一些小节点列表。就我而言，节点位于没有特定分布的 3D 空间中。

 verticesArray = 
[ 0 0 0,
  0 1 0
  1 0 0
  1 0 0
  1 1 1
  0 1 0
  1 2 3
  1 2 3
  0 1.0001 0
  0 1.1 0
  1 2 4]

公差为 的结果列表（0 表示顶点没有重复项）10^-3。

list = [ 0 1 2 2 0 1 3 3 1 0 0]

我已经编写了第一个版本，它运行良好但仍然很慢，尤其是顶点数量很大。

请注意，startItem我可以指定一个整数，而不是从数组的开头开始搜索。

MWE：

module test 

implicit none

contains

subroutine get_dup_nodes(nbNodes,dimP,arrayIn,nbDupNodes)
    !
    integer,intent(in) :: nbNodes,dimP                      ! number of nodes and dimension
    double precision,dimension(:,:),intent(in) :: arrayIn   ! list of coordinates
    !
    integer,intent(out) :: nbDupNodes   
    !
    double precision,dimension(dimP) :: coorNode

    integer,dimension(:),allocatable :: listDup         !list of duplicates


    logical :: currUnique
    double precision,allocatable :: distVal
    integer :: itN,itM,itF,minCurrIt,currIt,nbTmp,sizeR,startItemVal
    !
    double precision,parameter :: paraEps=1e-3
    !

    !initialize variables
    allocate(listDup(nbNodes))
    listDup=0
    nbDupNodes=0
    itF=0
    distVal=1.
    !
    do itN=1,nbNodes
        !coordinate current node
        coorNode=arrayIn(itN,:)
        currUnique=.true.
        !search for current nodes coordinates in the list of nodes
        if (listDup(itN).eq.0) then
            do itM=itN+1,nbNodes
                ! compute distance to current point
                distVal = NORM2(coorNode-arrayIn(itM,:))
                ! if the distance is to small then duplicate
                if (distVal.le.paraEps) then
                    !first time it is a duplicate
                    if (currUnique) then
                        currUnique=.false.
                        nbDupNodes=nbDupNodes+1
                        listDup(itN)=nbDupNodes
                    endif
                    listDup(itM)=nbDupNodes
                endif
            enddo                
        endif
    enddo

    print *,listDup
end subroutine get_dup_nodes

end module test

program testb
use test
implicit none

double precision,dimension(33) :: valTmp
double precision,dimension(11,3) :: verticesArray
integer :: nbd

integer :: i,j,k

valTmp = (/ 0.,0.,0.,0.,1.,0.,1.,0.,0.,1.,0.,0.,1.,1.,1.,0.,1.,0.,1.,2.,3.,1.,2.,3.,0.,1.0001,0.,0.,1.1,0.,1.,2.,4. /)

k=1
do i=1,11
    do j=1,3
        verticesArray(i,j)=ValTmp(k)
        k=k+1
    enddo
    print *,verticesArray(i,:)
enddo

call get_dup_nodes(11,3,verticesArray,nbd)

end program testb

附加要求：如果您有关于此类算法的书籍的参考资料，它可能会很有用。

标签： duplicatesfortran