online compiler and debugger for c/c++

// typ reprezentujący prostokąt interface Rectangle { x: number; y: number; width: number; height: number; // dodatkowa informacja, aby móc zidentyfikować elementy label?: string; } // klasa reprezentująca siatkę przestrzenną class SpatialHash { // mapa przechowująca komórki siatki i obiekty w nich zawarte private hashTable: Map<string, Rectangle[]> = new Map(); // tworząc siatkę decydujemy o rozmiarze komórek constructor(private cellSize: number) {} // metoda pomocnicza do sprawdzania czy dwa prostokąty się przecinają private intersects(a: Rectangle, b: Rectangle): boolean { return ( b.x <= a.x + a.width && b.x + b.width >= a.x && b.y <= a.y + a.height && b.y + b.height >= a.y ); } // metoda zwracająca klucz komórki na jej podstawie współrzędnych private getCellKey(gridX: number, gridY: number): string { // klucz będzie prostym stringiem zawierającym współrzędne komórki return `${gridX},${gridY}`; } // metoda zwracająca zakres komórek zajmowanych przez obiekt na jednej osi private getCellRange(startPos: number, size: number): [number, number] { // wyznaczamy początek i koniec zakresu komórek const start = Math.floor(startPos / this.cellSize); const end = Math.floor((startPos + size) / this.cellSize); // zwracamy zakres jako parę liczb return [start, end]; } // metoda zwracająca komórki zajmowane przez obiekt private getObjectCells(obj: Rectangle): string[] { // wyznaczamy zakres komórek zajmowanych przez obiekt na osi X const [minX, maxX] = this.getCellRange(obj.x, obj.width || 0); // oraz na osi Y const [minY, maxY] = this.getCellRange(obj.y, obj.height || 0); // tworzymy tablicę zawierającą klucze wszystkich komórek const cells: string[] = []; // iterujemy po wszystkich komórkach w zakresie for (let x = minX; x <= maxX; x++) { for (let y = minY; y <= maxY; y++) { // dodajemy klucz komórki do tablicy cells.push(this.getCellKey(x, y)); } } // zwracamy tablicę kluczy return cells; } // metoda dodająca obiekt do siatki public insert(obj: Rectangle): void { // wyznaczamy komórki zajmowane przez obiekt const cells = this.getObjectCells(obj); // iterujemy po wszystkich komórkach for (const key of cells) { // jeśli komórka nie istnieje, tworzymy ją if (!this.hashTable.has(key)) { this.hashTable.set(key, []); } // dodajemy obiekt do komórki this.hashTable.get(key)!.push(obj); } } // metoda zwracająca obiekty przecinające się z zadanym prostokątem public query(range: Rectangle): Rectangle[] { // tworzymy zbiór wyników const result = new Set<Rectangle>(); // wyznaczamy komórki zajmowane przez zadany prostokąt const cells = this.getObjectCells(range); // iterujemy po wszystkich komórkach for (const key of cells) { // pobieramy obiekty z komórki const objects = this.hashTable.get(key); if (objects) { // jeśli komórka istnieje, iterujemy po wszystkich obiektach w niej zawartych for (const obj of objects) { // sprawdzamy czy obiekt przecina się z zadanym prostokątem if (this.intersects(obj, range)) { // jeśli tak, dodajemy go do zbioru wyników result.add(obj); } } } } // zwracamy tablicę wyników return [...result]; } // metoda zwracająca zapisaną liczbę komórek w siatce public getCellCount(): number { return this.hashTable.size; } } // przykład użycia const sh = new SpatialHash(100); // dodawanie obiektów do drzewa sh.insert({ x: 100, y: 200, width: 50, height: 30, label: "A" }); sh.insert({ x: 300, y: 400, width: 100, height: 80, label: "B" }); sh.insert({ x: 100, y: 300, width: 20, height: 20, label: "C" }); sh.insert({ x: 250, y: 500, width: 10, height: 10, label: "D" }); sh.insert({ x: 900, y: 900, width: 5, height: 5, label: "E" }); sh.insert({ x: 500, y: 500, width: 100, height: 100, label: "F" }); sh.insert({ x: 100, y: 100, width: 100, height: 100, label: "G" }); // w wyniku dodania tych elementów, struktura wykorzysta 13 komórek siatki console.log(sh.getCellCount()); // wyszukiwanie w obszarze const searchArea: Rectangle = { x: 80, y: 180, width: 100, height: 100 }; const results = sh.query(searchArea); console.log(results); // powinno zwrócić obiekty A i G