Skip to content

Commit e7ed9ec

Browse files
macroscopic64KevinGilmore
macroscopic64
authored and
KevinGilmore
committed
[BAEL-3485] - Java Range lookup problem (eugenp#8392)
* [BAEL-3485] - Java Range lookup problem * [BAEL-3485] - Java Range lookup problem * [BAEL-3485] - Java Range lookup problem
1 parent 000ac07 commit e7ed9ec

4 files changed

Lines changed: 278 additions & 0 deletions

File tree

‎algorithms-searching/src/main/java/com/baeldung/algorithms/quadtree/Point.java‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
package com.baeldung.algorithms.quadtree;
2+
3+
public class Point {
4+
private float x;
5+
private float y;
6+
7+
public Point(float x, float y) {
8+
this.x = x;
9+
this.y = y;
10+
}
11+
12+
public float getX() {
13+
return x;
14+
}
15+
16+
public float getY() {
17+
return y;
18+
}
19+
20+
@Override
21+
public String toString() {
22+
return "[" + x + " , " + y + "]";
23+
}
24+
}

‎algorithms-searching/src/main/java/com/baeldung/algorithms/quadtree/QuadTree.java‎

Lines changed: 109 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,109 @@
1+
package com.baeldung.algorithms.quadtree;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
public class QuadTree {
7+
private static final int MAX_POINTS = 3;
8+
private Region area;
9+
private List<Point> points = new ArrayList<>();
10+
private List<QuadTree> quadTrees = new ArrayList<>();
11+
private StringBuilder searchTraversePath;
12+
13+
public QuadTree(Region area) {
14+
this.area = area;
15+
}
16+
17+
public boolean addPoint(Point point) {
18+
if (this.area.containsPoint(point)) {
19+
if (this.points.size() < MAX_POINTS) {
20+
this.points.add(point);
21+
return true;
22+
} else {
23+
if (this.quadTrees.size() == 0) {
24+
createQuadrants();
25+
}
26+
return addPointToOneQuadrant(point);
27+
}
28+
}
29+
return false;
30+
}
31+
32+
private boolean addPointToOneQuadrant(Point point) {
33+
boolean isPointAdded;
34+
for (int i = 0; i < 4; i++) {
35+
isPointAdded = this.quadTrees.get(i)
36+
.addPoint(point);
37+
if (isPointAdded)
38+
return true;
39+
}
40+
return false;
41+
}
42+
43+
private void createQuadrants() {
44+
Region region;
45+
for (int i = 0; i < 4; i++) {
46+
region = this.area.getQuadrant(i);
47+
quadTrees.add(new QuadTree(region));
48+
}
49+
}
50+
51+
public List<Point> search(Region searchRegion, List<Point> matches, String depthIndicator) {
52+
searchTraversePath = new StringBuilder();
53+
if (matches == null) {
54+
matches = new ArrayList<Point>();
55+
searchTraversePath.append(depthIndicator)
56+
.append("Search Boundary =")
57+
.append(searchRegion)
58+
.append("\n");
59+
}
60+
if (!this.area.doesOverlap(searchRegion)) {
61+
return matches;
62+
} else {
63+
for (Point point : points) {
64+
if (searchRegion.containsPoint(point)) {
65+
searchTraversePath.append(depthIndicator)
66+
.append("Found match " + point)
67+
.append("\n");
68+
matches.add(point);
69+
}
70+
}
71+
if (this.quadTrees.size() > 0) {
72+
for (int i = 0; i < 4; i++) {
73+
searchTraversePath.append(depthIndicator)
74+
.append("Q")
75+
.append(i)
76+
.append("-->")
77+
.append(quadTrees.get(i).area)
78+
.append("\n");
79+
quadTrees.get(i)
80+
.search(searchRegion, matches, depthIndicator + "\t");
81+
this.searchTraversePath.append(quadTrees.get(i)
82+
.printSearchTraversePath());
83+
}
84+
}
85+
}
86+
return matches;
87+
}
88+
89+
public String printTree(String depthIndicator) {
90+
String str = "";
91+
if (depthIndicator == "") {
92+
str += "Root-->" + area.toString() + "\n";
93+
}
94+
95+
for (Point point : points) {
96+
str += depthIndicator + point.toString() + "\n";
97+
}
98+
for (int i = 0; i < quadTrees.size(); i++) {
99+
str += depthIndicator + "Q" + String.valueOf(i) + "-->" + quadTrees.get(i).area.toString() + "\n";
100+
str += quadTrees.get(i)
101+
.printTree(depthIndicator + "\t");
102+
}
103+
return str;
104+
}
105+
106+
public String printSearchTraversePath() {
107+
return searchTraversePath.toString();
108+
}
109+
}

‎algorithms-searching/src/main/java/com/baeldung/algorithms/quadtree/Region.java‎

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
package com.baeldung.algorithms.quadtree;
2+
3+
public class Region {
4+
private float x1;
5+
private float y1;
6+
private float x2;
7+
private float y2;
8+
9+
public Region(float x1, float y1, float x2, float y2) {
10+
if (x1 >= x2 || y1 >= y2)
11+
throw new IllegalArgumentException("(x1,y1) should be lesser than (x2,y2)");
12+
this.x1 = x1;
13+
this.y1 = y1;
14+
this.x2 = x2;
15+
this.y2 = y2;
16+
}
17+
18+
public Region getQuadrant(int quadrantIndex) {
19+
float quadrantWidth = (this.x2 - this.x1) / 2;
20+
float quadrantHeight = (this.y2 - this.y1) / 2;
21+
22+
// 0=SW, 1=NW, 2=NE, 3=SE
23+
switch (quadrantIndex) {
24+
case 0:
25+
return new Region(x1, y1, x1 + quadrantWidth, y1 + quadrantHeight);
26+
case 1:
27+
return new Region(x1, y1 + quadrantHeight, x1 + quadrantWidth, y2);
28+
case 2:
29+
return new Region(x1 + quadrantWidth, y1 + quadrantHeight, x2, y2);
30+
case 3:
31+
return new Region(x1 + quadrantWidth, y1, x2, y1 + quadrantHeight);
32+
}
33+
return null;
34+
}
35+
36+
public boolean containsPoint(Point point) {
37+
// Consider left and top side to be inclusive for points on border
38+
return point.getX() >= this.x1
39+
&& point.getX() < this.x2
40+
&& point.getY() >= this.y1
41+
&& point.getY() < this.y2;
42+
}
43+
44+
public boolean doesOverlap(Region testRegion) {
45+
// Is test region completely to left of my region?
46+
if (testRegion.getX2() < this.getX1()) {
47+
return false;
48+
}
49+
// Is test region completely to right of my region?
50+
if (testRegion.getX1() > this.getX2()) {
51+
return false;
52+
}
53+
// Is test region completely above my region?
54+
if (testRegion.getY1() > this.getY2()) {
55+
return false;
56+
}
57+
// Is test region completely below my region?
58+
if (testRegion.getY2() < this.getY1()) {
59+
return false;
60+
}
61+
return true;
62+
}
63+
64+
@Override
65+
public String toString() {
66+
return "[Region (x1=" + x1 + ", y1=" + y1 + "), (x2=" + x2 + ", y2=" + y2 + ")]";
67+
}
68+
69+
public float getX1() {
70+
return x1;
71+
}
72+
73+
public float getY1() {
74+
return y1;
75+
}
76+
77+
public float getX2() {
78+
return x2;
79+
}
80+
81+
public float getY2() {
82+
return y2;
83+
}
84+
85+
}

‎algorithms-searching/src/test/java/com/baeldung/algorithms/quadtree/QuadTreeSearchUnitTest.java‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
package com.baeldung.algorithms.quadtree;
2+
3+
import org.junit.Assert;
4+
5+
import java.util.List;
6+
7+
import org.junit.BeforeClass;
8+
import org.junit.Test;
9+
import org.slf4j.Logger;
10+
import org.slf4j.LoggerFactory;
11+
12+
public class QuadTreeSearchUnitTest {
13+
14+
private static final Logger LOGGER = LoggerFactory.getLogger(QuadTreeSearchUnitTest.class);
15+
16+
private static QuadTree quadTree;
17+
18+
@BeforeClass
19+
public static void setUp() {
20+
Region area = new Region(0, 0, 400, 400);
21+
quadTree = new QuadTree(area);
22+
23+
float[][] points = new float[][] { { 21, 25 }, { 55, 53 }, { 70, 318 }, { 98, 302 },
24+
{ 49, 229 }, { 135, 229 }, { 224, 292 }, { 206, 321 }, { 197, 258 }, { 245, 238 } };
25+
26+
for (int i = 0; i < points.length; i++) {
27+
Point point = new Point(points[i][0], points[i][1]);
28+
quadTree.addPoint(point);
29+
}
30+
LOGGER.info("\n" + quadTree.printTree(""));
31+
LOGGER.info("==============================================");
32+
}
33+
34+
@Test
35+
public void givenQuadTree_whenSearchingForRange_thenReturn1MatchingItem() {
36+
Region searchArea = new Region(200, 200, 250, 250);
37+
List<Point> result = quadTree.search(searchArea, null, "");
38+
LOGGER.info(result.toString());
39+
LOGGER.info(quadTree.printSearchTraversePath());
40+
41+
Assert.assertEquals(1, result.size());
42+
Assert.assertArrayEquals(new float[] { 245, 238 },
43+
new float[]{result.get(0).getX(), result.get(0).getY() }, 0);
44+
}
45+
46+
@Test
47+
public void givenQuadTree_whenSearchingForRange_thenReturn2MatchingItems() {
48+
Region searchArea = new Region(0, 0, 100, 100);
49+
List<Point> result = quadTree.search(searchArea, null, "");
50+
LOGGER.info(result.toString());
51+
LOGGER.info(quadTree.printSearchTraversePath());
52+
53+
Assert.assertEquals(2, result.size());
54+
Assert.assertArrayEquals(new float[] { 21, 25 },
55+
new float[]{result.get(0).getX(), result.get(0).getY() }, 0);
56+
Assert.assertArrayEquals(new float[] { 55, 53 },
57+
new float[]{result.get(1).getX(), result.get(1).getY() }, 0);
58+
59+
}
60+
}

0 commit comments

Comments
 (0)