Znajdowanie pozycji prostokąta, która sprawia, że obejmuje ona maksymalne punkty w przestrzeni 2D

Biorąc pod uwagę przestrzeń 2D z punktami X, jak mogę skutecznie znaleźć miejsce, w którym umieszczam prostokąt o stałym rozmiarze, tak aby obejmował on największą możliwą liczbę tych X punktów?Znajdowanie pozycji prostokąta, która sprawia, że obejmuje ona maksymalne punkty w przestrzeni 2D

Potrzebuję czegoś wzdłuż tych linii, aby ustawić rzutnię w grze 2D, którą buduję.

Źródło

2015-09-06 Harry Mexican

Czy wolno włączyć prostokąt lub boki są równoległe do osi X i Y? – dasblinkenlight

Dlaczego nie określić min i maksimum X i Y punktów i skonstruować prostokąta zakresu. Jeśli osie prostokąta są obrócone, jest to minimalny prostokąt ograniczający obszar, to obejmie wszystkie punkty, takie jak prostokąt zasięgu, ale będzie miał mniejszy obszar. Pierwsza opcja łatwa do wdrożenia, druga jest trudniejsza. –

niedozwolone jest przekręcanie prostokąta. –

Sortuj punkty od lewej do prawej. Ustaw wskaźnik left w skrajnym lewym punkcie, a wskaźnik right w prawym skrajnym punkcie, który mieści się w zakresie left + width. Następnie należy powtórzyć wszystkie punkty, ponownie obliczając pozycję wskaźnika za każdym razem, aż znajdzie się w ostatnim punkcie.
Sortowanie każdego podzestawu punktów między lewym a prawym od góry do dołu. Ustaw wskaźnik top w najwyższym punkcie, a wskaźnik bottom w najniższym punkcie, który mieści się w zakresie top + height. Następnie należy powtórzyć wszystkie punkty, ponownie obliczając pozycję wskaźnika za każdym razem, aż znajdzie się w ostatnim punkcie.
Dla każdego podzbioru punktów między lewym, prawym, górnym i dolnym, sprawdź, ile posiada punktów, i zachowaj optymalny podzbiór.
Po znalezieniu optymalnego podzbioru środek prostokąta znajduje się w połowie drogi między skrajnym lewym i prawym punktem, a w połowie między najwyższym i najniższym punktem.

Poniżej znajduje się prosta implementacja w języku Javascript, którą można zoptymalizować w wielu punktach. Uruchom fragment kodu, aby zobaczyć wyniki z losowymi danymi.

function placeRectangle(p, width, height) { 
 
    var optimal, max = 0; 
 
    var points = p.slice(); 
 
    points.sort(horizontal); 
 

 
    for (var left = 0, right = 0; left < points.length; left++) { 
 
     while (right < points.length && points[right].x <= points[left].x + width) ++right; 
 
     var column = points.slice(left, right); 
 
     column.sort(vertical); 
 

 
     for (var top = 0, bottom = 0; top < column.length; top++) { 
 
      while (bottom < column.length && column[bottom].y <= column[top].y + height) ++bottom; 
 
      if (bottom - top > max) { 
 
       max = bottom - top; 
 
       optimal = column.slice(top, bottom); 
 
      } 
 
      if (bottom == column.length) break; 
 
     } 
 
     if (right == points.length) break; 
 
    } 
 

 
    var left = undefined, right = undefined, top = optimal[0].y, bottom = optimal[optimal.length - 1].y; 
 
    for (var i = 0; i < optimal.length; i++) { 
 
     var x = optimal[i].x; 
 
     if (left == undefined || x < left) left = x; 
 
     if (right == undefined || x > right) right = x; 
 
    } 
 
    return {x: (left + right)/2, y: (top + bottom)/2}; 
 

 
    function horizontal(a, b) { 
 
     return a.x - b.x; 
 
    } 
 

 
    function vertical(a, b) { 
 
     return a.y - b.y; 
 
    } 
 
} 
 

 
var width = 160, height = 90, points = []; 
 
for (var i = 0; i < 10; i++) points[i] = {x: Math.round(Math.random() * 300), y: Math.round(Math.random() * 200)}; 
 
var rectangle = placeRectangle(points, width, height); 
 

 
// SHOW RESULT IN CANVAS 
 
var canvas = document.getElementById("canvas"); 
 
canvas.width = 300; canvas.height = 200; 
 
canvas = canvas.getContext("2d"); 
 
paintRectangle(canvas, rectangle.x - width/2, rectangle.y - height/2, width, height, 1, "red"); 
 
for (var i in points) paintDot(canvas, points[i].x, points[i].y, 2, "blue"); 
 
function paintDot(canvas, x, y, size, color) { 
 
    canvas.beginPath(); 
 
    canvas.arc(x, y, size, 0, 6.2831853); 
 
    canvas.closePath(); 
 
    canvas.fillStyle = color; 
 
    canvas.fill(); 
 
} 
 
function paintRectangle(canvas, x, y, width, height, line, color) { 
 
    canvas.beginPath(); 
 
    canvas.rect(x, y, width, height); 
 
    canvas.closePath(); 
 
    canvas.lineWidth = line; 
 
    canvas.strokeStyle = color; 
 
    canvas.stroke(); 
 
}

<BODY STYLE="margin: 0; border: 0; padding: 0;"> 
 
<CANVAS ID="canvas" STYLE="width: 300px; height: 200px; float: left; background-color: #F8F8F8;"></CANVAS> 
 
</BODY>

Źródło

2015-09-08 06:42:47 m69

To jest absurdalnie kompletna odpowiedź. Uruchomiony kod, który możesz kliknąć! Dobra robota, akceptuję to. Nie wygląda na to, że go wykorzystam, ponieważ wprowadziłem pewne zmiany w grze, aby wymaganie w pytaniu nie musiało już być spełnione. Sądzę, że i tak byłoby to zbyt drogie. Musi uruchomić każdą klatkę przy 60 fps + wszystkie punkty są ciągle w ruchu. Sortowanie mogło go zabić. Tak czy siak, dzięki. –

@HarryMexican Napisałem kod, aby zademonstrować ten pomysł, ale to, czy faktycznie możesz to zrobić, zależy od tego, ile punktów istnieje i jak szybko musi być; uruchomienie tej gry z szybkością gry może być problematyczne z czymś więcej niż garstką punktów. Algorytm polega na sortowaniu, więc nie można tego pominąć, aby zwiększyć wydajność. Algorytm, który tylko patrzy na punkty, które wkrótce opuszczą prostokąt, a następnie stopniowo je przesunie, będzie prawdopodobnie bardziej wydajny w twoim przypadku. – m69

Tak, to ciekawy eksperyment myślowy w każdym przypadku. Mam nadzieję, że coś napisałeś i że pomaga to komuś, kto szuka algorytmu tego rodzaju.:) –

Znajdowanie pozycji prostokąta, która sprawia, że ​​obejmuje ona maksymalne punkty w przestrzeni 2D

Odpowiedz

Powiązane problemy

Znajdowanie pozycji prostokąta, która sprawia, że obejmuje ona maksymalne punkty w przestrzeni 2D