【思考题】如何让MC自动判断任意两条直线段是相交
mathcad吧
全部回复
仅看楼主
level 12
朱老剑客 楼主
上次的思考题
“对1层嵌套矩阵的所有元素求均值”https://tieba.baidu.com/p/4073612986
@angelycs 秒破,哎,尽管还是有很多可以深入的探讨余地,但貌似各位只要找到了一个方便的方法之后,就不会再去想其他的解了。我感觉各位还是在追求所谓的标准答案,仍没有脱离应试教育的思维窠臼。
如果我在那一题里说请举出5种不同的编程方法,或许就能把我的意思的传达的更清楚一些吧。
说正题。MC吧里已经有3个提问贴提到了“怎么让MC自动给出任意两条曲线的交点坐标(甚至交点轨迹)”,我这个思考题仅是把那3个提问说得更纯粹一些。
我们在MC中表示线段最常用的方法是组成向量,我举个例子:
在这里A1、B1分别是一个2×2的矩阵,按列提取就成了代表X,Y的向量,绘制这个X,Y向量对,就可以得到1个线段。
为了方便绘图,并把问题具体化一些,我把A1、B1顶点的坐标限制在(0,10)范围内。
嗯,基于连续统,我假设A1、B1的顶点坐标取值范围只要是相同的,就对我们的编程不会产生什么影响。所以咱们暂且规定
这两条线段的两端点坐标X,Y值的取值范围都是(0,10)吧。
这两条线组成的图形千变万化,那么:
(1)请通过编程让MC自己判断出这两条线段是否相交;如果相交,请让MC自己给出交点的坐标;如果不相交,返回(NaN,NaN)。
(2)让MC给出更多的描述信息,比如说:这两条线段的夹角是多少,是否平行、是否垂直,通过无数次的取值之后,这两条线段的长度和的期望值是多少,等等,自己发挥,也可以不回答。
下面这个是我做的初步分析,希望能够为各位的解题提供一些思路吧。
2015年10月14日 01点10分 1
level 12
朱老剑客 楼主
嗯,我感觉比较有意思的是,当把这个程序编出来,然后运行很多很多次,得到的那个“在一定的取值范围内,任意两条线段的可以发生相交的概率”是多少,可能会得到一个跟π有关的值吧。
2015年10月14日 01点10分 4
level 12
朱老剑客 楼主
@wwwdongliting @angelycs 线段要比直线麻烦一些,比如说:
这两条线段处在一条直线上,但没有交点。更过分的,在一条直线上的两条线段发生了重合,就等于有无数个交点,此时我们应该怎么界定“交点”的定义呢?这得自己发挥。
2015年10月14日 02点10分 5
原来是指线段
2015年10月14日 02点10分
level 12
朱老剑客 楼主
这题的关键是找思路。
比较暴力的解法是这样的:
可是各位也看到了,需要经过5次if判断!如果用这个方法来解更多条线段相交的问题的话,明显无效率。
我想问的是,有没有什么办法能够简化这个程序呢?能够使其运行的更快一些。
2015年10月14日 04点10分 6
level 12
朱老剑客 楼主
不是平行线的一般情况还是比较方便得到结果的:
但这个方法对于平行线平行线这种特殊情况来说,返回的都是(NaN,NaN)。
2015年10月14日 09点10分 8
level 12
朱老剑客 楼主
嗯,对于平行线,find不收敛,会报错,所以加了一句on error
咱们放大一些。有了这个error分支,就可以比较方便的往里面插“平行线”“共线不重合”以及“共线重合”这三种情况的算法了。
2015年10月14日 09点10分 9
level 12
朱老剑客 楼主
哦,我直接用搜狗拼音也能弄出这个来……
a×b = |a||b|sin(θ)
2015年10月14日 11点10分 12
不过复杂的比如带积分的公式,输入法就搞不定了。
2015年10月15日 12点10分
level 12
朱老剑客 楼主
当两个向量斜率相同的时候,如果截距不同,则是平行线,如果截距相同,则是共线了。
共线的情况比较复杂,有五种情况,如果这个斜率不是垂直于y轴,那么我们就可以通过每个点对x轴的投影,即每个点的横坐标值,来把这个问题简化为一维的排列组合问题。
当这个斜率垂直于y轴的时候,我们可以通过调换向量端点的x,y值,使其平行于y轴,转化为x轴投影问题。如下:
嗯,为方便后面的研究,我们定义一个简单的函数:
这个函数的目的是为了求出两对向量x,y各顶点之间的差的符号的。
嗯,为了保证函数运算结果统一性,首先用sort,因为是线段向量,只有两个顶点,通过sort颠倒了前后顺序之后并不会改变向量本身的性质。
z把y颠倒了一下,是为了方便后面的计算。
将x与y的差和x与z的差放在一个向量里,用sign()函数求值。sign()就是当x<0时;为-1,当x>0为1;当x=0时,为0。
由此,可以从两对向量里得到四个不同的数,从而能比较方便看出它们的一维的数值关系。
嗯,下面为了方便图示,我把共线的两条线段上下错开一些。为了方便研究,我使用了简单的例子,对x,y赋值,因为仅讨论的是正负号问题,所以尽量用简单的赋值会使思路更清晰一些。
第1种情况:
第2种情况:
第3种情况:
第4种情况:
第5种情况:
请注意以上5种情况的所得到的向量的和,分别是-4、-3、-2、-1、0。嗯,当B继续向左运动的时候,我们计算allcross(B,A)即可得到0,1,2,3,4了,对应的图形特点是和allcross(A,B)是一样的,也就是说如果我们对这个函数取绝对值,就可以标记不同的一维位置关系了。
但是这里还有一个特例,平行线是线段交叉问题的特例,重合共线是平行线的特例,下面这个两个线段完全相等,就是特例中的特例了:
它所得到的向量和也是0,也就是说,当这个allcross的向量和为0时,我们只要找那个比较短一些向量的两端端点坐标作为重合向量的坐标就可以了。
2015年10月14日 12点10分 13
level 12
朱老剑客 楼主
嗯,有意思的思路!通过矢量计算就能够是三角形的面积有正有负。但是您说的通过两面积的比值确定交点位置,我还不很明白,如果方便,还望您能给出一个例子。:)
2015年10月14日 14点10分 15
level 12
朱老剑客 楼主
实话说,还是没明白。 :(
2015年10月14日 15点10分 18
level 12
朱老剑客 楼主
按照你说的“面积值异号,或其中一值为零——两线段交叉。”,那么下面的怎么解释?
2015年10月14日 15点10分 20
level 12
朱老剑客 楼主
这道题超麻烦,除了我上面提到的特殊情况之外,还有其他特殊情况。比如说line()函数在向量垂直于x轴的时候不计算,比如说当两个向量互相垂直,且其中一个向量垂直于x轴的时候,更麻烦。
我初步编了一个程序,特么用了5个if,2个on error,总算是把所有可能的分支都铺全了!(因为题目说的是“线段”,不包括“点”,所以我没有考虑当这两个向量里有“点”的情况)
仅做了必要的注释,至于具体某个函数是怎么个意思,各位自己分析,不很难。
预先定义一些函数:
主程序:
用最麻烦的情况做一个验算:
源文件下载:http://1000eb.com/1gjov
2015年10月14日 17点10分 21
已下载,谢谢!
2015年10月14日 23点10分
level 12
朱老剑客 楼主
嗯,我现在也在考虑使用坐标旋转加坐标投影的方法使这个问题简化。而且我感觉在处理问题之前首先通过变换使其标准化,是简化“任意问题”的最好手段了。
2015年10月15日 00点10分 25
level 12
朱老剑客 楼主
通过计算两个向量在x,y轴上的投影的路子貌似行不通,我用smartsketch编了一个简单的模拟程序,发现在二维情况下是没有简单的投影规则可以利用的。
如果要用投影规律来做,就得对各投影之间的差进行比较精细的数值分析了,肯定能有一些成果,但我这边儿就没那么充裕的时间了。谁愿意接手,我可以把这个小模拟程序传给他。
2015年10月15日 06点10分 26
level 12
朱老剑客 楼主
这个题如果用复数会不会更方便些呢?
2015年10月15日 11点10分 30
至少求角度会方便直观,正如前面我提到过的,改成矢量归一化后叉乘即可。
2015年10月15日 12点10分
level 12
朱老剑客 楼主
没明白,看上去玄之又玄。@angelycs 你把你的思路具体说说?
2015年10月16日 16点10分 33
level 12
朱老剑客 楼主
有机会你把截图和源文件上传了,并注释一下你的思路,咱们再看看有没有方法可以解决你遇到的问题吧。你现在这么说,不清楚你这么做的最终目的,也就不好说还有什么替代手段了。
2015年10月16日 17点10分 35
放在38楼了
2015年10月17日 01点10分
level 12
朱老剑客 楼主
文本字符不可逆。
如果要在文本中插入数学字符,用ctrl shift A,但这也是不可逆的,在文本中加入的数学字符不能通过按空格键转化为文本字符。
2015年10月18日 01点10分 42
那就没辙了。我常常不经意间把正在输入的函数名按空格键,结果只好重新输入一遍。如果函数名很长,感觉很不爽。
2015年10月18日 02点10分
@月城翁 可以将误输入的部分copy出来,单独粘贴,就还是数学字符呀!
2015年10月18日 02点10分
@朱老剑客 哦,看来不是这样的…… :(
2015年10月18日 02点10分
您这方法是可行的,选择性粘贴—将无格式文本作为数学。我实践过。只是希望有快捷键,不然还是觉得麻烦。
2015年10月18日 02点10分
level 12
朱老剑客 楼主
@月城公寓寓公 ,我知道怎么做了,用shift + home键做出一个空白的数学输入占位符,然后把你误输入部分复制粘贴进来就可以了。
比如说下面的:
呵呵,这个快捷键在help里没有提到,我就喜欢聊help里没有提到的东西 :P
2015年10月18日 02点10分 43
神了!这个问题让我烦心好久了,总算解决了。衷心感谢。我这个“不经意间”的毛病老是改不了。所以希望有“涂改液”。
2015年10月18日 02点10分
level 12
朱老剑客 楼主
另外,shift + home 和 shift + end功能是一样的,都是在工作表的空白区域生成一个空白的数学占位符。
2015年10月18日 02点10分 44
谢谢!
2015年10月18日 03点10分
应该建个贴,收集这些不易被发现的快捷键和其他妙用。
2015年10月19日 01点10分
回复 angelycs :嗯,没人问,我也想不起来说的。
2015年10月19日 05点10分
@朱老剑客 所以更应该集思广益,集中记录下来。
2015年10月19日 06点10分
1