二维平面：直线与凸多边形相交，如何快速求交点坐标？

maohbao2 · 发表于 2015-1-11 23:00

本帖最后由 maohbao2 于 2015-1-11 23:01 编辑

如下图所示，n条直线构成一个凸多边形，另有一条直线L与凸多边形相交：

n条直线的方程为：
L1: a1*x+b1*y+c1=0
L2: a2*x+b2*y+c2=0
L3: a3*x+b3*y+c3=0
L4: a4*x+b4*y+c4=0
L5: a5*x+b5*y+c5=0
....
Ln: an*x+bn*y+cn=0

直线L的方程为：
L: a*x+b*y+c=0

需要请教的问题是：
（1）证明：L与凸多边形的边最多有两个交点（不考虑L与凸多边形某条边重合的情形）；
（2）如何快速求解出这两个交点？（最好不是依次将L与各条直线联立求解这种盲目枚举求解的方法）。

谢谢！

maohbao2 · 发表于 2015-1-12 18:49

Help! 怎么没有人回答啊？

maohbao2 · 发表于 2015-1-14 20:43

Help me please!

drc2000 · 发表于 2015-1-15 09:07

（1）凸多边形定义：图形总在任意直线同一侧的多边型
根据凸多边形定义，采取反证法，应该不算太困难。

（2）我觉的比较简单的方法，还是画图，结合图象去考虑。

maohbao2 · 发表于 2015-1-15 22:26

drc2000 发表于 2015-1-15 09:07
（1）凸多边形定义：图形总在任意直线同一侧的多边型
根据凸多边形定义，采取反证法，应该不算太困难。

...

针对问题（2），我要解决的是求交点坐标的通用解法，而不是针对某一特定情形！

drc2000 · 发表于 2015-1-16 14:40

本帖最后由 drc2000 于 2015-1-16 14:41 编辑

maohbao2 发表于 2015-1-15 22:26
针对问题（2），我要解决的是求交点坐标的通用解法，而不是针对某一特定情形！

>>>>>>最好不是依次将L与各条直线联立求解这种盲目枚举求解的方法.....

你既要求不用枚举法，又要求快速求，还要求通用…

你是不是想找个老婆？
要求具有韩国mm的美貌，又有日本女优的技术，还具备中国妇女的美德……

maohbao2 · 发表于 2015-1-18 23:09

关键是要算法通用，如果用枚举就不叫什么方法了吧。。。。。。

drc2000 · 发表于 2015-1-19 17:27

maohbao2 发表于 2015-1-18 23:09
关键是要算法通用，如果用枚举就不叫什么方法了吧。。。。。。

线形规划里面有个单纯形……估计作用不大。

maohbao2 · 发表于 2015-1-22 21:06

作用不大说它又有什么意思啊......

		自动登录	找回密码
密码			注册

二维平面：直线与凸多边形相交，如何快速求交点坐标？

本帖子中包含更多资源