us.ihmc.utilities.math.geometry
Class ConvexPolygon2d

java.lang.Object
  us.ihmc.utilities.math.geometry.ConvexPolygon2d

All Implemented Interfaces:

Geometry2d

public class ConvexPolygon2d
extends java.lang.Object
implements Geometry2d

Title:

Description:

Copyright: Copyright (c) 2007

Company:

Version:

1.0

Author:

IHMC-Yobotics Biped Team

Constructor Summary

ConvexPolygon2d(java.util.ArrayList<javax.vecmath.Point2d> pointList)

ConvexPolygon2d(ConvexPolygon2d convexPolygon2d)

ConvexPolygon2d(double[][] pointList)

Method Summary

void	applyTransform(javax.media.j3d.Transform3D transform)
void	applyTransform(javax.media.j3d.Transform3D transform, boolean requireTransformInPlane)
ConvexPolygon2d	applyTransformCopy(javax.media.j3d.Transform3D transform)
ConvexPolygon2d	applyTransformCopy(javax.media.j3d.Transform3D transform, boolean requireTransformInPlane)
static boolean	areAdjacentInClockwiseOrder(int index1, int index2, int numVertices)
static ConvexPolygon2dAndConnectingEdges	combineDisjointPolygons(ConvexPolygon2d polygon1, ConvexPolygon2d polygon2) Efficiently combines two Disjoint Polygons.
static ConvexPolygon2d	combinePolygons(ConvexPolygon2d firstPolygon, ConvexPolygon2d secondPolygon) combinePolygons Creates new convex polygon.
static ConvexPolygon2d	computeInsectionOfPolygons(ConvexPolygon2d polygonP, ConvexPolygon2d polygonQ) Computes the intersection of two convex polygons.
static ConvexPolygon2d	constructFromInteriorOfRays(java.util.ArrayList<Line2d> rays)
javax.media.j3d.Geometry	createGeometry()
double	distance(ConvexPolygon2d convexPolygon)
double	distance(Line2d line)
double	distance(LineSegment2d lineSegment)
double	distance(javax.vecmath.Point2d point)
double	distanceToClosestVertex(javax.vecmath.Point2d point)
double[]	distanceToEachVertex(javax.vecmath.Point2d point)
boolean	epsilonEquals(ConvexPolygon2d convexPolygon, double threshold)
java.util.ArrayList<javax.vecmath.Point2d>	getAllVisibleVerticesFromOutsideLeftToRight(javax.vecmath.Point2d observerPoint2d) Returns all of the vertices that are visible from the observerPoint2d, in left to right order.
LineSegment2d[]	getAroundTheCornerEdges(javax.vecmath.Point2d observerPoint2d) Returns the two LineSegment2ds that are the first segments around the corner that cannot be seen from the observerPoint2d.
BoundingBox2d	getBoundingBoxCopy()
javax.vecmath.Point2d	getCentroid()
void	getCentroid(javax.vecmath.Point2d centroid)
javax.vecmath.Point2d	getCentroidCopy()
java.util.ArrayList<javax.vecmath.Point2d>	getClockwiseOrderedListOfPoints()
java.util.ArrayList<javax.vecmath.Point2d>	getClockwiseOrderedListOfPointsCopy()
java.util.ArrayList<javax.vecmath.Point3d>	getClockwiseOrderedListOfPointsCopy(double z)
javax.vecmath.Point2d	getClosestVertexCopy(Line2d line)
javax.vecmath.Point2d	getClosestVertexCopy(javax.vecmath.Point2d point)
LineSegment2d[]	getIntersectingEdges(Line2d line2d)
javax.vecmath.Point2d[]	getLineOfSightVertices(javax.vecmath.Point2d observerPoint2d)
Line2d[]	getLinesOfSight(javax.vecmath.Point2d observerPoint)
static int	getMidEdgeOppositeClockwiseOrdering(int leftEdgeIndex, int rightEdgeIndex, int numEdges)
LineSegment2d[]	getNearestEdges(javax.vecmath.Point2d testPoint)
int	getNumberOfVertices()
java.util.ArrayList<javax.vecmath.Point2d>	getStartingFromLeftMostClockwiseOrderedListOfPointsCopy()
ConvexPolygon2d	intersectionWith(ConvexPolygon2d convexPolygon)
javax.vecmath.Point2d[]	intersectionWith(Line2d line)
javax.vecmath.Point2d[]	intersectionWith(LineSegment2d lineSegment2d)
javax.vecmath.Point2d[]	intersectionWithRay(Line2d ray)
boolean	isCompletelyInside(ConvexPolygon2d polygonQ)
boolean	isPointInside(double x, double y) isPointInside Determines whether a point is inside the convex polygon (point in polygon test).
boolean	isPointInside(javax.vecmath.Point2d point) isPointInside Determines whether a point is inside the convex polygon (point in polygon test).
boolean	isPointInside(javax.vecmath.Point2d[] points) isInside Determines whether all the points in points are inside the convex polygon.
boolean	isPolygonInside(ConvexPolygon2d polygon2) checks to see if the passed polygon is inside of this one.
boolean	isTransformationInPlane(javax.media.j3d.Transform3D transform)
javax.vecmath.Point2d	maxXMaxYPointCopy()
javax.vecmath.Point2d	maxXMinYPointCopy()
javax.vecmath.Point2d	minXMaxYPointCopy()
javax.vecmath.Point2d	minXMinYPointCopy()
void	orthogonalProjection(javax.vecmath.Point2d point2d)
javax.vecmath.Point2d	orthogonalProjectionCopy(javax.vecmath.Point2d point)
double	perimeter()
javax.vecmath.Point2d	pointOnPerimeterGivenParameter(double parameter)
void	pullPointTowardsCentroid(javax.vecmath.Point2d point, double percent)
javax.vecmath.Point2d	pullTowardsCentroidCopy(javax.vecmath.Point2d point, double percent)
static ConvexPolygon2d	shrinkConstantDistanceInto(double distance, ConvexPolygon2d polygonQ)
static ConvexPolygon2d	shrinkInto(ConvexPolygon2d polygonP, javax.vecmath.Point2d referencePointInP, ConvexPolygon2d polygonQ)
java.lang.String	toString()
ConvexPolygon2d	translateCopy(javax.vecmath.Tuple2d translation)

Methods inherited from class java.lang.Object

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

Constructor Detail

ConvexPolygon2d

public ConvexPolygon2d(java.util.ArrayList<javax.vecmath.Point2d> pointList)

ConvexPolygon2d

public ConvexPolygon2d(double[][] pointList)

ConvexPolygon2d

public ConvexPolygon2d(ConvexPolygon2d convexPolygon2d)

Method Detail

getCentroid

public void getCentroid(javax.vecmath.Point2d centroid)

getCentroid

public javax.vecmath.Point2d getCentroid()

getCentroidCopy

public javax.vecmath.Point2d getCentroidCopy()

getBoundingBoxCopy

public BoundingBox2d getBoundingBoxCopy()

getClockwiseOrderedListOfPoints

public java.util.ArrayList<javax.vecmath.Point2d> getClockwiseOrderedListOfPoints()

getClockwiseOrderedListOfPointsCopy

public java.util.ArrayList<javax.vecmath.Point2d> getClockwiseOrderedListOfPointsCopy()

getStartingFromLeftMostClockwiseOrderedListOfPointsCopy

public java.util.ArrayList<javax.vecmath.Point2d> getStartingFromLeftMostClockwiseOrderedListOfPointsCopy()

getClockwiseOrderedListOfPointsCopy

public java.util.ArrayList<javax.vecmath.Point3d> getClockwiseOrderedListOfPointsCopy(double z)

getNumberOfVertices

public int getNumberOfVertices()

distanceToEachVertex

public double[] distanceToEachVertex(javax.vecmath.Point2d point)

getClosestVertexCopy

public javax.vecmath.Point2d getClosestVertexCopy(javax.vecmath.Point2d point)

getClosestVertexCopy

public javax.vecmath.Point2d getClosestVertexCopy(Line2d line)

distanceToClosestVertex

public double distanceToClosestVertex(javax.vecmath.Point2d point)

isPointInside

public boolean isPointInside(javax.vecmath.Point2d point)

isPointInside Determines whether a point is inside the convex polygon (point in polygon test). Uses the orientation method (Nordbeck, Rystedt, 1967) Test is only valid for convex polygons, and only if the vertices are ordered clockwise.

Parameters:

point - Point2d the point to be tested

Returns:

boolean true if the point is inside the polygon

translateCopy

public ConvexPolygon2d translateCopy(javax.vecmath.Tuple2d translation)

isPointInside

public boolean isPointInside(double x,
                             double y)

isPointInside Determines whether a point is inside the convex polygon (point in polygon test). Uses the orientation method (Nordbeck, Rystedt, 1967) Test is only valid for convex polygons, and only if the vertices are ordered clockwise.

Parameters:

x -

y -

Returns:

boolean true if the point is inside the polygon

isPointInside

public boolean isPointInside(javax.vecmath.Point2d[] points)

isInside Determines whether all the points in points are inside the convex polygon.

Parameters:

points - Point2d[]

Returns:

boolean

isPolygonInside

public boolean isPolygonInside(ConvexPolygon2d polygon2)

checks to see if the passed polygon is inside of this one.

Parameters:

polygon2 -

Returns:

true if polygon2 is inside of this polygon

getLinesOfSight

public Line2d[] getLinesOfSight(javax.vecmath.Point2d observerPoint)

getAllVisibleVerticesFromOutsideLeftToRight

public java.util.ArrayList<javax.vecmath.Point2d> getAllVisibleVerticesFromOutsideLeftToRight(javax.vecmath.Point2d observerPoint2d)

Returns all of the vertices that are visible from the observerPoint2d, in left to right order. If the observerPoint2d is inside the polygon, returns null.

Parameters:

observerPoint2d - Point2d

Returns:

Point2d[]

getLineOfSightVertices

public javax.vecmath.Point2d[] getLineOfSightVertices(javax.vecmath.Point2d observerPoint2d)

getAroundTheCornerEdges

public LineSegment2d[] getAroundTheCornerEdges(javax.vecmath.Point2d observerPoint2d)

Returns the two LineSegment2ds that are the first segments around the corner that cannot be seen from the observerPoint2d. If the observerPoint2d is null returns null. The line segments are returned in order of left, then right. The line segments go from the line of sight points to the points that are not in view, but are around the corner.

Parameters:

observerPoint2d - Point2d marking the point of observation of this ConvexPolygon2d.

Returns:

LineSegment2d[] Two line segments going from the line of sight points to the first points around the corners that are out of sight. null if the observerPoint2d is inside this ConvexPolygon2d.

getNearestEdges

public LineSegment2d[] getNearestEdges(javax.vecmath.Point2d testPoint)

areAdjacentInClockwiseOrder

public static boolean areAdjacentInClockwiseOrder(int index1,
                                                  int index2,
                                                  int numVertices)

getMidEdgeOppositeClockwiseOrdering

public static int getMidEdgeOppositeClockwiseOrdering(int leftEdgeIndex,
                                                      int rightEdgeIndex,
                                                      int numEdges)

intersectionWith

public javax.vecmath.Point2d[] intersectionWith(LineSegment2d lineSegment2d)

Specified by:

intersectionWith in interface Geometry2d

intersectionWith

public javax.vecmath.Point2d[] intersectionWith(Line2d line)

Specified by:

intersectionWith in interface Geometry2d

intersectionWithRay

public javax.vecmath.Point2d[] intersectionWithRay(Line2d ray)

getIntersectingEdges

public LineSegment2d[] getIntersectingEdges(Line2d line2d)

orthogonalProjection

public void orthogonalProjection(javax.vecmath.Point2d point2d)

Specified by:

orthogonalProjection in interface Geometry2d

orthogonalProjectionCopy

public javax.vecmath.Point2d orthogonalProjectionCopy(javax.vecmath.Point2d point)

Specified by:

orthogonalProjectionCopy in interface Geometry2d

intersectionWith

public ConvexPolygon2d intersectionWith(ConvexPolygon2d convexPolygon)

Specified by:

intersectionWith in interface Geometry2d

distance

public double distance(javax.vecmath.Point2d point)

Specified by:

distance in interface Geometry2d

distance

public double distance(Line2d line)

Specified by:

distance in interface Geometry2d

distance

public double distance(LineSegment2d lineSegment)

Specified by:

distance in interface Geometry2d

distance

public double distance(ConvexPolygon2d convexPolygon)

Specified by:

distance in interface Geometry2d

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

createGeometry

public javax.media.j3d.Geometry createGeometry()

applyTransform

public void applyTransform(javax.media.j3d.Transform3D transform)

Specified by:

applyTransform in interface Geometry2d

applyTransform

public void applyTransform(javax.media.j3d.Transform3D transform,
                           boolean requireTransformInPlane)

Specified by:

applyTransform in interface Geometry2d

applyTransformCopy

public ConvexPolygon2d applyTransformCopy(javax.media.j3d.Transform3D transform)

Specified by:

applyTransformCopy in interface Geometry2d

applyTransformCopy

public ConvexPolygon2d applyTransformCopy(javax.media.j3d.Transform3D transform,
                                          boolean requireTransformInPlane)

Specified by:

applyTransformCopy in interface Geometry2d

isTransformationInPlane

public boolean isTransformationInPlane(javax.media.j3d.Transform3D transform)

minXMaxYPointCopy

public javax.vecmath.Point2d minXMaxYPointCopy()

minXMinYPointCopy

public javax.vecmath.Point2d minXMinYPointCopy()

maxXMaxYPointCopy

public javax.vecmath.Point2d maxXMaxYPointCopy()

maxXMinYPointCopy

public javax.vecmath.Point2d maxXMinYPointCopy()

perimeter

public double perimeter()

pointOnPerimeterGivenParameter

public javax.vecmath.Point2d pointOnPerimeterGivenParameter(double parameter)

pullPointTowardsCentroid

public void pullPointTowardsCentroid(javax.vecmath.Point2d point,
                                     double percent)

pullTowardsCentroidCopy

public javax.vecmath.Point2d pullTowardsCentroidCopy(javax.vecmath.Point2d point,
                                                     double percent)

combinePolygons

public static ConvexPolygon2d combinePolygons(ConvexPolygon2d firstPolygon,
                                              ConvexPolygon2d secondPolygon)

combinePolygons Creates new convex polygon. Its clockwiseOrderedListOfPoints is the convex hull of all the vertices of the polygons it was created from.

Parameters:

firstPolygon - ConvexPolygon2d

secondPolygon - ConvexPolygon2d

Returns:

ConvexPolygon2d

combineDisjointPolygons

public static ConvexPolygon2dAndConnectingEdges combineDisjointPolygons(ConvexPolygon2d polygon1,
                                                                        ConvexPolygon2d polygon2)

Efficiently combines two Disjoint Polygons. Returns null if not disjoint.

Parameters:

polygon1 - ConvexPolygon2d

polygon2 - ConvexPolygon2d

Returns:

ConvexPolygon2dAndConnectingEdges

computeInsectionOfPolygons

public static ConvexPolygon2d computeInsectionOfPolygons(ConvexPolygon2d polygonP,
                                                         ConvexPolygon2d polygonQ)

Computes the intersection of two convex polygons. For references see: http://www.iro.umontreal.ca/~plante/compGeom/algorithm.html Returns null if: 1) the polygons do not intersect 2) they intersect in a point or a line 3) either polygon is a point or line Returns the inside polygon if the two polygons are inside one another.

Parameters:

polygonP - ConvexPolygon2d

polygonQ - ConvexPolygon2d

Returns:

ConvexPolygon2d Intersection of polygonP and polygonQ

isCompletelyInside

public boolean isCompletelyInside(ConvexPolygon2d polygonQ)

epsilonEquals

public boolean epsilonEquals(ConvexPolygon2d convexPolygon,
                             double threshold)

shrinkConstantDistanceInto

public static ConvexPolygon2d shrinkConstantDistanceInto(double distance,
                                                         ConvexPolygon2d polygonQ)

constructFromInteriorOfRays

public static ConvexPolygon2d constructFromInteriorOfRays(java.util.ArrayList<Line2d> rays)

shrinkInto

public static ConvexPolygon2d shrinkInto(ConvexPolygon2d polygonP,
                                         javax.vecmath.Point2d referencePointInP,
                                         ConvexPolygon2d polygonQ)