GraphProcessor.cpp

Go to the documentation of this file.

// *****************************************************************
// Filename:    GraphProcessor.cpp
// Copyright:   Kai Welke, Chair Prof. Dillmann (IAIM),
//              Institute for Computer Science and Engineering (CSE),
//              University of Karlsruhe. All rights reserved.
// Author:      Kai Welke
// Date:        12.06.2007
// *****************************************************************
 
 
// *****************************************************************
// includes
// *****************************************************************
// system
#include <float.h>
#include <math.h>
 
// local includes
#include "Base/Math/MathTools.h"
#include "Base/Tools/DebugMemory.h"
#include "GraphProcessor.h"
 
void
GraphProcessor::transform(CSphericalGraph* pGraph, TTransform transform)
{
    TNodeList* pNodes = pGraph->getNodes();
 
    TSphereCoord position, position_tr;
 
    for (int n = 0; n < int(pNodes->size()); n++)
    {
        CSGNode* pNode = pNodes->at(n);
        position = pNode->getPosition();
        position_tr = MathTools::transform(position, transform);
        pNode->setPosition(position_tr);
    }
}
 
void
GraphProcessor::inverseTransform(CSphericalGraph* pGraph, TTransform transform)
{
    TNodeList* pNodes = pGraph->getNodes();
 
    TSphereCoord position, position_tr;
 
    for (int n = 0; n < int(pNodes->size()); n++)
    {
        CSGNode* pNode = pNodes->at(n);
        position = pNode->getPosition();
        position_tr = MathTools::inverseTransform(position, transform);
        pNode->setPosition(position_tr);
    }
}
 
void
GraphProcessor::invertPhi(CSphericalGraph* pGraph)
{
    TNodeList* pNodes = pGraph->getNodes();
 
    TSphereCoord position;
 
    for (int n = 0; n < int(pNodes->size()); n++)
    {
        CSGNode* pNode = pNodes->at(n);
        position = pNode->getPosition();
        position.fPhi = 360.0f - position.fPhi;
        pNode->setPosition(position);
    }
}
 
void
GraphProcessor::invertTheta(CSphericalGraph* pGraph)
{
    TNodeList* pNodes = pGraph->getNodes();
 
    TSphereCoord position;
 
    for (int n = 0; n < int(pNodes->size()); n++)
    {
        CSGNode* pNode = pNodes->at(n);
        position = pNode->getPosition();
        position.fTheta = 180.0f - position.fTheta;
        pNode->setPosition(position);
    }
}
 
void
GraphProcessor::copyGraphNodesAndEdges(CSphericalGraph* pSrcGraph, CSphericalGraph* pDstGraph)
{
    pDstGraph->clear();
 
    TNodeList* pNodes = pSrcGraph->getNodes();
    TEdgeList* pEdges = pSrcGraph->getEdges();
 
    for (int n = 0; n < int(pNodes->size()); n++)
    {
        CSGNode* pNode = pNodes->at(n);
        CSGNode* pNewNode = pDstGraph->getNewNode();
        pNewNode->setPosition(pNode->getPosition());
        pDstGraph->addNode(pNewNode);
    }
 
    for (int e = 0; e < int(pEdges->size()); e++)
    {
        CSGEdge* pEdge = pEdges->at(e);
        pDstGraph->addEdge(pEdge->nIndex1, pEdge->nIndex2, pEdge->nLeftFace, pEdge->nRightFace);
    }
}
 
int
GraphProcessor::findClosestNode(CSphericalGraph* pGraph, TSphereCoord coord)
{
    TNodeList* pNodes = pGraph->getNodes();
 
    float fMinDistance = FLT_MAX;
    float fDistance = 0.0f;
    int nIndex = -1;
 
    for (int n = 0; n < int(pNodes->size()); n++)
    {
        CSGNode* pNode = pNodes->at(n);
        fDistance = MathTools::getDistanceOnArc(pNode->getPosition(), coord);
 
        if (fDistance < fMinDistance)
        {
            fMinDistance = fDistance;
            nIndex = n;
        }
    }
 
    return nIndex;
}
 
void
GraphProcessor::findClosestNeighbours(CSphericalGraph* pGraph, int& s, int& t)
{
    TNodeList* pNodes = pGraph->getNodes();
 
    float fMinDistance = FLT_MAX;
    int nIndex1 = -1;
    int nIndex2 = -1;
    float fDistance;
 
    for (int i = 0; i < int(pNodes->size()); i++)
    {
        for (int j = 0; j < int(pNodes->size()); j++)
        {
            if (i != j)
            {
                fDistance = MathTools::getDistanceOnArc(pNodes->at(i)->getPosition(),
                                                        pNodes->at(j)->getPosition());
 
                if (fDistance < fMinDistance)
                {
                    fMinDistance = fDistance;
                    nIndex1 = i;
                    nIndex2 = j;
                }
            }
        }
    }
 
    s = nIndex1;
    t = nIndex2;
}
 
int
GraphProcessor::findEdge(CSphericalGraph* pGraph, int nIndex1, int nIndex2)
{
    TEdgeList* pEdges = pGraph->getEdges();
 
    for (int e = 0; e < int(pEdges->size()); e++)
    {
        if ((pEdges->at(e)->nIndex1 == nIndex1) && (pEdges->at(e)->nIndex2 == nIndex2))
        {
            return e;
        }
 
        if ((pEdges->at(e)->nIndex1 == nIndex2) && (pEdges->at(e)->nIndex2 == nIndex1))
        {
            return e;
        }
    }
 
    // not found
    return -1;
}
 
bool
GraphProcessor::insideCircumcircle(CSphericalGraph* pGraph,
                                   int nIndex1,
                                   int nIndex2,
                                   int nIndex3,
                                   int nPointIndex,
                                   bool& bInside)
{
    TNodeList* pNodes = pGraph->getNodes();
 
    TSphereCoord center;
    float fRadius;
 
    if (!getCircumcircle(pGraph, nIndex1, nIndex2, nIndex3, center, fRadius))
    {
        return false;
    }
 
    TSphereCoord point = pNodes->at(nPointIndex)->getPosition();
 
    // check with give coordinates
    float fDistance = sqrt((center.fPhi - point.fPhi) * (center.fPhi - point.fPhi) +
                           (center.fTheta - point.fTheta) * (center.fTheta - point.fTheta));
 
    bInside = (fDistance < (fRadius + 0.0001));
 
    return true;
}
 
bool
GraphProcessor::getCircumcircle(CSphericalGraph* pGraph,
                                int nIndex1,
                                int nIndex2,
                                int nIndex3,
                                TSphereCoord& center,
                                float& fRadius)
{
    TNodeList* pNodes = pGraph->getNodes();
    float cp;
 
    TSphereCoord s1, s2, s3;
    s1 = pNodes->at(nIndex1)->getPosition();
    s2 = pNodes->at(nIndex2)->getPosition();
    s3 = pNodes->at(nIndex3)->getPosition();
 
    cp = MathTools::CalculateCrossProductFromDifference(s1, s2, s3);
 
    if (cp != 0.0)
    {
        float p1Sq, p2Sq, p3Sq;
        float num;
        float cx, cy;
 
        p1Sq = s1.fPhi * s1.fPhi + s1.fTheta * s1.fTheta;
        p2Sq = s2.fPhi * s2.fPhi + s2.fTheta * s2.fTheta;
        p3Sq = s3.fPhi * s3.fPhi + s3.fTheta * s3.fTheta;
 
        num = p1Sq * (s2.fTheta - s3.fTheta) + p2Sq * (s3.fTheta - s1.fTheta) +
              p3Sq * (s1.fTheta - s2.fTheta);
        cx = num / (2.0f * cp);
        num = p1Sq * (s3.fPhi - s2.fPhi) + p2Sq * (s1.fPhi - s3.fPhi) + p3Sq * (s2.fPhi - s1.fPhi);
        cy = num / (2.0f * cp);
 
        center.fPhi = cx;
        center.fTheta = cy;
 
        fRadius = sqrt((center.fPhi - s1.fPhi) * (center.fPhi - s1.fPhi) +
                       (center.fTheta - s1.fTheta) * (center.fTheta - s1.fTheta));
        return true;
    }
    else
    {
        // points lie on a line
        return false;
    }
}
 
int
GraphProcessor::getDelaunayNeighbour(CSphericalGraph* pGraph, CSGEdge* pEdge)
{
    TNodeList* pNodes = pGraph->getNodes();
    float fMinRadius = FLT_MAX;
    float fRadius;
    int nIndex = -1;
 
    // go through all points
    for (int v = 0; v < int(pNodes->size()); v++)
    {
        if ((v == pEdge->nIndex1) || (v == pEdge->nIndex2))
        {
            continue;
        }
 
        // check if v is already connected to index1, index2
        if (GraphProcessor::isEdgePresent(pGraph, pEdge->nIndex1, v))
        {
            continue;
        }
 
        if (GraphProcessor::isEdgePresent(pGraph, pEdge->nIndex2, v))
        {
            continue;
        }
 
        // check if v is an unconnected node
        if (pGraph->getNodeAdjacency(v)->size() != 0)
        {
            continue;
        }
 
        TSphereCoord center;
 
        getCircumcircle(pGraph, pEdge->nIndex1, pEdge->nIndex2, v, center, fRadius);
 
        if (fRadius < fMinRadius)
        {
            fMinRadius = fRadius;
            nIndex = v;
        }
    }
 
    return nIndex;
}
 
bool
GraphProcessor::isEdgePresent(CSphericalGraph* pGraph, int nIndex1, int nIndex2)
{
 
    bool bPresent = false;
 
    vector<int>::iterator iter = pGraph->getNodeAdjacency(nIndex1)->begin();
 
    while (iter != pGraph->getNodeAdjacency(nIndex1)->end())
    {
        if ((*iter) == nIndex2)
        {
            bPresent = true;
        }
 
        iter++;
    }
 
    return bPresent;
}