求自相交多边形外边界的算法实现方案（附C语言示例代码）

我有一个可任意自相交的多边形，由边界点数组定义（数组中连续两点构成多边形边界的一条边，最后一个点默认与第一个点相连）。需要计算该多边形的外边界（忽略自相交产生的所有孔洞），注意这不是凸包，而是多边形的外包络——其所有边均来自原多边形的边界边。

以下是一段生成随机多边形的C语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct Point2D
{
    double x;
    double y;
} Point2D;

int main()
{
    srand( time( NULL ) );
    const unsigned int POLY_SIZE = 20;
    //Polygon, two consecutive array indices form a line in the boundary of the
    // polygon. last point assumed connects to the first point
    Point2D *pPoly = malloc( sizeof( Point2D ) * POLY_SIZE );

    //Generate the Polygon
    const double polyRangeMax = 100.0;
    const double polyRangeMin = -100.0;
    const double polyPointRange = (polyRangeMax - polyRangeMin); 
    const double polyRangeScale = polyPointRange / RAND_MAX;
    for( unsigned int polyPointIdx = 0; polyPointIdx < POLY_SIZE; ++polyPointIdx )
    {
        pPoly[polyPointIdx].x = polyRangeMin + ( rand() * polyRangeScale );
        pPoly[polyPointIdx].y = polyRangeMin + ( rand() * polyRangeScale );
    }

    for( unsigned int polyPointIdx = 0; polyPointIdx < POLY_SIZE; ++polyPointIdx )
    {
        printf("<%f,%f>",pPoly[polyPointIdx].x,pPoly[polyPointIdx].y);
        if( polyPointIdx == POLY_SIZE-1 )
        {
            printf("\n");
        }
        else
        {
            printf(" ");
        }
    }


    //Calculate Outer boundary of the polygon (it itself is a polygon), takes at most same amount of memory as pPoly above;
    unsigned int boundaryPolyPointCount = 0; //TODO calculate this alongside the poly
    Point2D *pOuterBoundaryPoly = malloc( sizeof( Point2D ) * POLY_SIZE );


    //TODO



    for( unsigned int polyPointIdx = 0; polyPointIdx < boundaryPolyPointCount; ++polyPointIdx )
    {
        printf("<%f,%f>",pOuterBoundaryPoly[polyPointIdx].x,pOuterBoundaryPoly[polyPointIdx].y);
        if( polyPointIdx == POLY_SIZE-1 )
        {
            printf("\n");
        }
        else
        {
            printf(" ");
        }
    }

    free( pOuterBoundaryPoly );
    free( pPoly );
    return 0;
}

我在Stack Overflow上查询到的相关答案均指向JavaScript或Python库，未提及具体算法本身。若已有相关答案，请告知，我会关闭此问题，但目前未找到合适内容。

内容的提问来源于stack exchange，提问作者yosmo78