确定一个由点数组定义的形状中是否包含点(x,y,z)。

Question

如果我有一个点数组（x，y，z），并且给定一个单独的点（x，y，z），那么我该使用什么代码来确定该点是否位于由数组定义的形状内？

我对此一无所知...

我正在使用C#。

编辑

谢谢大家的回复，从评论中我找到了这个链接（http://alienryderflex.com/polygon/），它很好地解释了这个过程。

谢谢！

FYI:

bool pointInPolygon() {
    
      int      i, j=polySides-1 ;
      boolean  oddNodes=NO      ;
    
      for (i=0; i<polySides; i++) {
        if (polyY[i]<y && polyY[j]>=y
        ||  polyY[j]<y && polyY[i]>=y) {
          if (polyX[i]+(y-polyY[i])/(polyY[j]-polyY[i])*(polyX[j]-polyX[i])<x) {
            oddNodes=!oddNodes; }}
        j=i; }
     
      return oddNodes; }

它需要一些工作，但那就是它的核心。

再次感谢

- Matt

---

可能是C#点在多边形内的问题的重复。 - Jim Lewis

这是一个众所周知的问题。请参见http://en.wikipedia.org/wiki/Point_in_polygon。 - Elian Ebbing

你的问题未明确说明。这个数组如何定义形状？它是由数组中的点构成的凸包吗？还是有一种多面三角形带顺序来定义一个多面体？ - Nordic Mainframe

@Jim，@Elian。不，不是这样的。它在多面体中的某个点。它有三维坐标。 - Nordic Mainframe

http://local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/ - Jaroslav Jandek

Answer 1

使用你知道在形状外部的一个点，并检查从该点到给定点的线是否通过形状的表面。如果它穿过奇数个表面，则给定点在形状内部。

- Guffa

---

优秀的回答，但实际上做起来比听起来更难。 - KeithS

你刚刚为马特创建了3个新问题。 - Amy West

这是我将要使用的方法。谢谢你的帮助。 - Matt

更好的方法可能是从您想要测试的点开始，并在循环中不断增加其x值。每当您的当前位置超过墙壁坐标时，将1添加到计数器中（除非上一个点也是墙壁）。如果在水平窗口上迭代后，您的计数器是奇数，则原始点在形状内。如果计数器是偶数，则原始点在形状外。您可以通过使用QuadTree来检查坐标是否为墙壁来使此方法更快。您还可以在开始时进行快速矩形检查以排除远离的点。 - John Kurlak

这是一个二维解决方案，但结论仍然有效。选择一个方向并前进，如果有奇数个交点，则您在形状内部，否则不在。您只需要适当修改if语句和循环以考虑三个维度，而不是两个。 - Nevyn

@Nevyn：不，正如所述，这是一个与维度无关的解决方案。该解决方案在二维、三维甚至四维或十四维中同样适用。当然，随着维度的增加，实际实现会变得更加复杂。 - Guffa

Answer 2

进一步回答Guffa的问题，要确定一条线是否与一个表面相交比听起来更困难。以下是相关数学知识：线和平面的相交。你需要使用这个基本算法（包括找到每个点的法向量，然后确定法向量和线之间的夹角以形成一个直角三角形，从而找到第三个点；WPF的Media3D库有关于点和向量的函数使得所有这些变得更加容易），然后确定你找到的点是否在该表面的平面内，且在该表面的边界内。为了做到这一点，你可以使用任何具有面积>0的该表面的2D投影，并执行“点在多边形内”的测试，这是你正在尝试做的“点在多面体内”的2D版本。

祝好运。

- KeithS

Answer 3

如果您正在Canvas上绘制形状，则这是一种快速简便的解决方案。

    private void Canvas_MouseMove(object sender, MouseEventArgs e)
    {
        if (e.OriginalSource is Polygon)
        {
            //do something
        }
    }

"

多边形

" 可以是来自 System.Windows.Shapes 的任何形状。

- Florian_Schaf