找到没有点的最大圆环的更好算法
better algorithm to find the biggest annulus without points in it
我有一个 BST，其排序基于笛卡尔点的半径和相位。这是实现：
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;
}
}
如果代码太长，我很抱歉，但我是 Stack Overflow 的新手，所以我不知道为了简洁起见省略部分代码是否会更好。不管怎样，我必须写一个方法来找到最大圆环的面积，它里面没有点（边界上的那些，所以半径等于圆环的两个半径之一就可以了）。
显然圆环的尺寸一定是有限的，所以平面上必然存在至少一个半径大于或等于圆环大半径的点。为此，我编写了一个辅助方法 Annulus(double r1, double r2) 来计算 BST 中有多少点的半径在 r1 和 r2 之间。这是代码：
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);
}
}
}
}
问题出在以下方法中：
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() 计算最大圆环的面积。为此，它调用 collectNodes (nodes, root) 方法，该方法将 BST 的节点插入到链表中。然后对于链表的每个元素，它计算其半径与链表的每个其他元素的半径（加上原点）之间的面积，但前提是两个半径之间的内部点数为 0。然后比较各个区域，我找到了最大的一个。
我绝对相信有很多更好的方法可以解决这个问题。以下是我所做的一些测试：
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);
}
}
从您当前的实现来看，圆环似乎必须以原点为中心。由于径向对称，这意味着您根本不需要关心点的角度（相位），只需要关心它们到原点的距离（半径）。
这意味着您几乎可以将整个问题简化为 one-dimensional。不需要复杂的数据结构，只需一个排序点列表。只有面积计算仍然是二维的。
在伪代码中：
# 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
我有一个 BST，其排序基于笛卡尔点的半径和相位。这是实现：
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;
}
}
如果代码太长，我很抱歉，但我是 Stack Overflow 的新手，所以我不知道为了简洁起见省略部分代码是否会更好。不管怎样，我必须写一个方法来找到最大圆环的面积，它里面没有点（边界上的那些，所以半径等于圆环的两个半径之一就可以了）。
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);
}
}
}
}
问题出在以下方法中：
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() 计算最大圆环的面积。为此，它调用 collectNodes (nodes, root) 方法，该方法将 BST 的节点插入到链表中。然后对于链表的每个元素，它计算其半径与链表的每个其他元素的半径（加上原点）之间的面积，但前提是两个半径之间的内部点数为 0。然后比较各个区域，我找到了最大的一个。
我绝对相信有很多更好的方法可以解决这个问题。以下是我所做的一些测试：
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);
}
}
从您当前的实现来看，圆环似乎必须以原点为中心。由于径向对称，这意味着您根本不需要关心点的角度（相位），只需要关心它们到原点的距离（半径）。
这意味着您几乎可以将整个问题简化为 one-dimensional。不需要复杂的数据结构，只需一个排序点列表。只有面积计算仍然是二维的。
在伪代码中：
# 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