• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            poj 1584 A Round Peg in a Ground Hole

               這個題需要多個計算幾何算法。第一個是判斷一系列點是否能夠構成凸多邊形,第二個是判斷一個點是否在一個簡單多邊形內(nèi)部,
            第三個是求一個點到一條線段(或者說直線)的距離,第四個是判斷一個圓是否則一個凸多邊形內(nèi)部。
               其實,我是要判斷一個圓是否則一個凸多邊形內(nèi)部而用到算法二和三。其實,有不需要判斷圓心是否則多邊形內(nèi)部的算法。
               算法一的思想,求所有邊的偏轉方向,必須都是逆時針或者順時針偏轉。算法二則是我前面發(fā)的那篇改進弧長法判斷點和多邊形的關系,
            算法三尤其簡單,直線上面取2點,用叉積求出這三點構成的三角形面積的2倍,再除以底邊。算法四則是先判斷圓心在多邊形內(nèi)部,然后
            判斷圓心到所有邊的距離要大于圓的半徑。
               貼出代碼,純粹為了以后作為模版使用等,防止遺忘,方便查找,其實現(xiàn)在也能手敲出來了。

             代碼如下:
            #include <stdio.h>
            #include <string.h>
            #include <math.h>
            #include <algorithm>
            #include <vector>
            using namespace std;

            const double fPre = 1e-8;
            int DblCmp(double fD)
            {
                if (fabs(fD) < fPre)
                {
                    return 0;
                }
                else
                {
                    return fD > 0 ? 1 : -1;
                }
            }

            struct Point
            {
                double x, y;
                bool operator == (const Point& p)
                {
                    return DblCmp(x - p.x) == 0 && DblCmp(y - p.y) == 0;
                }
            };

            Point operator-(const Point& a, const Point& b)
            {
                Point p;
                p.x = a.x - b.x;
                p.y = a.y - b.y;
                return p;
            }

            double Det(double fX1, double fY1, double fX2, double fY2)
            {
                return fX1 * fY2 - fX2 * fY1;
            }

            double Cross(Point a, Point b, Point c)
            {
                return Det(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
            }

            bool IsConvexPolygon(vector<Point>& vp)
            {
                int nN = vp.size();
                int nDirection = 0;
                bool bLine = true;//避免所有點共線
                for (int i = 0; i < nN; ++i)
                {
                    int nTemp = DblCmp(Cross(vp[i], vp[(i + 1) % nN], vp[(i + 2) % nN]));
                    if (nTemp)
                    {
                        bLine = false;
                    }
                    //這次的方向和上次的方向必須是相同的或者是3點和3點以上共線的情況
                    if (nDirection * nTemp < 0)
                    {
                        return false;
                    }
                    nDirection = nTemp;
                }
                return bLine == false;
            }

            int GetQuadrant(Point p)
            {
                return p.x >= 0 ? (p.y >= 0 ? 0 : 3) : (p.y >= 0 ? 1 : 2);
            }

            bool IsPtInPolygon(vector<Point>& vp, Point p)
            {
                int nN = vp.size();
                int nA1, nA2, nSum = 0;
                int i;
                
                nA1 = GetQuadrant(vp[0] - p);
                for (i = 0; i < nN; ++i)
                {
                    int j = (i + 1) % nN;
                    if (vp[i] == p)
                    {
                        break;
                    }
                    int nC = DblCmp(Cross(p, vp[i], vp[j]));
                    int nT1 = DblCmp((vp[i].x - p.x) * (vp[j].x - p.x));
                    int nT2 = DblCmp((vp[i].y - p.y) * (vp[j].y - p.y));
                    if (!nC && nT1 <= 0 && nT2 <= 0)
                    {
                        break;
                    }
                    nA2 = GetQuadrant(vp[j] - p);
                    switch ((nA2 - nA1 + 4) % 4)
                    {
                        case 1:
                            nSum++;
                            break;
                        case 2:
                            if (nC > 0)
                            {
                                nSum += 2;
                            }
                            else
                            {
                                nSum -= 2;
                            }
                            break;
                        case 3:
                            nSum--;
                            break;
                    }
                    nA1 = nA2;
                }
                
                if (i < nN || nSum)
                {
                    return true;
                }
                return false;
            }

            double PtDis(Point a, Point b)
            {
                return sqrt((a.x - b.x) * (a.x - b.x) + (b.y - a.y) * (b.y - a.y));
            }
            //點p到直線ab的距離
            //h = (2 * Spab) / |ab|
            double GetDis(Point a, Point b, Point p)
            {
                return fabs(Cross(a, b, p)) / PtDis(a, b);
            }

            bool IsCircleInPolygon(vector<Point>& vp, Point p, double fR)
            {
                if (!IsPtInPolygon(vp, p))
                {
                    return false;
                }
                
                int nN = vp.size();
                for (int i = 0; i < nN; ++i)
                {
                    if (GetDis(vp[i], vp[(i + 1) % nN], p) < fR)
                    {
                        return false;
                    }
                }
                return true;
            }

            int main()
            {
                int nN;
                double fR, fPx, fPy;
                vector<Point> vp;
                Point p;
                
                while (scanf("%d%lf%lf%lf", &nN, &fR, &fPx, &fPy), nN >= 3)
                {
                    vp.clear();
                    for (int i = 0; i < nN; ++i)
                    {
                        scanf("%lf%lf", &p.x, &p.y);
                        vp.push_back(p);
                    }
                    
                    if (IsConvexPolygon(vp))
                    {
                        p.x = fPx;
                        p.y = fPy;
                        if (IsCircleInPolygon(vp, p, fR))
                        {
                            printf("PEG WILL FIT\n");
                        }
                        else
                        {
                            printf("PEG WILL NOT FIT\n");
                        }
                    }
                    else
                    {
                        printf("HOLE IS ILL-FORMED\n");
                    }
                }
                
                return 0;
            }

            posted on 2012-07-20 21:41 yx 閱讀(1040) 評論(0)  編輯 收藏 引用 所屬分類: 計算幾何

            <2012年7月>
            24252627282930
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            導航

            統(tǒng)計

            公告

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            me

            好友

            同學

            網(wǎng)友

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久综合九色综合久99 | 99久久国产亚洲综合精品| 久久亚洲AV成人无码国产 | 亚洲精品国产综合久久一线| 国产99久久久国产精品~~牛| 国产精品一区二区久久精品| 久久久久久亚洲精品成人| 日本久久久久亚洲中字幕| 久久久久久精品成人免费图片| 欧美日韩精品久久免费| 三级三级久久三级久久| 久久精品免费一区二区| 人妻无码αv中文字幕久久琪琪布 人妻无码久久一区二区三区免费 人妻无码中文久久久久专区 | 亚洲欧美精品伊人久久| 91精品国产91久久久久久| 青青青青久久精品国产| 久久人人爽人人爽人人片AV麻豆| 久久久久亚洲av成人无码电影| 亚洲国产精品成人久久蜜臀| 狠狠色婷婷久久综合频道日韩| 久久亚洲欧美国产精品| 岛国搬运www久久| 久久久亚洲AV波多野结衣| 久久超碰97人人做人人爱| 国产成人久久久精品二区三区| 性做久久久久久久久久久| 性色欲网站人妻丰满中文久久不卡| AV色综合久久天堂AV色综合在| 久久国产成人午夜aⅴ影院| 久久久久se色偷偷亚洲精品av| 久久久久久夜精品精品免费啦| 久久九九亚洲精品| 久久频这里精品99香蕉久| 国产精品久久久久久一区二区三区| 国产香蕉97碰碰久久人人| 伊人久久大香线蕉av不卡| 91超碰碰碰碰久久久久久综合| 精品综合久久久久久97| 99久久亚洲综合精品成人| 久久久亚洲AV波多野结衣| 精品国产91久久久久久久a|