javabinary-search-tree
better algorithm to find the biggest annulus without points in it
I have a BST whose sorting is based on radius and phase of the Cartesian points. Here's the implementation:
public class BST {
private BinNode root;
private int size;
public BST() {
this.root = null;
size = 0;
}
private double getRadius(double x, double y) {
return Math.sqrt(x*x+y*y);
}
public double getRadius(BinNode t) {
if (t == null) return -1;
return getRadius(t.getCoordinates()[0],t.getCoordinates()[1]);
}
private double getPhase(double x, double y) {
return Math.atan2(y,x);
}
private double getPhase(BinNode t){
return getPhase(t.getCoordinates()[0],t.getCoordinates()[1]);
}
private BinNode BST_insert_aux(double x, double y, double r, double p, BinNode t) {
double tr = getRadius(t);
double tp = getPhase(t);
if (t.left == null && t.right != null) { //has only the right child
if (r < tr) {
t.setLeft(new BinNode(x, y)); return t.getLeft();
}
else if (r == tr) {
if (p < tp) {
t.setLeft(new BinNode(x, y)); return t.getLeft();
}
else if (p == tp) {
return null; }
else if (p > tp) {
return BST_insert_aux(x, y, r, p, t.getRight());
}
}
else if (r > tr) {
return BST_insert_aux(x, y, r, p, t.getRight());
}
}
else if (t.left != null && t.right == null) { //has only the left child
if (r < tr) {
return BST_insert_aux(x, y, r, p, t.getLeft()); }
else if (r == tr) {
if (p < tp) {
return BST_insert_aux(x, y, r, p, t.getLeft()); }
else if (p == tp) {
return null; }
else if (p > tp) {
t.setRight(new BinNode(x, y)); return t.getRight(); }
}
else if (r > tr) {
t.setRight(new BinNode(x, y)); return t.getRight(); }
}
else if (t.left == null && t.right == null) { //leaf
if (r < tr) {
t.setLeft(new BinNode(x, y)); return t.getLeft(); }
else if (r == tr) {
if (p < tp) {
t.setLeft(new BinNode(x, y)); return t.getLeft(); }
else if (p == tp) {
return null; }
else if (p > tp) {
t.setRight(new BinNode(x, y)); return t.getRight(); }
}
else if (r > tr) {
t.setRight(new BinNode(x, y)); return t.getRight(); }
}
else { //has both childs
if (r < tr) {
return BST_insert_aux(x, y, r, p, t.getLeft()); }
else if (r == tr) {
if (p < tp) {
return BST_insert_aux(x, y, r, p, t.getLeft()); }
else if (p == tp) {
return null; }
else if (p > tp) {
return BST_insert_aux(x, y, r, p, t.getRight()); }
}
else if (r > tr) {
return BST_insert_aux(x, y, r, p, t.getRight()); }
}
return null;
}
public BinNode BST_insert(double x, double y) {
if (root == null) {
root = new BinNode(x, y);
return root;
}
return BST_insert_aux(x, y, getRadius(x,y), getPhase(x,y), root);
}
private void print(BinNode t, int level, char pos) {
if (t==null) return;
for (int i = 0; i < level - 1; i++) {
System.out.print(" ");
}
if (level > 0) {
System.out.print(" "+pos+":--");
}
System.out.println("coordinate: ("+ t.getCoordinates()[0]+","+t.getCoordinates()[1]+"); radius="
+ getRadius(t) + " ; phase=" + getPhase(t) );
print(t.getLeft(), level + 1,'l');
print(t.getRight(), level + 1,'r');
}
public void BST_print() {
if (root!=null)
print(this.root, 0,' ');
}
/////////////////////////////////////////////////////////////
public class BinNode {
protected double[] coordinates;
protected BinNode left;
protected BinNode right;
public BinNode(double x, double y) {
coordinates = new double[2];
coordinates[0] = x;
coordinates[1] = y;
this.left = null;
this.right = null;
}
public BinNode getLeft(){
return left;
}
public BinNode getRight(){
return right;
}
public BinNode setLeft(BinNode n){
left = n;
return left;
}
public BinNode setRight(BinNode n){
right = n;
return right;
}
public double[] getCoordinates(){
return coordinates;
}
}
I am sorry if the code is too long, but I am new to Stack Overflow so I do not know if omitting part of the code for the sake of brevity would be better. Anyway, I have to write a method to find the area of the maximum annulus that has no points inside it (those on the border, so with a radius equal to one of the two radius of the annulus are fine). 
Obviously the annulus must be of finite size, so there must exist in the plane at least one point with a radius greater than or equal to that of the big radius of the annulus. To do this I wrote an auxiliary method Annulus(double r1, double r2) that count how many points in the BST have a radius between r1 and r2. Here is the code:
public int Annulus(double r1, double r2) {
System.out.println("RANGE QUERY: from " + r1 + " to " + r2);
if (r2 < r1) { System.out.println("r2 must be >= r1"); return -1; }
int[] cont = new int[1];
cont[0] = 0;
Annulus_aux(r1, r2, root, cont);
return cont[0];
}
private void Annulus_aux(double r1, double r2, BinNode t, int[] cont) {
if (t == null) {
return;
}
else {
double tr = getRadius(t);
double tp = getPhase(t);
if (r1 >= tr) {
Annulus_aux(r1, r2, t.getRight(), cont);
}
else {
Annulus_aux(r1, r2, t.getLeft(), cont);
if (r2 > tr) {
cont[0]++;
Annulus_aux(r1, r2, t.getRight(), cont);
}
}
}
}
The problem is in the following methods:
public double maxAnnulus() {
LinkedList<BinNode> nodes = new LinkedList<>();
collectNodes(nodes, root);
double maxArea = 0;
for (BinNode e: nodes) {
if (Annulus(0, getRadius(e)) == 0) { //r1 = origin
double currentArea = area(0, getRadius(e));
if (currentArea > maxArea) {
System.out.println("\n\n");
maxArea = currentArea;
}
}
for (BinNode ne: nodes) {
double r1 = getRadius(e);
double r2 = getRadius(ne);
if (Annulus(r1, r2) == 0) {
double currentArea = area(r1,r2);
if (currentArea > maxArea) {
System.out.println("\n\n");
maxArea = currentArea;
}
}
}
}
return maxArea;
}
private void collectNodes(LinkedList<BinNode> nodes, BinNode t) {
if (t != null) {
collectNodes(nodes, t.getLeft());
nodes.add(t);
collectNodes(nodes, t.getRight());
}
}
private double area(double r1, double r2) {
System.out.println("a1 = " + Math.PI * Math.pow(r1, 2));
System.out.println("a2 = " + Math.PI * Math.pow(r2, 2));
System.out.println("a2-a1 = " + Math.PI * (Math.pow(r2,2) - Math.pow(r1,2)));
System.out.println("\n\n");
return Math.PI * (Math.pow(r2,2) - Math.pow(r1,2));
}
}
maxAnnulus() calculates the area of the maximum annulus. To do this, it calls the collectNodes (nodes, root) method which inserts the nodes of the BST in a linkedlist. Then for each element of the linkedlist it calculates the area between its radius and the radius of every other element of the linkedlist (plus the origin), but only if the number of internal points between the two radius is 0. Then comparing the various areas, I find the largest one.
I am absolutely sure there are so many better ways to solve this problem. Here are some tests that I did:
public class Driver {
public static void main(String[] argv) {
int i;
BST b = new BST();
b.BST_insert(5,0);
b.BST_insert(2,0);
b.BST_insert(8,0);
b.BST_insert(1,0);
b.BST_insert(3,0);
b.BST_insert(6,0);
b.BST_insert(11,0);
b.BST_insert(1,0);
b.BST_insert(0,5);
b.BST_insert(0,6);
b.BST_insert(0,-5);
b.BST_insert(0,6);
System.out.println("############################################");
System.out.println("Tree: \n");
b.BST_print();
System.out.println("############################################\n\n");
double maxAnnulus = b.maxAnnulus();
System.out.println("Max Annulus: " + maxAnnulus);
BST b1 = new BST();
b1.BST_insert(1,4);
b1.BST_insert(-6,6);
b1.BST_insert(3,4);
b1.BST_insert(5,1);
b1.BST_insert(6,-4);
b1.BST_insert(4,1);
b1.BST_insert(2,7);
b1.BST_insert(2,2);
b1.BST_insert(8,1);
b1.BST_insert(-1,4);
b1.BST_insert(6,2);
b1.BST_insert(-8,7);
b1.BST_insert(1,-1);
b1.BST_insert(8,-1);
b1.BST_insert(8,-1);
b1.BST_insert(0,5);
b1.BST_insert(2,2);
System.out.println("############################################");
System.out.println("\n\n\nTree: \n");
b1.BST_print();
System.out.println("############################################\n\n");
maxAnellus = b1.maxAnnulus();
System.out.println("Max Annulus: " + maxAnnulus);
}
}
Solution
From your current implementation, it seems that the annulus must be centered on the origin. Due to radial symmetry, this means you don't need to care about the angle (phase) of the points at all, only about their distance to the origin (radius).
This means you can reduce almost the entire problem to be one-dimensional. There is no need for complicated data structures, just a list of sorted points. Only the area calculation remains 2D.
In pseudocode:
# Keep track of best candidate annulus found so far.
max_area = 0
best_inner_radius, best_outer_radius = 0, 0
# Loop through points in order of increasing radius.
sorted_points = sort points by increasing radius
for i in 0 through |sorted_points| - 1:
# Find the inner and outer radius of an annulus that fits between these two points.
inner_radius, outer_radius = points[i], points[i + 1]
# Compute area of this annulus.
area = pi * (outer_radius^2 - inner_radius^2)
# Store this one if it's better than the current candidate.
if area > max_area:
max_area = area
best_inner_radius, best_outer_radius = inner_radius, outer_radius
- Keep numbers which appear in both columns, in J lang
- Differentiation in J
- How to reshape an array with an arbitrary size in one dimension?
- Why is Insert (fold) right associative
- Write 4 : 'x&{.&.;: y' tacitly
- Alignment issue when printing formatted prime numbers in J language
- How can I define a verb in J that applies a different verb alternately to each atom in a list?
- How to get user input in the J programming language
- How to unbox a list of boxed lists of differing lengths in J?
- How can I fix 'noun result was required' error in J?
- In j, how can I define a verb locally in one scope and pass it to a defined adverb?
- Convert boxed array to normal array?
- Read column of CSV file as array
- Replace atom in array of strings
- What does the dyad `=` do to boxed strings?
- Index of minimum element using J
- How can I take the outer product of string vectors in J?
- Building an array of verbs in J
- Reading in multidigit command line parameter
- Amend with bond to new data shows unexpected behaviour
- How to turn a table or matrix into a (flat) list in J
- How to run dissect in J?
- How to define selection using index function in J
- How to exit the J console?
- Find 4-neighbors using J
- Writing custom verbs in J
- How do I negate a selector in J lang?
- How to use arbitrary selector in interchange in J lang?
- different result once square root is added inside tacit
- Sum of arrays with repeated indices