Проверка пересечения тысяч прямоугольников

Question

В настоящее время я работаю над плагином Bukkit, чтобы требовать настраиваемые области, и я использую прямоугольники (и .intersect()), чтобы проверить, перекрываются ли регионы перед созданием претензии.

Я пытаюсь понять, как мне не нужно проверять каждое существующее требование (которого в конечном итоге будет десятки тысяч), так как это займет довольно много времени. Мне также нужно будет проверить владельцев претензий, когда игроки делают такие вещи, как блокировать блоки или блокировать места.

В моей нынешней системе (которая не позволяет настраивать размеры претензий, только квадраты). Мне нужно только проверить не более 10 заявок, потому что я могу обнаруживать претензии в непосредственной близости от претензии (не более 64 блоков, максимальный радиус претензий в этой системе), но теперь размеры заявок могут быть бесконечно большими в теории с новой системой.

Проверяет ли все прямоугольники на значительное количество времени? Неужели я тупой, есть ли способ проверить прямоугольники в окрестностях, даже если размер неограничен?

Answer 1

Прежде всего, проверка тысяч прямоугольников не будет большой проблемой для java (или вашего плагина). Его простая математика и должна быть выполнена в миллисекундах. Чтобы справиться с вашим владельцем Проблема я бы рекомендовал вам создать собственный прямоугольник и класс владельца. Таким образом, ваш прямоугольник может иметь определенного владельца, и вы можете просто проверить, является ли игрок владельцем области, в которой он сейчас находится.

public class custom_Area extends Rectangle{ 

    private owner o; 

    public owner getOwner() { 
     return o; 
    } 

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

EDIT:

Я просто проверял, создавая 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 (область абы) возвращает вам, как человек область пересекается с областью абы метод checkOwner (владелец О.Б.) вернет вас как человек области принадлежат моему О.Б.

Answer 2

Рассмотрят хранить ваши прямоугольники в структуре ускорения, такие как quadtree , Чтобы протестировать новый прямоугольник против существующего набора, вы перемещаетесь по дереву к узлу, который будет его содержать, тестируя прямоугольники в каждом узле по пути, но игнорируя прямоугольники во всех узлах, которые вы не проходите. Это быстро устраняет множество прямоугольников, которые не могут пересекать новый, без необходимости тестировать каждый отдельно.

Другие конструкции ускорения также возможны в качестве альтернатив, таких как binary space partitioning. Читайте о spatial indexes для получения списка из нескольких других, которые могут иметь значение.

---

Добавление новых прямоугольников в набор происходит не очень часто, поэтому производительность, вероятно, не вызывает большой озабоченности.Но я бы предположил, что ваш плагин также должен проверить, находится ли конкретная координата (например, блок) в пределах одного из заявленных регионов, и это может произойти гораздо чаще - потенциально каждый кадр - так что действительно нужно быстро , Для этого будет полезной квадрантная или другая структура ускорения.