streamalism.org

1. Prehľad

V tomto rýchlom výučbe sa naučíme riešiť algoritmický problém kontroly, či sa dva dané obdĺžniky prekrývajú.

Začneme tým, že sa pozrieme na definíciu problému a potom postupne vypracujeme riešenie.

Nakoniec to implementujeme v Jave.

2. Definícia problému

Povedzme, že máme dva dané obdĺžniky - R1 a r2. Musíme skontrolovať, či je medzi nimi aspoň jeden spoločný bod R1 a r2. Ak áno, znamená to jednoducho, že sa tieto dva obdĺžniky prekrývajú.

Pozrime sa na niekoľko príkladov:

Ak si všimneme úplne posledný prípad, obdĺžniky R1 a r2 nemajú žiadne pretínajúce sa hranice. Stále sa prekrývajú obdĺžniky ako každý bod R1 je tiež bod v r2.

3. Počiatočné nastavenie

Pri riešení tohto problému by sme mali najskôr začať programovým definovaním obdĺžnika. Obdĺžnik možno ľahko znázorniť jeho ľavými a pravými hornými súradnicami:

public class Rectangle {private Point bottomLeft; private Point topRight; // konštruktor, getri a nastavovatelia boolean isOverlapping (obdĺžnik iný) {...}}

kde Bod je trieda predstavujúca bod (x, y) vo vesmíre:

public class Point {private int x; súkromné ​​int y; // konštruktor, getri a nastavovatelia}

Neskôr si to zadefinujeme isOverlapping (Obdĺžnik iné) metóda v našom Obdĺžnik triedy na kontrolu, či sa prekrýva s iným daným obdĺžnikom - iné.

4. Riešenie

Dva dané obdĺžniky sa nebudú prekrývať, ak platí niektorá z nasledujúcich podmienok:

1. Jeden z dvoch obdĺžnikov je nad horným okrajom druhého obdĺžnika
2. Jeden z dvoch obdĺžnikov je na ľavej strane od ľavého okraja druhého obdĺžnika

Vo všetkých ostatných prípadoch sa dva obdĺžniky navzájom prekrývajú. Aby sme sa presvedčili, vždy môžeme uviesť niekoľko príkladov.

5. Implementácia Java

Teraz, keď rozumieme riešeniu, implementujme naše isOverlapping () metóda:

public boolean isOverlapping (Rectangle other) {if (this.topRight.getY () other.topRight.getY ()) {return false; } if (this.topRight.getX () other.topRight.getX ()) {return false; } návrat pravdivý; }

Náš isOverlapping () metóda v Obdĺžnik trieda sa vracia nepravdivé ak je jeden z obdĺžnikov buď nad alebo naľavo od druhého, pravda inak.

Aby sme zistili, či je jeden obdĺžnik nad druhým, porovnáme ich súradnice y. Rovnako tak porovnávame súradnice x skontrolovať, či je jeden obdĺžnik vľavo od druhého.

6. Záver

V tomto krátkom článku sme sa naučili, ako vyriešiť algoritmický problém zisťovania, či sa dva dané obdĺžniky navzájom prekrývajú. Slúži ako stratégia detekcie kolízie pre dva obdĺžnikové objekty.

Celý zdrojový kód je ako obvykle k dispozícii na serveri Github.