1000分跪求高效2D线段集求交算法
线段集的元素为直线段，由两个点组成SP(x,y)和EP(x,y)
两条这样的线段之间求交的算法已有: IntersectSegment()。
但如果是N条线段组成的集合，它们相互间求交，效率就非常重要了。
最笨的办法是N条线段跟剩下的所有线段间求交，这需要调用IntersectSegment()N的阶乘次。
有没有谁知道像Macromedia FlashMX这样的软件，它的求交算法是怎样的呢？它的速度很快，相当快。。。
问题点数：100、回复次数：8Top
1 楼captainchain（一路漂着）回复于 2005-08-03 12:13:08 得分 0
有解决此问题者另外开贴给分
袁大侠应该知道的吧~~~~Top
2 楼CGChina（时空英雄）回复于 2005-08-04 15:35:34 得分 100
1m/s的速度够了吗？Top
3 楼CGChina（时空英雄）回复于 2005-08-04 15:55:31 得分 0
我自己有一个快速算法：
如有两直线A,B
如果((Asp.x-Bsp.x)(Aep.x-Bep.x))<0且((Asp.y-Bsp.y)(Aep.y-Bep.y))<0 那么直线A,B相交。
这个算法只是用来判断相交否的。
这个不需要三角函数，计算速度非常快。Top
4 楼captainchain（一路漂着）回复于 2005-08-04 17:27:32 得分 0
谢谢楼上的先~~~
不过，我的IntersectSegment()函数，也只有乘法，本身速度比较快哦。
关键在于如何在多线段的情况下，如何减少调用它的次数Top
5 楼CGChina（时空英雄）回复于 2005-08-05 02:05:06 得分 0
说一说具体目的！Top
6 楼captainchain（一路漂着）回复于 2005-08-05 09:07:39 得分 0
和MacroMedia FlashMX一样的矢量图形编辑的功能
刷子呀橡皮擦之类的Top
7 楼CGChina（时空英雄）回复于 2005-08-05 15:28:08 得分 0
线段的和区域的连接Top
8 楼captainchain（一路漂着）回复于 2005-08-05 16:17:58 得分 0
和区域没关系，输入是一个线段的集合，这个集合里的线段会有相交的情况，但没有求出交点
输出就是一堆求出了交点的线段集。
比方说，两条线段相交，生成四条线段Top
