【转载】matlab如何判断一个点是否在多面体内

时间:2021-10-29 05:18:51

转载自:http://www.52souji.net/point-within-a-polyhedron/

我遇到的一个实际问题是:要在空位区域随机放置一定数量的原子,这些原子在空位区域任何一处存在的概念是相同的。空位区域是由包围这个空位周边的一些原子定义的。

如果这个空位区域是一个标准的长方体,那么问题就比较简单,只需要产生随机数,然后再将随机数沿着基矢方向进行相应的缩放。

对于不规则的空间区域,也可以采用类似的思想:将空位区域(多面体)扩大到一个长方体,即长方体刚好是多面体的包络。然后在长方体内部随机产生点,如果点在多面体内部就保留;不在多面体内部就舍去,重新产生。

这其中就出现一个基础问题:如何判断一个点P是否在一个多面体内?多面体由空间三维点定义。

我的初步想法:

1. 将多面体划分成四面体

2. 判断这个点是否在这些四面体内部

3. 如果这个点在任何一个四面体内部,那么这个点就在这个多面体内部;

4. 如果这个点不在任何一个四面体内部,那么这个点就不在这个多面体内部。

那么核心问题就转换为:

1. 如何将多面体划分成许多的四面体?

2. 如何判断一个点是否在四面体内部?

对于第一个问题,matlab提供直接使用的函数 DelaunayTri 可以实现。

对于第二个问题,matlab也提供一个函数 tsearchn ,但是这个函数的健壮性比较差,至少我的问题没法解决。

没办法,在网上找到了有关的算法,自己写了代码。算法如下:

四面体由四个顶点定义:

V1 = (x1, y1, z1)
V2 = (x2, y2, z2)
V3 = (x3, y3, z3)
V4 = (x4, y4, z4)

要检测的点定义为:P = (x, y, z)

可以根据这些点组成的4个行列式来进行判断:

D0

|x1 y1 z1 1|
|x2 y2 z2 1|
|x3 y3 z3 1|
|x4 y4 z4 1|

D1

|x y z 1|
|x2 y2 z2 1|
|x3 y3 z3 1|
|x4 y4 z4 1|

D2

|x1 y1 z1 1|
|x y z 1|
|x3 y3 z3 1|
|x4 y4 z4 1|

D3

|x1 y1 z1 1|
|x2 y2 z2 1|
|x y z 1|
|x4 y4 z4 1|

D4

|x1 y1 z1 1|
|x2 y2 z2 1|
|x3 y3 z3 1|
|x y z 1|

判据:

如果Di (i=1,2,3,4)与D0的符号都相同,即同为正,或同为负,那么P点就在四面体内部;

否则P点在四面体外部。

以上算法参考:Point in Tetrahedron Test

具体代码如下:

function inflag = inpolyhedron(point_set,p_detected)
% point_set: a set of points stores the coordinates
% p_detected: point to be detected
% inflag:
%      flag = 1: the point is in the polyhedron.
%      flag = 0: the point is not in the polyhedron.
% Powered by: Xianbao Duan xianbao.d@gmail.com
% stores the coordinates of the convexes.
tri = DelaunayTri(point_set);
% number of the tetrahedrons decomposed from the polyhedron
num_tet = size(tri,1);
t_inflag = zeros(1,11);
for i = 1:num_tet
 v1_coord = point_set(tri(i,1),:);
 v2_coord = point_set(tri(i,2),:);
 v3_coord = point_set(tri(i,3),:);
 v4_coord = point_set(tri(i,4),:);
 D0 =det( [v1_coord,1;v2_coord,1;v3_coord,1;v4_coord,1]);
 D1 = det([p_detected,1;v2_coord,1;v3_coord,1;v4_coord,1]);
 D2 = det([v1_coord,1;p_detected,1;v3_coord,1;v4_coord,1]);
 D3 = det([v1_coord,1;v2_coord,1;p_detected,1;v4_coord,1]);
 D4 = det([v1_coord,1;v2_coord,1;v3_coord,1;p_detected,1]);

 if D0*D1 > 0 && D0*D2>0 && D0*D3>0 && D0*D4 > 0
 t_inflag(i) = 1;
 break;
 end

end

if sum(t_inflag) > 0
 inflag = 1;
% disp('The point is in the polyhedron.');
else
 inflag = 0;
% disp('The point is not in the polyhedron.');
end

【转载】matlab如何判断一个点是否在多面体内的更多相关文章

  1. (转载)python判断一个字符串是否是小数

    转载自:牛牛杂货铺 最近在写代码的时候,发现一个问题,想判断一个字符串是不是一个合法的小数,发现字符串没有内置判断小数的方法,然后就写了一个判断字符串是否是小数,可以判断正负小数,代码如下: def ...

  2. c c++怎么判断一个字符串中是否含有汉字

    c c++怎么判断一个字符串中是否含有汉字 (2013-02-05 10:44:23) 转载▼     #include  #include  int main() { char sztext[] = ...

  3. Js判断一个单词是否有重复字母

    今天上午刷到一道题,大体是写一个方法判断一个单词中是否有重复的字母(或者说一个字符串中是否有重复的字符).我的思路是一个字符一个字符地遍历,如果发现有重复的停止: function isIsogram ...

  4. 判断一个面(Polygon)是不是矩形

    判断一个面是不是矩形在GIS中很长用的功能,那么怎么判断一个面是不是矩形呢. 这里先要弄懂一些概念,面是什么,先看OGC标准的定义. 我的英文水平有限,(有翻译更好的请留言,如果翻译的准确将被采纳)大 ...

  5. matlab inpolygon 判断点在多边形内

    如何判断一个点在多边形内部? xv= [0 3 3 0 0]; %x坐标 yv= [0 0 3 3 0];%y坐标 x=1.5; y=1.5; in=inpolygon(x,y,xv,yv) plot ...

  6. OpenGL判断一个点是否可见

    关于OpenGL中判断一个点是否可见,可以分成两种情况讨论:点在2D空间中和3D空间中的时候.并且"在2D空间中"可以看作"在3D空间中"的特殊情况. 温馨提示 ...

  7. C#中怎么判断一个数组中是否存在某个数组值

    (1) 第一种方法: ,,}; ); // 这里的1就是你要查找的值 ) // 不存在 else // 存在 (2) 第二种方法: string[] strArr = {"a",& ...

  8. js 判断一个元素是否在滚动的可视区域内,不在就固定到可视区域的上方。

    前言:最近工作中,有这样一个场景,判断一个元素是否在滚动的可视区域内,不在就固定到可视区域的上方.为了以后再次遇到,所以记录下来,并分享.转载请注明出处:https://www.cnblogs.com ...

  9. PostgreSQL判断一个表是否存在

    postgresql判断一个表是否存在: 方法一: select count(*) from pg_class where relname = 'tablename'; 方法二: select cou ...

随机推荐

  1. HDU 1512 Monkey King ——左偏树

    [题目分析] 也是堆+并查集. 比起BZOJ 1455 来说,只是合并的方式麻烦了一点. WA了一天才看到是多组数据. 盲人OI (- ̄▽ ̄)- Best OI. 代码自带大常数,比启发式合并都慢 [ ...

  2. Json在前台与后台之间的使用

     一.将前台数据,使用ajax中的post.get传到后台 $.ajax({ type: 'post', url: 'your url', data: $("form").seri ...

  3. Android Studio NDK 学习之接受Java传入的Int数组

    本博客是基于Android Studio 1.3 preview版本,且默认你已经安装了Android SDK, Android NDK. 用Android Studio新建一个工程叫AndroidJ ...

  4. maven配置编译路径

    在build标签下添加 <build> <sourceDirectory>src/main/java</sourceDirectory> <resources ...

  5. cocos2d-x路~使得第一个字游戏(一个)

    前言 去年的回忆.另外,在第三.他们开发了他们的第一场比赛四月,它是游戏.所以我决定走上独立开发的道路上.了.第一款游戏达到它应有的盈利水平.然而这款游戏开发后的时间里.都没再取得还有一款令自己惬意的 ...

  6. 护眼纯黑色VS2012配色方案

    这些天由于公司项目比较忙,所以天天盯着电脑8小时,而且我的开发工具VS2012是白色背景的所以每天下班都搞的眼睛巨疼. 今天在网上找到一个很好的配色方案,所以有同样烦恼的童鞋们可以试试哦! 展示下效果 ...

  7. ubuntu16&period;04下编译安装vim8&period;1

    之前写过一篇centos7下编译安装vim8.0的教程,ubuntu16.04相比centos7下安装过程不同在于依赖包名字的不同,其余都是一样.下面给出ubuntu16.04编译安装vim8.0需要 ...

  8. SQL Server 从2000复制数据到2008及以上版本的一种方法

    1.通过Linked Servers 执行sql出现错误提示,无法执行复制数据操作. sql: insert into tb_User select from [**.**.*.**].DB.dbo. ...

  9. Underscore&period;js 入门-常用方法介绍

    Underscore.js是一个很精干的库,压缩后只有4KB.它提供了几十种函数式编程的方法,弥补了标准库的不足,大大方便了JavaScript的编程.MVC框架Backbone.js就将这个库作为自 ...

  10. 前后端协调处理checkbox

    需求:页面属于一个弹出窗体,查询结果,用checkbox展示,选择后,把选中的结果传递给调用页面. 由于要取得后端写的checkbox控件的值,所以在后端处理最后的提交事件,用这个语句把结果传递到页面 ...