求助：怎样判断一个点是否在一个封闭区域内

Tiner

如题
请给出思路，谢谢。

secondage

求出区域的各个平面，如果这个点在所有平面的内侧，则是在区域内了

william9527

我的想法是先求出这个封闭区域的minx,miny,maxx,maxy（3D请加入Z），然后将点的坐标与这些边界变量进行比较即可！
请大家批评指正！

Tiner

谢谢各位
刚刚找到一种算法
从要判断的点，引一条射线，如果交点是奇数??，?明点在封闭区域内。
反之在封闭区域外。

不知道还有没有更好的算法。

lizzard

呵呵,这是图形学里的标准方法.
要更好的方法,...得悬赏了...
补充一点的是边界有交叉的,内外点的定义问题.

QiKi

请问这个区域是个什么样的区域？

dkxw

只能判断凸的区域，并且形成区域的多边形法线必须都是向内或者是向外的(假设向内)，对于形成区域的每个平面P，P由N(法线),V(平面到坐标原点距离)组成，A是你需要判定的点。然后 N(V-A)>0,就是在平面的内部。如果所有结果都>0，那么就在区域内

lyzcom

我觉得最好的办法就是用多边形面求法，判断该点是否在所有的面内，如果在，就是在空间内。

lizzard

1.3楼的求法好像不行如: " B. "  .在B方格的右下房,但是不在区域内.

2.8楼的多边形面求法是7楼的那种发发吗?7楼N(V-A)容易得出来吗?怎样求最简单?

3.封闭区域如何描述?顶点(边||面)描述?面描述?还是其他方法?
   如果是顶点描述(多边形)那么用奇偶点法应该比较方便把.以下算法请大家指正:
  假定此n边多边形没有边界(边,面)交叉部分,可以是凹或凸多边形
  a.选定一个方向(如x正向)
  b.从判定点P引出一条射线,初始化计数器cP=0
  c.依次判断该直线是否传过各边界,如果是cP++;知道所有边界都判断完
     (这里以2d,x正方向为例:
      for(i=0;i<n;i++){
          if(MAX(Line(i).star.x,Line(i).end.x)&lt.x)   continue;//第i边Line(n)最大x坐标比p小
                                                                                   //则不可能有焦点go下一个
         if(Line(i).star.y*Line(i).end.y<0) {cp++;continue;}      //传过第i个边界
         else if(Line(i).star.y*Line(i).end.y==0&&Line(i).star.y!=0) //边界点
              {Line(i+1).star=Line(i).star; continue;}                  //这里line[n+1]改变了
          }            
  d.判断cP的奇偶,奇内偶外

4.上面只是n边多边形即边界是直线或平面的简陋算法,而且在边界上的点没有定义内外.嗯,其实多边形面求法应该算是比较完整简洁的算法,呵呵,还是想求 N(V-A)>0 的算法.         

cys2004

1。在实际运用中，一般都是要考虑点与多个封闭区域的关系，因此，可考虑：采用AABB层次包围盒处理
2。如果非要考虑点与单个封闭区域的关系的话，需要区分是否凸多面体，如果是，要好办些。
3。射线法倒是适合所有的多面体，但是，存在奇异情况：如，射线刚好经过多面体顶点、射线在某个面内或者射线与边共线。