UTGeometry.h

Go to the documentation of this file.

//==================================================================================================
// Copyright (C) 2010  Brian Tietz    sdbtietz at yahoo dot com
//
// This program is free software; you can redistribute it and/or modify it under the terms of the
// GNU General Public License as published by the Free Software Foundation, version 2.0 of the
// License.
//
// This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without
// even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public License along with this program; if
// not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
// 02110-1301, USA.
//
// For commercial software, the copyright holder (Brian Tietz, email sdbtietz at yahoo dot com)
// reserves the right and is willing to waive the proprietary source code disclosure aspects of that
// license as applied to the UT library in exchange for either substantial contributions to the
// development of the UT library or other forms of compensation.  Any such waiver must be
// established in writing between the copyright holder and the commercial entity obtaining such a
// waiver.
//==================================================================================================


#ifndef _UT_GEOMETRY_H_
#define _UT_GEOMETRY_H_


//==================================================================================================
//=== Project headers
//==================================================================================================
#include "UT.h"
#if __cplusplus
#include "UTLists.h"
#endif


//==================================================================================================
//=== Forward name declarations
//==================================================================================================
#if __cplusplus
class RegionHStripe_t;
class PoolAllocator_t;
#endif


//==================================================================================================
//=== Constants
//==================================================================================================
#define c_pi                                3.1415926535897932384626433832795

#define c_2_pi                              6.2831853071795864769252867665590

#define c_pi_div2                           1.5707963267948966192313216916398

#define c_3_pi_div2                         4.7123889803846898576939650749193

#define c_dbl_abs_min_denominator           1.0e-12

#define c_dbl_abs_min_denominator_squared   1.0e-24

#define c_dbl_abs_min_vh_radial_distance    0.6e-11

#define c_dbl_compare_equality_threshold    0.6e-6


EXTERN_C_BEGIN


//==================================================================================================
struct UT_EXPORT Point_t
//==================================================================================================
{
    float                   x;

    float                   y;

    #if __cplusplus

    inline                  Point_t();

    inline                  Point_t( float x, float y );

    inline                  Point_t(const Point_t& copy);

    inline const Point_t&   operator =(const Point_t& copy);

    bool                    operator ==(const Point_t& other) const;

    bool                    operator !=(const Point_t& other) const;

    inline Point_t          operator +(const Point_t& add) const;

    inline Point_t          operator -(const Point_t& subtract) const;

    inline const Point_t&   operator +=(const Point_t& add);

    inline const Point_t&   operator -=(const Point_t& subtract);

    #endif // __cplusplus
};


//==================================================================================================
struct UT_EXPORT Rect_t
//==================================================================================================
{
    float                   left;

    float                   top;

    float                   right;

    float                   bottom;

    #if __cplusplus
    inline                  Rect_t();

    inline                  Rect_t( float left, float top, float right, float bottom );

    inline                  Rect_t(const Rect_t& copy);

    inline const Rect_t&    operator =(const Rect_t& copy);

    bool                    operator ==(const Rect_t& other) const;

    bool                    operator !=(const Rect_t& other) const;

    inline Rect_t           operator +(const Point_t& add) const;

    inline Rect_t           operator -(const Point_t& subtract) const;

    inline const Rect_t&    operator +=(const Point_t& add);

    inline const Rect_t&    operator -=(const Point_t& subtract);

    bool                    Contains(const Point_t& point) const;

    bool                    Overlapping(const Rect_t& other) const;

    Rect_t                  operator &(const Rect_t& intersect) const;

    const Rect_t&           operator &=(const Rect_t& intersect);

    Rect_t                  operator |(const Rect_t& intersect) const;

    const Rect_t&           operator |=(const Rect_t& intersect);

    inline float            Width() const;

    inline float            Height() const;

    void                    OffsetTo(const Point_t& left_top);

    inline void             InsetBy(float value);

    inline void             InsetBy( float left, float top, float right, float bottom );

    inline void             ExpandBy(float value);

    inline void             ExpandBy( float left, float top, float right, float bottom );

    void                    ExpandToInteger();

    inline Rect_t           OffsetToCopy(const Point_t& left_top) const;

    inline Rect_t           InsetByCopy(float value) const;

    inline Rect_t           InsetByCopy( float left, float top, float right, float bottom ) const;

    inline Rect_t           ExpandByCopy(float value) const;

    inline Rect_t           ExpandByCopy( float left, float top, float right, float bottom ) const;

    inline Point_t          LeftTop() const;

    inline Point_t          RightTop() const;

    inline Point_t          LeftBottom() const;

    inline Point_t          RightBottom() const;

    #endif // __cplusplus
};


EXTERN_C_END

#if __cplusplus


//==================================================================================================
class UT_EXPORT Region_t
//==================================================================================================
{
    //----------------------------------------------------------------------------------------------
    public:
    //----------------------------------------------------------------------------------------------
                    Region_t(bool main_thread_only = false);

                    Region_t( const Rect_t& rect, bool main_thread_only = false );

                    Region_t( const Region_t& copy, bool main_thread_only = false );

                    ~Region_t();

    const Region_t& operator =(const Region_t& copy);

    const Region_t& operator =(const Rect_t& copy);

    const Region_t& operator |=(const Rect_t& rect);

    const Region_t& operator +=(const Rect_t& rect);

    const Region_t& operator -=(const Rect_t& rect);

    const Region_t& operator &=(const Rect_t& rect);

    const Region_t& operator |=(const Region_t& other);

    const Region_t& operator +=(const Region_t& other);

    const Region_t& operator -=(const Region_t& other);

    const Region_t& operator &=(const Region_t& other);

    bool            operator ==(const Region_t& other);

    inline bool     operator !=(const Region_t& other);

    int             CountRects() const;

    inline Rect_t   RectAt(int index) const;

    void            GetRectAt( out Rect_t* rect, int index ) const;

    void            Clear();

    void            Shift(const Point_t& offset);

    bool            Contains(const Point_t& point) const;

    bool            Overlapping(const Rect_t& rect) const;

    inline Rect_t   BoundingBox() const;

    void            GetBoundingBox(out Rect_t* bounding_box) const;

    //----------------------------------------------------------------------------------------------
    private:
    //----------------------------------------------------------------------------------------------
    bool            PrepForStripeOpMainLoop(    const Rect_t& op_rect,
                                                bool add_op_rect,
                                                RegionHStripe_t** existing,
                                                float* merge_y,
                                                bool* any_changes_made );
    void            StripeOpMainLoop(   const Rect_t& op_rect,
                                        bool add_op_rect,
                                        RegionHStripe_t* existing,
                                        float merge_y,
                                        bool any_changes_made );
    void            ConsolidateRows(const Rect_t& op_rect);

    //----------------------------------------------------------------------------------------------
    private:
    //----------------------------------------------------------------------------------------------
    PoolAllocator_t*                    m_allocator;
    BTree_t< RegionHStripe_t, float >   m_stripes;
    mutable int                         m_optimize_num_rects;
    mutable RegionHStripe_t*            m_optimize_rect_at_index_stripe;
    mutable int                         m_optimize_rect_at_index_index;
                                            // Valid only if m_optimize_rect_at_index_stripe is not
                                            // NULL
};


//==================================================================================================
class UT_EXPORT Polygon_t
//==================================================================================================
{
    //----------------------------------------------------------------------------------------------
    public:
    //----------------------------------------------------------------------------------------------
    inline                  Polygon_t();

                            Polygon_t( const Point_t* vertices, int num_vertices );

                            Polygon_t(const Rect_t& rect);

                            Polygon_t(const Polygon_t& polygon);

    inline void             AddVertex(const Point_t& vertex);

    inline void             InsertVertex( const Point_t& vertex, int index );

    inline void             RemoveVertex(int index);

    inline void             ReplaceVertex( int index, const Point_t& vertex );

    inline int              CountVertices() const;

    inline void             Clear();

    inline const Point_t&   VertexAt(int index) const;

    const Polygon_t&        operator =(const Polygon_t& copy);

    const Polygon_t&        operator =(const Rect_t& rect);

    void                    Shift(const Point_t& offset);

    bool                    Contains(const Point_t& point) const;

    bool                    Overlapping(const Rect_t& rect) const;

    inline Rect_t           BoundingBox() const;

    void                    GetBoundingBox(out Rect_t* bounding_box) const;

    void                    FindClosestPoint(   const Point_t& from,
                                                out Point_t* closest_point_on_polygon,
                                                out int* after_index,
                                                bool on_edge_if_inside ) const;

    void                    RotateAbout( double radians, const Point_t& point );

    //----------------------------------------------------------------------------------------------
    private:
    //----------------------------------------------------------------------------------------------
    Array_t<Point_t>        m_vertices;
    Point_t                 m_builtin_points[4];
    int                     m_num_vertices;
};


#endif // __cplusplus

EXTERN_C_BEGIN


//==================================================================================================
struct UT_EXPORT Circle_t
//==================================================================================================
{
    Point_t                 center;

    double                  radius;

    #if __cplusplus
    inline                  Circle_t();

    inline                  Circle_t( const Point_t& center, double radius );

    inline                  Circle_t(const Circle_t& copy);

    inline void             Set( const Point_t& center, double radius );

    inline const Circle_t&  operator =(const Circle_t& copy);

    inline Circle_t         operator +(const Point_t& add) const;

    inline Circle_t         operator -(const Point_t& subtract) const;

    inline const Circle_t&  operator +=(const Point_t& add);

    inline const Circle_t&  operator -=(const Point_t& subtract);

    bool                    Contains(const Point_t& point) const;

    bool                    Overlapping(const Rect_t& rect) const;

    inline Rect_t           BoundingBox() const;

    inline void             GetBoundingBox(out Rect_t* bounding_box) const;

    int                     FindXIntercepts(    float y,
                                                out float* x,
                                                out double* radian = NULL,
                                                out double* slope = NULL ) const;

    int                     FindYIntercepts(    float x,
                                                out float* y,
                                                out double* radian = NULL,
                                                out double* slope = NULL ) const;

    void                    FindClosestPoint(   const Point_t& from,
                                                bool on_edge_if_inside,
                                                out Point_t* closest_point_on_circle,
                                                out double* radian = NULL,
                                                out double* slope = NULL ) const;
    #endif // __cplusplus
};


EXTERN_C_END

#if __cplusplus


//==================================================================================================
class UT_EXPORT Ellipse_t
//==================================================================================================
{
    //----------------------------------------------------------------------------------------------
    public:
    //----------------------------------------------------------------------------------------------
    inline                  Ellipse_t();

                            Ellipse_t(  const Point_t& center,
                                        float width,
                                        float height,
                                        double rotation );

                            Ellipse_t(const Ellipse_t& copy);

    void                    Set(    const Point_t& center,
                                    float width,
                                    float height,
                                    double rotation );

    inline Point_t          Center() const;

    inline void             GetCenter(out Point_t* center) const;

    inline float            Width() const;

    inline float            Height() const;

    inline double           Rotation() const;

    const Ellipse_t&        operator =(const Ellipse_t& copy);

    inline Ellipse_t        operator +(const Point_t& add) const;

    inline Ellipse_t        operator -(const Point_t& subtract) const;

    inline const Ellipse_t& operator +=(const Point_t& add);

    inline const Ellipse_t& operator -=(const Point_t& subtract);

    bool                    Contains(const Point_t& point) const;

    bool                    Overlapping(const Rect_t& rect) const;

    inline Rect_t           BoundingBox() const;

    void                    GetBoundingBox( out Rect_t* bounding_box,
                                            out double* t_left = NULL,
                                            out double* t_top = NULL,
                                            out double* t_right = NULL,
                                            out double* t_bottom = NULL ) const;

    void                    GetPointAndSlopeAtT(    double t,
                                                    out Point_t* point_on_ellipse,
                                                    out double* slope = NULL ) const;

    int                     FindXIntercepts(    float y,
                                                out float* x,
                                                out double* t = NULL,
                                                out double* slope = NULL ) const;

    int                     FindYIntercepts(    float x,
                                                out float* y,
                                                out double* t = NULL,
                                                out double* slope = NULL ) const;

    void                    FindClosestPoint(   const Point_t& from,
                                                bool on_edge_if_inside,
                                                out Point_t* closest_point_on_ellipse,
                                                out double* t = NULL,
                                                out double* slope = NULL ) const;

    void                    Rotate(double radians);

    void                    RotateAbout( double radians, const Point_t& point );

    //----------------------------------------------------------------------------------------------
    private:
    //----------------------------------------------------------------------------------------------
    void                PrecalculateValues();
    int                 FindUnrotatedXIntercepts(   float y,
                                                    out float* x,
                                                    out double* t ,
                                                    out double* slope ) const;
    int                 Find90DegreeRotatedXIntercepts( float y,
                                                        out float* x,
                                                        out double* t,
                                                        out double* slope ) const;
    int                 FindRotatedNoWidthXIntercepts(  float y,
                                                        out float* x,
                                                        out double* t,
                                                        out double* slope ) const;
    int                 FindRotatedNoHeightXIntercepts( float y,
                                                        out float* x,
                                                        out double* t,
                                                        out double* slope ) const;

    int                 FindUnrotatedYIntercepts(   float x,
                                                    out float* y,
                                                    out double* t ,
                                                    out double* slope ) const;
    int                 Find90DegreeRotatedYIntercepts( float x,
                                                        out float* y,
                                                        out double* t,
                                                        out double* slope ) const;
    int                 FindRotatedNoWidthYIntercepts(  float x,
                                                        out float* y,
                                                        out double* t,
                                                        out double* slope ) const;
    int                 FindRotatedNoHeightYIntercepts( float x,
                                                        out float* y,
                                                        out double* t,
                                                        out double* slope ) const;

    void                FindClosestPointNoWidth(    double point_x,
                                                    double point_y,
                                                    out Point_t* closest_point_on_ellipse,
                                                    out double* t,
                                                    out double* slope ) const;
    void                FindClosestPointNoHeight(   double point_x,
                                                    double point_y,
                                                    out Point_t* closest_point_on_ellipse,
                                                    out double* t,
                                                    out double* slope ) const;

    //----------------------------------------------------------------------------------------------
    private:
    //----------------------------------------------------------------------------------------------
    Point_t             m_center;
    float               m_half_width;
    float               m_half_height;
    double              m_rotation;

    // Pre-calculated values:
    bool                m_rotated;
    uint8               m_rotated_90_degree_increments;
    double              m_sin_rotation;
    double              m_cos_rotation;
};


EXTERN_C_BEGIN
#endif // __cplusplus


//==================================================================================================
//=== Utility functions
//==================================================================================================

extern UT_EXPORT void expand_to_integer( float* value, bool expand_to_lower_number );

extern UT_EXPORT bool find_line_intercept(  const Point_t* line_a_from,
                                            const Point_t* line_a_to,
                                            const Point_t* line_b_from,
                                            const Point_t* line_b_to,
                                            out Point_t* intercept,
                                            bool only_if_line_segments_intercept );

#if __cplusplus
EXTERN_C_END

inline bool find_line_intercept(    const Point_t& line_a_from,
                                    const Point_t& line_a_to,
                                    const Point_t& line_b_from,
                                    const Point_t& line_b_to,
                                    out Point_t* intercept,
                                    bool only_if_line_segments_intercept = true );

EXTERN_C_BEGIN
#endif // __cplusplus

extern UT_EXPORT bool find_slope_intercept( const Point_t* line_a_from,
                                            double line_a_slope,
                                            const Point_t* line_b_from,
                                            double line_b_slope,
                                            out Point_t* intercept );

#if __cplusplus
EXTERN_C_END

inline bool find_slope_intercept(   const Point_t& line_a_from,
                                    double line_a_slope,
                                    const Point_t& line_b_from,
                                    double line_b_slope,
                                    out Point_t* intercept );

EXTERN_C_BEGIN
#endif // __cplusplus

extern UT_EXPORT bool find_line_x_intercept(    const Point_t* line_a_from,
                                                const Point_t* line_a_to,
                                                const Point_t* line_b_from,
                                                const Point_t* line_b_to,
                                                out float* x_intercept,
                                                bool only_if_line_segments_intercept );

#if __cplusplus
EXTERN_C_END

inline bool find_line_x_intercept(  const Point_t& line_a_from,
                                    const Point_t& line_a_to,
                                    const Point_t& line_b_from,
                                    const Point_t& line_b_to,
                                    out float* x_intercept,
                                    bool only_if_line_segments_intercept = true );

EXTERN_C_BEGIN
#endif // __cplusplus

extern UT_EXPORT bool find_slope_x_intercept(   const Point_t* line_a_from,
                                                double line_a_slope,
                                                const Point_t* line_b_from,
                                                double line_b_slope,
                                                out float* x_intercept );

#if __cplusplus
EXTERN_C_END

inline bool find_slope_x_intercept( const Point_t& line_a_from,
                                    double line_a_slope,
                                    const Point_t& line_b_from,
                                    double line_b_slope,
                                    out float* x_intercept );

EXTERN_C_BEGIN
#endif // __cplusplus

extern UT_EXPORT bool find_line_y_intercept(    const Point_t* line_a_from,
                                                const Point_t* line_a_to,
                                                const Point_t* line_b_from,
                                                const Point_t* line_b_to,
                                                out float* y_intercept,
                                                bool only_if_line_segments_intercept );

#if __cplusplus
EXTERN_C_END

inline bool find_line_y_intercept(  const Point_t& line_a_from,
                                    const Point_t& line_a_to,
                                    const Point_t& line_b_from,
                                    const Point_t& line_b_to,
                                    out float* y_intercept,
                                    bool only_if_line_segments_intercept = true );

EXTERN_C_BEGIN
#endif // __cplusplus

extern UT_EXPORT bool find_slope_y_intercept(   const Point_t* line_a_from,
                                                double line_a_slope,
                                                const Point_t* line_b_from,
                                                double line_b_slope,
                                                out float* y_intercept );

#if __cplusplus
EXTERN_C_END

inline bool find_slope_y_intercept( const Point_t& line_a_from,
                                    double line_a_slope,
                                    const Point_t& line_b_from,
                                    double line_b_slope,
                                    out float* y_intercept );

EXTERN_C_BEGIN
#endif // __cplusplus

extern UT_EXPORT void normalize_radians(double* radian);

#if __cplusplus
EXTERN_C_END




//==================================================================================================
//==================================================================================================
//===
//=== Inline function implementations: utility functions
//===
//==================================================================================================
//==================================================================================================
inline bool
find_line_intercept(    const Point_t& line_a_from,
                        const Point_t& line_a_to,
                        const Point_t& line_b_from,
                        const Point_t& line_b_to,
                        out Point_t* intercept,
                        bool only_if_line_segments_intercept )
{
    return find_line_intercept( &line_a_from,
                                &line_a_to,
                                &line_b_from,
                                &line_b_to,
                                intercept,
                                only_if_line_segments_intercept );
}


inline bool
find_slope_intercept(   const Point_t& line_a_from,
                        double line_a_slope,
                        const Point_t& line_b_from,
                        double line_b_slope,
                        out Point_t* intercept )
{
    return find_slope_intercept(    &line_a_from,
                                    line_a_slope,
                                    &line_b_from,
                                    line_b_slope,
                                    intercept );
}


inline bool
find_line_x_intercept(  const Point_t& line_a_from,
                        const Point_t& line_a_to,
                        const Point_t& line_b_from,
                        const Point_t& line_b_to,
                        out float* x_intercept,
                        bool only_if_line_segments_intercept )
{
    return find_line_x_intercept(   &line_a_from,
                                    &line_a_to,
                                    &line_b_from,
                                    &line_b_to,
                                    x_intercept,
                                    only_if_line_segments_intercept );
}


inline bool
find_slope_x_intercept( const Point_t& line_a_from,
                        double line_a_slope,
                        const Point_t& line_b_from,
                        double line_b_slope,
                        out float* x_intercept )
{
    return find_slope_x_intercept(  &line_a_from,
                                    line_a_slope,
                                    &line_b_from,
                                    line_b_slope,
                                    x_intercept );
}


inline bool
find_line_y_intercept(  const Point_t& line_a_from,
                        const Point_t& line_a_to,
                        const Point_t& line_b_from,
                        const Point_t& line_b_to,
                        out float* y_intercept,
                        bool only_if_line_segments_intercept )
{
    return find_line_y_intercept(   &line_a_from,
                                    &line_a_to,
                                    &line_b_from,
                                    &line_b_to,
                                    y_intercept,
                                    only_if_line_segments_intercept );
}


inline bool
find_slope_y_intercept( const Point_t& line_a_from,
                        double line_a_slope,
                        const Point_t& line_b_from,
                        double line_b_slope,
                        out float* y_intercept )
{
    return find_slope_y_intercept(  &line_a_from,
                                line_a_slope,
                                &line_b_from,
                                line_b_slope,
                                y_intercept );
}




//==================================================================================================
//==================================================================================================
//===
//=== Inline function implementations: struct Point_t
//===
//==================================================================================================
//==================================================================================================
inline
Point_t::Point_t()
{
    // Constructor for an uninitialized point, just to make the compiler happy (not actually
    // initialized).
}


inline
Point_t::Point_t( float a_x, float a_y )
{
    x = a_x;
    y = a_y;
}


inline
Point_t::Point_t(const Point_t& copy)
{
    x = copy.x;
    y = copy.y;
}


inline const Point_t&
Point_t::operator =(const Point_t& copy)
{
    x = copy.x;
    y = copy.y;
    return *this;
}


inline Point_t
Point_t::operator +(const Point_t& add) const
{
    return Point_t( x+add.x, y+add.y );
}


inline Point_t
Point_t::operator -(const Point_t& subtract) const
{
    return Point_t( x-subtract.x, y-subtract.y );
}


inline const Point_t&
Point_t::operator +=(const Point_t& add)
{
    x += add.x;
    y += add.y;
    return *this;
}


inline const Point_t&
Point_t::operator -=(const Point_t& subtract)
{
    x -= subtract.x;
    y -= subtract.y;
    return *this;
}




//==================================================================================================
//==================================================================================================
//===
//=== Inline function implementations: struct Rect_t
//===
//==================================================================================================
//==================================================================================================
inline
Rect_t::Rect_t()
{
    // Constructor for an uninitialized rectangle, just to make the compiler happy.
}


inline
Rect_t::Rect_t( float a_left, float a_top, float a_right, float a_bottom )
{
    left = a_left;
    top = a_top;
    right = a_right;
    bottom = a_bottom;
}


inline
Rect_t::Rect_t(const Rect_t& copy)
{
    left = copy.left;
    top = copy.top;
    right = copy.right;
    bottom = copy.bottom;
}


inline const Rect_t&
Rect_t::operator =(const Rect_t& copy)
{
    left = copy.left;
    top = copy.top;
    right = copy.right;
    bottom = copy.bottom;
    return *this;
}


inline Rect_t
Rect_t::operator +(const Point_t& add) const
{
    return Rect_t( left+add.x, top+add.y, right+add.x, bottom+add.y );
}


inline Rect_t
Rect_t::operator -(const Point_t& subtract) const
{
    return Rect_t( left-subtract.x, top-subtract.y, right-subtract.x, bottom-subtract.y );
}


inline const Rect_t&
Rect_t::operator +=(const Point_t& add)
{
    left += add.x;
    right += add.x;
    top += add.y;
    bottom += add.y;
    return *this;
}


inline const Rect_t&
Rect_t::operator -=(const Point_t& subtract)
{
    left -= subtract.x;
    right -= subtract.x;
    top -= subtract.y;
    bottom -= subtract.y;
    return *this;
}


inline float
Rect_t::Width() const
{
    return right - left;
}


inline float
Rect_t::Height() const
{
    return bottom - top;
}


inline void
Rect_t::InsetBy(float value)
{
    left += value;
    top += value;
    right -= value;
    bottom -= value;
}


inline void
Rect_t::InsetBy( float d_left, float d_top, float d_right, float d_bottom )
{
    left += d_left;
    top += d_top;
    right -= d_right;
    bottom -= d_bottom;
}


inline void
Rect_t::ExpandBy(float value)
{
    left -= value;
    top -= value;
    right += value;
    bottom += value;
}


inline void
Rect_t::ExpandBy( float d_left, float d_top, float d_right, float d_bottom )
{
    left -= d_left;
    top -= d_top;
    right += d_right;
    bottom += d_bottom;
}


inline Rect_t
Rect_t::OffsetToCopy(const Point_t& left_top) const
{
    Rect_t offset = *this;
    offset.OffsetTo(left_top);
    return offset;
}


inline Rect_t
Rect_t::InsetByCopy(float value) const
{
    return Rect_t( left+value, top+value, right-value, bottom-value );
}


inline Rect_t
Rect_t::InsetByCopy( float d_left, float d_top, float d_right, float d_bottom ) const
{
    return Rect_t( left+d_left, top+d_top, right-d_right, bottom-d_bottom );
}


inline Rect_t
Rect_t::ExpandByCopy(float value) const
{
    return Rect_t( left-value, top-value, right+value, bottom+value );
}


inline Rect_t
Rect_t::ExpandByCopy( float d_left, float d_top, float d_right, float d_bottom ) const
{
    return Rect_t( left-d_left, top-d_top, right+d_right, bottom+d_bottom );
}


inline Point_t
Rect_t::LeftTop() const
{
    return Point_t( left, top );
}


inline Point_t
Rect_t::RightTop() const
{
    return Point_t( right, top );
}


inline Point_t
Rect_t::LeftBottom() const
{
    return Point_t( left, bottom );
}


inline Point_t
Rect_t::RightBottom() const
{
    return Point_t( right, bottom );
}




//==================================================================================================
//==================================================================================================
//===
//=== Inline function implementations: class Region_t
//===
//==================================================================================================
//==================================================================================================
inline bool
Region_t::operator !=(const Region_t& other)
{
    return !(*this == other);
}


inline Rect_t
Region_t::RectAt(int index) const
{
    Rect_t rect;
    GetRectAt( &rect, index );
    return rect;
}


inline Rect_t
Region_t::BoundingBox() const
{
    Rect_t rect;
    GetBoundingBox(&rect);
    return rect;
}




//==================================================================================================
//==================================================================================================
//===
//=== Inline function implementations: class Polygon_t
//===
//==================================================================================================
//==================================================================================================
inline
Polygon_t::Polygon_t()
{
    m_vertices.InstallStackBuffer( m_builtin_points, 4 );
}


inline void
Polygon_t::AddVertex(const Point_t& vertex)
{
    m_vertices += vertex;
}


inline void
Polygon_t::InsertVertex( const Point_t& vertex, int index )
{
    m_vertices.AddItemAt( vertex, index );
}


inline void
Polygon_t::ReplaceVertex( int index, const Point_t& vertex )
{
    m_vertices[index] = vertex;
}


inline void
Polygon_t::RemoveVertex(int index)
{
    m_vertices.RemoveItemAt(index);
}


inline int
Polygon_t::CountVertices() const
{
    return m_vertices.CountItems();
}


inline void
Polygon_t::Clear()
{
    m_vertices.SetNumValidItems(0);
}


inline const Point_t&
Polygon_t::VertexAt(int index) const
{
    assert( index < m_vertices.CountItems() );
    return m_vertices[index];
}


inline Rect_t
Polygon_t::BoundingBox() const
{
    Rect_t bounding_box;
    GetBoundingBox(&bounding_box);
    return bounding_box;
}




//==================================================================================================
//==================================================================================================
//===
//=== Inline function implementations: struct Circle_t
//===
//==================================================================================================
//==================================================================================================
inline
Circle_t::Circle_t()
{
    // Constructor for an uninitialized circle, just to make the compiler happy.
}


inline
Circle_t::Circle_t( const Point_t& a_center, double a_radius )
{
    center = a_center;
    radius = a_radius;
}


inline
Circle_t::Circle_t(const Circle_t& copy)
{
    center = copy.center;
    radius = copy.radius;
}


inline void
Circle_t::Set( const Point_t& a_center, double a_radius )
{
    center = a_center;
    radius = a_radius;
}


inline const Circle_t&
Circle_t::operator =(const Circle_t& copy)
{
    center = copy.center;
    radius = copy.radius;
    return *this;
}


inline Circle_t
Circle_t::operator +(const Point_t& add) const
{
    return Circle_t( center + add, radius );
}


inline Circle_t
Circle_t::operator -(const Point_t& subtract) const
{
    return Circle_t( center - subtract, radius );
}


inline const Circle_t&
Circle_t::operator +=(const Point_t& add)
{
    center += add;
    return *this;
}


inline const Circle_t&
Circle_t::operator -=(const Point_t& subtract)
{
    center -= subtract;
    return *this;
}


inline Rect_t
Circle_t::BoundingBox() const
{
    return Rect_t(  center.x-static_cast<float>(radius),
                    center.y-static_cast<float>(radius),
                    center.x+static_cast<float>(radius),
                    center.y+static_cast<float>(radius) );
}


inline void
Circle_t::GetBoundingBox(out Rect_t* bounding_box) const
{
    bounding_box->left = center.x-static_cast<float>(radius);
    bounding_box->top = center.y-static_cast<float>(radius);
    bounding_box->right = center.x+static_cast<float>(radius);
    bounding_box->bottom = center.y+static_cast<float>(radius);
}




//==================================================================================================
//==================================================================================================
//===
//=== Inline function implementations: class Ellipse_t
//===
//==================================================================================================
//==================================================================================================
inline
Ellipse_t::Ellipse_t()
{
    m_half_width = 0;
    m_half_height = 0;
    m_rotation = 0;
    m_rotated = false;
    m_rotated_90_degree_increments = false;
    m_sin_rotation = 0;
    m_cos_rotation = 1;
}


inline Point_t
Ellipse_t::Center() const
{
    return m_center;
}


inline void
Ellipse_t::GetCenter(out Point_t* center) const
{
    *center = m_center;
}


inline float
Ellipse_t::Width() const
{
    return m_half_width * 2;
}


inline float
Ellipse_t::Height() const
{
    return m_half_height * 2;
}


inline double
Ellipse_t::Rotation() const
{
    return m_rotation;
}


inline Ellipse_t
Ellipse_t::operator +(const Point_t& add) const
{
    return Ellipse_t( m_center+add, m_half_width*2, m_half_height*2, m_rotation );
}


inline Ellipse_t
Ellipse_t::operator -(const Point_t& subtract) const
{
    return Ellipse_t( m_center-subtract, m_half_width*2, m_half_height*2, m_rotation );
}


inline const Ellipse_t&
Ellipse_t::operator +=(const Point_t& add)
{
    m_center += add;
    return *this;
}


inline const Ellipse_t&
Ellipse_t::operator -=(const Point_t& subtract)
{
    m_center -= subtract;
    return *this;
}


inline Rect_t
Ellipse_t::BoundingBox() const
{
    Rect_t temp;
    GetBoundingBox(&temp);
    return temp;
}


#endif // __cplusplus
#endif // _UT_GEOMETRY_H_