如何在三维域中检测某序列的结束位置（x，y，z）

Question

我对蛋白质进行了三维creo-EM扫描，这样它就包含了一条围绕自身弯曲和扭曲的链，并且在三维空间中有两条链的末端（就像连续的绳子）。我需要检测（x，y，z）的位置在给定的立方体空间的两个或可能的乘数2结束。扫描的立方体空间由扫描电镜提供的每个体素的密度表示（范围从0到1），因此“现有物质”给出的值接近1，“无物质”给出的密度值接近0。我需要一种方法来检测蛋白质的“绳子”边缘（可能的“绳子结束”的定义是在某些缠结的方向缺乏连续性。直观地说，我认为至少有两种方法：1）图论中的某个方法（我不能精确地指定-如果你知道一个-请命名或描述它）。2） 解析代数的导数-但我又不能说明具体的态度-所以请说出或解释一个。请指定建议方法的计算复杂度。我的项目是用Python实现的。请帮忙。提前谢谢。你知道吗

Answer 1

如果要在三维扫描中枚举每个连续路径（从而获得每个路径的端点），可以对每个位置应用基本的深度优先搜索，例如：

//applied at some voxel
dfs(...)
    for each surrounding voxel 
        dfs(...)

或细节：

class coordinate{
    x
    y
    z
    visited
}

initialize pathList
initialize coords

add all coordinates which contain "matter" to coords

dfs(coordinate,path)
    coordinate.visited = TRUE
    isEnd = TRUE
    FOR each coordinate
        //check each of the 26 possible locations (total 26 conditionals)
        IF coordinate.get(x-1,y-1,z+1) IN coords AND 
           NOT coordinate.get(x-1,y-1,z+1).visited THEN
            isEnd = FALSE
            path += coordinate.get(x-1,y-1,z+1)
            dfs(coordinate.get(x-1,y-1,z+1),path)
        ...
        IF coordinate.get(x+1,y+1,z-1) IN coords AND 
           NOT coordinate.get(x+1,y+1,z-1).visited THEN 
            isEnd = FALSE
            path += coordinate.get(x+1,y+1,z-1) 
            dfs(coordinate.get(x+1,y+1,z-1),path)
    IF isEnd THEN
        add path to pathList
    remove coordinate from coords

WHILE coords isn't empty
    dfs(coords.get(0),"")

通用过程（dfs）在许多其他站点上都有很好的文档记录，但是如果您想测试它，这里有一些粗糙的java（我对python不太熟悉）可以反映上面的内容：

public class C {

    ArrayList<Coordinate> coords = new ArrayList<>();
    ArrayList<String> paths = new ArrayList<>();



    static class Coordinate {
        int x, y, z;
        boolean visited;
        Coordinate(int x,int y,int z){
            this.x = x;
            this.y = y;
            this.z = z;
            visited = false;
        }

        public String toString() {
            return "("+x+","+y+","+z+")";
        }
    }



    void dfs(Coordinate c,String path) {
        c.visited=true;
        path+=c.toString();
        boolean isEnd = true;
        //apply dfs to 26 possible neighbors
        for(int x = c.x-1; x <= c.x+1; x++) {
            for (int y = c.y-1; y <= c.y+1; y++) {
                for (int z = c.z+1; z >= c.z-1; z ) {
                    Coordinate coord = getCoordinate(x,y,z);
                    //if coord exists and it's not been visited
                    if(coord!=null && !coord.visited && !coord.equals(c)) {
                        isEnd = false;
                        dfs(coord, path);
                    }
                }
            }
        }
        if(isEnd) paths.add(path);

        coords.remove(c);
    }

    Coordinate getCoordinate(int x,int y,int z){
        for(Coordinate b: coords){
            if(x==b.x && y==b.y && z==b.z) return b;
        }
        return null;
    }


    void search(){
        //while there are points in 3d space extend a path from one
        while(!coords.isEmpty()){
            dfs(coords.get(0),"");
        }
    }




    public static void main(String[] args) {

        C coord = new C();

        //for each place where there exists matter
        //create a coordinate object and add to coords
        // for example:
        coord.coords.add(new Coordinate(0,0,0));
        coord.coords.add(new Coordinate(-1,1,1));
        coord.coords.add(new Coordinate(1,1,1));
        coord.coords.add(new Coordinate(-1,2,2));
        coord.coords.add(new Coordinate(-1,0,2));
        coord.coords.add(new Coordinate(1,2,2));
        coord.coords.add(new Coordinate(1,0,2));

        coord.search();
        //print out each path on separate line, 
        //the path endings can easily be obtained from this 
        for(String s:coord.paths) System.out.println(s);

    }
}