如何确定一个点是否在一个矩形内？ [英] how to determine whether a point lies inside a rectangle?

问题描述

可能重复：
  <一href="http://stackoverflow.com/questions/2752725/finding-whether-a-point-lies-inside-a-rectangle-or-not">Finding一个点是否位于矩形里面还是没有

有一个面试问题是，如何确定一个点是否在一个矩形内

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交叉口），它的外面。

Pick a point that's definitely outside the rectangle. Then create a segment from that point to the point in question. Solve the linear equations for intersections between that segment and the segments that make up the rectangle. If you get exactly one intersection, the point is inside the rectangle. Otherwise (0 or 2 intersections), it's outside.

这是微不足道的延伸到基本上任何多边形 - 交点奇数指点在多边形的内部，和一个偶数意味着它的外

This is trivial to extend to essentially any polygon -- an odd number of intersections means the point is inside the polygon, and an even number means it's outside.

编辑：它可能不会立即明显，所以我强调，我们选择矩形（多边形）以外的点完全是任意的。我们可以选择任何时候，我们想只要我们相信它的多边形外。为了保持我们的计算方便，我们通常会做的就是挑选（P <子> X ，无穷大）（其中P <子> X 是x的点P，我们是坐标测试） - 也就是说，我们正在创造什么本质上是一个垂直的光线。这简化了测试了一下，因为我们只需要测试的一端点找到一个交集。它还简化了求解线性方程组的一点，它是几乎没有可认识的求解线性方程组了。我们真的只需要计算该行的P <子> X 的Y坐标，看看它是不是P <子>是更大。这样，求解线性方程分解为：

It may not be immediately obvious, so I'll emphasize that the point we pick outside the rectangle (polygon) is entirely arbitrary. We can pick whatever point we want as long as we're sure it's outside the polygon. To keep our computations easy, what we'll typically do is pick (P_x, infinity) (where P_x is the x coordinate of the point P that we're testing) -- that is, what we're creating is essentially a vertical ray. That simplifies testing a bit, because we only have to test against one end-point to find an intersection. It also simplifies solving the linear equations to the point that it's barely recognizable as solving linear equations anymore. We really just need to compute the Y coordinate for the line at the P_x, and see if it's greater than P_y. As such, solving the linear equation breaks down to:

1. 检查X值是否为X值的范围内为片段
2. ，如果它是，堵塞X值到该行的方程
3. 所产生的Y值测试是否大于P <子>是

如果这些通过，我们有一个交叉点。还要注意的是测试可以并行进行（方便的，如果我们这样做是对并行硬件像GPU）。

If those pass, we have an intersection. Also note that the tests can be carried out in parallel (handy if we're doing this on parallel hardware like a GPU).

这篇关于如何确定一个点是否在一个矩形内？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！