fair_splitrule.h

// Description: Fair splitting rule

#ifndef PASTELGEOMETRY_FAIR_SPLITRULE_H
#define PASTELGEOMETRY_FAIR_SPLITRULE_H

#include "pastel/sys/pointset/pointset_concept.h"
#include "pastel/sys/locator/locator_concept.h"

#include "pastel/geometry/splitrule/splitrule_concept.h"
#include "pastel/geometry/shape/alignedbox.h"

namespace Pastel
{

    //! Fair splitting rule.
    class Fair_SplitRule
    {
    public:
        template <
            PointSet_Concept PointSet,
            typename Real = PointSet_Real<PointSet>,
            int N = PointSet_Dimension<PointSet>::value
        >
        std::pair<Real, integer> operator()(
            const PointSet& pointSet,
            const AlignedBox<Real, N>& bound) const
        {
            // Split along the longest dimension.

            integer splitAxis = maxIndex(bound.extent());
            Real splitPosition = linear(
                bound.min()[splitAxis], 
                bound.max()[splitAxis], 0.5);

            if (pointSet.empty())
            {
                return std::make_pair(splitPosition, splitAxis);
            }

            // Find out the minimum bounding interval for
            // the contained points on the splitting axis.

            Real minPosition = Infinity();
            Real maxPosition = -Infinity();

            for (auto&& point : pointSet)
            {
                Real position = 
                    pointAxis(point, splitAxis);

                if (position < minPosition)
                {
                    minPosition = position;
                }
                if (position > maxPosition)
                {
                    maxPosition = position;
                }
            }

            // Split at the midpoint of the minimum
            // bounding interval.

            splitPosition = 
                linear(minPosition, maxPosition, 0.5);

            return std::make_pair(splitPosition, splitAxis);
        }
    };

}

#endif