com.xilinx.rapidwright.placer.blockplacer

Class SmallestEnclosingCircle

Object

com.xilinx.rapidwright.placer.blockplacer.SmallestEnclosingCircle

public class SmallestEnclosingCircle
extends Object

This class provides methods necessary for determining creating a new point which minimizes the maximum distance from the new point to any point in a given set of points in the plane. Useful for relocating registers.

Constructor Summary

Constructors

Constructor and Description
SmallestEnclosingCircle()

Method Summary

Modifier and Type	Method and Description
static double	angle(Point a, Point b, Point c) Computes the angle ABC from the points a, b, c.
static ArrayList<Point>	convexHull(ArrayList<Point> points) Given a set of points, returns the set of points in the convex hull in counterclockwise order.
static int	crossProduct(Point o, Point a, Point b) Performs a 2D cross product of OA and OB vectors.
static double	dotProduct(Point a, Point b, Point c) Computes the dot product of the vectors ba, bc from the points a, b, c.
static Point	getCenterPoint(HashSet<Point> pointsSet) Returns a new point which is the center of the smallest enclosing circle on points.
static Point	getCircumcenter(Point a, Point b, Point c) Determines the circumcenter of a circle that circumscribes triangle abc.
static void	main(String[] args) Command line interface for debug.
static void	printPoints(HashSet<Point> points)

Methods inherited from class Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

SmallestEnclosingCircle

public SmallestEnclosingCircle()

Method Detail

getCenterPoint

public static Point getCenterPoint(HashSet<Point> pointsSet)

Returns a new point which is the center of the smallest enclosing circle on points. This minimizes the maximum distance from the new point to any other point in points. http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm

Parameters:

pointsSet - the points in the set to consider.

Returns:

Point, the center of the smallest enclosing circle.

convexHull

public static ArrayList<Point> convexHull(ArrayList<Point> points)

Given a set of points, returns the set of points in the convex hull in counterclockwise order. http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain

Parameters:

points - the input set of points

Returns:

The set of points in the convex hull

getCircumcenter

public static Point getCircumcenter(Point a,
                                    Point b,
                                    Point c)

Determines the circumcenter of a circle that circumscribes triangle abc. http://en.wikipedia.org/wiki/Circumscribed_circle

Parameters:

a - Point A of the triangle

b - Point B of the triangle

c - Point C of the triangle

Returns:

Point, the circumcenter

crossProduct

public static int crossProduct(Point o,
                               Point a,
                               Point b)

Performs a 2D cross product of OA and OB vectors. Returns a positive value if OAB makes a counter-clockwise turn, negative for a clockwise turn, and zero if the points are collinear. http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain

Parameters:

o - Point O

a - Point A

b - Point B

Returns:

int, the cross product

printPoints

public static void printPoints(HashSet<Point> points)

angle

public static double angle(Point a,
                           Point b,
                           Point c)

Computes the angle ABC from the points a, b, c. http://forums.devx.com/archive/index.php/t-154064.html

Parameters:

a - Point A

b - Point B

c - Point C

Returns:

double, the angle

dotProduct

public static double dotProduct(Point a,
                                Point b,
                                Point c)

Computes the dot product of the vectors ba, bc from the points a, b, c. http://forums.devx.com/archive/index.php/t-154064.html

Parameters:

a - Point A

b - Point B

c - Point C

Returns:

double, the dot product

main

public static void main(String[] args)

Command line interface for debug.

Parameters:

args - No args defined for this main()