前幾天需要做一個(gè)鼠標(biāo)點(diǎn)擊判定，具體是判斷一個(gè)點(diǎn)是否在某個(gè)凸四邊形中。
最簡(jiǎn)單的方法莫過(guò)于判斷鼠標(biāo)點(diǎn)是否在2個(gè)三角形中。但是很多判定方法都是有問(wèn)題的，比如說(shuō)
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)就判定為沒(méi)有在其內(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ì)器來(lái)說(shuō)無(wú)所謂了，如果有好的準(zhǔn)確算法，可以討論