随笔-341  评论-2670  文章-0  trackbacks-0

    首先吐槽一下:今天考IT项目管理,100道选择题。前几天考配置管理,10道大题。如今的老师都喜欢走极端……

    这个方法是在考完试回宿舍的路上想到的,适用于2D与3D。主要想法是这样的。给定两个几何图形A、B,把A和B都分成『内『、『外』两部分。A的『内』就是处于B内部的部分。于是A和B就变成了A内、A外、B内、B外。然后就有如下公式:
    ·A and B=A外+B外
    ·A sub B=A外+B内
    ·A or B=A内+B内
    ·A xor B=A外+B外+A内+B内
    这种数据结构是为了满足如下算法:一个A点在图形内<==>过这个点的直线交图形与点集P,其中|{Pi|Pi<=A}|和|{Pi|Pi>=A}|都是奇数。注意我们使用的是<=和>=,这样的话两个集合的数量的奇偶性都是一致的。这个算法无论2D、3D多边形还是3D多面体都能适用,就算是这个图形有孔(镶嵌)也可以,而且跟凹凸体无关。这个算法只有一种情况是不能用的:就是自己跟自己有交叉,譬如我们习惯的5条直线构成五角星的画法。这样的话首先要对这个图形进行处理,成为镶嵌的图形。

    让我们来图示一下。现在我们给出两个回形的红色和蓝色向前多边形:

    然后我们把两个图形分为内外一共四部分,其中内使用粗线:

   
    我们把这个图形转换成拓扑结构,得到了下面的连线图。现在让我们来求蓝 sub 红,也就是蓝外+红内:

    我们可以很容易地看到现在图形分成了4各部分,因为下面的拓扑结构构成的图一共有4个连同体。

    后来我自己做过实验,求蓝 And  红的时候图形会被分成6个连同体,其中有5个是镶嵌的孔。但是哪个是孔在整个过程中并没有关系。因为我们只需要把所有的Component求出来,内Component就是Component内的一点在另一个图里,而且判断是不是内部点的算法已经给出了。整个流程跟哪一个连同体是孔并没有关系。而且在实际情况下,2D多边形和3D多面体的渲染并不在乎哪个是孔,可以正确渲染出来。唯独3D多边形在乎。这种情况下再慢慢处理吧。而且判断的算法也是差不多的。不过我似乎没有见到3D多边形的布尔运算有什么常见的应用。

    期末考过后就可以开始写布尔运算的代码了。
posted on 2008-06-16 19:20 陈梓瀚(vczh) 阅读(4487) 评论(7)  编辑 收藏 引用 所属分类: 2D

评论:
# re: 使用拓扑进行几何图形布尔运算 2008-06-16 20:03 | 长江三峡
比较高深
学习一下  回复  更多评论
  
# re: 使用拓扑进行几何图形布尔运算 2008-06-16 20:18 | 陈梓瀚(vczh)
第二幅图有点小bug,不过不改了,知道什么意思就好。红色的细线应该是DE和LM。  回复  更多评论
  
# re: 使用拓扑进行几何图形布尔运算 2008-06-17 17:39 | 天蝎鱼
楼主,你的方法确实比较形象,从直观计算来说,确实不错,是做题的一种方法,但是我想不通一个东西,那就是求交点,多边形求交点的时候,这里面要找到所有的A~P的点,需要多少代价?我的意思是,怎么去最小化找点划分A外,A内,B外,B内? 其实当判断出这四个部分的时候,布尔运算已经有结果了,那是很简单的。
鉴于计算几何的方法,应该说用DECL的结构会比较合适,不知楼主打算如何构造,。。。 等待解决中

另,楼主说的自相交的多边形,其实可以在最早的时候做一个多边形拆分,就可以解决,我们只关注无自相交的多边形就好了吧?... ... 不知我的想法对不~  回复  更多评论
  
# re: 使用拓扑进行几何图形布尔运算 2008-06-17 19:33 | 陈梓瀚(vczh)
1:只能两两求交,不过这里有很多优化的办法。譬如AABB box啊,甚至以前还有一位做3D的朋友建议我用BSP不过我觉得太复杂还是算了。一种简单但是不是很快的办法就是把交点插入原来的多边形内部,然后就可以把交点用index来表示了。不过代价是没有办法的,因为无论你是用什么布尔运算的算法,所有交点始终都是要算出来的。不然你根本无法表示结果。

2:所有的交点都获得了以后,交点之间的polyline集合都是互相之间不想交的,随便拿一个点或者线段的中点看看在不在另一个多边形内部就知道是内还是外了。至于判断一个点是否在多边形内部应该会吧。

到了这里就解决了问题了。至于自相交的话的确是需要先拆分的,只不过在我自己的实际需要中不需要处理自相交的部分,所以我就没考虑怎么做了。  回复  更多评论
  
# re: 使用拓扑进行几何图形布尔运算 2008-08-04 18:34 | pgc
大方向是正确的,不过有很多细节问题没有考虑。譬如误差,共线,共面……,你做到那一步的时候就知道了。  回复  更多评论
  
# re: 使用拓扑进行几何图形布尔运算 2010-06-02 21:44 | 林小坚
很多细节都没有考虑,真正实现起来非常麻烦。你怎样在窗口中显示?用GDI还是OPENGL?棱边不相交的多边形中的凹多边形也没有现成的显示函数,必须转化为多个凸多边形或三角形。其中还要考虑误差,如何判断一个点是否在多边形内。如何把排除剩下的边再组合成多边形,都是非常难的过程。  回复  更多评论
  
# re: 使用拓扑进行几何图形布尔运算 2010-06-02 22:10 | 陈梓瀚(vczh)
@林小坚
只要我们有“镶嵌多边形”的概念,这些都不是问题。如今的新显卡都直接支持,不需要我自己做。  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理