de.unihalle.informatik.MiToBo.core.datatypes
Class MTBPolygon2D

java.lang.Object
  extended by de.unihalle.informatik.Alida.operator.ALDData
      extended by de.unihalle.informatik.MiToBo.core.datatypes.MTBPolygon2D
All Implemented Interfaces:
Cloneable
Direct Known Subclasses:
MTBSnake

@ALDParametrizedClass
public class MTBPolygon2D
extends de.unihalle.informatik.Alida.operator.ALDData
implements Cloneable

Polygon datatype with double precision.

This class re-implements the class Polygon. The main reason for this is the awt-polygons are based on integer points. However, in MiToBo we require double precision in snake calculations.

Each polygon can be of complex or simple nature (i.e. does or does not intersect with itself), can be open or closed and is sorted either counter-clockwise or clockwise. Note that boundary points belongs to the polygon per definition.

The point of the polygon must have positive values for x- and y-coordinates. Negative coordinates can afford an undesirable behavior of some methods.

Note that some of the methods to be found here rely on the GeoLib library. The library is accessed via the wrapper class MTBPolygon2D_GeoPolygonsWrapper.

Author:
moeller, misiak
See Also:
Polygon, MTBPolygon2D_GeoPolygonsWrapper

Field Summary
protected  boolean isClosed
          Indicates if the polygon is closed or not.
protected  Vector<Point2D.Double> points
          List of polygon points.
 
Constructor Summary
MTBPolygon2D()
          Default constructor.
MTBPolygon2D(double[] xp, double[] yp, boolean closed)
          Construct polygon from coordinate arrays.
MTBPolygon2D(Vector<Point2D.Double> ps, boolean closed)
          Construct from point list.
 
Method Summary
 void addPoint(double x, double y)
          Appends a new point to the end of the polygon.
 MTBPolygon2D clone()
           
 boolean contains(double px, double py, int w, int h)
          Determines if a point lies inside a polygon or on its boundary.
 boolean containsPoint(double x, double y)
          Checks if given point lies inside of the polygon.
 void drawPolygon(MTBImage img)
          Draw a polygon into an image (in red color).
 void drawPolygon(MTBImage img, int color)
          Draw a polygon into an image.
 void drawPolygonPoints(MTBImage img)
          Draw polygon points into an image (in red color and as crosses).
 void drawPolygonPoints(MTBImage img, int color, int mode)
          Draw polygon points into an image.
 boolean equals(Object obj)
           
 int[][] getBinaryMask(int w, int h)
          Generates binary mask for inside part of the polygon.
 double[] getBoundingBox()
          Calculates the axes-parallel bounding box of the snake.
 double getLength()
           
 int getPointNum()
          Get the number of points from the polygon.
 Vector<Point2D.Double> getPoints()
          Get polygon points.
 MTBPolygon2D getPolygon()
          Get a Polygon2D copy of this object.
 double getSignedArea()
          Calculates the signed area of simple (!)
 boolean isClosed()
          Returns true if the polygon forms a closed polygon.
 boolean isConvex()
          Check if polygon is convex.
 boolean isOrderedClockwise()
          Check if points are ordered clockwise.
 boolean isOrderedCounterClockwise()
          Check if points are ordered counter-clockwise.
 boolean isSimple()
          Check if polygon is simple, i.e. has no self-overlaps.
 void makeSimple()
          Makes the polygon simple, i.e. removes self-overlaps.
 void resample(double segmentLength)
           Method to re-sample the line segments of the polygon in a range of a given segment length.
 void reversePolypoints()
          Changes the ordering of the polygon points.
 void setClosed()
          Set polygon closed.
 void setOpen()
          Set polygon opened (not closed).
 void setPoints(Vector<Point2D.Double> ps)
          Set all points of the polygon from the specified point vector object.
 void shift(double shiftValue, int imageSizeX, int imageSizeY)
          Method to shift the whole polygon outward (positive value) ore inward (negative value) to its normal vector from every line segment.
 boolean simplify()
          Deprecated. 
 Point2D.Double standardization(Point2D.Double p)
           
 
Methods inherited from class de.unihalle.informatik.Alida.operator.ALDData
cloneProperties, getLocation, getProperty, getPropertyKeys, print, setLocation, setProperty
 
Methods inherited from class java.lang.Object
finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

points

@ALDClassParameter(label="List of points")
protected Vector<Point2D.Double> points
List of polygon points.


isClosed

@ALDClassParameter(label="Polygon is closed")
protected boolean isClosed
Indicates if the polygon is closed or not.

Constructor Detail

MTBPolygon2D

public MTBPolygon2D()
Default constructor.


MTBPolygon2D

public MTBPolygon2D(double[] xp,
                    double[] yp,
                    boolean closed)
Construct polygon from coordinate arrays.

Parameters:
xp - x coordinates of points.
yp - y coordinates of points.
closed - Should be true if polygon is closed.

MTBPolygon2D

public MTBPolygon2D(Vector<Point2D.Double> ps,
                    boolean closed)
Construct from point list.

Parameters:
ps - List with points.
closed - Should be true if polygon is closed.
Method Detail

equals

public boolean equals(Object obj)
Overrides:
equals in class Object

setClosed

public void setClosed()
Set polygon closed.


setOpen

public void setOpen()
Set polygon opened (not closed).


isClosed

public boolean isClosed()
Returns true if the polygon forms a closed polygon.


setPoints

public void setPoints(Vector<Point2D.Double> ps)
Set all points of the polygon from the specified point vector object.

Parameters:
ps - vector with new points of the polygon

getPoints

public Vector<Point2D.Double> getPoints()
Get polygon points.

Returns:
Vector with points.

getPointNum

public int getPointNum()
Get the number of points from the polygon.

Returns:
Number of included points.

clone

public MTBPolygon2D clone()
Overrides:
clone in class Object

getPolygon

public MTBPolygon2D getPolygon()
Get a Polygon2D copy of this object.

Returns:
Copy of this Polygon2D object.

addPoint

public void addPoint(double x,
                     double y)
Appends a new point to the end of the polygon.

Parameters:
x - Point x coordinate.
y - Point y coordinate.

getSignedArea

public double getSignedArea()
Calculates the signed area of simple (!) polygons.

The area is calculated according to the formulas found at

http://www.faqs.org/faqs/graphics/algorithms-faq/,

item 2.01. If the polygon points are ordered counter-clockwise the area will be larger than zero, otherwise smaller.

Note: if the polygon is complex, the result is undetermined! TODO Replace with JNI CGAL function.

Returns:
Signed area of the polygon.

getLength

public double getLength()

getBoundingBox

public double[] getBoundingBox()
Calculates the axes-parallel bounding box of the snake.

The function extracts the coordinates of the upper left and lower right corner of the bounding box of the snake. Note that the there is at least one point of the snake lying on each side of the bounding box, i.e. the snake not just touches the box, but lies on it.

The result array contains the corner coordinates in the following order: [xmin, ymin, xmax, ymax]

Returns:
Coordinates of upper left and lower right corners.

getBinaryMask

public int[][] getBinaryMask(int w,
                             int h)
Generates binary mask for inside part of the polygon. Negative coordinates of the polygon should be avoid.

Parameters:
w - image width
h - image height
Returns:
Binary mask, 0= outside / 1=inside

isOrderedClockwise

public boolean isOrderedClockwise()
Check if points are ordered clockwise.

Returns:
True, if points are ordered clockwise.

isOrderedCounterClockwise

public boolean isOrderedCounterClockwise()
Check if points are ordered counter-clockwise.

Returns:
True, if points are ordered counter-clockwise.

isSimple

public boolean isSimple()
Check if polygon is simple, i.e. has no self-overlaps.

Returns:
True, if polygon is simple.

isConvex

public boolean isConvex()
Check if polygon is convex.

Returns:
True, if polygon is convex.

containsPoint

public boolean containsPoint(double x,
                             double y)
Checks if given point lies inside of the polygon.

Note that the polygons boundary does not belong to the interior.

Parameters:
x - x-coordinate of the point to test.
y - y-coordinate of the point to test.
Returns:
True, if the point lies in the polygon's interior.

reversePolypoints

public void reversePolypoints()
Changes the ordering of the polygon points.

If the polygon points are ordered clockwise afterwards they are ordered counter-clockwise and vice versa.


contains

public boolean contains(double px,
                        double py,
                        int w,
                        int h)
Determines if a point lies inside a polygon or on its boundary.

Use this method only for single point testing. If a couple of points should be tested, use the getBinaryMask method to get the region inside the polygon and test the points whether they are inside (value = 1) or outside (value = 0) the polygon.

Parameters:
px - x coordinate of point to check
py - y coordinate of point to check
w - width of the image where the polygon is included
h - height of the image where the polygon is included
Returns:
True, if point lies on the boundary or inside of the polygon.

makeSimple

public void makeSimple()
Makes the polygon simple, i.e. removes self-overlaps.


simplify

@Deprecated
public boolean simplify()
Deprecated. 

Simplifies the polygon.

Given a polygon with points sorted counter-clockwise any self-intersection is eliminated. Basically, at first all intersections are calculated and then inserted into the point list, which results in a new pointlist including all polygon points and the intersections in between.
In a second step the complete pointlist is traversed counter-clockwise. Non-intersection points are directly added to the simplified polygon. If an intersection point is found, its second counter-part in the list is searched. Then the neighbor of that point with lies left of the current segment is added to the simple polygon and traversal continues in the direction of the recently added point.
The whole procedure stops when the starting point is reached again.

Complexity of the algorithm:
Searching for all intersection points requires to check each segment against each other, yielding a complexity of O(N*N). During pointlist traversal each point of the list is considered maximal once, however, the list is traversed two times in two different directions to make sure that we run in the correct direction on the polygon. Thus, traversal needs O(2*|pointlist|).
Altogether this results in O(N*N + N), i.e. quadratic complexity.

IMPORTANT! It is strongly required that the polygon is sorted counter-clockwise!

Returns:
True, if the simplification procedure was successful.

resample

public void resample(double segmentLength)
 
 Method to re-sample the line segments of the polygon in a range of a given
 segment length. The range is calculated from the given length of a segment
 by calculation: 
 - minimum = segment length * 0.5
 - maximum = segment length * 1.5
 
 If a line segment (p,q) is too small, the point q is removed from the list.
 Then the new line segment (p,r) is observed, where r is the successor of q.
 
 If a line segment (p,q) is too large, new points will be added.
 The number of new points is calculated by the possible number of points
 (depending on the given segment length) that fit into the line segment
 between p and q.
 
 


shift

public void shift(double shiftValue,
                  int imageSizeX,
                  int imageSizeY)
Method to shift the whole polygon outward (positive value) ore inward (negative value) to its normal vector from every line segment.

ATTENTION!!! After shifting a polygon, it can happen that the polygon is not simple !!!

Parameters:
shiftValue - positive ore negative value to shift the polygon
imageSizeX - width of the image to test whether the coordinates of the shifted polygon are valid
imageSizeY - height of the image to test whether the coordinates of the shifted polygon are valid

standardization

public Point2D.Double standardization(Point2D.Double p)

drawPolygon

public void drawPolygon(MTBImage img)
Draw a polygon into an image (in red color).

Parameters:
img - Image where to draw the polygon into.

drawPolygon

public void drawPolygon(MTBImage img,
                        int color)
Draw a polygon into an image.

Parameters:
img - Image where to draw the polygon into.

drawPolygonPoints

public void drawPolygonPoints(MTBImage img)
Draw polygon points into an image (in red color and as crosses).

Parameters:
img - Image where to draw the polygon points into.

drawPolygonPoints

public void drawPolygonPoints(MTBImage img,
                              int color,
                              int mode)
Draw polygon points into an image.

Parameters:
img - Image where to draw the polygon points into.
color - Color to be used.
mode - Shape to be drawn.


Copyright © 2010–2015 Martin Luther University Halle-Wittenberg. All rights reserved.