us.ihmc.utilities.math.geometry
Class ConvexPolygon2d

java.lang.Object
  extended by 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

Nested Class Summary
static class ConvexPolygon2d.FewerThanOnePointException
           
 
Constructor Summary
ConvexPolygon2d(ConvexPolygon2d convexPolygon2d)
           
ConvexPolygon2d(double[][] pointList)
           
ConvexPolygon2d(java.util.List<javax.vecmath.Point2d> 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)
           
 boolean areAllPointsInside(javax.vecmath.Point2d[] points)
          areAllPointsInside Determines whether all the points in points are inside the convex polygon.
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 computeIntersectionOfPolygons(ConvexPolygon2d polygonP, ConvexPolygon2d polygonQ)
          Computes the intersection of two convex polygons.
static ConvexPolygon2d constructFromInteriorOfRays(java.util.ArrayList<Line2d> rays)
           
 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.
 double getArea()
           
 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.List<javax.vecmath.Point2d> getClockwiseOrderedListOfPoints()
           
 java.util.ArrayList<javax.vecmath.Point2d> getClockwiseOrderedListOfPointsCopy()
           
 java.util.ArrayList<javax.vecmath.Point3d> getClockwiseOrderedListOfPointsCopy(double z)
           
 LineSegment2d getClosestEdge(javax.vecmath.Point2d point)
           
 int[] getClosestEdgeVertexIndicesInClockwiseOrderedList(javax.vecmath.Point2d point)
           
 javax.vecmath.Point2d getClosestVertexCopy(Line2d line)
           
 javax.vecmath.Point2d getClosestVertexCopy(javax.vecmath.Point2d point)
           
 java.util.ArrayList<javax.vecmath.Point2d> getCounterClockwiseOrderedListOfPointsCopy()
           
 LineSegment2d[] getIntersectingEdges(Line2d line2d)
           
 javax.vecmath.Point2d[] getLineOfSightVertices(javax.vecmath.Point2d observerPoint2d)
           
 Line2d[] getLinesOfSight(javax.vecmath.Point2d observerPoint)
           
 javax.vecmath.Point2d getMeanPoint()
           
static int getMidEdgeOppositeClockwiseOrdering(int leftEdgeIndex, int rightEdgeIndex, int numEdges)
           
 LineSegment2d[] getNearestEdges(javax.vecmath.Point2d testPoint)
           
 int getNumberOfVertices()
           
 java.util.ArrayList<javax.vecmath.Vector2d> getOutSideFacingOrthoNormalVectors()
           
 java.util.ArrayList<javax.vecmath.Point2d> getStartingFromLeftMostClockwiseOrderedListOfPointsCopy()
           
static javax.vecmath.Point2d[] intersection(LineSegment2d lineSegment, ConvexPolygon2d convexPolygon)
           
 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)
           
 boolean isPointInside(double x, double y, double epsilon)
          isPointInside Determines whether a point is inside the convex polygon (point in polygon test).
 boolean isPointInside(javax.vecmath.Point2d point)
           
 boolean isPointInside(javax.vecmath.Point2d point, double epsilon)
          isPointInside Determines whether a point is inside the convex polygon (point in polygon test).
 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()
           
 boolean pointIsOnPerimeter(javax.vecmath.Point2d point)
           
 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.List<javax.vecmath.Point2d> pointList)

ConvexPolygon2d

public ConvexPolygon2d(double[][] pointList)

ConvexPolygon2d

public ConvexPolygon2d(ConvexPolygon2d convexPolygon2d)
Method Detail

getArea

public double getArea()

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.List<javax.vecmath.Point2d> getClockwiseOrderedListOfPoints()

getClockwiseOrderedListOfPointsCopy

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

getCounterClockwiseOrderedListOfPointsCopy

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

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

public boolean isPointInside(javax.vecmath.Point2d point,
                             double epsilon)
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

public boolean isPointInside(double x,
                             double y,
                             double epsilon)
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

areAllPointsInside

public boolean areAllPointsInside(javax.vecmath.Point2d[] points)
areAllPointsInside 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)

intersectionWith

public ConvexPolygon2d intersectionWith(ConvexPolygon2d convexPolygon)
Specified by:
intersectionWith in interface Geometry2d

getClosestEdge

public LineSegment2d getClosestEdge(javax.vecmath.Point2d point)

getClosestEdgeVertexIndicesInClockwiseOrderedList

public int[] getClosestEdgeVertexIndicesInClockwiseOrderedList(javax.vecmath.Point2d point)

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

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

pointIsOnPerimeter

public boolean pointIsOnPerimeter(javax.vecmath.Point2d point)

computeIntersectionOfPolygons

public static ConvexPolygon2d computeIntersectionOfPolygons(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 the polygons do not intersect 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)

getMeanPoint

public javax.vecmath.Point2d getMeanPoint()

getOutSideFacingOrthoNormalVectors

public java.util.ArrayList<javax.vecmath.Vector2d> getOutSideFacingOrthoNormalVectors()

distance

public double distance(javax.vecmath.Point2d point)
Specified by:
distance in interface Geometry2d

orthogonalProjectionCopy

public javax.vecmath.Point2d orthogonalProjectionCopy(javax.vecmath.Point2d point)
Specified by:
orthogonalProjectionCopy in interface Geometry2d

orthogonalProjection

public void orthogonalProjection(javax.vecmath.Point2d point2d)
Specified by:
orthogonalProjection in interface Geometry2d

intersection

public static javax.vecmath.Point2d[] intersection(LineSegment2d lineSegment,
                                                   ConvexPolygon2d convexPolygon)