mi32/region2d.h

Go to the documentation of this file.

/**
 * \file region2d.h <mi32/region2d.h>
 * \brief Functions and structure for regions
 *
 * \if NODOC
 * $Id: region2d.h_v 1.23 2004/03/30 22:01:29 scowan Exp $
 *
 * $Log: region2d.h_v $
 * Revision 1.23  2004/03/30 22:01:29  scowan
 * Added get numislands method.
 *
 * Revision 1.22  2003/11/28 16:52:25  scowan
 * Added threshold to is equiv to method.
 *
 * Revision 1.21  2003/11/25 00:30:28  scowan
 * Added is equivalent to methods.
 *
 * Revision 1.20  2003/09/26 21:52:25  scowan
 * Added flag to convert legacy region dest to new region.
 *
 * Revision 1.19  2003/09/15 13:49:56  fileserver!dwilliss
 * Doxygen
 *
 * Revision 1.18  2003/09/09 17:56:39  scowan
 * Added another convert to long method.
 *
 * Revision 1.17  2003/08/27 21:31:04  scowan
 * Removed map proj param from assign method.
 *
 * Revision 1.16  2003/06/12 19:45:15  scowan
 * More const.
 *
 * Revision 1.15  2003/06/11 16:03:36  scowan
 * nc.
 *
 * Revision 1.14  2003/06/06 21:34:56  scowan
 * Added methods.
 *
 * Revision 1.13  2003/05/08 22:27:01  scowan
 * Chagned to use a 3d rect.
 *
 * Revision 1.12  2003/05/07 15:26:22  scowan
 * *** empty log message ***
 *
 * Revision 1.11  2003/05/07 15:24:56  scowan
 * Added test and assignment methods.
 *
 * Revision 1.10  2003/04/23 21:59:00  scowan
 * Added methods.
 *
 * Revision 1.9  2002/12/10 18:16:21  scowan
 * Added more friends.
 *
 * Revision 1.8  2002/11/26 21:30:17  dwilliss
 * never mind...
 *
 * Revision 1.7  2002/11/21 18:59:48  dwilliss
 * Added constructor taking MILIST<POLYLINE>&
 *
 * Revision 1.6  2002/11/13 18:22:28  scowan
 * Added begin and end iterators for both classes.
 *
 * Revision 1.5  2002/10/23 16:27:58  scowan
 * Code completed, not tested.
 *
 * Revision 1.4  2002/10/22 22:24:29  scowan
 * Added parameters.
 *
 * Revision 1.3  2002/10/11 21:47:06  scowan
 * Added intersect code.
 *
 * Revision 1.2  2002/10/11 17:07:41  scowan
 * Allowed vector interface class as a friend.
 *
 * Revision 1.1  2002/10/09 22:32:03  scowan
 * Initial revision
 *
 * \endif
**/

#ifndef  INC_MI32_REGION2D_H
#define  INC_MI32_REGION2D_H

#ifndef  INC_MI32_POLYLINE_H
   #include <mi32/polyline.h>
#endif

#ifndef  INC_MI32_RECT_H
   #include <mi32/rect.h>
#endif

#ifndef  INC_MI32_MILIST_H
   #include <mi32/milist.h>
#endif

#ifndef GENERATING_DOXYGEN_OUTPUT
class TRANS2D_AFFINE;      //!< Forward declarations
class TRANS2D_MAPGEN;
struct DREGION;
class REGION2D;
namespace RVC {
   class VECTOR;
   class REGION;
   }
#endif //!< GENERATING_DOXYGEN_OUTPUT

//! SUBREGION2D class - Definitions and methods to support a generic 2D sub-region object in memory.
//! The sub-region can be represented by either a single rectangle or as a polygon and a list of zero
//! or more islands.  The polygon in the sub-region is stored in ORIENTATION_Clockwise and all islands 
//! are stored ORIENTATION_CounterClockwise.

class SUBREGION2D {
   public:
   
      typedef MILIST<POLYLINE>::CONST_ITERATOR CONST_ITERATOR;
   
      //! Default Constructor
      SUBREGION2D (
         );
         
      //! Copy Constructor
      SUBREGION2D (
         const SUBREGION2D& rhs
         );
         
      //! Constructor from DRECT2D
      SUBREGION2D (
         const DRECT2D& rect
         );
         
      //! Destructor
      ~SUBREGION2D (
         );
         
      //! Assignment operator
      SUBREGION2D& operator= (
         const SUBREGION2D& rhs
         );

      //! Assignment operator from rectangle
      SUBREGION2D& operator= (
         const DRECT2D& rhs
         );

      //! Assigns the sub-region to the passed in polygon
      //! This will clear any existing information in 'this'
      ERRVALUE Assign (
         const POLYLINE& Polygon
         );

      //! Assigns the sub-region to the passed in polygon.
      //! A validated polygon is a polygon that does not intersect itself.
      //! This will clear any existing information in 'this'
      void AssignValidated (
         const POLYLINE& Polygon
         );
         
      //! Get the beginning of the list of POLYLINE's.
      //! The first item is the shell polygon, the rest following are islands.
      //! If the sub-region is a rectangle, the list will be empty
      //! @return Iterator to the beginning of the POLYLINE list
      CONST_ITERATOR Begin (
         ) const { return (m_ItemList.Begin()); }

      //! Clear the sub-region
      void Clear (
         );
         
      //! Clip a polyline to a sub-region, call the ClipTarget for each segment
      //! @return TRUE if part of the line is clipped, FALSE if not, < 0 error
      int ClipLine (
         POLYLINE& PolyLine,
         POLYLINE::CLIP& ClipTarget,
         CLIPMODE ClipMode = CLIPMODE_Inside
         ) const;
         
      //! Compute the sub-region area in sub-region units
      double ComputeArea (
         ) const;
   
      //! Compute the sub-region area in sub-region units but do not exclude islands in the calculation
      double ComputeAreaNoIslands (
         ) const;
   
      //! Compute the sub-region perimeter in sub-region units
      double ComputePerimeter (
         ) const;
   
      //! Compute the sub-region perimeter in sub-region units but do not include islands in the calculation
      double ComputePerimeterNoIslands (
         ) const;
   
      //! Translate the sub-region using an affine transformation
      void ConvertForward (
         const TRANS2D_AFFINE& taf
         );
   
      //! Translate the sub-region using a mapgen transformation
      ERRVALUE ConvertForward (
         const TRANS2D_MAPGEN& tmg
         );
   
      //! Translate the sub-region using a mapgen transformation with densification
      //! If the sub-region is the extents only, this will convert it to a polygon sub-region
      //! before doing the transformation
      ERRVALUE ConvertForwardDense (
         const TRANS2D_MAPGEN& tmg
         );
   
      //! Translate the sub-region using an affine transformation
      void ConvertInverse (
         const TRANS2D_AFFINE& taf
         );
   
      //! Translate the sub-region using a mapgen transformation
      ERRVALUE ConvertInverse (
         const TRANS2D_MAPGEN& tmg
         );
   
      //! Translate the sub-region using a mapgen transformation with densification
      //! If the sub-region is the extents only, this will convert it to a polygon sub-region
      //! before doing the transformation
      ERRVALUE ConvertInverseDense (
         const TRANS2D_MAPGEN& tmg
         );
         
      //! Convert subregion from double's to INT32's with rounding, removes duplicate points
      ERRVALUE ConvertToLongRound (
         SIMPLE_ARRAY<LPOLYGON>& PolygonArray,
         SIMPLE_ARRAY<LPOINT2D>& PointArray
         ) const;
   
      //! Get the end of the list of POLYLINE's
      //! @return End of POLYLINE list, see Begin() for details
      CONST_ITERATOR End (
         ) const { return (m_ItemList.End()); }

      //! Get sub-region extents
      //! @return Extents of the sub-region
      const DRECT3D& GetExtents (
         ) const { return (m_Extents); }
   
      //! Get sub-region extents
      //! @return Extents of the sub-region
      const DRECT2D& GetExtents2D (
         ) const { return (m_Extents); }
   
      //! Get number of islands in the sub-region
      //! @return Number of islands in the sub-region
      INT32 GetNumIslands (
         ) const { return (m_ItemList.GetNumItems()-1); }
   
      //! Intersect an specified rectangle area with the sub-region
      //! If the rectangle does not intersect with the sub-region area, 'this' will be set to empty
      ERRVALUE Intersect (
         const DRECT2D& Rect,
         MILIST<SUBREGION2D>& SubRegionList        //!< Filled in if operation creates more than one sub-region
         );

      //! Intersect an specified area against the sub-region
      //! If the polygon does not intersect the sub-region area, 'this' will be set to empty
      //! If the "PolyLine" passed in is invalid, this method will only use one of the 
      //! valid polygons it finds, otherwise the results will be in error.
      ERRVALUE Intersect (
         const POLYLINE& PolyLine,
         MILIST<SUBREGION2D>& SubRegionList        //!< Filled in if operation creates more than one sub-region
         );

      //! Intersect an specified area against the sub-region
      //! If the "SubRegion" does not intersect with the sub-region area, 'this' will be set to empty
      ERRVALUE Intersect (
         const SUBREGION2D& SubRegion,
         MILIST<SUBREGION2D>& SubRegionList        //!< Filled in if operation creates more than one sub-region
         );

      //! Intersect an specified area from the sub-region known to be valid
      //! A validated polygon is a polygon that does not intersect itself.
      //! If the polygon does not intersect the sub-region area, 'this' will be set to empty
      ERRVALUE IntersectValidated (
         const POLYLINE& PolyLine,
         MILIST<SUBREGION2D>& SubRegionList        //!< Filled in if operation creates more than one sub-region
         );
         
      //! Determine if the two subregions are equivalent 
      //! This method uses "Fuzzy" vertex comparisons and the direction and order of the elements are not relevant
      //! Specify a different threshold to allow greater distances
      //! @return 'True' if they are, 'False' if not
      bool IsEquivalentTo (
         const SUBREGION2D& rhs,
         double threshold = 0.0        //!< Default threshold is max absolute value of rectangle coordinate * 1.0E-13
         ) const;
   
      //! Determine if the point falls inside the sub-region
      //! @return 'True' if point is inside the sub-region, 'false' if not
      bool IsPointInside (
         const DPOINT2D& point
         ) const;
   
      //! Is the sub-region an empty sub-region
      bool IsEmpty (
         ) const { return (!m_Extents.IsValid()); }

      //! Is the sub-region a simple rectangle region?         
      bool IsRectangle (
         ) const { return (m_ItemList.GetNumItems() == 0); }

      //! Remove an specified area from the sub-region
      //! If the island removes the entire sub-region area, 'this' will be set to empty
      //! If the "Island" passed in is invalid, this method will only use one of the 
      //! valid polygons it finds, otherwise the results will be in error.
      ERRVALUE Subtract (
         const POLYLINE& Island,
         MILIST<SUBREGION2D>& SubRegionList        //!< Filled in if operation creates more than one sub-region
         );

      //! Remove an specified area from the sub-region
      //! If the "SubRegion" removes the entire sub-region area, 'this' will be set to empty
      ERRVALUE Subtract (
         const SUBREGION2D& SubRegion,
         MILIST<SUBREGION2D>& SubRegionList        //!< Filled in if operation creates more than one sub-region
         );

      //! Remove an specified rectangle area from the sub-region
      //! If the island removes the entire sub-region area, 'this' will be set to empty
      ERRVALUE Subtract (
         const DRECT2D& IslandRect,
         MILIST<SUBREGION2D>& SubRegionList        //!< Filled in if operation creates more than one sub-region
         );

      //! Remove an specified area from the sub-region known to be valid
      //! A validated polygon is a polygon that does not intersect itself.
      //! If the island removes the entire sub-region area, 'this' will be set to empty
      ERRVALUE SubtractValidated (
         const POLYLINE& Island,
         MILIST<SUBREGION2D>& SubRegionList        //!< Filled in if operation creates more than one sub-region
         );
         
      //! Test the line given the test criteria against the sub-region
      //! @return "True" if the line meets the criteria, "false" if not
      bool TestLine (
         const POLYLINE& PolyLine,
         TESTCRITERIA TestCriteria
         ) const;

      //! Test the line against the sub-region
      //! @return POLYLINE::COMPRESULT
      POLYLINE::COMPRESULT TestLine (
         const POLYLINE& PolyLine
         ) const;

      //! Test the point given the test criteria against the sub-region
      //! @return "True" if the point meets the criteria, "false" if not
      bool TestPoint (
         const DPOINT2D& Point,
         TESTCRITERIA TestCriteria
         ) const;

      //! Test the polygon given the test criteria against the sub-region
      //! @return "True" if the polygon meets the criteria, "false" if not
      bool TestPolygon (
         const POLYLINE& PolyLine,
         TESTCRITERIA TestCriteria
         ) const;

      //! Test the polygon against the sub-region
      //! @return POLYLINE::COMPRESULT
      POLYLINE::COMPRESULT TestPolygon (
         const POLYLINE& PolyLine
         ) const;

      //! Test the subregion given the test criteria against 'this'
      //! @return "True" if the subregion meets the criteria, "false" if not
      bool TestSubRegion (
         const SUBREGION2D& SubRegion,
         TESTCRITERIA TestCriteria
         ) const;

      //! Test the subregion against 'this'
      //! @return POLYLINE::COMPRESULT
      POLYLINE::COMPRESULT TestSubRegion (
         const SUBREGION2D& SubRegion
         ) const;

      //! Union (ADD) a rectangle to the sub-region
      ERRVALUE Union (
         const DRECT2D& Rect,
         MILIST<SUBREGION2D>& SubRegionList,       //!< Filled in if operation creates more than one sub-region
         POLYLINE::COMBINERESULT& CombineResult
         );

      //! Union (ADD) a Polygon to the sub-region
      ERRVALUE Union (
         const POLYLINE& PolyLine,
         MILIST<SUBREGION2D>& SubRegionList        //!< Filled in if operation creates more than one sub-region
         );

      //! Union (ADD) a sub-region to the sub-region
      ERRVALUE Union (
         const SUBREGION2D& SubRegion,
         MILIST<SUBREGION2D>& SubRegionList,       //!< Filled in if operation creates more than one sub-region
         POLYLINE::COMBINERESULT& CombineResult
         );

      //! Union (ADD) a polygon to the sub-region
      ERRVALUE UnionValidated (
         const POLYLINE& PolyLine,
         MILIST<SUBREGION2D>& SubRegionList,       //!< Filled in if operation creates more than one sub-region
         POLYLINE::COMBINERESULT& CombineResult
         );
         
   private:
      #ifndef GENERATING_DOXYGEN_OUTPUT
   
      MILIST<POLYLINE> m_ItemList;
      DRECT3D m_Extents;
      
      ERRVALUE UpdateFromShells (MILIST<POLYLINE>& PolyLineList, MILIST<SUBREGION2D>& SubRegionList);
   
      friend class RVC::VECTOR;        //!< For RVC::VECTOR::ReadSubRegion() and RVC::VECTOR::ReadRegion()
      friend class RVC::REGION;        //!< For RVC::REGION::GetRegion() and RVC::REGION::SetRegion()
      friend class REGION2D;           //!< For RVC::REGION::Assign()
      #endif // GENERATING_DOXYGEN_OUTPUT
   };
         

//! REGION2D class - Definitions and methods to support a generic 2D region object in memory.  
//! The region can be represented by either a single rectangle or as a list of sub-regions.

class REGION2D {
   public:

      typedef MILIST<SUBREGION2D>::CONST_ITERATOR CONST_ITERATOR;
      
      //! Default constructor, initializes to an invalid region      
      REGION2D (
         );
   
      //! Copy constructor
      REGION2D (
         const REGION2D& rhs
         );
   
      //! Constructor from DRECT2D
      REGION2D (
         const DRECT2D& rhs
         );
   
      //! Constructor from a list of polylines
      REGION2D (
         const MILIST<POLYLINE>&
         );
   
      //! Destructor
      ~REGION2D (
         );
         
      //! Assignment
      REGION2D& operator= (
         const REGION2D& rhs
         );
         
      //! Assignment
      REGION2D& operator= (
         const DRECT2D& rhs
         );

      //! Assign a legacy region to REGION2D.  Will only assign the Source region part, not the destination
      ERRVALUE Assign (
         const DREGION& region,
         bool UseDest = false
         );
         
      //! Assign from a POLYLINE and an index array defining how the polyline is formatted
      ERRVALUE Assign (
         const POLYLINE& PolyLine,
         const SIMPLE_ARRAY<INT32>& Index       //!< Each entry is the number of points >0 is shell <0 is island
         );
         
      //! Get the beginning of the list of SUBREGION's.
      //! If the region is a rectangle, the list will be empty
      //! @return Iterator to the beginning of the subregion list
      CONST_ITERATOR Begin (
         ) const { return (m_SubList.Begin()); }

      //! Clear the region
      void Clear (
         );
         
      //! Clip a polyline to a region, call the ClipTarget for each segment
      //! @return TRUE if part of the line is clipped, FALSE if not, < 0 error
      int ClipLine (
         POLYLINE& PolyLine,
         POLYLINE::CLIP& ClipTarget,
         CLIPMODE ClipMode = CLIPMODE_Inside
         ) const;
         
      //! Compute the region area in region units
      double ComputeArea (
         ) const;
   
      //! Compute the region area in region units but do not exclude islands in the calculation
      double ComputeAreaNoIslands (
         ) const;
   
      //! Compute the region perimeter in region units
      double ComputePerimeter (
         ) const;
   
      //! Compute the region perimeter in region units but do not include sub-region islands in the calculation
      double ComputePerimeterNoIslands (
         ) const;
   
      //! Translate the region using an affine transformation
      void ConvertForward (
         const TRANS2D_AFFINE& taf
         );
   
      //! Translate the region using a mapgen transformation
      ERRVALUE ConvertForward (
         const TRANS2D_MAPGEN& tmg
         );
   
      //! Translate the region using a mapgen transformation with densification
      //! If the region is the extents only, this will convert it to a proper sub-region
      //! before doing the transformation
      ERRVALUE ConvertForwardDense (
         const TRANS2D_MAPGEN& tmg
         );
   
      //! Translate the region using an affine transformation
      void ConvertInverse (
         const TRANS2D_AFFINE& taf
         );
   
      //! Translate the region using a mapgen transformation
      ERRVALUE ConvertInverse (
         const TRANS2D_MAPGEN& tmg
         );
   
      //! Translate the region using a mapgen transformation with densification
      //! If the region is the extents only, this will convert it to a proper sub-region
      //! before doing the transformation
      ERRVALUE ConvertInverseDense (
         const TRANS2D_MAPGEN& tmg
         );
         
      //! Get the end of the list of SUBREGION's
      //! @return End of SUBREGION list, see Begin() for details
      CONST_ITERATOR End (
         ) const { return (m_SubList.End()); }

      //! Exclusive Union (XOR) RegionB with 'this'
      ERRVALUE ExclusiveUnion (
         const REGION2D& RegionB
         );
         
      //! Exclusive Union (XOR) RegionB with RegionA and place in 'this'
      ERRVALUE ExclusiveUnion (
         const REGION2D& RegionA,
         const REGION2D& RegionB
         );
         
      //! Get region extents
      //! @return Extents of the entire region
      const DRECT3D& GetExtents (
         ) const { return (m_Extents); }
   
      //! Get region extents
      //! @return Extents of the entire region
      const DRECT2D& GetExtents2D (
         ) const { return (m_Extents); }
   
      //! Get number of sub-regions
      //! @return Number of sub-regions
      INT32 GetNumSubRegions (
         ) const;
   
      //! Intersect rectangle with 'this'
      ERRVALUE Intersect (
         const DRECT2D& Rect
         );
         
      //! Intersect a polygon with 'this'
      ERRVALUE Intersect (
         const POLYLINE& PolyLine
         );
         
      //! Intersect a sub-region with 'this'
      ERRVALUE Intersect (
         const SUBREGION2D& SubRegion
         );
         
      //! Intersect RegionB with 'this'
      ERRVALUE Intersect (
         const REGION2D& RegionB
         );
         
      //! Intersect RegionB with RegionA and place in 'this'
      ERRVALUE Intersect (
         const REGION2D& RegionA,
         const REGION2D& RegionB
         );
         
      //! Intersect a validated polygon with 'this'
      ERRVALUE IntersectValidated (
         const POLYLINE& PolyLine
         );
         
      //! Is the region an empty region
      bool IsEmpty (
         ) const { return (!m_Extents.IsValid()); }

      //! Determine if the two regions are equivalent 
      //! This method uses "Fuzzy" vertex comparisons and the direction and order of the elements are not relevant
      //! Specify a different threshold to allow greater distances
      //! @return 'True' if they are, 'False' if not
      bool IsEquivalentTo (
         const REGION2D& rhs,
         double threshold = 0.0        //!< Default threshold is max absolute value of rectangle coordinate * 1.0E-13
         ) const;
   
      //! Determine if the point falls inside the region
      //! @return 'True' if point is inside region, 'false' if not
      bool IsPointInside (
         const DPOINT2D& point
         ) const;
         
      //! Is the region a simple rectangle region?
      bool IsRectangle (
         ) const { return (m_SubList.GetNumItems() == 0); }

      //! Subtract rectangle from 'this'
      ERRVALUE Subtract (
         const DRECT2D& Rect
         );
         
      //! Subtract a polygon from 'this'
      ERRVALUE Subtract (
         const POLYLINE& PolyLine
         );
         
      //! Subtract a sub-region from 'this'
      ERRVALUE Subtract (
         const SUBREGION2D& SubRegion
         );
         
      //! Subtract RegionB from 'this'
      ERRVALUE Subtract (
         const REGION2D& RegionB
         );
         
      //! Subtract RegionB from RegionA and place in 'this'
      ERRVALUE Subtract (
         const REGION2D& RegionA,
         const REGION2D& RegionB
         );
         
      //! Subtract a validated polygon from 'this'
      ERRVALUE SubtractValidated (
         const POLYLINE& PolyLine
         );
         
      //! Test the line given the test criteria against the region
      //! @return "True" if the line meets the criteria, "false" if not
      bool TestLine (
         const POLYLINE& PolyLine,
         TESTCRITERIA TestCriteria
         ) const;

      //! Test the point given the test criteria against the sub-region
      //! @return "True" if the point meets the criteria, "false" if not
      bool TestPoint (
         const DPOINT2D& Point,
         TESTCRITERIA TestCriteria
         ) const;

      //! Test the polygon given the test criteria against the region
      //! @return "True" if the polygon meets the criteria, "false" if not
      bool TestPolygon (
         const POLYLINE& PolyLine,
         TESTCRITERIA TestCriteria
         ) const;

      //! Test the sub-region given the test criteria against the region
      //! @return "True" if the sub-region meets the criteria, "false" if not
      bool TestSubRegion (
         const SUBREGION2D& SubRegion,
         TESTCRITERIA TestCriteria
         ) const;

      //! Union (ADD) rectangle to 'this'
      ERRVALUE Union (
         const DRECT2D& Rect
         );
         
      //! Union (ADD) a polygon to 'this'
      ERRVALUE Union (
         const POLYLINE& PolyLine
         );
         
      //! Union (ADD) a sub-region to the region
      ERRVALUE Union (
         const SUBREGION2D& SubRegion
         );
         
      //! Union (ADD) RegionB to RegionA and place in 'this'
      ERRVALUE Union (
         const REGION2D& RegionA,
         const REGION2D& RegionB
         );
         
      //! Union (ADD) RegionB to 'this'
      ERRVALUE Union (
         const REGION2D& RegionB
         );
         
      //! Union (ADD) a validated polygon to 'this'
      ERRVALUE UnionValidated (
         const POLYLINE& PolyLine
         );
         
   private:
      #ifndef GENERATING_DOXYGEN_OUTPUT
   
      MILIST<SUBREGION2D> m_SubList;
      DRECT3D m_Extents;
      
      void AppendDisjointRegion (const REGION2D& rhs);
      void AppendDisjointSubRegion (const SUBREGION2D& rhs);
   
      class INTERSECTREGION;
      friend class INTERSECTREGION;
      friend class RVC::VECTOR;           //!< For RVC::VECTOR::ReadRegion()
      friend class RVC::REGION;           //!< For RVC::REGION::GetRegion() and RVC::REGION::SetRegion()
      #endif // GENERATING_DOXYGEN_OUTPUT
   };
   
#endif      //!< INC_MI32_REGION2D_H

---