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

Class Polygon

java.lang.Object

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

All Implemented Interfaces:

SpatialComparable

public class Polygon
extends java.lang.Object
implements 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.

Since:

0.4.0

Author:

Erich Schubert

Field Summary

Fields

Modifier and Type	Field and Description
private double[]	max Maximum values
private double[]	min Minimum values
private java.util.List<double[]>	points The actual points

Constructor Summary

Constructors

Constructor and Description
Polygon(java.util.List<double[]> points) Constructor.
Polygon(java.util.List<double[]> points, double minx, double maxx, double miny, double maxy) Constructor.

Method Summary

Modifier and Type	Method and Description
java.lang.StringBuilder	appendToBuffer(java.lang.StringBuilder buf) Append the polygon to the buffer.
double	areaShoelace() Compute the polygon area (geometric, not geographic) using the Shoelace formula.
boolean	containsPoint2D(double[] v) Point in polygon test, based on http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html by W.
double[]	get(int idx) Get a double[] 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.
ArrayListIter<double[]>	iter() Get an iterator to the double[] contents.
int	size() Get the polygon length.
int	testClockwise() Test polygon orientation.
java.lang.String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

points

private java.util.List<double[]> points

The actual points

min

private double[] min

Minimum values

max

private double[] max

Maximum values

Constructor Detail

Polygon

public Polygon(java.util.List<double[]> points)

Constructor.

Parameters:

points - Polygon points

Polygon

public Polygon(java.util.List<double[]> points,
               double minx,
               double maxx,
               double miny,
               double maxy)

Constructor.

Parameters:

points - Polygon points

minx - Minimum x value

maxx - Maximum x value

miny - Minimum y value

maxy - Maximum y value

Method Detail

iter

public ArrayListIter<double[]> iter()

Get an iterator to the double[] contents.

Returns:

Iterator

appendToBuffer

public java.lang.StringBuilder appendToBuffer(java.lang.StringBuilder buf)

Append the polygon to the buffer.

Parameters:

buf - Buffer to append to

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

size

public int size()

Get the polygon length.

Returns:

Polygon length

get

public double[] get(int idx)

Get a double[] by index.

Parameters:

idx - Index to get

Returns:

double[]

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 0 ≤ 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 0 ≤ 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(double[] 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.

areaShoelace

public double areaShoelace()

Compute the polygon area (geometric, not geographic) using the Shoelace formula. This is appropriate for simple polygons in the cartesian plane only.

Returns:

Area