200分求一暴难算法，提供方案就给分，在线等

Question

用直线或圆弧画出几个不规则的封闭图形，怎样用简单的方法判断任意两封闭图形的位置关系？也就是一个封闭图形是在另一封闭图形之内还是之外，或是有相交部分。
假如有如下用连续直线(也可能是圆弧)组成的图形，怎么判断比较好？
_________________         ________________
|         \  ____  /              |
|          \ |__| /               |
|           \    /                |
 \            \  /                /
  \             \/                /
   \     ___________              /
   /     |_________|              \
  /                               \
 /                                \
|     /\                   |
|    /  \                        |
|__________/    \_______________________|
有源码或好方法可加分!!!!!!!!!!!!!!!!!!!!!!!

Answer 1

转贴两个算法：
1。判断点是否在多边形中
以点P为端点，向左方作射线L，由于多边形是有界的，所以射线L的左端一定在多边形外，
考虑沿着L从无穷远处开始自左向右移动，遇到和多边形的第一个交点的时候，进入到了多边形的内部，遇到第二个交点的时候，离开了多边形，……所以很容易看出当L和多边形的交点数目C是奇数的时候，P在多边形内，是偶数的话P在多边形外。
但是有些特殊情况要加以考虑。如果L和多边形的顶点相交，有些情况下交点只能计算一个，有些情况下交点不应被计算（你自己画个图就明白了）；如果L和多边形的一条边重合，
这条边应该被忽略不计。为了统一起见，我们在计算射线L和多边形的交点的时候，1。对
于多边形的水平边不作考虑；2。对于多边形的顶点和L相交的情况，如果该顶点是其所属
的边上纵坐标较大的顶点，则计数，否则忽略；3。对于P在多边形边上的情形，直接可判
断P属于多边行。由此得出算法的伪代码如下：
1. count ← 0;
2. 以P为端点，作从右向左的射线L; 
3, for 多边形的每条边s
4. do if P在边s上 
5. then return true;
6. if s不是水平的
7. then if s的一个端点在L上且该端点是s两端点中纵坐标较大的端点
9. then count ← count+1
10. else if s和L相交
11. then count ← count+1;
12. if count mod 2 = 1 
13. then return true
14. else return false;
其中做射线L的方法是：设P'的纵坐标和P相同，横坐标为正无穷大（很大的一个正数），
则P和P'就确定了射线L。这个算法的复杂度为O(n)。
//判断点是否在多边形的范围内
2。16.10. 判断线段是否在多边形内
线段在多边形内的一个必要条件是线段的两个端点都在多边形内；
如果线段和多边形的某条边内交（两线段内交是指两线段相交且交点不在两线段的端点）
，因为多边形的边的左右两侧分属多边形内外不同部分，所以线段一定会有一部分在多边
形外。于是我们得到线段在多边形内的第二个必要条件：线段和多边形的所有边都不内交
；线段和多边形交于线段的两端点并不会影响线段是否在多边形内；但是如果多边形的某个
顶点和线段相交，还必须判断两相邻交点之间的线段是否包含与多边形内部。因此我们可
以先求出所有和线段相交的多边形的顶点，然后按照X-Y坐标排序，这样相邻的两个点就是在线段上相邻的两交点，如果任意相邻两点的中点也在多边形内，则该线段一定在多边形
内。证明如下：
命题1：
如果线段和多边形的两相邻交点P1 ，P2的中点P' 也在多边形内，则P1, P2之间的所有点
都在多边形内。
证明：
假设P1,P2之间含有不在多边形内的点，不妨设该点为Q，在P1, P'之间，因为多边形是闭合曲线，所以其内外部之间有界，而P1属于多边行内部，Q属于多边性外部，P'属于多边性内部，P1-Q-P'完全连续，所以P1Q和QP'一定跨越多边形的边界，因此在P1,P'之间至少还有两个该线段和多边形的交点，这和P1P2是相邻两交点矛盾，故命题成立。证毕
由命题1直接可得出推论：
推论2：
设多边形和线段PQ的交点依次为P1,P2,……Pn，其中Pi和Pi+1是相邻两交点，线段PQ在多边形内的充要条件是：P，Q在多边形内且对于i =1, 2,……, n-1，Pi ,Pi+1的中点也在多
边形内。在实际编程中，没有必要计算所有的交点，首先应判断线段和多边形的边是否内交，倘若
线段和多边形的某条边内交则线段一定在多边形外；如果线段和多边形的每一条边都不内
交，则线段和多边形的交点一定是线段的端点或者多边形的顶点，只要判断点是否在线段
上就可以了。
至此我们得出算法如下：1. if 线端PQ的端点不都在多边形内 
2. then return false;
3. 点集pointSet初始化为空;
4. for 多边形的每条边s
5. do if 线段的某个端点在s上
6. then 将该端点加入pointSet;
7. else if s的某个端点在线段PQ上
8. then 将该端点加入pointSet;
9. else if s和线段PQ相交 // 这时候可以肯定是内交
10. then return false;
11. 将pointSet中的点按照X-Y坐标排序，X坐标小的排在前面，对于X坐标相同的点，Y坐
标小的排在前面；
12. for pointSet中每两个相邻点 pointSet[i] , pointSet[ i+1]
13. do if pointSet[i] , pointSet[ i+1] 的中点不在多边形中
14. then return false;
15. return true;
这个算法的复杂度也是O(n)。其中的排序因为交点数目肯定远小于多边形的顶点数目n，所
以最多是常数级的复杂度，几乎可以忽略不计。
你参考一下

Answer 2

统一楼上，要看你的这些图形的创建方式了。是通过窗口坐标还是极坐标（例如画线，你是指定两个端点呢，还是指定一个端点、线段长度和角度来完成的）。如果都是通过点的连结来完成的话比较容易。对任意两个单元，首先通过CreateEllipticRgn、CreatePolyPolygonRgn等等来创建区域，然后利用CombineRgn将两个区域合并，通过设置不同的合并方式和判断返回值就可以知道两个区域是什么关系了。

Answer 3

我提供一个思路，请看是否可行：
把图形转化为区域Region；
使用CombineRgn判断两个区域是否相交。
使用EqualRgn判断相交区域是否和原始区域相等---如相等则是被包含。

Answer 4

TechnoFantasy(www.applevb.com)(★★★★★)高手出现了,关注!