• <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>

            戰(zhàn)魂小筑

            討論群:309800774 知乎關(guān)注:http://zhihu.com/people/sunicdavy 開源項(xiàng)目:https://github.com/davyxu

               :: 首頁(yè) :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::
              257 隨筆 :: 0 文章 :: 506 評(píng)論 :: 0 Trackbacks

            前幾天需要做一個(gè)鼠標(biāo)點(diǎn)擊判定,具體是判斷一個(gè)點(diǎn)是否在某個(gè)凸四邊形中。

            最簡(jiǎn)單的方法莫過于判斷鼠標(biāo)點(diǎn)是否在2個(gè)三角形中。但是很多判定方法都是有問題的,比如說

             

            copy自IndieLib

            bool Triangle2D::Inside2( const Vector2& p )
            {
                Vector2 v0 = mP3 - mP1;
                Vector2 v1 = mP2 - mP1;
                Vector2 v2 = p - mP1; 
            
                // Compute dot products
                float dot00 =  Vector2::DotProduct( v0, v0 );
                float dot01 =  Vector2::DotProduct( v0, v1 );
                float dot02 =  Vector2::DotProduct( v0, v2 );
                float dot11 =  Vector2::DotProduct( v1, v1 );
                float dot12 =  Vector2::DotProduct( v1, v2 ); 
            
                // Compute barycentric coordinates
                float invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
                float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
                float v = (dot00 * dot12 - dot01 * dot02) * invDenom; 
            
                // Check if point is in triangle
                return (u > 0) && (v > 0) && (u + v < 1);
            } 
            
              
            

            Google出的某人代碼

            float Triangle2D::CrossProduct3(const Vector2& p1,const Vector2& p2, const Vector2& p0 )
            {
                return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
            } 
            
            bool Triangle2D::Inside( const Vector2& p )
            {
                return (CrossProduct3(mP1,p,mP2)*CrossProduct3(mP3,p,mP2)<0) &&
                       (CrossProduct3(mP2,p,mP1)*CrossProduct3(mP3,p,mP1)<0) &&
                       (CrossProduct3(mP1,p,mP3)*CrossProduct3(mP2,p,mP3)<0);
            } 
            

             

            這2個(gè)方法都有缺陷,當(dāng)點(diǎn)在三角形邊上時(shí),就無(wú)法得出。當(dāng)用在一個(gè)正方形判斷時(shí),正方形中心點(diǎn)就判定為沒有在其內(nèi)部,顯然是一個(gè)錯(cuò)誤。

             

            之后,又Google出某幾個(gè)大俠的算法和思想,考慮了下,判定點(diǎn)與四邊形重心點(diǎn)的線段是否與四邊形4條邊相交,相交時(shí),其在四邊形外部,反之亦然。

            bool Quadrangle::Inside2( const Vector2& p )
            {
                Vector2 c = Segement2D::GetCrossPoint( mP1, mP3, mP2, mP4 ); 
            
                return !(Segement2D::Intersect( mP1, mP2, c, p) || 
                       Segement2D::Intersect( mP2, mP3, c, p) ||
                       Segement2D::Intersect( mP3, mP4, c, p) ||
                       Segement2D::Intersect( mP4, mP1, c, p) );
            } 
            
            bool Segement2D::Intersect( const Vector2& p1, const Vector2& p2,const Vector2& p3, const Vector2& p4 )
            {
                float gradab, gradcd, ycptab, ycptcd, interceptX, intercepty; 
            
                // In order to avoid divisions by zero
                //if (mP1.y == mP2.y)
                //    mP2.y += 0.0001f; 
            
                //if (mP1.x == mP2.x)
                //    mP2.x += 0.0001f; 
            
                //if (seg.mP1.y == seg.mP2.y)
                //    seg.mP2.y += 0.0001f; 
            
                //if (seg.mP1.x == seg.mP2.x)
                //    seg.mP2.x += 0.0001f; 
            
                // Calculates the intersection between the two lines
                gradab = (p1.y - p2.y) / (p1.x - p2.x);
                gradcd = (p3.y - p4.y) / (p3.x - p4.x); 
            
                ycptab = p1.y - p1.x * gradab;
                ycptcd = p3.y - p3.x * gradcd;
                interceptX = (ycptab - ycptcd) / (gradcd - gradab);
                intercepty = (ycptab - (gradab * ycptcd) / gradcd) / (1 - gradab / gradcd); 
            
                // Checking in the intersection is inside the segment
                if (!((interceptX >= p1.x && interceptX <= p2.x) || (interceptX >= p2.x && interceptX <= p1.x)))
                    return 0; 
            
                if (!((intercepty >= p1.y && intercepty <= p2.y) || (intercepty >= p2.y && intercepty <= p1.y)))
                    return 0; 
            
                if (!((interceptX >= p3.x && interceptX <= p4.x) || (interceptX >= p4.x && interceptX <= p3.x)))
                    return 0; 
            
                if (!((intercepty >= p3.y && intercepty <= p4.y) || (intercepty >= p4.y && intercepty <= p3.y)))
                    return 0; 
            
                return 1;
            } 
            
            Vector2 Segement2D::GetCrossPoint(const Vector2& p1, const Vector2& p2, const Vector2& q1, const Vector2& q2)
            {
                //必須相交求出的才是線段的交點(diǎn),但是下面的程序段是通用的 
            
                /*根據(jù)兩點(diǎn)式化為標(biāo)準(zhǔn)式,進(jìn)而求線性方程組*/
                Vector2 crossPoint;
                //求x坐標(biāo)
                float tempLeft = (q2.x - q1.x) * (p1.y - p2.y) - (p2.x - p1.x) * (q1.y - q2.y);
                float tempRight = (p1.y - q1.y) * (p2.x - p1.x) * (q2.x - q1.x) + q1.x * (q2.y - q1.y) * (p2.x - p1.x) - p1.x * (p2.y - p1.y) * (q2.x - q1.x);
                crossPoint.x = tempRight / tempLeft;
                //求y坐標(biāo)
                tempLeft = (p1.x - p2.x) * (q2.y - q1.y) - (p2.y - p1.y) * (q1.x - q2.x);
                tempRight = p2.y * (p1.x - p2.x) * (q2.y - q1.y) + (q2.x- p2.x) * (q2.y - q1.y) * (p1.y - p2.y) - q2.y * (q1.x - q2.x) * (p2.y - p1.y);
                crossPoint.y = tempRight / tempLeft; 
            
                return crossPoint;
            }
            

            這個(gè)算法效率并不是很高,但對(duì)于設(shè)計(jì)器來說無(wú)所謂了,如果有好的準(zhǔn)確算法,可以討論


            評(píng)論

            # re: 判斷點(diǎn)在凸四邊形中 2010-01-08 10:33 forestkeeper
            這題coding沒那么麻煩吧。。。直接用向量分析很容易啊。  回復(fù)  更多評(píng)論
              

            # re: 判斷點(diǎn)在凸四邊形中 2010-01-08 11:12 陳梓瀚(vczh)
            過判斷的點(diǎn)來一橫線,求出所有焦點(diǎn)(最多兩個(gè)),然后看看左邊如果有一個(gè)交點(diǎn)那就是在里面了,當(dāng)你求交到頂點(diǎn)的時(shí)候,如果頂點(diǎn)的兩條邊在你的橫線的同一側(cè),算兩個(gè)交點(diǎn)。

            何必呢  回復(fù)  更多評(píng)論
              

            # re: 判斷點(diǎn)在凸四邊形中 2010-01-08 20:57 陳昱(CY)
            凸n邊型知道各頂點(diǎn)圍繞順序的話,向量叉乘最容易  回復(fù)  更多評(píng)論
              

            # re: 判斷點(diǎn)在凸四邊形中[未登錄] 2010-01-12 17:39 feng
            凸四邊形構(gòu)造出來四條直線,設(shè)解析式是
            f_1(x,y), f_2(x,y), f_3(x,y), f_4(x,y)
            將點(diǎn)坐標(biāo)帶進(jìn)去,計(jì)算一下這些解析式的數(shù)值即可判斷  回復(fù)  更多評(píng)論
              

            # re: 判斷點(diǎn)在凸四邊形中 2010-03-25 17:28 hoodlum1980
            (1)是通用的射線法,即判斷改點(diǎn)出發(fā)的射線和多邊形相交次數(shù),那么無(wú)所謂幾邊形也無(wú)所謂凸否。
            (2)是構(gòu)建這樣一個(gè)多邊形區(qū)域,然后用PtInRgn判斷好了。  回復(fù)  更多評(píng)論
              

            久久亚洲中文字幕精品一区四 | 久久精品国产精品亚洲下载| 91精品国产高清久久久久久91| 亚洲狠狠综合久久| 亚洲国产精品无码久久九九| 久久精品人人做人人妻人人玩| 久久er热视频在这里精品| 亚洲国产精品狼友中文久久久| 欧美噜噜久久久XXX| 久久99精品久久久久久野外| 亚洲中文久久精品无码ww16 | 欧美久久综合性欧美| 欧美激情精品久久久久久久| 久久精品人人做人人爽电影蜜月| 国产激情久久久久影院| 久久亚洲精品成人AV| 99久久综合国产精品免费| 亚洲欧美精品伊人久久| 久久精品午夜一区二区福利| 一本色道久久88综合日韩精品| 日本精品久久久久中文字幕8| 人妻少妇久久中文字幕一区二区| 久久久久亚洲精品天堂久久久久久| 99久久无码一区人妻a黑| 亚洲精品无码久久久久久| 久久亚洲精品国产精品婷婷| 精品久久久久久无码人妻热 | 久久久久久久综合综合狠狠| 99久久超碰中文字幕伊人| 久久精品aⅴ无码中文字字幕不卡| 无码8090精品久久一区| 久久免费香蕉视频| 久久国产综合精品五月天| 精品久久久久久久中文字幕| 日本免费一区二区久久人人澡| 99久久综合狠狠综合久久止| AV狠狠色丁香婷婷综合久久| 7777久久亚洲中文字幕| 久久精品国产99国产电影网| 日本精品久久久久中文字幕8| 四虎国产精品免费久久5151|