The Physiologist's Friend Simulation API

ch.unizh.ini.friend.graphics
Class ConvexPolygon

java.lang.Object
  extended by ch.unizh.ini.friend.graphics.AbstractTransformable
      extended by ch.unizh.ini.friend.graphics.ConvexPolygon
All Implemented Interfaces:
Intersectable, Transformable, Shape, Cloneable

public class ConvexPolygon
extends AbstractTransformable
implements Intersectable, Shape

This class implements the notion of a convex polygon. It ensures that the polygon it represents is convex, no three vertices are co-linear and the vertices are in counterclockwise order. The implementaion of the intersection algorithm is based on a note from J. O'Rourke et al., Computer Graphics and Image Processing 19, 384-391 (1982).

The points are stored as linear array are x,y pairs of coordinates.

Version:
$Revision: 1.10 $
Author:
Christof Marti

Field Summary
 int npoints
          The number of vertices (xpoints and ypoints may have more elements than vertices present).
 float[] points
          The coordinates of the vertices, as x,y pairs.
 
Constructor Summary
ConvexPolygon()
          Initializes xpoints and ypoints to three elements.
ConvexPolygon(float[] points, int npoints)
          Ensures that the represented polygon is convex, no three vertices are co-linear and the vertices are in counterclockwise order.
ConvexPolygon(int n)
          Initializes xpoints and ypoints to n elements.
 
Method Summary
 void addPoint(float x, float y)
          Adds the given vertex at the end of the allready added vertices iff the resulting polygon is still convex, no three vertices co-linear and in counterclockwise order.
protected  void addPointOfIntersection(float x, float y)
          Adds a point to the polygon iff it isCompliant(x, y).
protected  void addPointSilently(float x, float y)
          Adds the given vertex at the end of the allready added vertices.
 Transformable apply(AffineTransform at)
          Applies the given transformation to the vertices of the polygon.
 float area()
          Calculates the area of this polygon.
 Object clone()
          Clones the polygon by allocating a new polygon and copying the array of coordinates.
 boolean contains(double x, double y)
          Determines whether the given point (x, y) is contained by this instance of ConvexPolygon.
 boolean contains(double x, double y, double w, double h)
          Determines whether the given rectangle is completely contained by this instance of ConvexPolygon.
 boolean contains(Point2D point2D)
          Determines whether the given point is contained by this instance of ConvexPolygon.
 boolean contains(Rectangle2D rectangle2D)
          Determines whether the given rectangle is completely contained by this instance of ConvexPolygon.
protected  boolean doIntersect(float x11, float y11, float x12, float y12, float x21, float y21, float x22, float y22)
          Determines whether the two given lines intersect.
protected  float dotProd(float x1, float y1, float x2, float y2)
          Computes the dot product of the two given vectors.
 Rectangle getBounds()
          Computes a bounding box around this instance of ConvexPolygon.
 Rectangle2D getBounds2D()
          Computes a bounding box around this instance of ConvexPolygon.
 Point2D getCenter()
          Computes the center of this ConvexPolygon.
static ConvexPolygon getNGonInstance(float x, float y, float r, int n)
          Creates an instance of ConvexPolygon initalizing it as a regular n-gon with the given radius of the enclosing circle and the given center.
static ConvexPolygon getNGonInstance(float r, int n)
          Creates an instance of ConvexPolygon initalizing it as a regular n-gon with the given radius of the enclosing circle and the center at (0,0).
static ConvexPolygon getNGonInstance(int n)
          Creates an instance of ConvexPolygon initalizing it as a regular n-gon with radius 1.0 of the enclosing circle and the center at (0,0).
 PathIterator getPathIterator(AffineTransform at)
          Returns a PathIterator for this polygon, applying the transform if not null.
 PathIterator getPathIterator(AffineTransform at, double flatness)
          Returns a PathIterator for this polygon, applying the transform if not null.
static ConvexPolygon getRectangleInstance(float x, float y, float w, float h)
          Creates an instance of ConvexPolygon initalizing it as a rectangle.
protected  void intersect(float x11, float y11, float x12, float y12, float x21, float y21, float x22, float y22, float[] coords)
          Intersects the two given lines and stores the intersection point in the given array.
 Intersectable intersect(Intersectable other)
          Intersects this convex polygon with n vertices with the given convex polygon with m vertices and returns the intersection which is again a convex polygon with at most n+m vertices.
 boolean intersects(double x, double y, double w, double h)
          Determines whether the given rectangle intersects with this polygon.
 boolean intersects(Rectangle2D rect)
          Determines whether the given rectangle intersects with this polygon.
 boolean isCompliant()
          Determines whether the represented polygon is convex, has no three co-linear vertices and the vertices are counterclockwise ordered.
 boolean isCompliant(float x, float y)
          Determines whether the polygon obtained by adding the given point (x,y) at the end would still be convex, have no three co-linear vertices and have the vertices in counterclockwise order.
protected  boolean isInHalfPlane(float x1, float y1, float x2, float y2, float x, float y)
          Determines whether (x,y) is on the left of the straight line defined by (x1,y1) and (x2, y2) (looking from the first to the second), including the line itself.
protected  boolean isInPolygon(float x, float y, ConvexPolygon P)
          Determines whether a given point is in the given polygon.
protected  boolean isStrictlyInHalfPlane(float x1, float y1, float x2, float y2, float x, float y)
          Determines whether (x,y) is on the left of the straight line defined by (x1,y1) and (x2, y2) (looking from the first to the second), excluding the line itself.
protected  float pointInHalfPlane(float x1, float y1, float x2, float y2, float x, float y)
          Determines whether (x,y) is on the left, right of or on the straight line defined by (x1,y1) and (x2, y2) (looking from the first to the second), including the line itself.
protected  float signedArea(float x1, float y1, float x2, float y2, float x3, float y3)
          Calculates the twice the signed area of the defined by the given three vertices p1, p2 and p3, where the sign is positive iff (p1p2p3) form a counterclockwise cycle.
 String toString()
          Returns a String-representation of the polygon.
 
Methods inherited from class ch.unizh.ini.friend.graphics.AbstractTransformable
rotate, rotate, scale, scale, translate
 
Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface ch.unizh.ini.friend.graphics.Transformable
rotate, rotate, scale, scale, translate
 

Field Detail

npoints

public int npoints
The number of vertices (xpoints and ypoints may have more elements than vertices present).


points

public float[] points
The coordinates of the vertices, as x,y pairs.

Constructor Detail

ConvexPolygon

public ConvexPolygon()
Initializes xpoints and ypoints to three elements.


ConvexPolygon

public ConvexPolygon(int n)
Initializes xpoints and ypoints to n elements.

Parameters:
n - The number of vertices that initially can be stored with this polygon.

ConvexPolygon

public ConvexPolygon(float[] points,
                     int npoints)
Ensures that the represented polygon is convex, no three vertices are co-linear and the vertices are in counterclockwise order. If they do not satisfy this npoints will be set to two.

Parameters:
points - The x,y-coordinates of the vertices.
npoints - The number of initial vertices.
Method Detail

getNGonInstance

public static ConvexPolygon getNGonInstance(float x,
                                            float y,
                                            float r,
                                            int n)
Creates an instance of ConvexPolygon initalizing it as a regular n-gon with the given radius of the enclosing circle and the given center.

Parameters:
x - x-coordinate of the center.
y - y-coordinate of the center.
r - The radius of the enclosing circle.
n - The number of edges the polygon will have.
Returns:
A regular n-gon.

getNGonInstance

public static ConvexPolygon getNGonInstance(float r,
                                            int n)
Creates an instance of ConvexPolygon initalizing it as a regular n-gon with the given radius of the enclosing circle and the center at (0,0).

Parameters:
r - The radius of the enclosing circle.
n - The number of edges the polygon will have.
Returns:
A regular n-gon.

getNGonInstance

public static ConvexPolygon getNGonInstance(int n)
Creates an instance of ConvexPolygon initalizing it as a regular n-gon with radius 1.0 of the enclosing circle and the center at (0,0).

Parameters:
n - The number of edges the polygon will have.
Returns:
A regular n-gon.

getRectangleInstance

public static ConvexPolygon getRectangleInstance(float x,
                                                 float y,
                                                 float w,
                                                 float h)
Creates an instance of ConvexPolygon initalizing it as a rectangle.

Parameters:
x - x-coordinate of the vertex with smallest value.
y - y-coordinate of the vertex with smallest value.
w - Width of the rectangle.
h - Height of the rectangle.
Returns:
A rectangle.

isCompliant

public boolean isCompliant()
Determines whether the represented polygon is convex, has no three co-linear vertices and the vertices are counterclockwise ordered.

Returns:
True iff the instance is compliant to these rules.

signedArea

protected float signedArea(float x1,
                           float y1,
                           float x2,
                           float y2,
                           float x3,
                           float y3)
Calculates the twice the signed area of the defined by the given three vertices p1, p2 and p3, where the sign is positive iff (p1p2p3) form a counterclockwise cycle.

Parameters:
x1 - x-coordinate of the first vertex.
y1 - y-coordinate of the first vertex.
x2 - x-coordinate of the second vertex.
y2 - y-coordinate of the second vertex.
x3 - x-coordinate of the third vertex.
y3 - y-coordinate of the third vertex.
Returns:
Twice the signed area of the triangle definded by the given vertices.

isCompliant

public boolean isCompliant(float x,
                           float y)
Determines whether the polygon obtained by adding the given point (x,y) at the end would still be convex, have no three co-linear vertices and have the vertices in counterclockwise order.


addPoint

public void addPoint(float x,
                     float y)
Adds the given vertex at the end of the allready added vertices iff the resulting polygon is still convex, no three vertices co-linear and in counterclockwise order.

Parameters:
x - x-coordinate of the vertex to add.
y - y-coordinate of the vertex to add.

addPointSilently

protected void addPointSilently(float x,
                                float y)
Adds the given vertex at the end of the allready added vertices. The number of vertices npoints will not be increased and no checks regarding the conformance are made.

Parameters:
x - x-coordinate of the vertex to add.
y - y-coordinate of the vertex to add.

contains

public boolean contains(Rectangle2D rectangle2D)
Determines whether the given rectangle is completely contained by this instance of ConvexPolygon.

Specified by:
contains in interface Shape
Parameters:
rectangle2D - The rectangle to check.
Returns:
true iff the given rectangle is contained by the polygon.

contains

public boolean contains(Point2D point2D)
Determines whether the given point is contained by this instance of ConvexPolygon.

Specified by:
contains in interface Shape
Parameters:
point2D - The point to check.
Returns:
true iff the given point is contained by the polygon.

contains

public boolean contains(double x,
                        double y)
Determines whether the given point (x, y) is contained by this instance of ConvexPolygon.

Specified by:
contains in interface Shape
Parameters:
x - x-coordinate of the point to check.
y - y-coordinate of the point to check.
Returns:
True iff the point is contained in the polygon.

contains

public boolean contains(double x,
                        double y,
                        double w,
                        double h)
Determines whether the given rectangle is completely contained by this instance of ConvexPolygon.

Specified by:
contains in interface Shape
Parameters:
x - x-coordinate of the vertex with the smallest value.
y - y-coordinate of the vertex with the smallest value.
w - Width of the rectangle.
h - Height of the rectangle.
Returns:
True iff the given rectangle is contained by the polygon.

getBounds

public Rectangle getBounds()
Computes a bounding box around this instance of ConvexPolygon.

Specified by:
getBounds in interface Shape
Returns:
The bounding box as an instance of Rectangle.

getBounds2D

public Rectangle2D getBounds2D()
Computes a bounding box around this instance of ConvexPolygon.

Specified by:
getBounds2D in interface Shape
Returns:
The bounding box as an instance of Rectangle2D.

getCenter

public Point2D getCenter()
Computes the center of this ConvexPolygon. This is the average location of all the points the make up the polygon.

Returns:
the center point.

getPathIterator

public PathIterator getPathIterator(AffineTransform at)
Returns a PathIterator for this polygon, applying the transform if not null.

Specified by:
getPathIterator in interface Shape
Parameters:
at - The transform to apply.
Returns:
The PathIterator
See Also:
PathIterator

getPathIterator

public PathIterator getPathIterator(AffineTransform at,
                                    double flatness)
Returns a PathIterator for this polygon, applying the transform if not null.

Specified by:
getPathIterator in interface Shape
Parameters:
at - The transform to apply.
flatness - Has no meaning because the polygon is flat by nature.
Returns:
The PathIterator
See Also:
PathIterator

clone

public Object clone()
Clones the polygon by allocating a new polygon and copying the array of coordinates.

Specified by:
clone in interface Transformable
Overrides:
clone in class AbstractTransformable
Returns:
The clone.

intersects

public boolean intersects(Rectangle2D rect)
Determines whether the given rectangle intersects with this polygon.

Specified by:
intersects in interface Shape
Parameters:
rect - The rectangle to check against.
Returns:
True iff they intersect.

intersects

public boolean intersects(double x,
                          double y,
                          double w,
                          double h)
Determines whether the given rectangle intersects with this polygon.

Specified by:
intersects in interface Shape
Parameters:
x - x-coordinate of the vertex with the smallest value.
y - y-coordinate of the vertex with the smallest value.
w - width of the rectangle.
h - height of the rectangle.
Returns:
True iff they intersect.

dotProd

protected float dotProd(float x1,
                        float y1,
                        float x2,
                        float y2)
Computes the dot product of the two given vectors.

Parameters:
x1 - x-coordinate of the first vector.
y1 - y-coordinate of the first vector.
x2 - x-coordinate of the second vector.
y2 - y-coordinate of the second vector.
Returns:
The dot product of the two given vectors.

pointInHalfPlane

protected float pointInHalfPlane(float x1,
                                 float y1,
                                 float x2,
                                 float y2,
                                 float x,
                                 float y)
Determines whether (x,y) is on the left, right of or on the straight line defined by (x1,y1) and (x2, y2) (looking from the first to the second), including the line itself.

Parameters:
x1 - x-coordinate of the first point defining the half-plane.
y1 - y-coordinate of the first point defining the half-plane.
x2 - x-coordinate of the second point defining the half-plane.
y2 - y-coordinate of the second point defining the half-plane.
x - x-coordinate of the point to check.
y - y-coordinate of the point to check.
Returns:
Positive for 'left', zero for 'on', negative for 'right'.

isInHalfPlane

protected boolean isInHalfPlane(float x1,
                                float y1,
                                float x2,
                                float y2,
                                float x,
                                float y)
Determines whether (x,y) is on the left of the straight line defined by (x1,y1) and (x2, y2) (looking from the first to the second), including the line itself.

Parameters:
x1 - x-coordinate of the first point defining the half-plane.
y1 - y-coordinate of the first point defining the half-plane.
x2 - x-coordinate of the second point defining the half-plane.
y2 - y-coordinate of the second point defining the half-plane.
x - x-coordinate of the point to check.
y - y-coordinate of the point to check.
Returns:
True iff (x,y) is on the left of the straight line defined by (x1,y1) and (x2, y2).

isStrictlyInHalfPlane

protected boolean isStrictlyInHalfPlane(float x1,
                                        float y1,
                                        float x2,
                                        float y2,
                                        float x,
                                        float y)
Determines whether (x,y) is on the left of the straight line defined by (x1,y1) and (x2, y2) (looking from the first to the second), excluding the line itself.

Parameters:
x1 - x-coordinate of the first point defining the half-plane.
y1 - y-coordinate of the first point defining the half-plane.
x2 - x-coordinate of the second point defining the half-plane.
y2 - y-coordinate of the second point defining the half-plane.
x - x-coordinate of the point to check.
y - y-coordinate of the point to check.
Returns:
True iff (x,y) is on the left of the straight line defined by (x1,y1) and (x2, y2).

doIntersect

protected boolean doIntersect(float x11,
                              float y11,
                              float x12,
                              float y12,
                              float x21,
                              float y21,
                              float x22,
                              float y22)
Determines whether the two given lines intersect. Adapted for special cases of the algorithm for intersecting two polygons. This isn't done accurately yet.

Parameters:
x11 - x-coordinate of the first point of the first line.
y11 - y-coordinate of the first point of the first line.
x12 - x-coordinate of the second point of the first line.
y12 - y-coordinate of the second point of the first line.
x21 - x-coordinate of the first point of the second line.
y21 - y-coordinate of the first point of the second line.
x22 - x-coordinate of the second point of the second line.
y22 - y-coordinate of the second point of the second line.
Returns:
True iff they intersect.

intersect

protected void intersect(float x11,
                         float y11,
                         float x12,
                         float y12,
                         float x21,
                         float y21,
                         float x22,
                         float y22,
                         float[] coords)
Intersects the two given lines and stores the intersection point in the given array. This isn't done accurately yet.

Parameters:
x11 - x-coordinate of the first point of the first line.
y11 - y-coordinate of the first point of the first line.
x12 - x-coordinate of the second point of the first line.
y12 - y-coordinate of the second point of the first line.
x21 - x-coordinate of the first point of the second line.
y21 - y-coordinate of the first point of the second line.
x22 - x-coordinate of the second point of the second line.
y22 - y-coordinate of the second point of the second line.
coords - The array the intersection point is stored in.

addPointOfIntersection

protected void addPointOfIntersection(float x,
                                      float y)
Adds a point to the polygon iff it isCompliant(x, y).


isInPolygon

protected boolean isInPolygon(float x,
                              float y,
                              ConvexPolygon P)
Determines whether a given point is in the given polygon.

Parameters:
x - x-coordinate of the point.
y - y-coordinate of the point.
P - the polygon to check against.
Returns:
true iff the point is within the polygon.

intersect

public Intersectable intersect(Intersectable other)
Intersects this convex polygon with n vertices with the given convex polygon with m vertices and returns the intersection which is again a convex polygon with at most n+m vertices. The algorithm runs in O(n + m) and is due to J. O'Rourke et al., Computer Graphics and Image Processing 19, 384-391 (1982).

Specified by:
intersect in interface Intersectable
Parameters:
other - The polygon to intersect with.
Returns:
The intersection.

area

public float area()
Calculates the area of this polygon.

Specified by:
area in interface Intersectable
Returns:
The area.

toString

public String toString()
Returns a String-representation of the polygon.

Overrides:
toString in class Object

apply

public Transformable apply(AffineTransform at)
Applies the given transformation to the vertices of the polygon. This applies the transformation to all the points and leaves them in the transformed state.

Specified by:
apply in interface Transformable
Parameters:
at - The affine transformation to apply.
Returns:
this - for easy concatenation.

http://www.ini.unizh.ch/~tobi/friend