tetrees/Plugins/Wwise/Source/AkAudio/Classes/GTE/Mathematics/IsPlanarGraph.h

// David Eberly, Geometric Tools, Redmond WA 98052
// Copyright (c) 1998-2020
// Distributed under the Boost Software License, Version 1.0.
// https://www.boost.org/LICENSE_1_0.txt
// https://www.geometrictools.com/License/Boost/LICENSE_1_0.txt
// Version: 4.0.2019.08.13

#pragma once

#include <algorithm>
#include <array>
#include <map>
#include <set>
#include <vector>

// Test whether an undirected graph is planar.  The input positions must be
// unique and the input edges must be unique, so the number of positions is
// at least 2 and the number of edges is at least one.  The elements of the
// edges array must be indices in {0,..,positions.size()-1}.
// 
// A sort-and-sweep algorithm is used to determine edge-edge intersections.
// If none of the intersections occur at edge-interior points, the graph is
// planar.  See Game Physics (2nd edition), Section 6.2.2: Culling with
// Axis-Aligned Bounding Boxes for such an algorithm.  The operator()
// returns 'true' when the graph is planar.  If it returns 'false', the
// 'invalidIntersections' set contains pairs of edges that intersect at an
// edge-interior point (that by definition is not a graph vertex).  Each set
// element is a pair of indices into the 'edges' array; the indices are
// ordered so that element[0] < element[1].  The Real type must be chosen
// to guarantee exact computation of edge-edge intersections.

namespace WwiseGTE
{
    template <typename Real>
    class IsPlanarGraph
    {
    public:
        IsPlanarGraph()
            :
            mZero(0),
            mOne(1)
        {
        }

        enum
        {
            IPG_IS_PLANAR_GRAPH = 0,
            IPG_INVALID_INPUT_SIZES = 1,
            IPG_DUPLICATED_POSITIONS = 2,
            IPG_DUPLICATED_EDGES = 4,
            IPG_DEGENERATE_EDGES = 8,
            IPG_EDGES_WITH_INVALID_VERTICES = 16,
            IPG_INVALID_INTERSECTIONS = 32
        };

        // The function returns a combination of the IPG_* flags listed in the
        // previous enumeration.  A combined value of 0 indicates the input
        // forms a planar graph.  If the combined value is not zero, you may
        // examine the flags for the failure conditions and use the Get*
        // member accessors to obtain specific information about the failure.
        // If the positions.size() < 2 or edges.size() == 0, the
        // IPG_INVALID_INPUT_SIZES flag is set.

        int operator()(std::vector<std::array<Real, 2>> const& positions,
            std::vector<std::array<int, 2>> const& edges)
        {
            mDuplicatedPositions.clear();
            mDuplicatedEdges.clear();
            mDegenerateEdges.clear();
            mEdgesWithInvalidVertices.clear();
            mInvalidIntersections.clear();

            int flags = IsValidTopology(positions, edges);
            if (flags == IPG_INVALID_INPUT_SIZES)
            {
                return flags;
            }

            std::set<OrderedEdge> overlappingRectangles;
            ComputeOverlappingRectangles(positions, edges, overlappingRectangles);
            for (auto key : overlappingRectangles)
            {
                // Get the endpoints of the line segments for the edges whose
                // bounding rectangles overlapped.  Determine whether the line
                // segments intersect.  If they do, determine how they
                // intersect.
                std::array<int, 2> e0 = edges[key.V[0]];
                std::array<int, 2> e1 = edges[key.V[1]];
                std::array<Real, 2> const& p0 = positions[e0[0]];
                std::array<Real, 2> const& p1 = positions[e0[1]];
                std::array<Real, 2> const& q0 = positions[e1[0]];
                std::array<Real, 2> const& q1 = positions[e1[1]];
                if (InvalidSegmentIntersection(p0, p1, q0, q1))
                {
                    mInvalidIntersections.push_back(key);
                }
            }

            if (mInvalidIntersections.size() > 0)
            {
                flags |= IPG_INVALID_INTERSECTIONS;
            }

            return flags;
        }

        // A pair of indices (v0,v1) into the positions array is stored as
        // (min(v0,v1), max(v0,v1)).  This supports sorted containers of
        // edges.
        struct OrderedEdge
        {
            OrderedEdge(int v0 = -1, int v1 = -1)
            {
                if (v0 < v1)
                {
                    // v0 is minimum
                    V[0] = v0;
                    V[1] = v1;
                }
                else
                {
                    // v1 is minimum
                    V[0] = v1;
                    V[1] = v0;
                }
            }

            bool operator<(OrderedEdge const& edge) const
            {
                // Lexicographical ordering used by std::array<int,2>.
                return V < edge.V;
            }

            std::array<int, 2> V;
        };

        inline std::vector<std::vector<int>> const& GetDuplicatedPositions() const
        {
            return mDuplicatedPositions;
        }

        inline std::vector<std::vector<int>> const& GetDuplicatedEdges() const
        {
            return mDuplicatedEdges;
        }

        inline std::vector<int> const& GetDegenerateEdges() const
        {
            return mDegenerateEdges;
        }

        inline std::vector<int> const& GetEdgesWithInvalidVertices() const
        {
            return mEdgesWithInvalidVertices;
        }

        inline std::vector<typename IsPlanarGraph<Real>::OrderedEdge> const&
        GetInvalidIntersections() const
        {
            return mInvalidIntersections;
        }

    private:
        class Endpoint
        {
        public:
            Real value;     // endpoint value
            int type;       // '0' if interval min, '1' if interval max.
            int index;      // index of interval containing this endpoint

            // Comparison operator for sorting.
            bool operator<(Endpoint const& endpoint) const
            {
                if (value < endpoint.value)
                {
                    return true;
                }
                if (value > endpoint.value)
                {
                    return false;
                }
                return type < endpoint.type;
            }
        };

        int IsValidTopology(std::vector<std::array<Real, 2>> const& positions,
            std::vector<std::array<int, 2>> const& edges)
        {
            int const numPositions = static_cast<int>(positions.size());
            int const numEdges = static_cast<int>(edges.size());
            if (numPositions < 2 || numEdges == 0)
            {
                // The graph must have at least one edge.
                return IPG_INVALID_INPUT_SIZES;
            }

            // The positions must be unique.
            int flags = IPG_IS_PLANAR_GRAPH;
            std::map<std::array<Real, 2>, std::vector<int>> uniquePositions;
            for (int i = 0; i < numPositions; ++i)
            {
                std::array<Real, 2> p = positions[i];
                auto iter = uniquePositions.find(p);
                if (iter == uniquePositions.end())
                {
                    std::vector<int> indices;
                    indices.push_back(i);
                    uniquePositions.insert(std::make_pair(p, indices));
                }
                else
                {
                    iter->second.push_back(i);
                }
            }
            if (uniquePositions.size() < positions.size())
            {
                // At least two positions are duplicated.
                for (auto const& element : uniquePositions)
                {
                    if (element.second.size() > 1)
                    {
                        mDuplicatedPositions.push_back(element.second);
                    }
                }
                flags |= IPG_DUPLICATED_POSITIONS;
            }

            // The edges must be unique.
            std::map<OrderedEdge, std::vector<int>> uniqueEdges;
            for (int i = 0; i < numEdges; ++i)
            {
                OrderedEdge key(edges[i][0], edges[i][1]);
                auto iter = uniqueEdges.find(key);
                if (iter == uniqueEdges.end())
                {
                    std::vector<int> indices;
                    indices.push_back(i);
                    uniqueEdges.insert(std::make_pair(key, indices));
                }
                else
                {
                    iter->second.push_back(i);
                }
            }
            if (uniqueEdges.size() < edges.size())
            {
                // At least two edges are duplicated, possibly even a pair of
                // edges (v0,v1) and (v1,v0) which is not allowed because the
                // graph is undirected.
                for (auto const& element : uniqueEdges)
                {
                    if (element.second.size() > 1)
                    {
                        mDuplicatedEdges.push_back(element.second);
                    }
                }
                flags |= IPG_DUPLICATED_EDGES;
            }

            // The edges are represented as pairs of indices into the
            // 'positions' array.  The indices for a single edge must be
            // different (no edges allowed from a vertex to itself) and all
            // indices must be valid.  At the same time, keep track of unique
            // edges.
            for (int i = 0; i < numEdges; ++i)
            {
                std::array<int, 2> e = edges[i];
                if (e[0] == e[1])
                {
                    // The edge is degenerate, originating and terminating at
                    // the same vertex.
                    mDegenerateEdges.push_back(i);
                    flags |= IPG_DEGENERATE_EDGES;
                }

                if (e[0] < 0 || e[0] >= numPositions || e[1] < 0 || e[1] >= numPositions)
                {
                    // The edge has an index that references a nonexistent
                    // vertex.
                    mEdgesWithInvalidVertices.push_back(i);
                    flags |= IPG_EDGES_WITH_INVALID_VERTICES;
                }
            }

            return flags;
        }

        void ComputeOverlappingRectangles(std::vector<std::array<Real, 2>> const& positions,
            std::vector<std::array<int, 2>> const& edges,
            std::set<OrderedEdge>& overlappingRectangles) const
        {
            // Compute axis-aligned bounding rectangles for the edges.
            int const numEdges = static_cast<int>(edges.size());
            std::vector<std::array<Real, 2>> emin(numEdges);
            std::vector<std::array<Real, 2>> emax(numEdges);
            for (int i = 0; i < numEdges; ++i)
            {
                std::array<int, 2> e = edges[i];
                std::array<Real, 2> const& p0 = positions[e[0]];
                std::array<Real, 2> const& p1 = positions[e[1]];

                for (int j = 0; j < 2; ++j)
                {
                    if (p0[j] < p1[j])
                    {
                        emin[i][j] = p0[j];
                        emax[i][j] = p1[j];
                    }
                    else
                    {
                        emin[i][j] = p1[j];
                        emax[i][j] = p0[j];
                    }
                }
            }

            // Get the rectangle endpoints.
            int const numEndpoints = 2 * numEdges;
            std::vector<Endpoint> xEndpoints(numEndpoints);
            std::vector<Endpoint> yEndpoints(numEndpoints);
            for (int i = 0, j = 0; i < numEdges; ++i)
            {
                xEndpoints[j].type = 0;
                xEndpoints[j].value = emin[i][0];
                xEndpoints[j].index = i;
                yEndpoints[j].type = 0;
                yEndpoints[j].value = emin[i][1];
                yEndpoints[j].index = i;
                ++j;

                xEndpoints[j].type = 1;
                xEndpoints[j].value = emax[i][0];
                xEndpoints[j].index = i;
                yEndpoints[j].type = 1;
                yEndpoints[j].value = emax[i][1];
                yEndpoints[j].index = i;
                ++j;
            }

            // Sort the rectangle endpoints.
            std::sort(xEndpoints.begin(), xEndpoints.end());
            std::sort(yEndpoints.begin(), yEndpoints.end());

            // Sweep through the endpoints to determine overlapping
            // x-intervals.  Use an active set of rectangles to reduce the
            // complexity of the algorithm.
            std::set<int> active;
            for (int i = 0; i < numEndpoints; ++i)
            {
                Endpoint const& endpoint = xEndpoints[i];
                int index = endpoint.index;
                if (endpoint.type == 0)  // an interval 'begin' value
                {
                    // In the 1D problem, the current interval overlaps with
                    // all the active intervals.  In 2D this we also need to
                    // check for y-overlap.
                    for (auto activeIndex : active)
                    {
                        // Rectangles activeIndex and index overlap in the
                        // x-dimension.  Test for overlap in the y-dimension.
                        std::array<Real, 2> const& r0min = emin[activeIndex];
                        std::array<Real, 2> const& r0max = emax[activeIndex];
                        std::array<Real, 2> const& r1min = emin[index];
                        std::array<Real, 2> const& r1max = emax[index];
                        if (r0max[1] >= r1min[1] && r0min[1] <= r1max[1])
                        {
                            if (activeIndex < index)
                            {
                                overlappingRectangles.insert(OrderedEdge(activeIndex, index));
                            }
                            else
                            {
                                overlappingRectangles.insert(OrderedEdge(index, activeIndex));
                            }
                        }
                    }
                    active.insert(index);
                }
                else  // an interval 'end' value
                {
                    active.erase(index);
                }
            }
        }

        bool InvalidSegmentIntersection(
            std::array<Real, 2> const& p0, std::array<Real, 2> const& p1,
            std::array<Real, 2> const& q0, std::array<Real, 2> const& q1) const
        {
            // We must solve the two linear equations
            //   p0 + t0 * (p1 - p0) = q0 + t1 * (q1 - q0)
            // for the unknown variables t0 and t1.  These may be written as
            //   t0 * (p1 - p0) - t1 * (q1 - q0) = q0 - p0
            // If denom = Dot(p1 - p0, Perp(q1 - q0)) is not zero, then
            //   t0 = Dot(q0 - p0, Perp(q1 - q0)) / denom = numer0 / denom
            //   t1 = Dot(q0 - p0, Perp(p1 - p0)) / denom = numer1 / denom
            // For an invalid intersection, we need (t0,t1) with:
            // ((0 < t0 < 1) and (0 <= t1 <= 1)) or ((0 <= t0 <= 1) and
            // (0 < t1 < 1).

            std::array<Real, 2> p1mp0, q1mq0, q0mp0;
            for (int j = 0; j < 2; ++j)
            {
                p1mp0[j] = p1[j] - p0[j];
                q1mq0[j] = q1[j] - q0[j];
                q0mp0[j] = q0[j] - p0[j];
            }

            Real denom = p1mp0[0] * q1mq0[1] - p1mp0[1] * q1mq0[0];
            Real numer0 = q0mp0[0] * q1mq0[1] - q0mp0[1] * q1mq0[0];
            Real numer1 = q0mp0[0] * p1mp0[1] - q0mp0[1] * p1mp0[0];

            if (denom != mZero)
            {
                // The lines of the segments are not parallel.
                if (denom > mZero)
                {
                    if (mZero <= numer0 && numer0 <= denom && mZero <= numer1 && numer1 <= denom)
                    {
                        // The segments intersect.
                        return (numer0 != mZero && numer0 != denom) || (numer1 != mZero && numer1 != denom);
                    }
                    else
                    {
                        return false;
                    }
                }
                else  // denom < mZero
                {
                    if (mZero >= numer0 && numer0 >= denom && mZero >= numer1 && numer1 >= denom)
                    {
                        // The segments intersect.
                        return (numer0 != mZero && numer0 != denom) || (numer1 != mZero && numer1 != denom);
                    }
                    else
                    {
                        return false;
                    }
                }
            }
            else
            {
                // The lines of the segments are parallel.
                if (numer0 != mZero || numer1 != mZero)
                {
                    // The lines of the segments are separated.
                    return false;
                }
                else
                {
                    // The segments lie on the same line.  Compute the
                    // parameter intervals for the segments in terms of the
                    // t0-parameter and determine their overlap (if any).
                    std::array<Real, 2> q1mp0;
                    for (int j = 0; j < 2; ++j)
                    {
                        q1mp0[j] = q1[j] - p0[j];
                    }
                    Real sqrLenP1mP0 = p1mp0[0] * p1mp0[0] + p1mp0[1] * p1mp0[1];
                    Real value0 = q0mp0[0] * p1mp0[0] + q0mp0[1] * p1mp0[1];
                    Real value1 = q1mp0[0] * p1mp0[0] + q1mp0[1] * p1mp0[1];
                    if ((value0 >= sqrLenP1mP0 && value1 >= sqrLenP1mP0)
                        || (value0 <= mZero && value1 <= mZero))
                    {
                        // If the segments intersect, they must do so at
                        // endpoints of the segments.
                        return false;
                    }
                    else
                    {
                        // The segments overlap in a positive-length interval.
                        return true;
                    }
                }
            }
        }

        std::vector<std::vector<int>> mDuplicatedPositions;
        std::vector<std::vector<int>> mDuplicatedEdges;
        std::vector<int> mDegenerateEdges;
        std::vector<int> mEdgesWithInvalidVertices;
        std::vector<OrderedEdge> mInvalidIntersections;
        Real mZero, mOne;
    };
}