edu.umd.cfar.lamp.viper.geometry
Class ConvexPolygon

java.lang.Object
  edu.umd.cfar.lamp.viper.geometry.PolyList
      edu.umd.cfar.lamp.viper.geometry.ConvexPolygon

All Implemented Interfaces:

java.lang.Cloneable, HasCentroid

Direct Known Subclasses:

BoundingBox, OrientedBox

public class ConvexPolygon

extends PolyList

implements java.lang.Cloneable, HasCentroid

A class representing a Convex Polygon. Polygon with vertexes listed in counterclockwise order such that all interior angles are less than 180 degrees. Unlike polylist or BoundingBox, this is limited to containing a single polygon.

See Also:

"Computational Geometry in C"

Field Summary

Fields inherited from class edu.umd.cfar.lamp.viper.geometry.PolyList

area, bbox, CARVE_POLYS, composed, originals, polys

Constructor Summary

ConvexPolygon()
Creates an empty convex polygon, whatever that means.

ConvexPolygon(ConvexPolygon old)
Copy constructor.

ConvexPolygon(CountingStringTokenizer input)
Creates a new convex polygon from the given set of tokens.

ConvexPolygon(int[] points)
Initialize a convex polygon from a sequence of points.

ConvexPolygon(java.util.List points)
Initialize a convex polygon from a sequence of points.

Method Summary

static ConvexPolygon[]	add(ConvexPolygon P, ConvexPolygon Q) Returns a set of polygons that, together, cover all and only the region covered by the specified polygons.
boolean	addVertex(Pnt point) Adds a single point to the polygon.
Rational	area() Finds the area inside the polygon.
protected void	clearPolygon()
static ConvexPolygon[]	clip(ConvexPolygon P, Pnt a, Pnt b) Cuts the polygon into two slices.
java.lang.Object	clone() Gets a copy of this polygon.
boolean	contains(int X, int Y) Tests to see if the point is within this region.
boolean	contains(Pnt point) Tests to see if the point is within this region.
boolean	equals(java.lang.Object o) Tests to see if this region is the same as that covered by the specified shape.
Pnt	getCentroid() Gets the center of the bounding box of the polygon, for now.
PolyList	getIntersection(PolyList other) Gets the region shared between this polygon and all those in the specified PolyList.
Pnt	getNearIntersection(Pnt q1) Get the point of intersection between the ray from the centroid of this box through q1 that is closest to q1.
java.util.Iterator	getPolys() Gets all the component polygons of this set.
protected void	initBbox() Creates a BoundingBox around this, for use by getBoundingBox, etc.
static ConvexPolygon	intersection(ConvexPolygon P, ConvexPolygon Q) This creates a new area that is the intersection of both.
boolean	isInside(ConvexPolygon P) Tests to see if the specified polygon is completely contained within this polygon.
static PolyList	subtract(ConvexPolygon P, ConvexPolygon Q) Subtracts the second shape from the first.
java.lang.String	toString() Gets a string representation of the polygon.
java.lang.String	toStringListOfPoints() Gets a String representation of the polygon as a list of points, where each point is given as (x,y).

Methods inherited from class edu.umd.cfar.lamp.viper.geometry.PolyList

addPoly, clearPolyList, getBoundingBox, getConvexPolygonArray, getFragmentationCount, getOriginals, getPoints, hashCode, intersection, intersects, union

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

ConvexPolygon

public ConvexPolygon()

Creates an empty convex polygon, whatever that means.

ConvexPolygon

public ConvexPolygon(CountingStringTokenizer input)
              throws BadDataException

Creates a new convex polygon from the given set of tokens. Useful for parsing, as it will throw exceptions with the appropriate character offset information.

Parameters:

input - the tokenized string to parse

Throws:

BadDataException - if the string isn't formatted properly

ConvexPolygon

public ConvexPolygon(ConvexPolygon old)

Copy constructor.

Parameters:

old - the convex polygon to duplicate.

ConvexPolygon

public ConvexPolygon(int[] points)

Initialize a convex polygon from a sequence of points.

Parameters:

points - a list of points as (x, y) pairs, such that point k's cooridinates are (points[k/2], points[k/2 + 1]).

ConvexPolygon

public ConvexPolygon(java.util.List points)

Initialize a convex polygon from a sequence of points.

Parameters:

points - a list of viper.geometry.Pnt objects

Method Detail

initBbox

protected void initBbox()

Description copied from class: PolyList

Creates a BoundingBox around this, for use by getBoundingBox, etc. This is called whenever the bbox is requested and it is currently set to null; the bbox field therefore acts as a dirty bit.

Overrides:

initBbox in class PolyList

clone

public java.lang.Object clone()

Gets a copy of this polygon.

Overrides:

clone in class PolyList

Returns:

a new ConvexPolygon that equals this

getIntersection

public PolyList getIntersection(PolyList other)

Gets the region shared between this polygon and all those in the specified PolyList.

Overrides:

getIntersection in class PolyList

Parameters:

other - the region to intersect with

Returns:

a set of polygons that together covers only and all of the region shared by this polygon and the specified region.

getNearIntersection

public Pnt getNearIntersection(Pnt q1)

Get the point of intersection between the ray from the centroid of this box through q1 that is closest to q1.

Parameters:

q1 - A point that is not the centroid.

Returns:

A point on the perimeter of the box on the ray from the centroid through q1.

getCentroid

public Pnt getCentroid()

Gets the center of the bounding box of the polygon, for now.

Specified by:

getCentroid in interface HasCentroid

Returns:

supposed to be the center of the polygon

clip

public static ConvexPolygon[] clip(ConvexPolygon P,
                                   Pnt a,
                                   Pnt b)

Cuts the polygon into two slices. If it cuts it, returns a two-element array, with the first being the area to the left of the segment, and the second with the region to the right. If it does not segment the polygon, it returns a one element array containing a copy of the original polygon.

Parameters:

P - the polygon to slice

a - a point along the slicing line

b - another point, != to a, along the slicing line

Returns:

one or two polygons such that the returned polygons union to the specified polygon but contain no edges that cross the slicing line

subtract

public static PolyList subtract(ConvexPolygon P,
                                ConvexPolygon Q)

Subtracts the second shape from the first.

Parameters:

P - the shape to subtract from

Q - the shape to subtract

Returns:

P - Q, or P ^ ~Q

add

public static ConvexPolygon[] add(ConvexPolygon P,
                                  ConvexPolygon Q)

Returns a set of polygons that, together, cover all and only the region covered by the specified polygons.

Parameters:

P - a convex polygon to union

Q - a convex polygon to union

Returns:

a set of non-overlapping convex polygons that represents the union of P and Q

isInside

public boolean isInside(ConvexPolygon P)

Tests to see if the specified polygon is completely contained within this polygon.

Parameters:

P - the polygon to check for

Returns:

true iff all of P is within this polygon

intersection

public static ConvexPolygon intersection(ConvexPolygon P,
                                         ConvexPolygon Q)

This creates a new area that is the intersection of both.

Parameters:

P - a polygon to intersect

Q - a polygon to intersect

Returns:

the polygon representing the region in both polygons

addVertex

public boolean addVertex(Pnt point)
                  throws BadDataException

Adds a single point to the polygon. Note that this must maintain the convexity property. Before calling this, allocate edge. After calling this, call initBbox.

Overrides:

addVertex in class PolyList

Parameters:

point - the point to add to the polygon

Returns:

true if added, false if collinear

Throws:

BadDataException - if attempting to add reflex vertex

clearPolygon

protected void clearPolygon()

toStringListOfPoints

public final java.lang.String toStringListOfPoints()

Gets a String representation of the polygon as a list of points, where each point is given as (x,y).

Overrides:

toStringListOfPoints in class PolyList

Returns:

the points around the edge of the polygon

toString

public java.lang.String toString()

Gets a string representation of the polygon. If it is composed, uses the PolyList version.

Overrides:

toString in class PolyList

Returns:

a String representation of the object

area

public Rational area()

Finds the area inside the polygon.

Overrides:

area in class PolyList

Returns:

an approximation of the polygon's size

contains

public boolean contains(int X,
                        int Y)

Tests to see if the point is within this region.

Parameters:

X - the x-coordinate of the point to check

Y - the y-coordinate of the point to check

Returns:

true iff the point is within the polygon

contains

public boolean contains(Pnt point)

Tests to see if the point is within this region.

Overrides:

contains in class PolyList

Parameters:

point - the point to look for within the polygon

Returns:

true iff the point is within the polygon

equals

public boolean equals(java.lang.Object o)

Tests to see if this region is the same as that covered by the specified shape.

Overrides:

equals in class PolyList

Parameters:

o - the shape to check against. Works for most children of PolyList

Returns:

false if the two regions are unequal

getPolys

public java.util.Iterator getPolys()

Gets all the component polygons of this set.

Overrides:

getPolys in class PolyList

Returns:

an iterator that just returns one element, this