streamalism.org

1. Pregled

U ovom brzom uputstvu naučit ćemo riješiti algoritamski problem provjere preklapaju li se dva dana pravokutnika.

Započet ćemo s razmatranjem definicije problema, a zatim ćemo postupno donositi rješenje.

Napokon, implementirat ćemo ga u Javu.

2. Definicija problema

Recimo da imamo dva dana pravokutnika - r1 i r2. Moramo provjeriti postoji li barem jedna zajednička točka r1 i r2. Ako je odgovor da, to jednostavno znači da se ova dva pravokutnika preklapaju.

Pogledajmo nekoliko primjera:

Ako primijetimo zadnji slučaj, pravokutnike r1 i r2 nemaju granice koje se presijecaju. Ipak, preklapaju se pravokutnici kao i svaka točka r1 je također točka u r2.

3. Početno postavljanje

Da bismo riješili taj problem, prvo bismo trebali započeti programskim definiranjem pravokutnika. Pravokutnik se lako može predstaviti koordinatama dolje lijevo i gore desno:

pravokutnik javne klase {private Point bottomLeft; private Point topRight; // konstruktor, getteri i postavljači boolean isOverlapping (Pravokutnik ostalo) {...}}

gdje Točka je klasa koja predstavlja bod (x, y) u svemiru:

javni razred Point {private int x; privatni int y; // konstruktor, getteri i postavljači}

Kasnije ćemo definirati isOverlapping (Pravokutnik ostalo) metoda u našem Pravokutnik klasa da provjeri preklapa li se s drugim zadanim pravokutnikom - drugo.

4. Rješenje

Dva zadani pravokutnici neće se preklapati ako vrijedi bilo koji od dolje navedenih uvjeta:

1. Jedan od dva pravokutnika nalazi se iznad gornjeg ruba drugog pravokutnika
2. Jedan od dva pravokutnika nalazi se na lijevoj strani lijevog ruba drugog pravokutnika

U svim ostalim slučajevima, dva pravokutnika preklopit će se međusobno. Da bismo se uvjerili, uvijek možemo izvući nekoliko primjera.

5. Implementacija Jave

Sad kad razumijemo rješenje, provedimo svoje isOverlapping () metoda:

javni boolean isOverlapping (Pravokutnik ostalo) {if (this.topRight.getY () other.topRight.getY ()) {return false; } if (this.topRight.getX () other.topRight.getX ()) {return false; } return true; }

Naše isOverlapping () metoda u Pravokutnik klasa se vraća lažno ako je jedan od pravokutnika iznad ili s lijeve strane drugog, pravi inače.

Da bismo saznali je li jedan pravokutnik iznad drugog, uspoređujemo njihov y-koordinate. Isto tako, uspoređujemo x koordinate kako bi provjerili nalazi li se jedan pravokutnik lijevo od drugog.

6. Zaključak

U ovom kratkom članku naučili smo kako riješiti algoritamski problem pronalaska preklapaju li se dva dana pravokutnika. Služi kao strategija otkrivanja sudara za dva pravokutna objekta.

Kao i obično, cijeli izvorni kod dostupan je na Githubu.