streamalism.org

1. Overzicht

In deze korte tutorial leren we een algoritmisch probleem op te lossen door te controleren of de twee gegeven rechthoeken elkaar overlappen.

We beginnen met het bekijken van de probleemdefinitie en bouwen vervolgens geleidelijk aan een oplossing.

Ten slotte zullen we het in Java implementeren.

2. Probleemomschrijving

Laten we zeggen dat we twee gegeven rechthoeken hebben - r1 en r2. We moeten controleren of er minstens één gemeenschappelijk punt is r1 en r2. Zo ja, dan betekent dit dat deze twee rechthoeken elkaar overlappen.

Laten we eens kijken naar enkele voorbeelden:

Als we het allerlaatste geval opmerken, de rechthoeken r1 en r2 hebben geen elkaar kruisende grenzen. Toch zijn het overlappende rechthoeken zoals elk punt in r1 is ook een punt in r2.

3. Eerste installatie

Om dit probleem op te lossen, moeten we eerst beginnen met het programmatisch definiëren van een rechthoek. Een rechthoek kan eenvoudig worden weergegeven door de coördinaten linksonder en rechtsboven:

openbare klasse Rechthoek {privé Punt bottomLeft; privé Point topRight; // constructor, getters en setters boolean isOverlapping (Rectangle other) {...}}

waar Punt is een klasse die een punt vertegenwoordigt (x, y) in de ruimte:

openbare klasse Point {private int x; privé int y; // constructeur, getters en setters}

We zullen later definiëren isOverlapping (andere rechthoek) methode in onze Rechthoek klasse om te controleren of deze overlapt met een andere gegeven rechthoek - andere.

4. Oplossing

De twee bepaalde rechthoeken overlappen elkaar niet als een van de onderstaande voorwaarden is waar:

1. Een van de twee rechthoeken bevindt zich boven de bovenrand van de andere rechthoek
2. Een van de twee rechthoeken bevindt zich aan de linkerkant van de linkerrand van de andere rechthoek

In alle andere gevallen overlappen de twee rechthoeken elkaar. Om onszelf te overtuigen, kunnen we altijd meerdere voorbeelden geven.

5. Java-implementatie

Nu we de oplossing begrijpen, gaan we onze isOverlapping () methode:

openbare boolean isOverlapping (Rectangle other) {if (this.topRight.getY () other.topRight.getY ()) {return false; } if (this.topRight.getX () other.topRight.getX ()) {return false; } retourneren waar; }

Onze isOverlapping () methode in Rechthoek klasse keert terug false als een van de rechthoeken zich boven of links van de andere bevindt, waar anders.

Om erachter te komen of de ene rechthoek boven de andere staat, vergelijken we hun y-coördinaten. Evenzo vergelijken we de x-coördinaten om te controleren of de ene rechthoek zich links van de andere bevindt.

6. Conclusie

In dit korte artikel hebben we geleerd hoe we een algoritmisch probleem kunnen oplossen om te achterhalen of de twee gegeven rechthoeken elkaar overlappen. Het dient als een botsingsdetectiestrategie voor twee rechthoekige objecten.

Zoals gewoonlijk is de volledige broncode beschikbaar op Github.