2008年6月17日
摘要: 首先吐槽一下：今天考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条直线构成五角星的画法。这
阅读全文
posted @
2008-06-16 19:20 陈梓瀚(vczh) 阅读(4686) |
评论 (7) |
编辑 收藏