de.lmu.ifi.dbs.elki.data.spatial
Class Polygon

java.lang.Object
  de.lmu.ifi.dbs.elki.data.spatial.Polygon

All Implemented Interfaces:

SpatialComparable, Iterable<Vector>

public class Polygon
extends Object
implements Iterable<Vector>, SpatialComparable

Class representing a simple polygon. While you can obviously store non-simple polygons in this, note that many of the supplied methods will assume that the polygons are simple.

Field Summary

private double[]	max Maximum values
private double[]	min Minimum values
private List<Vector>	points The actual points

Constructor Summary

Polygon(List<Vector> points)
Constructor.

Polygon(List<Vector> points, double minx, double maxx, double miny, double maxy)

Method Summary

void	appendToBuffer(StringBuffer buf) Append the polygon to the buffer.
boolean	containsPoint2D(Vector v) Point in polygon test, based on http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html by W.
ListIterator<Vector>	descendingIterator() Return an iterator that iterates the list backwards.
Vector	get(int idx) Get a vector by index.
int	getDimensionality() Returns the dimensionality of the object.
double	getMax(int dimension) Returns the maximum coordinate at the specified dimension.
double	getMin(int dimension) Returns the minimum coordinate at the specified dimension.
boolean	intersects2DIncomplete(Polygon other) Simple polygon intersection test.
Iterator<Vector>	iterator()
ListIterator<Vector>	listIterator() Get a list iterator.
int	size() Get the polygon length.
int	testClockwise() Test polygon orientation.
String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

points

private List<Vector> points

The actual points

min

private double[] min

Minimum values

max

private double[] max

Maximum values

Constructor Detail

Polygon

public Polygon(List<Vector> points)

Constructor.

Parameters:

points - Polygon points

Polygon

public Polygon(List<Vector> points,
               double minx,
               double maxx,
               double miny,
               double maxy)

Method Detail

iterator

public Iterator<Vector> iterator()

Specified by:

iterator in interface Iterable<Vector>

listIterator

public ListIterator<Vector> listIterator()

Get a list iterator.

Returns:

List iterator.

descendingIterator

public ListIterator<Vector> descendingIterator()

Return an iterator that iterates the list backwards.

Returns:

Reversed iterator

appendToBuffer

public void appendToBuffer(StringBuffer buf)

Append the polygon to the buffer.

Parameters:

buf - Buffer to append to

toString

public String toString()

Overrides:

toString in class Object

size

public int size()

Get the polygon length.

Returns:

Polygon length

get

public Vector get(int idx)

Get a vector by index.

Parameters:

idx - Index to get

Returns:

Vector

getDimensionality

public int getDimensionality()

Description copied from interface: SpatialComparable

Returns the dimensionality of the object.

Specified by:

getDimensionality in interface SpatialComparable

Returns:

the dimensionality

getMin

public double getMin(int dimension)

Description copied from interface: SpatialComparable

Returns the minimum coordinate at the specified dimension.

Specified by:

getMin in interface SpatialComparable

Parameters:

dimension - the dimension for which the coordinate should be returned, where 1 ≤ dimension ≤ getDimensionality()

Returns:

the minimum coordinate at the specified dimension

getMax

public double getMax(int dimension)

Description copied from interface: SpatialComparable

Returns the maximum coordinate at the specified dimension.

Specified by:

getMax in interface SpatialComparable

Parameters:

dimension - the dimension for which the coordinate should be returned, where 1 ≤ dimension ≤ getDimensionality()

Returns:

the maximum coordinate at the specified dimension

testClockwise

public int testClockwise()

Test polygon orientation.

Returns:

-1, 0, 1 for counterclockwise, undefined and clockwise.

intersects2DIncomplete

public boolean intersects2DIncomplete(Polygon other)

Simple polygon intersection test.

FIXME: while this is found on some web pages as "solution" and satisfies or needs, it clearly is not correct; not even for convex polygons: Consider a cross where the two bars are made out of four vertices each. No vertex is inside the other polygon, yet they intersect. I knew this before writing this code, but this O(n) code was the simplest thing to come up with, and it would work for our current data sets. A way to fix this is to augment it with the obvious O(n*n) segment intersection test. (Note that you will still need to test for point containment, since the whole polygon could be contained in the other!)

Parameters:

other - Other polygon

Returns:

True when the polygons intersect

containsPoint2D

public boolean containsPoint2D(Vector v)

Point in polygon test, based on http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html by W. Randolph Franklin

Parameters:

v - Point to test

Returns:

True when contained.