RasterPolygon.h

Go to the documentation of this file.

/*
 * Copyright (C) by
 *   MetraLabs GmbH (MLAB), GERMANY
 * and
 *   Neuroinformatics and Cognitive Robotics Labs (NICR) at TU Ilmenau, GERMANY
 * All rights reserved.
 *
 * Contact: info@mira-project.org
 *
 * Commercial Usage:
 *   Licensees holding valid commercial licenses may use this file in
 *   accordance with the commercial license agreement provided with the
 *   software or, alternatively, in accordance with the terms contained in
 *   a written agreement between you and MLAB or NICR.
 *
 * GNU General Public License Usage:
 *   Alternatively, this file may be used under the terms of the GNU
 *   General Public License version 3.0 as published by the Free Software
 *   Foundation and appearing in the file LICENSE.GPL3 included in the
 *   packaging of this file. Please review the following information to
 *   ensure the GNU General Public License version 3.0 requirements will be
 *   met: http://www.gnu.org/copyleft/gpl.html.
 *   Alternatively you may (at your option) use any later version of the GNU
 *   General Public License if such license has been publicly approved by
 *   MLAB and NICR (or its successors, if any).
 *
 * IN NO EVENT SHALL "MLAB" OR "NICR" BE LIABLE TO ANY PARTY FOR DIRECT,
 * INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF
 * THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF "MLAB" OR
 * "NICR" HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * "MLAB" AND "NICR" SPECIFICALLY DISCLAIM ANY WARRANTIES, INCLUDING,
 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
 * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
 * ON AN "AS IS" BASIS, AND "MLAB" AND "NICR" HAVE NO OBLIGATION TO
 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS OR MODIFICATIONS.
 */

#ifndef _MIRA_BASE_INCLUDE_GEOMETRY_RASTERPOLYGON_H_
#define _MIRA_BASE_INCLUDE_GEOMETRY_RASTERPOLYGON_H_

#include <geometry/RasterPolygonUtils.h>
#include <geometry/Rect.h>

namespace mira {


namespace Private {


template<class Visitor>
bool processActiveEdges(ActiveEdgeCuts& activeEdges, const Rect2i& region, Visitor& visitor)
{
    // even-odd rule ensures every complete horizontal cut has an even number of points
    assert(activeEdges.begin <= activeEdges.end);
    assert(std::distance(activeEdges.begin, activeEdges.end) % 2 == 0);

    // sort active edges by their current x (x for y)
    std::sort(activeEdges.begin, activeEdges.end, &Private::compareCurrentCut);

    if (region.y0() <= activeEdges.currentY && activeEdges.currentY < region.y1()) {
        for (auto it = activeEdges.begin; it != activeEdges.end; std::advance(it, 2)) {
            const auto x_start = std::max(region.x0(),
                                          (int)std::floor(it->getCurrentCut()));
            const auto x_end   = std::min(region.x1() - 1,
                                          (int)std::floor(std::next(it)->getCurrentCut()));

            if (visitInterval(x_start, x_end, activeEdges.currentY, visitor)) {
                return true;
            }
        }
    }

    advanceEdgeCuts(activeEdges);
    return false;
}

template<class Visitor>
bool processTwoActiveEdges(ActiveEdgeCuts& activeEdges, const Rect2i& region,
                           Visitor& visitor, const int nextY)
{
    assert(std::distance(activeEdges.begin, activeEdges.end) == 2);

    auto& firstEdge = *activeEdges.begin;
    auto& secondEdge = *std::next(activeEdges.begin);
    while (activeEdges.currentY > nextY) {
        if (region.y0() <= activeEdges.currentY && activeEdges.currentY < region.y1()) {
            auto cut1 = (int)std::floor(firstEdge.getCurrentCut());
            auto cut2 = (int)std::floor(secondEdge.getCurrentCut());

            if (cut1 > cut2)
                std::swap(cut1, cut2);

            const auto x_start = std::max(region.x0(), cut1);
            const auto x_end   = std::min(region.x1() - 1, cut2);

            if (visitInterval(x_start, x_end, activeEdges.currentY, visitor)) {
                return true;
            }
        }

        firstEdge.advanceToNextCut();
        secondEdge.advanceToNextCut();
        --activeEdges.currentY;
    }

    removeEmptyEdges(activeEdges);

    return false;
}

template<class Visitor>
bool processIntervals(const ActiveEdgeCuts& activeEdges, Intervals& intervals, const Rect2i& region,
                      Visitor& visitor, uint precision)
{
    if (activeEdges.currentY % precision == 0) {
        const int y_inGrid_coordinates = activeEdges.currentY / (int)precision;

        if (region.y0() <= y_inGrid_coordinates && y_inGrid_coordinates < region.y1()) {
            for (const auto& interval : intervals.getIntervals()) {
                const auto x_start = std::max(region.x0(),
                                              scaleDown(std::floor(interval.start), precision));
                const auto x_end   = std::min(region.x1() - 1,
                                              scaleDown(std::floor(interval.end), precision));

                if (visitInterval(x_start, x_end, y_inGrid_coordinates, visitor)) {
                    return true;
                }
            }
        }
        intervals.clear();
    }

    return false;
}

template<class Visitor>
bool processActiveEdges(ActiveEdgeCuts& activeEdges, Intervals& intervals, const Rect2i& region,
                        Visitor& visitor, uint precision)
{
    // even-odd rule ensures every complete horizontal cut has an even number of points
    assert(activeEdges.begin <= activeEdges.end);
    assert(std::distance(activeEdges.begin, activeEdges.end) % 2 == 0);

    // sort active edges by their current x (x for y)
    std::sort(activeEdges.begin, activeEdges.end, &Private::compareCurrentCut);

    for (auto it = activeEdges.begin; it != activeEdges.end; std::advance(it, 2)) {
        intervals.addOrMerge({it->getCurrentCut(), std::next(it)->getCurrentCut()});
    }

    if (processIntervals(activeEdges, intervals, region, visitor, precision)) {
        return true;
    }

    advanceEdgeCuts(activeEdges);
    return false;
}

template<class Visitor>
bool processTwoActiveEdges(ActiveEdgeCuts& activeEdges, Intervals& intervals, const Rect2i& region,
                           Visitor& visitor, const uint precision, const int nextY)
{
    assert(std::distance(activeEdges.begin, activeEdges.end) == 2);

    auto& firstEdge = *activeEdges.begin;
    auto& secondEdge = *std::next(activeEdges.begin);
    while (activeEdges.currentY > nextY) {
        auto cut1 = std::floor(firstEdge.getCurrentCut());
        auto cut2 = std::floor(secondEdge.getCurrentCut());

        if(cut1 > cut2)
            std::swap(cut1, cut2);

        intervals.addOrMerge({cut1, cut2});

        if (processIntervals(activeEdges, intervals, region, visitor, precision)) {
            return true;
        }

        firstEdge.advanceToNextCut();
        secondEdge.advanceToNextCut();
        --activeEdges.currentY;
    }

    removeEmptyEdges(activeEdges);

    return false;
}


} // namespace Private

template<class TransformationInRegion, class Visitor>
void rasterPolygon(const Polygon2f& polygon, const Rect2i& region,
                   TransformationInRegion&& transformation, Visitor&& visitor)
{
    if (polygon.size() <= 2)
        return;

    if (!region.isValid())
        return;

    auto edgeList = Private::createEdgeList(polygon,
                                            std::forward<TransformationInRegion>(transformation));

    if (edgeList.empty())
        return;

    assert(edgeList.size() >= 2);
    auto activeEdges = Private::ActiveEdgeCuts(edgeList.begin());

    for (; activeEdges.end != edgeList.end(); ++activeEdges.end) {
        while (activeEdges.currentY > activeEdges.end->getMaxY()) {
            // the case with two edges can be handled more efficiently and is quite common (any convex polygon)
            if (std::distance(activeEdges.begin, activeEdges.end) == 2) {
                if (processTwoActiveEdges(activeEdges, region, visitor, activeEdges.end->getMaxY())) {
                    return;
                }
            }
            else if (processActiveEdges(activeEdges, region, visitor)) {
                return;
            }
        }
    }

    while (activeEdges.begin != activeEdges.end) {
        // the case with two edges can be handled more efficiently and is quite common (any convex polygon)
        if (std::distance(activeEdges.begin, activeEdges.end) == 2) {
            const auto yEnd = activeEdges.currentY - activeEdges.begin->getNumberOfCutsWithGrid();
            if (processTwoActiveEdges(activeEdges, region, visitor, yEnd)) {
                return;
            }
        }
        else if (processActiveEdges(activeEdges, region, visitor)) {
            return;
        }
    }
}


template<class TransformationInRegion, class Visitor>
void rasterPolygon(const Polygon2f& polygon, const Rect2i& region,
                   TransformationInRegion&& transformation, Visitor&& visitor, uint precision)
{
    // without precision, just call plain rasterPolygon()
    if (precision <= 1) {
        rasterPolygon(polygon, region, std::forward<TransformationInRegion>(transformation),
                      std::forward<Visitor>(visitor));
        return;
    }

    if (polygon.size() <= 2)
        return;

    if (!region.isValid())
        return;

    auto edgeList = Private::createEdgeList(polygon, [&](const Point2f& p) {
        const Point2f p_transformed = transformation(p) * (float)precision;
        return p_transformed;
    });

    if (edgeList.empty())
        return;

    assert(edgeList.size() >= 2);
    auto activeEdges = Private::ActiveEdgeCuts(edgeList.begin());

    Private::Intervals intervals;

    for (; activeEdges.end != edgeList.end(); ++activeEdges.end) {
        while (activeEdges.currentY > activeEdges.end->getMaxY()) {
            // the case with two edges can be handled more efficiently and is quite common (any convex polygon)
            if (std::distance(activeEdges.begin, activeEdges.end) == 2) {
                if (processTwoActiveEdges(activeEdges, intervals, region, visitor, precision,
                                          activeEdges.end->getMaxY())) {
                    return;
                }
            }
            else if (processActiveEdges(activeEdges, intervals, region, visitor, precision)) {
                return;
            }
        }
    }

    while (activeEdges.begin != activeEdges.end || !intervals.empty()) {
        // the case with two edges can be handled more efficiently and is quite common (any convex polygon)
        if (std::distance(activeEdges.begin, activeEdges.end) == 2) {
            const auto yEnd = activeEdges.currentY - activeEdges.begin->getNumberOfCutsWithGrid();
            if (processTwoActiveEdges(activeEdges, intervals, region, visitor, precision, yEnd)) {
                return;
            }
        }
        else if (processActiveEdges(activeEdges, intervals, region, visitor, precision)) {
            return;
        }
    }
}


} // namespace mira

#endif