确定一个二维点是四边形内 [英] Determine if a 2D point is within a quadrilateral

问题描述

我工作的一个JS程序，我需要确定是否点中的四个角落的坐标系

I'm working on a JS program which I need to have determine if points are within four corners in a coordinate system.

可能有人点我一个答案的方向？

Could somebody point me in the direction of an answer?

我在寻找什么，我认为被称为凸四边形。也就是说，4 pretty的随机选择的拐角位置与所有角度大于180°小。

I'm looking at what I think is called a convex quadrilateral. That is, four pretty randomly chosen corner positions with all angles smaller than 180°.

感谢。

推荐答案

有两个比较简单的方法。第一种方法是从点到无限（实际上，多边形以外的任何点）画一个线，并计算有多少多边形的射线相交边。点是当且仅当计数为奇数的多边形内。

There are two relatively simple approaches. The first approach is to draw a ray from the point to "infinity" (actually, to any point outside the polygon) and count how many sides of the polygon the ray intersects. The point is inside the polygon if and only if the count is odd.

第二种方法是去周围的多边形顺序和每对顶点诉<子>我和V <子> I + 1 （折回第一个顶点，如果有必要），计算量（X - X <子>我）*（Y <子> I + 1 - 是<子>我） - （X <子> I + 1 - X <子>我）*（Y - 是<子>我）。如果这些量都具有相同的符号，该点位于多边形内。 （这些量是向量的积的Z分量（V <子> I + 1 - v <子>我）和（p - v <子>我 ），它们都具有相同的符号的条件是相同的条件下，p为在同一侧的每边的（左或右）。）

The second approach is to go around the polygon in order and for every pair of vertices v_i and v_i+1 (wrapping around to the first vertex if necessary), compute the quantity (x - x_i) * (y_i+1 - y_i) - (x_i+1 - x_i) * (y - y_i). If these quantities all have the same sign, the point is inside the polygon. (These quantities are the Z component of the cross product of the vectors (v_i+1 - v_i) and (p - v_i). The condition that they all have the same sign is the same as the condition that p is on the same side (left or right) of every edge.)

这两种方法都需要处理该点也正是上边缘或上的顶点的情况。首先，您需要决定是否要指望这样的点作为内多边形与否。然后，你需要相应地调整测试。请注意，轻微的数值舍入误差可以给一个虚假的答案两种方式。这只是一些你不得不忍受。

Both approaches need to deal with the case that the point is exactly on an edge or on a vertex. You first need to decide whether you want to count such points as being inside the polygon or not. Then you need to adjust the tests accordingly. Be aware that slight numerical rounding errors can give a false answer either way. It's just something you'll have to live with.

既然你有一个凸四边形，还有另一种方法。挑选任何三个顶点，并计算重心坐标的点的并第四顶点的相对于所述由三个选择顶点的三角形而形成的。如果点的重心坐标都是正并且比第四顶点的重心坐标的所有更小，则点是四边形内

Since you have a convex quadrilateral, there's another approach. Pick any three vertices and compute the barycentric coordinates of the point and of the fourth vertex with respect to the triangle formed by the three chosen vertices. If the barycentric coordinates of the point are all positive and all less than the barycentric coordinates of the fourth vertex, then the point is inside the quadrilateral.

P.S。只是找到了一个不错的网页。这里列出相当多的策略。其中有些是非常有趣的。

P.S. Just found a nice page here that lists quite a number of strategies. Some of them are very interesting.

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