如何求四条直线所围成的四边形的顶点

jianjiandandan

感谢楼上的回答，用网状图来描述这个确实很严谨，
目前感觉用C来做这样的事情不怎么顺手，要设计一
堆适合这个问题的数据结构吧，本人对数据结构不太
熟悉，有没有高人在这个方面指导下啊，谢谢！

iceviewer

晕， 数据结构是算法的基础把。。。

drowsyboy

原帖由 NewCore 于 2007-9-28 18:59 发表
楼主，我觉得首先你的思路是通过判断4条直线的交点个数来检查4条直线是否围成4边形就是有漏洞的，漏掉的情况也不止2楼上提到的那种。
比如A，B，C，D四条直线，A与B平行，CD的交点在A和B中间，4条直线交点个数 ...

这个方法确实不错。

其实只要一个4*4的表即可，然后改问题就可以简化为旅商问题（两条直线相交，求出交点;如果平行，则表示不可到达），那么问题的本质就可以表达为：某一节点出发，经过4步，是否可以到达出发点的问题了。

数据结构也很容易构造

1. 
   
2. struct sLineRela {
   
3.           bool   bConjuction;
   
4.           Point sCrossPoint;  
   
5. };
   
6. 
   
7. struct sLineRela aGraphic[4][4]；
   

复制代码

四边形找出来以后，再判断是凸，还是凹，是梯形，还是平行四边形，就不难了。

jianjiandandan

谢谢楼上的热心人，
不过感觉还是有点抽象，能不能写个详细点的伪代码呢？
再次谢谢！！！

醉卧水云间

这个问题很容易。

每条直线必须且只能和另外两条相交。四条线都要满足这个条件，然后四个交点不要重合就行了。

补充一点：三维的话先求共面情况，同样也容易。

[ 本帖最后由 醉卧水云间 于 2007-9-29 20:51 编辑 ]

NewCore

回复楼上

如下情况，满足你的题设

比如A，B，C，D四条直线，A与B平行，CD的交点在A和B中间，4条直线交点个数是5个，但是也不能构成4边形。

能构成四边形吗？

[ 本帖最后由 NewCore 于 2007-9-29 22:46 编辑 ]

jianjiandandan

感谢各位的回答，这类问题应该有个通用的解答方法，
哪位高人能搞个通用的算法，设计一个优雅的模块出来。
不知道这类问题属于哪个领域，想找个解决这类问题的
函数库，找了很久都没有找到，请大家指点啊！

drowsyboy

原帖由 醉卧水云间 于 2007-9-29 20:50 发表
这个问题很容易。

每条直线必须且只能和另外两条相交。四条线都要满足这个条件，然后四个交点不要重合就行了。

补充一点：三维的话先求共面情况，同样也容易。

感觉这种方法不行．　每条直线和另外三条直线都相交，仍有可能围成四边形．

drowsyboy

原帖由 jianjiandandan 于 2007-9-30 07:58 发表
感谢各位的回答，这类问题应该有个通用的解答方法，
哪位高人能搞个通用的算法，设计一个优雅的模块出来。
不知道这类问题属于哪个领域，想找个解决这类问题的
函数库，找了很久都没有找到，请大家指点啊！

大家都说这么多了。呵呵，楼主也要表达点诚意啊
我们可都等你优雅的模块呢

Godbach

期待实现的代码