Skip to content

Instantly share code, notes, and snippets.

@steghio
Created July 4, 2021 11:35
Show Gist options
  • Save steghio/dbab8ae6db5171e3bc7bdf72108997ee to your computer and use it in GitHub Desktop.
Save steghio/dbab8ae6db5171e3bc7bdf72108997ee to your computer and use it in GitHub Desktop.
Algorithms dealing with geometry
package com.blogspot.groglogs.structures;
import java.util.Objects;
public class DoublePoint {
public double x, y, val;
public DoublePoint(double x, double y, int val){
this.x = x;
this.y = y;
this.val = val;
}
public DoublePoint(double x, double y){
this.x = x;
this.y = y;
this.val = -1;
}
@Override
public int hashCode() {
return Objects.hash(this.x, this.y, this.val);
}
@Override
public boolean equals(Object o) {
if(this == o){
return true;
}
if(!(o instanceof DoublePoint)){
return false;
}
DoublePoint other = (DoublePoint)o;
return this.x == other.x && this.y == other.y && this.val == other.val;
}
}
package com.blogspot.groglogs.geometryutils;
import com.blogspot.groglogs.structures.DoublePoint;
public class GeometryUtils {
public static final double SQRT_2 = Math.sqrt(2);
//helper for drawHTree, draws a straight line between the two given points
public static void drawLine(DoublePoint p1, DoublePoint p2){
}
/**
* Given a start point which is the center of the first line,
* draw the H tree of given depth using lines of given length.
* An H tree is a tree where each corner point of the H is the center point of the middle
* line of another H for each increasing depth.
* At each deeper level the length is divided by square root of two.
* Lines will be drawn parallel to the axis.
* @param start the center point of the first line.
* @param depth the maximum depth of the tree.
* @param length the starting length of the lines at initial depth, with increasing depth, this length
* is divided by square root of two.
*/
public static void drawHTree(DoublePoint start, int depth, double length){
if(depth == 0){
return;
}
double delta = length / 2;//precision
//boundaries of horizontal line with center in this point
DoublePoint left = new DoublePoint(start.x - delta, start.y);
DoublePoint right = new DoublePoint(start.x + delta, start.y);
drawLine(left, right);
//boundaries of vertical line with center in left point
DoublePoint leftTop = new DoublePoint(left.x, left.y + delta);
DoublePoint leftBottom = new DoublePoint(left.x, left.y - delta);
drawLine(leftTop, leftBottom);
//boundaries of vertical line with center in right point
DoublePoint rightTop = new DoublePoint(right.x, right.y + delta);
DoublePoint rightBottom = new DoublePoint(right.x, right.y - delta);
drawLine(rightTop, rightBottom);
//for each boundary point, recurse at deeper depth and update length of line
double newLength = length/SQRT_2;
drawHTree(leftTop, depth - 1, newLength);
drawHTree(leftBottom, depth - 1, newLength);
drawHTree(rightTop, depth - 1, newLength);
drawHTree(rightBottom, depth - 1, newLength);
}
}
@steghio
Copy link
Author

steghio commented Jul 4, 2021

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment