getElements not working propper

[TypeOverride]

i have the problem that when i try to fetch the elements that are inside a rectangle (with getElements) that

A) you insert all the time a new element

My solution to this was modifying the findRegion(..) method:

private int findRegion(QuadRectangle r) { return findRegion(r, false); }

private int findRegion(QuadRectangle r, boolean split) { .... if (nodes.size() >= maxItemByNode && this.level < maxLevel) { if (regions == null) { if(split) { // then create the subregions this.split(); } }

if(regions != null) { .... } .... }

public void insert(QuadRectangle r, T element) { int region = this.findRegion(r, true); ....

}

B) when you are on an edge of a region, the method getElements(...) gives you all elements back that are inside this region.. thats a lot of elements. This means (worst case).. when you are on the edge of the utter region, that every element in the quadTree will be returned. This means that on edges the quadtree will return elements that you dont want to fetch. This is making the quad tree useless in usage (to say it straight).

[alwex]

Thank you for the A suggestion. The behaviour of a quadTree is to return the parent container in case of an intersection, that means that if an element is intersecting with the uppermost parent container, then it will return all elements that are contained in that container. I don't see any fix for this as it is the expected behaviour. The quadTree is supposed to be as big as your game world, if something is overlapping your game world boudaries, then it should not be inserted in the quadTree at all.

What are your suggestion?

[ulixit]

This is my proposal to return strictly the elements intersecting with r instead of the default behavior "to return the parent container in case of an intersection, that means that if an element is intersecting with the uppermost parent container,then it will return all elements that are contained in that container."

one method added to QuadRectangle.java:

// this overlaps with r ? 
// from https://www.geeksforgeeks.org/find-two-rectangles-overlap/
public boolean overlaps(QuadRectangle r) {
  if ( this.width > 0 && this.height > 0 && r.width > 0 && r.height > 0 ) {
    if ( this.x > r.x + r.width || r.x > this.x + this.width) return false;
    if ( this.y > r.y + r.height || r.y > this.y + this.height) return false;
    return true;
  } else return false;
}	

two methods added to QuadTree.java:

 public ArrayList<T> getElements(ArrayList<T> list, QuadRectangle r, boolean ckOverlaps) {
    int region = this.findRegion(r, false);
    int length = nodes.size();
    for (int i = 0; i < length; i++) {
		if ( ckOverlaps ) {
			// add ONLY if rectangle intersect/overlaps
			if ( nodes.get(i).r.overlaps(r) ) 
				list.add(nodes.get(i).element);
		} else {
			// original behavior
			list.add(nodes.get(i).element);
		} // endif
    }
    if (region != REGION_SELF) {
        regions[region].getElements(list, r, ckOverlaps);
    } else {
        getAllElements(list, true, r, ckOverlaps);
    }
    return list;
}

public ArrayList<T> getAllElements(ArrayList<T> list, boolean firstCall, QuadRectangle r, boolean ckOverlaps) {
    if (regions != null) {
        regions[REGION_NW].getAllElements(list, false, r, ckOverlaps);
        regions[REGION_NE].getAllElements(list, false, r, ckOverlaps);
        regions[REGION_SW].getAllElements(list, false, r, ckOverlaps);
        regions[REGION_SE].getAllElements(list, false, r, ckOverlaps);
    }
    if (!firstCall) {
        int length = nodes.size();
        for (int i = 0; i < length; i++) {
	if ( ckOverlaps ) {
	    // add ONLY if rectangles intersect/overlaps
	    if ( nodes.get(i).r.overlaps(r) ) 
            	list.add(nodes.get(i).element);
	} else {
	    // original behavior
	   list.add(nodes.get(i).element);
	  } // endif
        } // endfor
    }
    return list;
}

then in sample code:

quadTree.getElements(list, new QuadRectangle(2, 2, 1, 1), true);