Polygon class. More...

#include <rpolygon.h>

Inheritance diagram for RPolygon:
[legend]
Collaboration diagram for RPolygon:
[legend]

Public Member Functions

 RPolygon (void)
 
 RPolygon (size_t nb,...)
 
 RPolygon (const RPolygon &poly)
 
int Compare (const RPolygon &poly) const
 
size_t GetNbVertices (void) const
 
R::RCursor< RPointGetVertices (void) const
 
void GetEdges (RContainer< RLine, true, false > &edges) const
 
const RPointoperator[] (size_t idx) const
 
RPointoperator[] (size_t idx)
 
void Clear (void)
 
void InsertVertex (tCoord x, tCoord y)
 
void InsertVertex (const RPoint &pt)
 
void InsertVertex (RPoint *pt)
 
void DeleteVertex (RPoint *pt)
 
RPolygonoperator= (const RPolygon &poly)
 
bool operator== (const RPolygon &poly) const
 
bool operator!= (const RPolygon &poly) const
 
RPolygonoperator+= (const RPoint &pt)
 
RPolygonoperator-= (const RPoint &pt)
 
RPoint GetConX (const RPoint &pt) const
 
RPoint GetConY (const RPoint &pt) const
 
RPoint GetBottomLeft (void) const
 
size_t GetBottomLeftIndex (void) const
 
RPointGetBottomLeft (const tCoord minx, const tCoord miny, const tCoord maxx) const
 
RPointGetLeftBottom (void) const
 
RPointGetLeftBottom (const tCoord minx, const tCoord miny, const tCoord maxy) const
 
RPoint GetTopRight (void) const
 
size_t GetTopRightIndex (void) const
 
RPointGetTopRight (const tCoord minx, const tCoord miny, const tCoord maxx) const
 
RPointGetRightTop (void) const
 
RPointGetRightTop (const tCoord minx, const tCoord miny, const tCoord maxy) const
 
bool IsVertex (const tCoord x, const tCoord y) const
 
bool IsVertex (const RPoint &pt) const
 
bool IsOnEdge (const tCoord x, const tCoord y) const
 
bool IsOnEdge (const RPoint &pt) const
 
bool IsOnEdge (const RPoint &pt1, const RPoint &pt2) const
 
bool IsIn (const RPoint &pt, bool overlap=true) const
 
bool IsIn (const tCoord x, const tCoord y, bool overlap=true) const
 
bool IsIn (const RPolygon &poly, bool overlap=true) const
 
size_t GetNbInter (const RLine &line) const
 
bool IsIn (const RLine &line, bool overlap=true) const
 
bool Contained (const RRect &rect) const
 
tCoord Area (void) const
 
void EdgeDecomposition (RContainer< RLine, true, false > &edges, RRect &outside) const
 
void ExternalBoundary (RRect &rect) const
 
void ChangeOrientation (const tOrientation o)
 
void RectDecomposition (RContainer< RRect, true, false > &rects) const
 
void Rectangularize (double loss)
 
void GetEdges (RContainer< RPoint, true, false > &points) const
 
bool IsClockwise (void) const
 
void ReOrder (void)
 
void ReValid (double t=0.0)
 
bool DuplicateVertices (void) const
 
RPoint GetCentralPoint (void)
 
void Save (RTextFile &f)
 
RPoint Calibrate (void)
 
bool IsRect (void) const
 
bool IsRectangular (void) const
 
bool IsSquare (void) const
 

Private Member Functions

size_t AddAfterVerifyEdge (RPoint *edge, size_t &pos, size_t nbedges)
 
- Private Member Functions inherited from RContainer< RPoint, true, false >
 RContainer (size_t m, size_t i=0)
 
 RContainer (const RContainer< RPoint, true, bOrder > &src)
 
 RContainer (const RContainer< RPoint, false, bOrder > &src)
 
int Compare (const RContainer< RPoint, bAlloc, bOrder > &) const
 
size_t GetNb (void) const
 
size_t GetMaxPos (void) const
 
size_t GetMaxNb (void) const
 
size_t GetIncNb (void) const
 
bool VerifyIndex (size_t idx) const
 
void VerifyTab (size_t max=0)
 
void Clear (size_t m=0, size_t i=0, bool force=false)
 
void ReOrder (int sortOrder(const void *, const void *), size_t min, size_t max)
 
void ReOrder (int sortOrder(const void *, const void *))
 
void ReOrder (void)
 
void Exchange (size_t pos1, size_t pos2)
 
void Shift (size_t idx, bool reverse)
 
void Transfer (RContainer< RPoint, a, o > &src)
 
RContaineroperator= (const RContainer< RPoint, true, bOrder > &src)
 
RContaineroperator= (const RContainer< RPoint, false, bOrder > &src)
 
void Copy (const RContainer< RPoint, a, bOrder > &src)
 
RContaineroperator+= (const RContainer< RPoint, a, o > &src)
 
size_t GetIndex (const TUse &tag, bool &find, size_t min=0, size_t max=0) const
 
bool IsIn (const TUse &tag, bool sortkey, size_t min=0, size_t max=0) const
 
bool IsIn (const TUse &tag, size_t min=0, size_t max=0) const
 
const RPointoperator[] (size_t idx) const
 
RPointoperator[] (size_t idx)
 
const RPointGetPtrAt (size_t idx) const
 
RPointGetPtrAt (size_t idx)
 
RPointGetPtr (const TUse &tag, bool sortkey, size_t min=0, size_t max=0) const
 
RPointGetPtr (const TUse &tag, size_t min=0, size_t max=0) const
 
RPointGetInsertPtr (const TUse &tag, bool sortkey, size_t min=0, size_t max=0)
 
RPointGetInsertPtr (const TUse &tag, size_t min=0, size_t max=0)
 
RPointGetInsertPtrAt (const TUse &tag, size_t pos)
 
RContainer< RPoint, false,
bOrder > * 
GetPtrs (const TUse &tag, size_t min=0, size_t max=0) const
 
size_t GetTab (const void **tab, size_t min=0, size_t max=0) const
 
size_t GetTab (void **tab, size_t min=0, size_t max=0)
 
size_t GetTab (const RPoint **tab, size_t min=0, size_t max=0) const
 
size_t GetTab (RPoint **tab, size_t min=0, size_t max=0)
 
void InsertPtrAt (RPoint *ins, size_t pos, bool del)
 
void InsertPtrAt (RPoint *ins, size_t pos)
 
void InsertPtr (RPoint *ins, bool del=false, size_t min=0, size_t max=0)
 
void DeletePtrAt (size_t pos, bool shift, bool del)
 
void DeletePtrAt (size_t pos, bool shift)
 
void DeletePtrAt (size_t pos)
 
void DeletePtr (const TUse &tag, bool sortkey, bool del, size_t min=0, size_t max=0)
 
void DeletePtr (const TUse &tag, bool sortkey, size_t min=0, size_t max=0)
 
void DeletePtr (const TUse &tag, size_t min=0, size_t max=0)
 
void Inter (const iRContainer< RPoint > &src1, const iRContainer< RPoint > &src2)
 
void Union (const iRContainer< RPoint > &src1, const iRContainer< RPoint > &src2)
 
virtual ~RContainer (void)
 
- Private Member Functions inherited from iRContainer< RPoint >
size_t GetNb (void) const
 
size_t GetMaxPos (void) const
 
size_t GetMaxNb (void) const
 
size_t GetIncNb (void) const
 
bool VerifyIndex (size_t idx) const
 
void VerifyTab (size_t max=0)
 
void Clear (size_t m=0, size_t i=0, bool force=false)
 
void ReOrder (int sortOrder(const void *, const void *), size_t min, size_t max)
 
void ReOrder (int sortOrder(const void *, const void *))
 
void ReOrder (void)
 
void Exchange (size_t pos1, size_t pos2)
 
void Shift (size_t idx, bool reverse)
 
void Transfer (iRContainer< RPoint > &src)
 
iRContaineroperator= (const iRContainer< RPoint > &src)
 
void Copy (const iRContainer< RPoint > &src)
 
iRContaineroperator+= (const iRContainer< RPoint > &src)
 
size_t GetIndex (bool order, const TUse &tag, bool &find, size_t min=0, size_t max=0) const
 
size_t GetIndex (const TUse &tag, bool &find, size_t min=0, size_t max=0) const
 
bool IsIn (const TUse &tag, bool sortkey, size_t min=0, size_t max=0) const
 
bool IsIn (const TUse &tag, size_t min=0, size_t max=0) const
 
const RPointoperator[] (size_t idx) const
 
RPointoperator[] (size_t idx)
 
const RPointGetPtrAt (size_t idx) const
 
RPointGetPtrAt (size_t idx)
 
RPointGetPtr (const TUse &tag, bool sortkey, size_t min=0, size_t max=0) const
 
RPointGetPtr (const TUse &tag, size_t min=0, size_t max=0) const
 
RPointGetInsertPtr (const TUse &tag, bool sortkey, size_t min=0, size_t max=0)
 
RPointGetInsertPtr (const TUse &tag, size_t min=0, size_t max=0)
 
RPointGetInsertPtrAt (const TUse &tag, size_t pos)
 
size_t GetTab (const void **tab, size_t min=0, size_t max=0) const
 
size_t GetTab (void **tab, size_t min=0, size_t max=0)
 
size_t GetTab (const RPoint **tab, size_t min=0, size_t max=0) const
 
size_t GetTab (RPoint **tab, size_t min=0, size_t max=0)
 
void InsertPtrAt (RPoint *ins, size_t pos, bool del)
 
void InsertPtrAt (RPoint *ins, size_t pos)
 
void InsertPtr (RPoint *ins, bool del=false, size_t min=0, size_t max=0)
 
void DeletePtrAt (size_t pos, bool shift, bool del)
 
void DeletePtrAt (size_t pos, bool shift)
 
void DeletePtrAt (size_t pos)
 
void DeletePtr (const TUse &tag, bool sortkey, bool del, size_t min=0, size_t max=0)
 
void DeletePtr (const TUse &tag, bool sortkey, size_t min=0, size_t max=0)
 
void DeletePtr (const TUse &tag, size_t min=0, size_t max=0)
 
void Inter (const iRContainer< RPoint > &src1, const iRContainer< RPoint > &src2)
 
void Union (const iRContainer< RPoint > &src1, const iRContainer< RPoint > &src2)
 
virtual ~iRContainer (void)
 
void Create (const iRContainer< RPoint > &src)
 
iRContainerNormalCopy (const iRContainer< RPoint > &src)
 
void DeepCopy (const iRContainer< RPoint > &src)
 
iRContainerAdd (const iRContainer< RPoint > &src)
 

Private Attributes

bool Order
 
bool Rect
 
- Private Attributes inherited from iRContainer< RPoint >
RPoint ** Tab
 
size_t NbPtr
 
size_t MaxPtr
 
size_t LastPtr
 
size_t IncPtr
 

Additional Inherited Members

- Static Private Member Functions inherited from RContainer< RPoint, true, false >
static int SortOrder (const void *a, const void *b)
 
- Static Private Member Functions inherited from iRContainer< RPoint >
static int SortOrder (const void *a, const void *b)
 

Detailed Description

Polygon class.

This class represent a polygon as a set of points regroup in a container. Most of the functions assume that the order of the points in the container must be anti-clockwise. The ReOrder() method does this job, it is automatically called by these functions.

Attention
Currently, some methods work only with rectangular polygons.

Constructor & Destructor Documentation

RPolygon ( void  )

Construct a polygon.

RPolygon ( size_t  nb,
  ... 
)

Construct a polygon with a number of vertices. Each vertex is defined by two coordinates that must be of the type double.

RPolygon Poly(4,12.5,15.5,12.,52.,45.,41.,0.,0.);

Using "12." rather than "12" ensures that the number will be passed as a double and not as an integer.

Parameters
nbNumber of vertices.
...Coordinates of each vertices.
RPolygon ( const RPolygon poly)

Construct a polygon from another.

Parameters
polyPolygon used as reference.

Member Function Documentation

int Compare ( const RPolygon poly) const

This function compares two polygons. This function is used for the class RContainer.

Parameters
polyPolygon used for the comparison.
Returns
  • -1 The left-bottom point of the current polygon is more at the left (at the bottom) of the other one.
  • 0 if there have the same number of points and at the same positions.
  • +1 The left-bottom point of the current polygon is more at the right ( upper) of the other one.
Attention
The polygons are reordered.
size_t GetNbVertices ( void  ) const

Get the number of vertices

Returns
the number of vertices.
R::RCursor<RPoint> GetVertices ( void  ) const

Get a cursor on the vertices of the polygon.

Returns
RPointCursor.
void GetEdges ( RContainer< RLine, true, false > &  edges) const

Put the edges of the polygon in a container. In practice, the container is not cleared.

Parameters
edgesContainer that will contain the edges.
Returns
const RPoint* operator[] ( size_t  idx) const

Get the ith vertex of the polygon (Only read). The operator generates an exception is the index is out of range.

Parameters
idxIndex of the vertex to get.
Returns
Return a point.
RPoint* operator[] ( size_t  idx)

Get the ith vertex of the polygon (Read/Write). The operator generates an exception is the index is out of range.

Parameters
idxIndex of the vertex to get.
Returns
the pointer.
void Clear ( void  )

Clear the polygon.

void InsertVertex ( tCoord  x,
tCoord  y 
)

Insert an vertex into the polygon.

Parameters
xX Position.
yY Position.
void InsertVertex ( const RPoint pt)

Insert an vertex into the polygon. A new RPoint is created and added to the polygon.

Parameters
ptVertex to insert.
void InsertVertex ( RPoint pt)

Insert an vertex into the polygon.

Parameters
ptVertex to insert.
void DeleteVertex ( RPoint pt)

Delete an vertex from the polygon.

Parameters
ptVertex to insert.
RPolygon& operator= ( const RPolygon poly)

The assign operator.

bool operator== ( const RPolygon poly) const

The equal operator.

Attention
The polygons are reordered.
bool operator!= ( const RPolygon poly) const

The non-equal operator.

Attention
The polygons are reordered.
RPolygon& operator+= ( const RPoint pt)

Make a translation of the polygon.

Parameters
ptThe point representing the vector used.
RPolygon& operator-= ( const RPoint pt)

Make a translation of the polygon.

Parameters
ptThe point representing the vector used.
RPoint GetConX ( const RPoint pt) const

This function returns a pointer to the vertex on the same horizontal line. If the polygon is not a rectangular one, such a vertex may not be found.

Parameters
ptPoint used as reference.
Returns
the vertex or an infinitive point (no vertex found).
RPoint GetConY ( const RPoint pt) const

This function returns a pointer to the vertex on the same vertical line. If the polygon is not a rectangular one, such a vertex may not be found.

Parameters
ptPoint used as reference.
Returns
the vertex or an infinitive point (no vertex found).
RPoint GetBottomLeft ( void  ) const

Return a pointer to the most bottom-left vertex of the polygon.

size_t GetBottomLeftIndex ( void  ) const

Get the index of the most bottom-left vertex of the polygon.

RPoint* GetBottomLeft ( const tCoord  minx,
const tCoord  miny,
const tCoord  maxx 
) const

Return a pointer to the most bottom-left vertex of the polygon responding to the criteria.

Parameters
minxMinimal X position of the vertex to search.
minyMinimal Y position of the vertex to search.
maxxMaximal X position of the vertex to search.
RPoint* GetLeftBottom ( void  ) const

Return a pointer to the most left-bottom vertex of the polygon.

RPoint* GetLeftBottom ( const tCoord  minx,
const tCoord  miny,
const tCoord  maxy 
) const

Return a pointer to the most left-bottom vertex of the polygon responding to the criteria.

Parameters
minxMinimal X position of the vertex to search.
minyMinimal Y position of the vertex to search.
maxyMaximal Y position of the vertex to search.
RPoint GetTopRight ( void  ) const

Return a pointer to the most top-right vertex of the polygon.

size_t GetTopRightIndex ( void  ) const

Get the index of the most top-right vertex of the polygon.

RPoint* GetTopRight ( const tCoord  minx,
const tCoord  miny,
const tCoord  maxx 
) const

Return a pointer to the most top-right vertex of the polygon responding to the criteria.

Parameters
minxMinimal X position of the vertex to search.
minyMinimal Y position of the vertex to search.
maxxMaximal X position of the vertex to search.
RPoint* GetRightTop ( void  ) const

Return a pointer to the most top-right vertex of the polygon.

RPoint* GetRightTop ( const tCoord  minx,
const tCoord  miny,
const tCoord  maxy 
) const

Return a pointer to the most top-right vertex of the polygon responding to the criteria.

Parameters
minxMinimal X position of the vertex to search.
minyMinimal Y position of the vertex to search.
maxyMaximal Y position of the vertex to search.
bool IsVertex ( const tCoord  x,
const tCoord  y 
) const

Look if a point is a vertex.

Parameters
xX-coordinate of the point.
yY-coordinate of the point.
Returns
true if it is a vertex.
bool IsVertex ( const RPoint pt) const

Look if the point is a vertex.

Parameters
ptPoint to verify.
Returns
true if it is a vertex.
bool IsOnEdge ( const tCoord  x,
const tCoord  y 
) const

Look if the point is on one of edges of the polygon.

Parameters
xX-coordinate of the point.
yY-coordinate of the point.
Returns
true if the point is inside the polygon.
bool IsOnEdge ( const RPoint pt) const

Look if the point is on one of edges of the polygon.

Parameters
ptPoint to verify.
Returns
true if the point is inside the polygon.
bool IsOnEdge ( const RPoint pt1,
const RPoint pt2 
) const

Look if two points are on the same edge.

Parameters
pt1The first point used.
pt2The second point used.
Returns
true if two points are on the same edge.
bool IsIn ( const RPoint pt,
bool  overlap = true 
) const

Look if the point is inside the polygon.

Parameters
ptPoint to verify.
overlapSpecify if the point can be on one of the edges. By default, it is true.
Returns
true if the point is inside.
bool IsIn ( const tCoord  x,
const tCoord  y,
bool  overlap = true 
) const

Look if the point is inside the polygon.

Parameters
xX-coordinate of the point.
yY-coordinate of the point.
overlapSpecify if the point can be on one of the edges. By default, it is true.
Returns
true if the point is inside.
bool IsIn ( const RPolygon poly,
bool  overlap = true 
) const

Look if a given polygon is contained in the current polygon. The two polygons are supposed to be "rectangular". This function determines if all the vertices of poly are inside the polygon.

Parameters
polyThe polygon to known if is in.
overlapSpecify if the polygon may overlap, i.e. some of its vertices or edges may completely overlap an edge of the other one. By default, it is true.
Returns
true if poly is contained in the polygon.
size_t GetNbInter ( const RLine line) const

Count the number of intersections of a line with the polygon.

Parameters
lineLine to verify.
Returns
the number of intersections with the polygon (a line combined with an edge count for 4).
bool IsIn ( const RLine line,
bool  overlap = true 
) const

Look if a line is inside the polygon.

Parameters
lineLine to verify.
overlapSpecify if the line can be on one of the edges. By default, it is true.
Returns
true if the line is inside.
bool Contained ( const RRect rect) const

Return true if the polygon is inside the rectangle.

Parameters
rectRectangle to known if contains.
tCoord Area ( void  ) const

Compute the area of the polygon.

Returns
the area.
Attention
The polygon is reordered.
void EdgeDecomposition ( RContainer< RLine, true, false > &  edges,
RRect outside 
) const

Compute the edges of the polygon.

Parameters
edgesEdges that compose the polygon. The container is not cleared by the method.
outsideOutside boundary rectangle.
void ExternalBoundary ( RRect rect) const

Compute the external boundary rectangle of the polygon.

Parameters
rectThe rectangle.
void ChangeOrientation ( const tOrientation  o)

Modify the polygon to a certain orientation.

Parameters
oThe orientation.
void RectDecomposition ( RContainer< RRect, true, false > &  rects) const

Decompose the polygon in a container of rectangles. This is only possible for a rectangular polygon.

Parameters
rectsA pointer to the container of rectangles.
Attention
The polygon is reordered.
void Rectangularize ( double  loss)

Transform a polygon in a rectangular one. In practice, each non horizontal or vertical vertex is transform into a set of combinations of a pair of horizontal and vertical vertices.

In the process, there is always a loss of area, but it can be minimised by the parameter.

Parameters
lossLevel of area loss accepted. In practice, it must be a number between 0.01 and 1 (if necessary, the parameter is adapted). The parameter is not global but is verified for each vertex modified. A value of 1 implies the highest possible area loss.
size_t AddAfterVerifyEdge ( RPoint edge,
size_t &  pos,
size_t  nbedges 
)
private

Add a edge at a given position in the polygon. Verify also if the edge before or after must be deleted or not.

Parameters
edgeEdge to add.
posPosition after which the edge must be added. It is incremented or unmodified if the edge was inserted or replace an existing one.
nbedgesNumber of edges actually in the polygon.
Returns
the number of nodes really added (can be 0 or 1).
void GetEdges ( RContainer< RPoint, true, false > &  points) const

Get the edges of the polygon to a container of points.

Parameters
pointsA pointer to the container of points.
bool IsClockwise ( void  ) const

Look if the polygon is clockwise or not.

Returns
true if it is clockwise.
Remarks
The sum of $(x_j-x_i)(y_j+y_i)$ is computed for each edges of vertices $v_i(x_i,y_i)$ and $v_j(x_j,y_j)$. If the result is positive the polygon is clockwise, otherwise it is anticlockwise.
void ReOrder ( void  )

Shift the vertices of the polygon to make the bottom-left point be the first one, and the rest are in the anti-clockwise order.

void ReValid ( double  t = 0.0)

Goes trough the vertices and if two adjacent vertices are closer than a given threshold, the second one is removed.

Parameters
tThreshold.
bool DuplicateVertices ( void  ) const

This function returns when there are duplicate vertices.

RPoint GetCentralPoint ( void  )

Compute a point in the polygon which represents a sort of "Mass Point".

void Save ( RTextFile f)

Save the polygon in a file. The number of vertices is written on the current line and then each vertex on a single line. param f Text file where the information must be written.

RPoint Calibrate ( void  )

Calibrate the polygon, make the bottom-left point at (0,0).

Returns
The translation that has be done.
bool IsRect ( void  ) const
Returns
true if the polygon is a rectangle.
bool IsRectangular ( void  ) const
Returns
true if the polygon is rectangular.
bool IsSquare ( void  ) const
Returns
true if the polygon is a square.

Field Documentation

bool Order
private

Remember if the polygon is reordered.

bool Rect
private

Remember if the polygon is a rectangular one.