C語言中實(shí)現(xiàn)點(diǎn)在多邊形內(nèi)算法

本文是采用射線法判斷點(diǎn)是否在多邊形內(nèi)的C語言程序。這是個C語言的小算法的實(shí)現(xiàn)程序，本來不想放到這里?？墒?，當(dāng)我自己要實(shí)現(xiàn)這樣一個算法的時候，想在網(wǎng)上找個現(xiàn)成的，考察下來竟然一個符合需要的也沒有。我對自己大學(xué)讀書時寫的代碼沒有信心，所以，決定重新寫一個，并把它放到這里，以饗讀者。也增加一下BLOG的點(diǎn)擊量。
    首先定義點(diǎn)結(jié)構(gòu)如下：
    以下是引用片段：
    /* Vertex structure */
    typedef struct
    {
    double x, y;
    } vertex_t;
    本算法里所指的多邊形，是指由一系列點(diǎn)序列組成的封閉簡單多邊形。它的首尾點(diǎn)可以是或不是同一個點(diǎn)(不強(qiáng)制要求首尾點(diǎn)是同一個點(diǎn))。這樣的多邊形可以是任意形狀的，包括多條邊在一條絕對直線上。因此，定義多邊形結(jié)構(gòu)如下：
    以下是引用片段：
    /* Vertex list structure – polygon */
    typedef struct
    {
    int num_vertices; /* Number of vertices in list */
    vertex_t *vertex; /* Vertex array pointer */
    } vertexlist_t;
    為加快判別速度，首先計(jì)算多邊形的外包矩形(rect_t)，判斷點(diǎn)是否落在外包矩形內(nèi)，只有滿足落在外包矩形內(nèi)的條件的點(diǎn)，才進(jìn)入下一步的計(jì)算。為此，引入外包矩形結(jié)構(gòu)rect_t和求點(diǎn)集合的外包矩形內(nèi)的方法vertices_get_extent，代碼如下：
    以下是引用片段：
    /* bounding rectangle type */
    typedef struct
    {
    double min_x, min_y, max_x, max_y;
    } rect_t;
    /* gets extent of vertices */
    void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
    rect_t* rc /* out extent*/ )
    {
    int i;
    if (np > 0){
    rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y;
    }else{
    rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */
    }
    for(i=1; i
    {
    if(vl[i].x < rc->min_x) rc->min_x = vl[i].x;
    if(vl[i].y < rc->min_y) rc->min_y = vl[i].y;
    if(vl[i].x > rc->max_x) rc->max_x = vl[i].x;
    if(vl[i].y > rc->max_y) rc->max_y = vl[i].y;
    }
    }
    當(dāng)點(diǎn)滿足落在多邊形外包矩形內(nèi)的條件，要進(jìn)一步判斷點(diǎn)(v)是否在多邊形(vl：np)內(nèi)。本程序采用射線法，由待測試點(diǎn)(v)水平引出一條射線B(v，w)，計(jì)算B與vl邊線的交點(diǎn)數(shù)目，記為c，根據(jù)奇內(nèi)偶外原則(c為奇數(shù)說明v在vl內(nèi)，否則v不在vl內(nèi))判斷點(diǎn)是否在多邊形內(nèi)。