polygonintersector.h

Go to the documentation of this file.

/*
* Copyright 2016 Autodesk, Inc. All rights reserved.
* Use of this software is subject to the terms of the Autodesk license agreement and any attachments or Appendices thereto provided at the time of installation or download,
* or which otherwise accompanies this software in either electronic or hard copy form, or which is signed by you and accepted by Autodesk.
*/


#pragma once

#include "gwnavruntime/base/memory.h"
#include "gwnavruntime/math/vec3f.h"
#include "gwnavruntime/math/closedcontour.h"

namespace Kaim
{

/*
class PolygonIntersector
*/
class PolygonIntersector
{
    KY_DEFINE_NEW_DELETE_OPERATORS(MemStat_Query)

public:
    PolygonIntersector(const Vec2f* points, KyUInt32 pointCount, KyFloat32 integerPrecision)
    {
        if (pointCount > 0)
        {
            bool inputPolylineIsClosed = points[0] == points[pointCount-1];
            m_points.Resize(inputPolylineIsClosed ? pointCount : pointCount+1);

            for(KyUInt32 i = 0; i < pointCount; ++i)
            {
                m_points[i] = points[i];
                m_box2f.ExpandByPos(points[i]);
            }

            if (inputPolylineIsClosed ==  false)
                m_points[pointCount] = points[0];
        }

        m_integerPrecision = integerPrecision;
    }

    bool DoesIntersectEdge(const CoordPos64& startEdgeCoordPos, const CoordPos64& endEdgeCoordPos)
    {
        const Vec2f startEdgePos(startEdgeCoordPos.x * m_integerPrecision, startEdgeCoordPos.y * m_integerPrecision);
        const Vec2f endEdgePos(endEdgeCoordPos.x * m_integerPrecision, endEdgeCoordPos.y * m_integerPrecision);

        Box2f edgeBox(
            Kaim::Min(startEdgePos.x, endEdgePos.x), Kaim::Min(startEdgePos.y, endEdgePos.y),
            Kaim::Max(startEdgePos.x, endEdgePos.x), Kaim::Max(startEdgePos.y, endEdgePos.y));

        if (Math::IsBoxVsBox2f(m_box2f, edgeBox) == false)
            return false;

        if (IsPointInsidePolyline(startEdgePos))
            return true;

        if (IsPointInsidePolyline(endEdgePos))
            return true;

        return DoesEdgeIntersectOnePolylineBorder(startEdgePos, endEdgePos);
    }

    bool IsPointInsidePolyline(const Vec2f& point)
    {
        if (m_box2f.DoesContain(point) == false)
            return false;

        return ClosedContour::DoesContain2f(point, m_points.GetDataPtr(), m_points.GetCount());
    }

    bool DoesEdgeIntersectOnePolylineBorder(const Vec2f& startEdgePos, const Vec2f& endEdgePos)
    {
        KyUInt32 pointCount = m_points.GetCount();
        for(KyUInt32 i = 0; i < pointCount - 1; ++i)
        {
            if (Math::IsSegmentVsSegment2f(m_points[i], m_points[i+1], startEdgePos, endEdgePos))
                return true;
        }

        return false;
    }
private:
    KyArrayPOD<Vec2f> m_points;
    Box2f m_box2f;
    KyFloat32 m_integerPrecision;
};


}