2016-10-04 4 views
2

현재 Bukkit 플러그인을 사용하여 사용자 정의 영역을 요청하고 있으며, 직사각형 (및 .intersect())을 사용하여 요청이 생성되기 전에 영역이 겹치는 지 확인합니다.수천 개의 직사각형이 교차하는지 확인합니다.

필자는 분명히 꽤 많은 시간이 걸릴 것으로 예상되는 모든 기존의 주장 (실제로는 수만 명이 될 것입니다)을 확인할 필요가없는 방법을 생각하려고합니다. 또한 플레이어가 휴식 블록이나 장소 블록과 같은 일을 할 때 클레임 소유자를 확인해야합니다.

내 시스템 (사용자 정의 클레임 크기를 허용하지 않음, 사각형 만 허용) 클레임 주변의 클레임 (최대 64 블록 떨어져 있음)을 감지 할 수 있기 때문에 최대 10 개 클레임 만 검사하면됩니다. 이 시스템에서 클레임의 최대 반경)하지만 이제는 클레임 ​​크기가 새로운 시스템의 이론상으로 무한히 커질 수 있습니다.

방대한 양의 시간이 걸릴 모든 사각형을 확인하고 있습니까? 내가 멍청한가요? 크기가 무제한이라도 근처의 직사각형을 확인하는 방법이 있습니까?

답변

1

우선 수천 개의 사각형을 검사하는 것이 Java (또는 플러그인)에 큰 도움이되지는 않습니다. 간단한 수학은 밀리 초 단위로 수행되어야합니다. 당신의 소유자 문제를 다루기 위해서 당신은 내 자신의 사각형과 소유자 클래스를 생성 할 것을 권한다. 따라서 사각형에 정의 된 소유자가있을 수 있으며 현재 플레이어가 자신이 속한 영역의 소유자인지 간단히 확인할 수 있습니다.

public class custom_Area extends Rectangle{ 

    private owner o; 

    public owner getOwner() { 
     return o; 
    } 

    public void setOwner(owner o) { 
     this.o = o; 
    }  
} 

편집 :

난 그냥 100.000 임의의 사각형을 만들고 그 중 하나가 다른 사람과 교차할지 어떨지를 체크하여 테스트했습니다.

--Custom 사각형 클래스

public class area extends Rectangle{ 
private owner o; 
public area(owner o, int i, int i1, int i2, int i3) { 
    super(i, i1, i2, i3); 
    this.o = o; 
} 
public owner getO() { 
    return o; 
} 
public void setO(owner o) { 
    this.o = o; 
} 

}

--Custom 소유자 클래스

public class owner { 
String name; 

public owner(String name) { 
    this.name = name; 
} 
public String getName() { 
    return name; 
} 
public void setName(String name) { 
    this.name = name; 
} 

}

--main 클래스

public class Rectanglesearch { 
     public static area a[] = new area[100000]; 
     public static owner o[] = new owner[10]; 
     public static int intersectCounter = 0; 
     public static int ownerCounter = 0; 

    public static void main(String[] args) { 
     for(int y = 0; y<10;y++){ 
     o[y] = new owner("y"); 
     } 
     for (int i = 0; i < 100000; i++) { 
      a[i] = new area(o[(int)(Math.random() * 10)],random(),random(),random(),random()); 
     } 
     checkArea(a[10]); 
     checkOwner(o[3]); 
     System.out.println("Area a[10] intersects with "+intersectCounter+" out of "+a.length); 
     System.out.println("Owner o[3] owns "+ownerCounter+" areas out of "+a.length); 
    } 
    public static int random(){ 
    return (int)(Math.random() * 100000) + 1; 
    } 
    public static void checkArea(area ab){ 
      for (area a1 : a) { 
       if (ab.intersects(a1)) { 
        intersectCounter +=1; 
       } 
      } 
    } 
    public static void checkOwner(owner ob){ 
      for (area a1 : a){ 
       if(a1.getOwner()==ob){ 
        ownerCounter +=1; 
       } 
      } 
    } 
} 
checkArea (영역 AB)은 남자 영역과 교차 방법을 반환

방법 영역 AB 방법 checkOwner (소유자 산부인과) 매뉴얼 영역을 소유하는 방법

1

같은 quadtree으로 가속 구조에 사각형을 저장 생각해 내 산부인과 돌아 . 기존 세트를 기준으로 새 사각형을 테스트하려면 트리를 포함 할 노드로 트리를 탐색하고, 도중에 각 노드의 사각형에 대해 테스트하지만 트래버스하지 않는 모든 노드에서 사각형을 무시합니다. 이렇게하면 개별적으로 개별적으로 테스트하지 않고도 새로운 사각형과 교차 할 수없는 많은 사각형이 빠르게 제거됩니다.

binary space partitioning과 같은 다른 가속 구조도 대안으로 사용할 수 있습니다. 관련성이있는 몇 가지 다른 목록을 보려면 spatial indexes을 읽어보십시오.


집합에 새로운 직사각형을 추가하는 것이 자주 발생하지 않으므로 성능이 크게 우려되지 않습니다.그러나 플러그인이 특정 지역 (블록과 같은)이 요청 된 지역 중 하나에 있는지 여부를 확인해야 할 필요가 있다고 생각합니다. 잠재적으로 모든 프레임 - 매우 빠를 필요가 있습니다. . quadtree 나 다른 가속 구조가 유용 할 것입니다.