2008-01-25

Geometría Computacional - Problemas - Problemas Básicos

Download
Algoritmos

1. Download

Aplicación sencillo demostrando el uso de los algoritmos siguientes

Proyecto Visual Studio 2005 (C++)

Captura de pantalla

2. Algoritmos

Búsqueda de extremos

Hallar el punto con mayor abscisa.

int MaximumAbscissa(std::vector<Point2D> * pvPoints, Point2D * pptResult)
{
    if(pvPoints->size() == 0)
        return 0;
 
    bool bDoubles = false;
 
    Point2D ptTemp = (*pvPoints)[0];
    for(unsigned int i = 1; i < pvPoints->size(); i++){
        if((*pvPoints)[i].x > ptTemp.x){
            ptTemp = (*pvPoints)[i];
            bDoubles = false;
        }
        else if((*pvPoints)[i].x == ptTemp.x)
            bDoubles = true;
    }
 
    *pptResult = ptTemp;
      
    if(bDoubles)
        return 2;
    else
        return 1;
}

bool MaximumAbscissaMultiple(std::vector<Point2D> * pvPoints, std::vector<Point2D> * pvResult)
{
    pvResult->clear();
 
    Point2D ptTemp;
    int iResult = MaximumAbscissa(pvPoints, &ptTemp);
    if(iResult == 0)
        return false;
    else if(iResult == 1){
        pvResult->push_back(ptTemp);
        return true;
    }
    else{
        for(unsigned int i = 0; i < pvPoints->size(); i++){
            if((*pvPoints)[i].x == ptTemp.x)
                pvResult->push_back((*pvPoints)[i]);
            return true;
        }
        return false;
    }
}

Dada un vector, hallar el extremo según la dirección de ese vector.

int MaximumInDirection(std::vector<Point2D> * pvPoints, Point2D ptDireccion, Point2D * pptResult)
{
    if(pvPoints->size() == 0)
        return 0;
 
    bool bDoubles = false;
 
    Point2D ptTemp = (*pvPoints)[0];
    float fLength = (*pvPoints)[0] * ptDireccion;
    for(unsigned int i = 1; i < pvPoints->size(); i++){
        if(fLength < (*pvPoints)[i] * ptTemp){
            ptTemp = (*pvPoints)[i];
            fLength = (*pvPoints)[i] * ptTemp;
            bDoubles = false;
        }
        else if(fLength == (*pvPoints)[i] * ptTemp)
            bDoubles = true;
    }
 
    *pptResult = ptTemp;
 
    if(bDoubles)
        return 2;
    else
        return 1;
}

Hallar el rectángulo mínimo de lados paralelos a los ejes que contiene a todos los puntos.

bool BoundingBox(std::vector<Point2D> * pvPoints, Rect2D * prctResult)
{
    if(pvPoints->size() == 0)
        return false;
 
    Point2D ptLeftBottom, ptUpperRight;
    ptLeftBottom = ptUpperRight = (*pvPoints)[0];
    for(unsigned int i = 1; i < pvPoints->size(); i++){
        ptLeftBottom = min(ptLeftBottom, (*pvPoints)[i]);
        ptUpperRight = max(ptUpperRight, (*pvPoints)[i]);
    }
 
    *prctResult = Rect2D(ptLeftBottom, ptUpperRight);
    return true;
}

Ordenaciones

Ordenar los puntos segun sus abscisas de menor a mayor.

void SortPointsByAbscissaAscending(std::vector<Point2D> * pvPoints, std::vector<Point2D> * pvResult)
{
    pvResult->clear();
 
    pvResult->insert(pvResult->begin(), pvPoints->begin(), pvPoints->end());
    std::sort(pvResult->begin(), pvResult->end(), SortAbscissaAsc);
}

bool SortAbscissaAsc(Point2D ptPoint1, Point2D ptPoint2)
{
    return ptPoint1.x < ptPoint2.x;
}

Ordenar los puntos según una dirección dada por un vector.

void SortPointsByDirectionAscending(std::vector<Point2D> * pvPoints, Point2D ptDireccion, std::vector<Point2D> * pvResult)
{
    pvResult->clear();
 
    std::vector<SPOINTWITHDIRECTION> vTemp;
 
    SPOINTWITHDIRECTION spwdPointTemp;
    for(unsigned int i = 0; i < pvPoints->size(); i++){
        spwdPointTemp.ptPoint = (*pvPoints)[i];
        spwdPointTemp.fProjection = spwdPointTemp.ptPoint * ptDireccion;
        vTemp.push_back(spwdPointTemp);
    }
 
    std::sort(vTemp.begin(), vTemp.end(), SortDirectionAsc);
 
    for(unsigned int i = 0; i < vTemp.size(); i++)
        pvResult->push_back(vTemp[i].ptPoint);
}

bool SortDirectionAsc(SPOINTWITHDIRECTION ptPoint1, SPOINTWITHDIRECTION ptPoint2)
{
    return ptPoint1.fProjection < ptPoint2.fProjection;
}

Ordenar los puntos angularmente respecto de un punto dado y en sentido positivo, comenzando por el de menor ordenada.

void SortPointsAngular(std::vector<Point2D> * pvPoints, Point2D ptRef, std::vector<Point2D> * pvResult)
{
    pvResult->clear();
    if(pvPoints->size() == 0)
        return;
 
    std::vector<SPOINTWITHDIRECTION> vPointsQ1, vPointsQ2, vPointsQ3, vPointsQ4;
 
    for(unsigned int i = 0; i < pvPoints->size(); i++){
        Point2D ptTemp = (*pvPoints)[i];
        SPOINTWITHDIRECTION spwdTemp;
        spwdTemp.ptPoint = ptTemp;
        spwdTemp.fProjection = abs(ptTemp.x - ptRef.x);
 
        if(ptTemp.x >= ptRef.x){
            if(ptTemp.y <= ptRef.y)
                vPointsQ1.push_back(spwdTemp);
            else
                vPointsQ2.push_back(spwdTemp);
        }
        else{
            if(ptTemp.y >= ptRef.y)
                vPointsQ3.push_back(spwdTemp);
            else
                vPointsQ4.push_back(spwdTemp);
        }
    }
 
    std::sort(vPointsQ1.begin(), vPointsQ1.end(), SortDirectionAsc);
    std::sort(vPointsQ2.begin(), vPointsQ2.end(), SortDirectionDesc);
    std::sort(vPointsQ3.begin(), vPointsQ3.end(), SortDirectionAsc);
    std::sort(vPointsQ4.begin(), vPointsQ4.end(), SortDirectionDesc);
 
    std::vector<SPOINTWITHDIRECTION> vJoin;
 
    vJoin.insert(vJoin.end(), vPointsQ1.begin(), vPointsQ1.end());
    vJoin.insert(vJoin.end(), vPointsQ2.begin(), vPointsQ2.end());
    vJoin.insert(vJoin.end(), vPointsQ3.begin(), vPointsQ3.end());
    vJoin.insert(vJoin.end(), vPointsQ4.begin(), vPointsQ4.end());
 
    int iIndex = 0;
    float fMinOrd = vJoin[0].ptPoint.y;
    for(unsigned int i = 1; i < vJoin.size(); i++){
        if(vJoin[i].ptPoint.y <= fMinOrd){
            fMinOrd = vJoin[i].ptPoint.y;
            iIndex = i;
        }
    }
 
    for(unsigned int i = iIndex; i < vJoin.size(); i++)
        pvResult->push_back(vJoin[i].ptPoint);
 
    for(unsigned int i = 0; i < iIndex; i++)
        pvResult->push_back(vJoin[i].ptPoint);
}

bool SortDirectionDesc(SPOINTWITHDIRECTION ptPoint1, SPOINTWITHDIRECTION ptPoint2)
{
    return ptPoint1.fProjection > ptPoint2.fProjection;
}

Búsqueda en rangos

Escribir un algoritmo que calcule, para cada rectángulo de lados paralelos a los ejes, el número de puntos del conjunto que contiene.

void PointsInRect(std::vector<Point2D> * pvPoints, Rect2D rcFrame, std::vector<Point2D> * pvResult)
{
    pvResult->clear();
 
    for(unsigned int i = 0; i < pvPoints->size(); i++){
        Point2D ptTemp = (*pvPoints)[i];
        if(ptTemp.x >= rcFrame.ptLeftBottom.x && ptTemp.y >= rcFrame.ptLeftBottom.y && ptTemp.x <= rcFrame.ptUpperRight.x && ptTemp.y <= rcFrame.ptUpperRight.y)
            pvResult->push_back(ptTemp);
    }
}

Geometrí­a Computacional - Problemas - Problemas Básicos

Contents

Geometría Computacional - Problemas - Problemas Básicos