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

jianjiandandan

小弟近来遇到一个问题如下：
已知四条直线的方程，判断出这四条直线是否围成了一个四边形，
如果围成了一个四边形，那么请求出这四个顶点。
程序倒是编出来，但是感觉很丑陋，代码也很长。
现在向各位大侠请教有什么优雅的方法解决这个问题，谢谢！

Godbach

先谈一下你的算法啊

jianjiandandan

我看到自己的算法就想吐，感觉很不好，但是也拿出来给大家解剖下：
我的算法的思路如下：
首先就是把交点都求出来，如果交点数小于4个，那么就不能组成四边形；
如果交点是四个，说明是平行四边形；
如果交点是四个以上，说明是梯形或者一般的四边形，
这种情况下会有五个或者六个交点，需要排除一个或者两个，我先统计每条
直线上的交点数，如果点数为3，那么中间的那个点必定为顶点，经过这个步骤，
就能找到两个或者三个顶点，这三个点有个性质就是：对每个点，其余由四个点跟他
同处于前面已知的直线上，只有一个点跟他的联系不是前面已知的直线之一，把这样
的两个点视为一对。把满足这个关系的点对都找出来，排除重复的，就找到了四边形
对角线上的点。到此结束。
感觉很麻烦，请大家指点！谢谢

紫星河

要说算法的话，个人感觉是数学问题。当初数学没学好，现在越来越吃力了，唉～

jianjiandandan

是啊，感觉是高中时候的东西，现在做起来感觉很生涩了

zwylinux

原帖由 jianjiandandan 于 2007-9-28 16:35 发表
我看到自己的算法就想吐，感觉很不好，但是也拿出来给大家解剖下：
我的算法的思路如下：
首先就是把交点都求出来，如果交点数小于4个，那么就不能组成四边形；
如果交点是四个，说明是平行四边形；
如果交 ...

交点是4也有可能没构成四边形
比如线A，B，C交于同一点，线D和其他三线相交又有三个交点。

jianjiandandan

这个漏掉了，谢谢楼上的啊

依赛特小子

2D?3D? 好算法当然可以把代码减少哦

jianjiandandan

2D的，谢谢楼上的补充

NewCore

楼主，我觉得首先你的思路是通过判断4条直线的交点个数来检查4条直线是否围成4边形就是有漏洞的，漏掉的情况也不止2楼上提到的那种。
比如A，B，C，D四条直线，A与B平行，CD的交点在A和B中间，4条直线交点个数是5个，但是也不能构成4边形。

实际上，我认为这道题可以简化为：平面上N各点组成一个网状图，问这个网状图是否有一个4边形的回路。
这样，我的大概思路如下：
1）求出4边形的所有交点。
2）构造6*6的网状图（4条直线交点最多4*(4-1)/2=6）
3）遍历之，存在路径=4的回路即是所求。（结果可能不唯一，且不区分凹还是凸4边形）

为减小后面的运算量，1步的时候可以做一些判断，如果3条直线无交点，或者有唯一交点等情况都不能构成4边形。