package uk.me.parabola.util;
import java.awt.Rectangle;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import uk.me.parabola.imgfmt.app.Area;
import uk.me.parabola.imgfmt.app.Coord;
public class QuadTreeNode
{
private static final int MAX_POINTS =
20;
private Collection<Coord
> points
;
private final Area bounds
;
private Area coveredBounds
;
public Area getCoveredBounds
() {
return coveredBounds
;
}
private QuadTreeNode
[] children
;
public static final class QuadTreePolygon
{
private final java.
awt.
geom.
Area javaArea
;
private final Area bbox
;
public QuadTreePolygon
(java.
awt.
geom.
Area javaArea
) {
this.
javaArea = javaArea
;
Rectangle bboxRect = javaArea.
getBounds();
bbox =
new Area(bboxRect.
y, bboxRect.
x, bboxRect.
y
+ bboxRect.
height, bboxRect.
x + bboxRect.
width);
}
public QuadTreePolygon
(List<Coord
> points
) {
this(Java2DConverter.
createArea(points
));
}
public QuadTreePolygon
(Collection<List<Coord
>> polygonList
) {
this.
javaArea =
new java.
awt.
geom.
Area();
for (List<Coord
> polygon : polygonList
) {
javaArea.
add(Java2DConverter.
createArea(polygon
));
}
Rectangle bboxRect = javaArea.
getBounds();
bbox =
new Area(bboxRect.
y, bboxRect.
x, bboxRect.
y
+ bboxRect.
height, bboxRect.
x + bboxRect.
width);
}
public Area getBbox
() {
return bbox
;
}
public java.
awt.
geom.
Area getArea
() {
return javaArea
;
}
}
public QuadTreeNode
(Area bounds
) {
this(bounds,
Collections.
<Coord
>emptyList
());
}
public QuadTreeNode
(Area bounds,
Collection<Coord
> points
) {
this.
bounds = bounds
;
this.
children =
null;
int minLat =
Integer.
MAX_VALUE;
int maxLat =
Integer.
MIN_VALUE;
int minLong =
Integer.
MAX_VALUE;
int maxLong =
Integer.
MIN_VALUE;
for (Coord c : points
) {
if (c.
getLatitude() < minLat
) {
minLat = c.
getLatitude();
}
if (c.
getLatitude() > maxLat
) {
maxLat = c.
getLatitude();
}
if (c.
getLongitude() < minLong
) {
minLong = c.
getLongitude();
}
if (c.
getLongitude() > maxLong
) {
maxLong = c.
getLongitude();
}
}
coveredBounds =
new Area(minLat, minLong, maxLat, maxLong
);
if (points.
size() > MAX_POINTS
) {
this.
points = points
;
split
();
} else {
this.
points =
new HashSet<>(points
);
}
}
public Area getBounds
() {
return this.
bounds;
}
public boolean add
(Coord c
) {
if (coveredBounds ==
null) {
coveredBounds =
new Area(c.
getLatitude(), c.
getLongitude(),
c.
getLatitude(), c.
getLongitude());
} else if (!coveredBounds.
contains(c
)) {
coveredBounds =
new Area(Math.
min(coveredBounds.
getMinLat(),
c.
getLatitude()),
Math.
min(coveredBounds.
getMinLong(),
c.
getLongitude()),
Math.
max(coveredBounds.
getMaxLat(),
c.
getLatitude()),
Math.
max(coveredBounds.
getMaxLong(),
c.
getLongitude()));
}
if (isLeaf
()) {
boolean added = points.
add(c
);
if (points.
size() > MAX_POINTS
)
split
();
return added
;
} else {
for (QuadTreeNode nodes : children
) {
if (nodes.
getBounds().
contains(c
)) {
return nodes.
add(c
);
}
}
return false;
}
}
public List<Coord
> get
(Area bbox,
List<Coord
> resultList
) {
if (isLeaf
()) {
if (bbox.
contains(coveredBounds
)) {
// the bounding box is contained completely in the bbox
// => add all points without further check
resultList.
addAll(points
);
} else {
// check each point
for (Coord c : points
) {
if (bbox.
contains(c
)) {
resultList.
add(c
);
}
}
}
} else {
for (QuadTreeNode child : children
) {
if (bbox.
intersects(child.
getCoveredBounds())) {
resultList = child.
get(bbox, resultList
);
}
}
}
return resultList
;
}
public List<Coord
> get
(QuadTreePolygon polygon,
List<Coord
> resultList
) {
if (polygon.
getBbox().
intersects(getBounds
())) {
if (isLeaf
()) {
for (Coord c : points
) {
if (polygon.
getArea().
contains(c.
getLongitude(),
c.
getLatitude())) {
resultList.
add(c
);
}
}
} else {
for (QuadTreeNode child : children
) {
if (polygon.
getBbox().
intersects(child.
getBounds())) {
java.
awt.
geom.
Area subArea =
(java.
awt.
geom.
Area) polygon
.
getArea().
clone();
subArea.
intersect(createArea
(child.
getBounds()));
child.
get(new QuadTreePolygon
(subArea
), resultList
);
}
}
}
}
return resultList
;
}
private static java.
awt.
geom.
Area createArea
(Area bbox
) {
return new java.
awt.
geom.
Area(
new Rectangle(bbox.
getMinLong(), bbox.
getMinLat(), bbox.
getWidth(), bbox.
getHeight()));
}
public boolean isLeaf
() {
return points
!=
null;
}
private void split
() {
if (bounds.
getHeight() <=
1 || bounds.
getWidth() <=
1) {
return;
}
int halfLat =
(bounds.
getMinLat() + bounds.
getMaxLat()) /
2;
int halfLong =
(bounds.
getMinLong() + bounds.
getMaxLong()) /
2;
children =
new QuadTreeNode
[4];
Area swBounds =
new Area(bounds.
getMinLat(), bounds.
getMinLong(),
halfLat, halfLong
);
Area nwBounds =
new Area(halfLat, bounds.
getMinLong(),
bounds.
getMaxLat(), halfLong
);
Area seBounds =
new Area(bounds.
getMinLat(), halfLong, halfLat,
bounds.
getMaxLong());
Area neBounds =
new Area(halfLat, halfLong, bounds.
getMaxLat(),
bounds.
getMaxLong());
children
[0] =
new QuadTreeNode
(swBounds
);
children
[1] =
new QuadTreeNode
(nwBounds
);
children
[2] =
new QuadTreeNode
(seBounds
);
children
[3] =
new QuadTreeNode
(neBounds
);
Collection<Coord
> copyPoints = points
;
points =
null;
for (Coord c : copyPoints
) {
add
(c
);
}
}
public void clear
() {
this.
children =
null;
points =
new HashSet<>();
coveredBounds =
new Area(Integer.
MAX_VALUE,
Integer.
MAX_VALUE,
Integer.
MIN_VALUE,
Integer.
MIN_VALUE);
}
}