• 回复@大雨582:社会人不可能像自然人一样自由,你还得尊重别人的意愿!不然咱随便生产啥都强行让你要,咱是自由了,你呢? 2019-10-12
  • 发改委每月首个工作日公布限制乘坐火车飞机人员名单 2019-10-12
  • 全国啦啦操联赛临汾站开幕 2019-10-08
  • 《爱疯音乐家》陈洁仪:不完美的美其实更美爱疯音乐家陈洁仪 2019-10-08
  • 中冶置业兴隆百万平米新城正式亮相 将打造全配套高铁康养小镇 2019-10-06
  • 以政府拟严打“乱拍摄”以军行为 最高10年监禁 2019-10-03
  • 图解:关于中国梦,习近平总书记这十句话直抵人心 2019-09-20
  • “舌尖”之后, “风味”能否再续辉煌? 2019-09-17
  • 腾讯要花32亿收购《绝地求生》开发商10%股份 2019-09-17
  • 涨知识!文字里的秘密 最全甲骨文书展来了 2019-09-13
  • 晋中市着力将“厕所革命”进行到底 2019-09-05
  • 供应链如何更“智慧” 2019-09-05
  • 红枣食疗效果好 6种吃法最滋补-美食资讯 2019-09-01
  • 党的十九大最重大的理论成就 2019-08-28
  • 余世存:阅读经典不仅是消费,也是责任 2019-08-20
  • 福建体彩3选7走势图: 基础知识 判断两线段是否相交并求交点

    11
    回复
    648
    查看
    打印 上一主题 下一主题
    [ 复制链接 ]
    排名
    64937
    昨日变化

    福建36选7和值走势图 www.00-na.com 3

    主题

    13

    帖子

    42

    积分

    Rank: 1

    UID
    37884
    好友
    1
    蛮牛币
    181
    威望
    0
    注册时间
    2014-8-4
    在线时间
    24 小时
    最后登录
    2019-7-15

    马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

    您需要 登录 才可以下载或查看,没有帐号?注册帐号

    x
    本帖最后由 greatclock 于 2019-6-27 14:59 编辑

    曾经在作游戏时遇到求两线段交点的问题,好一顿推导之后得到一方法。前两天和别人讨论提及了这个问题,好信上网一搜,赫然没有找到我推得的那个方法。就此萌生了写第一篇技术博客的想法,阐述拙见。

    首先明确一下问题,已知2D坐标下两线段AB和CD,即ABCD四个点的坐标,ABCD两两不重合,判断两线段是否相交,并求交点。

    需要用到的知识点:向量,向量与标量相乘,向量点乘,向量投影。

    解题思路:

    如上图,O为直线AB和直线CD的交点,设 。
    ,则设 。
    。
    两边同时乘以 得: 。
    如图,根据向量投影原理, 上的投影与 上的投影相同,
    得: 。
    等号两边都是标量,相除后可以得到:

    为0,则表示直线AB与直线CD平等。除此情况外t 可求。
    ,则表示直线AB与直线CD的交点O在AB之间,即线段AB与直线CD有交点。
    同理可求两直线交点是否在CD之间。
    若已求得t,根据 可求 以及交点O。

    附c#代码
    [C#] 纯文本查看 复制代码
    using UnityEngine;
    
    public static class SegmentCross {
    
            public static float LineCDCutAB(Vector2 a, Vector2 b, Vector2 c, Vector2 d) {
                    Vector2 cd = d - c;
                    Vector2 n = new Vector2(cd.y, -cd.x);
                    float div = Vector2.Dot(b - a, n);
                    return div == 0f ? float.NaN : Vector2.Dot(c - a, n) / div;
            }
    
            public static bool CalculateCross(Vector2 a, Vector2 b, Vector2 c, Vector2 d, out Vector2 cross) {
                    float t1 = LineCDCutAB(a, b, c, d);
                    float t2 = LineCDCutAB(c, d, a, b);
                    if (float.IsNaN(t1) || float.IsNaN(t2)) {
                            cross = new Vector2(float.NaN, float.NaN);
                            return false;
                    }
                    cross = (b - a) * t1 + a;
                    return t1 >= 0f && t1 <= 1f && t2 >= 0f && t2 <= 1f;
            }
    
    #if UNITY_EDITOR
            [UnityEditor.MenuItem("SegmentCross/Test")]
            static void Test() {
                    Test(new Vector2(0f, 0f), new Vector2(2f, 2f), new Vector2(0f, 2f), new Vector2(2f, 0f));
                    Test(new Vector2(1f, 1f), new Vector2(3f, 5f), new Vector2(2f, 2f), new Vector2(4f, 6f));
                    Test(new Vector2(0f, 0f), new Vector2(1f, 1f), new Vector2(0f, 4f), new Vector2(4f, 0f));
            }
    
            static void Test(Vector2 a, Vector2 b, Vector2 c, Vector2 d) {
                    Vector2 cross;
                    bool ret = CalculateCross(a, b, c, d, out cross);
                    if (ret) {
                            Debug.LogFormat("Cross of Segments {0}-{1} and {2}-{3} is {4}", a, b, c, d, cross);
                    } else {
                            Debug.LogErrorFormat("No cross of Segments {0}-{1} and {2}-{3}. Line cross : {4}", a, b, c, d, cross);
                    }
            }
    #endif
    
    }
    

    7日久生情
    2335/5000
    排名
    4093
    昨日变化

    0

    主题

    1581

    帖子

    2335

    积分

    Rank: 7Rank: 7Rank: 7Rank: 7

    UID
    254705
    好友
    1
    蛮牛币
    2101
    威望
    0
    注册时间
    2017-11-16
    在线时间
    392 小时
    最后登录
    2019-10-21
    沙发
    2019-6-25 08:05:39 只看该作者
    66666666666666666666666666
    6蛮牛粉丝
    1125/1500
    排名
    2967
    昨日变化

    7

    主题

    67

    帖子

    1125

    积分

    Rank: 6Rank: 6Rank: 6

    UID
    156147
    好友
    1
    蛮牛币
    773
    威望
    0
    注册时间
    2016-7-10
    在线时间
    557 小时
    最后登录
    2019-10-18
    板凳
    2019-6-25 09:18:00 只看该作者
    本帖最后由 tianma0042 于 2019-6-25 09:19 编辑

    你换种思路,你先求出两条线段所在直线的交点。
    如果没有交点,则两条线段没有交点。
    如果有交点,判断此交点是否分别在两条线段上即可。
    排名
    64937
    昨日变化

    3

    主题

    13

    帖子

    42

    积分

    Rank: 1

    UID
    37884
    好友
    1
    蛮牛币
    181
    威望
    0
    注册时间
    2014-8-4
    在线时间
    24 小时
    最后登录
    2019-7-15
    地板
    楼主 2019-6-25 11:07:09 只看该作者
    本帖最后由 greatclock 于 2019-6-25 11:18 编辑
    tianma0042 发表于 2019-6-25 09:18
    你换种思路,你先求出两条线段所在直线的交点。
    如果没有交点,则两条线段没有交点。
    如果有交点,判断此交 ...

    如果已知两直线交点O和线段AB和CD,那么判断O在线段AB上怎么搞呢?
    计算OA和OB长的和,然后和线段AB长比较,相等就是在线段AB上?
    如果这样,考虑到浮点数精度、算法和CPU计算复杂度,这种思路完败呀!
    或者另有高见?
    6蛮牛粉丝
    1125/1500
    排名
    2967
    昨日变化

    7

    主题

    67

    帖子

    1125

    积分

    Rank: 6Rank: 6Rank: 6

    UID
    156147
    好友
    1
    蛮牛币
    773
    威望
    0
    注册时间
    2016-7-10
    在线时间
    557 小时
    最后登录
    2019-10-18
    5#
    2019-6-25 13:36:29 只看该作者
    greatclock 发表于 2019-6-25 11:07
    如果已知两直线交点O和线段AB和CD,那么判断O在线段AB上怎么搞呢?
    计算OA和OB长的和,然后和线段AB长比较 ...

    我不知道你是基于何等的自信说出这种话。
    浮点数精度我不知道你的应用场景,大部分场景是够的。
    算法,你认为你做除法运算会比普通加减法速度快吗?
    CPU计算复杂度 呵呵。
    5熟悉之中
    538/1000
    排名
    10961
    昨日变化

    1

    主题

    89

    帖子

    538

    积分

    Rank: 5Rank: 5

    UID
    130631
    好友
    0
    蛮牛币
    786
    威望
    0
    注册时间
    2015-12-2
    在线时间
    354 小时
    最后登录
    2019-10-18
    6#
    2019-6-25 14:12:34 只看该作者
    看着好熟悉   有种上学做数学题的感觉 -.-
    排名
    64937
    昨日变化

    3

    主题

    13

    帖子

    42

    积分

    Rank: 1

    UID
    37884
    好友
    1
    蛮牛币
    181
    威望
    0
    注册时间
    2014-8-4
    在线时间
    24 小时
    最后登录
    2019-7-15
    7#
    楼主 2019-6-27 10:58:48 只看该作者
    tianma0042 发表于 2019-6-25 13:36
    我不知道你是基于何等的自信说出这种话。
    浮点数精度我不知道你的应用场景,大部分场景是够的。
    算法,你 ...

    期待你能拿出更有说服力的内容。
    排名
    64937
    昨日变化

    3

    主题

    13

    帖子

    42

    积分

    Rank: 1

    UID
    37884
    好友
    1
    蛮牛币
    181
    威望
    0
    注册时间
    2014-8-4
    在线时间
    24 小时
    最后登录
    2019-7-15
    8#
    楼主 2019-6-27 11:30:30 只看该作者
    re9ret 发表于 2019-6-25 14:12
    看着好熟悉   有种上学做数学题的感觉 -.-

    其实思路上还是有差异的。典型的高中解析几何的思路并不适合方便地拿代码来实现。就像你楼上那位的思路,如果搞出俩直线方程再用行列式解个二元一次方程组还不知道要算多少次除法呢!总之应该比我一次计算总共两次除法要多。总之高中数学里一个看似简单的判断,在电脑上似乎并不是那么回事。比如Vector2 AB,BC,AC这仨向量,由于浮点数精度问题,AB + BC 很可能不等于AC,这点你楼上那哥们似乎也不清楚。
    5熟悉之中
    538/1000
    排名
    10961
    昨日变化

    1

    主题

    89

    帖子

    538

    积分

    Rank: 5Rank: 5

    UID
    130631
    好友
    0
    蛮牛币
    786
    威望
    0
    注册时间
    2015-12-2
    在线时间
    354 小时
    最后登录
    2019-10-18
    9#
    2019-6-27 15:37:26 只看该作者
    greatclock 发表于 2019-6-27 11:30
    其实思路上还是有差异的。典型的高中解析几何的思路并不适合方便地拿代码来实现。就像你楼上那位的思路, ...

      在计算的时候 一般都是小于1-6E算是等于
    排名
    64937
    昨日变化

    3

    主题

    13

    帖子

    42

    积分

    Rank: 1

    UID
    37884
    好友
    1
    蛮牛币
    181
    威望
    0
    注册时间
    2014-8-4
    在线时间
    24 小时
    最后登录
    2019-7-15
    10#
    楼主 2019-6-27 17:22:23 只看该作者
    re9ret 发表于 2019-6-27 15:37
    在计算的时候 一般都是小于1-6E算是等于

    一般写作1E-6。之前曾因浮点数和其他数值类型转换和相关的精度问题,为某个设备上一个莫名其妙的表现查了好久,心有余悸。
    5熟悉之中
    854/1000
    排名
    4111
    昨日变化

    1

    主题

    303

    帖子

    854

    积分

    Rank: 5Rank: 5

    UID
    245227
    好友
    0
    蛮牛币
    1049
    威望
    0
    注册时间
    2017-9-21
    在线时间
    190 小时
    最后登录
    2019-10-17
    11#
    2019-6-28 09:39:51 只看该作者
    在有除法的地方还是感觉很危险, 最好用两点式转换成一般方程然后用线性代数的行列式求解才是最可靠的.
    排名
    64937
    昨日变化

    3

    主题

    13

    帖子

    42

    积分

    Rank: 1

    UID
    37884
    好友
    1
    蛮牛币
    181
    威望
    0
    注册时间
    2014-8-4
    在线时间
    24 小时
    最后登录
    2019-7-15
    12#
    楼主 2019-7-1 14:33:28 只看该作者
    tiancaiwlk 发表于 2019-6-28 09:39
    在有除法的地方还是感觉很危险, 最好用两点式转换成一般方程然后用线性代数的行列式求解才是最可靠的. ...

    我也很想知道解线性代数行列式的代码怎样写才能不用到除法。
    您需要登录后才可以回帖 登录 | 注册帐号

    本版积分规则

  • 回复@大雨582:社会人不可能像自然人一样自由,你还得尊重别人的意愿!不然咱随便生产啥都强行让你要,咱是自由了,你呢? 2019-10-12
  • 发改委每月首个工作日公布限制乘坐火车飞机人员名单 2019-10-12
  • 全国啦啦操联赛临汾站开幕 2019-10-08
  • 《爱疯音乐家》陈洁仪:不完美的美其实更美爱疯音乐家陈洁仪 2019-10-08
  • 中冶置业兴隆百万平米新城正式亮相 将打造全配套高铁康养小镇 2019-10-06
  • 以政府拟严打“乱拍摄”以军行为 最高10年监禁 2019-10-03
  • 图解:关于中国梦,习近平总书记这十句话直抵人心 2019-09-20
  • “舌尖”之后, “风味”能否再续辉煌? 2019-09-17
  • 腾讯要花32亿收购《绝地求生》开发商10%股份 2019-09-17
  • 涨知识!文字里的秘密 最全甲骨文书展来了 2019-09-13
  • 晋中市着力将“厕所革命”进行到底 2019-09-05
  • 供应链如何更“智慧” 2019-09-05
  • 红枣食疗效果好 6种吃法最滋补-美食资讯 2019-09-01
  • 党的十九大最重大的理论成就 2019-08-28
  • 余世存:阅读经典不仅是消费,也是责任 2019-08-20
  • 大中华彩票娱乐平台 单纯参与网赌会抓吗 百乐捕鱼最新版 官方通比牛牛下载 手机炸金花骗了多少人 北京pk10全部赛车记录 甘肃11选5任3推荐号码 排列五和值走势图带连线专业版 特码图报 山东群英会基本走势图 福彩3d独胆王 斯诺克中国锦标赛四强 什么方法买马稳赚 排列三组选6多少注 福彩3d走势图