There is an interview question that is, "How to determine whether a point lies inside a rectangle"
Note that the rectangle could be rotated as well. So the simple solution of checking point inside the rectangle doesn't stands valid here...
Please share your thoughts on this question..
I found a link on internet, and was trying to understand it, but failed.... Please if any body out here can give complete solution with bit of computer graphics logic, because i have forgotten all the basics....How to determine if a point is inside rectangle.
最佳答案
选择一个绝对在矩形之外的点。然后创建从该点到该问题的线段。求解该线段和组成矩形的线段之间的交点的线性方程式。如果恰好得到一个交点,则该点位于矩形内。否则(0个或2个交叉点)在外面。
将其扩展到基本上任何多边形都是微不足道的-奇数个交点表示该点在多边形内,偶数个数表示在多边形外。
编辑:这可能不是立即显而易见的,所以我要强调一点,我们在矩形(多边形)外部选取的点是完全任意的。只要确定点在多边形之外,我们就可以选择任意点。为了使我们的计算容易,我们通常要做的是拾取(Px,无穷大)(其中Px是我们正在测试的点P的x坐标)-也就是说,我们创建的基本上是一个垂直射线。这简化了一点测试,因为我们只需要针对一个端点进行测试以找到一个相交。它也简化了线性方程的求解,以至于几乎不再被视为求解线性方程。我们真的只需要计算Px处的线的Y坐标,然后查看它是否大于Py。这样,求解线性方程可分解为: