注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Tsecer的回音岛

Tsecer的博客

 
 
 

日志

 
 

如何判断一个点是否在矩形之内及C++的操作符重载  

2017-12-18 00:15:02|  分类: 计算机图形学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

一、常规情况
通常情况下,这个矩形都是和坐标系平行的一个矩形,例如典型的windows系统中,一个窗口总是和屏幕坐标平行的。在这种情况下,判断一个点是否在矩形之内就非常简单:只需要判断该点在x和y轴方向是否在矩形范围内即可。
简单代码如下,当然,如果在确定x1和x2关系的情况,实现可以更加简洁。
tsecer@harry: cat point.in.rect.cpp 
struct rect
{
int x1,y1;
int x2,y2;
bool InRect(int x, int y)
{
return (x1 -x) * (x2 - x) <= 0 && (y1 - y) * (y2 - y) <= 0;
}
};

二、考虑旋转之后的矩形
如果把矩形在坐标系中旋转一下,此时判断一个给定点是否在举行内就更加麻烦一些。直观的想法是把矩形和点都进行坐标系旋转,旋转为和坐标轴平行的正经矩形,此时判断就简单很多。问题在于,判断逻辑比较简单,但是旋转比较复杂,并且代价很高,需要计算cos、sin等浮点运算。
这个时候,如果利用矩阵点乘的几何意义,这个判断就比较简洁。向量的点乘结果为两个向量的长度和夹角theta的cos theta的乘积。所以如果一个点在矩形之内,那么它在矩形一边上的投影(cos theta)就应该小于另外一边。
假设说待判断点为P,一边为A和B,并且PA与PB之间的夹角为theta,那么|PA|*cos theta <|AB| 两遍同时乘以|AB|, |PA||AB| cos theta < |AB| |AB|,由于AB重合,所以cos theta为1,上面的表达式就是
向量 PA 和 AB 的点乘 小于 AB向量自己的点乘。
这个是一个最关键的判断条件,也就是下面的讨论所表达的主要观点https://math.stackexchange.com/questions/190111/how-to-check-if-a-point-is-inside-a-rectangle。我们使用代码实现下,其中使用的是一个变长为2的正方形,倾斜45度。

tsecer@harry: cat point.in.rect.cpp
#include <stdio.h>

struct point
{
int x, y;
point():
x(),y()
{}

point(int ix, int iy)
:x(ix),y(iy)
{}

point operator - (point p)
{
 return point(x - p.x, y - p.y);
}

int operator *(point p)
{
return x * p.x + y * p.y;
}

};

struct rect
{
point p[3];
rect(point p1, point p0, point p2)
{
p[0] = p0;
p[1] = p1;
p[2] = p2;
}
bool pointinrect(point pp)
{
for (int i = 1; i < 3; i++)
{
int iMid = (pp - p[0]) * (p[i] - p[0]);
int iUp  = (p[i] - p[0]) * (p[i] - p[0]);
if (!(0 <= iMid && iMid <= iUp))
{
return false;
}
}
return true;
}
};

int main(int argc, char * argv[])
{
rect r(point(0,2), point(2, 0), point(4, 2));
for (int i = 0; i < 6; i++)
{
for (int j = 0; j < 6; j++)
{
printf("point x %d y %d %s in rect\n", i, j, r.pointinrect(point(i, j))? "" : "not" );
}
}
return 0;
}
tsecer@harry: g++ point.in.rect.cpp
tsecer@harry: ./a.out 
point x 0 y 0 not in rect
point x 0 y 1 not in rect
point x 0 y 2  in rect
point x 0 y 3 not in rect
point x 0 y 4 not in rect
point x 0 y 5 not in rect
point x 1 y 0 not in rect
point x 1 y 1  in rect
point x 1 y 2  in rect
point x 1 y 3  in rect
point x 1 y 4 not in rect
point x 1 y 5 not in rect
point x 2 y 0  in rect
point x 2 y 1  in rect
point x 2 y 2  in rect
point x 2 y 3  in rect
point x 2 y 4  in rect
point x 2 y 5 not in rect
point x 3 y 0 not in rect
point x 3 y 1  in rect
point x 3 y 2  in rect
point x 3 y 3  in rect
point x 3 y 4 not in rect
point x 3 y 5 not in rect
point x 4 y 0 not in rect
point x 4 y 1 not in rect
point x 4 y 2  in rect
point x 4 y 3 not in rect
point x 4 y 4 not in rect
point x 4 y 5 not in rect
point x 5 y 0 not in rect
point x 5 y 1 not in rect
point x 5 y 2 not in rect
point x 5 y 3 not in rect
point x 5 y 4 not in rect
point x 5 y 5 not in rect
tsecer@harry: 

代码中要求iMid >= 0,这个可以保证 PA 和 AB之间的夹角在90以内,由于另外一边同样要求 PA 和 AC 之间夹角在90度以内,所以这个边就PA就不可能在矩形之外(因为BA和CA之间夹角为90)。

三、C++算符的重载
《ANSI C++ Reference.pdf》
13.5 Overloaded operators
6 An operator function shall either be a nonstatic member function or be a nonmember function and have at least one parameter whose type is a class, a reference to a class, an enumeration, or a reference to an enumeration. It is not possible to change the precedence, grouping, or number of operands of operators. The meaning of the operators =, (unary) &, and , (comma), predefined for each type, can be changed for specific types by defining operator functions that implement these operators. Operator functions are inherited the same as other functions, but because an instance of operator= is automatically constructed for each class (12.8, 13.5.3), operator= is never inherited by a class from its bases.
这里的强限制在于,至少要有一个参数的类型是类、类的引用、枚举、或者枚举的引用。并且不能改变操作符的优先级、分组或者是操作数的个数。

值得注意的是,这个地方并没有对操作符的返回值类型进行任何约束,也就是说 == 操作符的结果并不一定需要是返回一个bool值。例如

tsecer@harry: cat -n c++.operator.overload.cpp
     1 #include <stdio.h>
     2
     3 struct S
     4 {
     5 S operator == (int i)
     6 {
     7 return *this;
     8 }
     9
    10 int x;
    11
    12 };
    13
    14 int main()
    15 {
    16 S s;
    17 S ss = s==10;
    18
    19 if (s == 10)
    20 {
    21 return 0;
    22 }
    23 }
tsecer@harry: g++ c++.operator.overload.cpp
c++.operator.overload.cpp: In function ‘int main()’:
c++.operator.overload.cpp:19:7: error: could not convert ‘s.S::operator==(10)’ from ‘S’ to ‘bool’
 if (s == 10)
       ^
tsecer@harry: 


可以看到,只是在使用的时候出错,函数返回任意类型都可以通过编译。

  评论这张
 
阅读(37)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018