• 8种家居环境很败“性” 2019-06-28
  • 2018年全军院校招生计划下达:计划招收学员3.05万名 2019-06-15
  • 晋城市举办干部素质提升工程第十八期专题讲座 2019-06-15
  • 抖音广告出现对英烈邱少云不敬内容 今日头条致歉 2019-06-13
  • 超半数巴西民众对世界杯不感兴趣--旅游频道 2019-06-12
  • 外交部举行中外媒体吹风会:王毅介绍上合组织青岛峰会情况 2019-06-12
  • 2018网络中国节·端午 2019-06-04
  • 韩媒:韩美商定暂停原定8月“乙支自由卫士”联演 2019-06-03
  • 重庆市公安局交通管理局互联网交通安全服务管理平台 2019-06-03
  • 俄侦察船穿越英吉利海峡 英国急派军舰战机监视 2019-05-28
  • 网购陷阱多 女子花3000元买5套化妆品只有2套是真的 2019-05-28
  • 环保约谈濂溪区主要负责同志 谢一平要求立行立改真抓真改 2019-05-25
  • 官宣!广东签约北京3冠功勋 大莫助拳阿联未来可期 2019-05-25
  • 党建第一责任与发展第一要务相融合br全面提升机关党建工作水平 2019-05-22
  • 卡纳瓦罗:对比赛结果不满意 晋级机会各占一半 2019-05-22
  • 今期36选7开奖结果查询: 基础知识 判断两线段是否相交并求交点

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

    福建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日久生情
    1958/5000
    排名
    4092
    昨日变化

    0

    主题

    1259

    帖子

    1958

    积分

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

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

    7

    主题

    66

    帖子

    1051

    积分

    Rank: 6Rank: 6Rank: 6

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

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

    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蛮牛粉丝
    1051/1500
    排名
    2966
    昨日变化

    7

    主题

    66

    帖子

    1051

    积分

    Rank: 6Rank: 6Rank: 6

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

    我不知道你是基于何等的自信说出这种话。
    浮点数精度我不知道你的应用场景,大部分场景是够的。
    算法,你认为你做除法运算会比普通加减法速度快吗?
    CPU计算复杂度 呵呵。
    4四处流浪
    497/500
    排名
    10960
    昨日变化

    1

    主题

    87

    帖子

    497

    积分

    Rank: 4

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

    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
    我不知道你是基于何等的自信说出这种话。
    浮点数精度我不知道你的应用场景,大部分场景是够的。
    算法,你 ...

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

    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,这点你楼上那哥们似乎也不清楚。
    4四处流浪
    497/500
    排名
    10960
    昨日变化

    1

    主题

    87

    帖子

    497

    积分

    Rank: 4

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

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

    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熟悉之中
    765/1000
    排名
    4110
    昨日变化

    1

    主题

    246

    帖子

    765

    积分

    Rank: 5Rank: 5

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

    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
    在有除法的地方还是感觉很危险, 最好用两点式转换成一般方程然后用线性代数的行列式求解才是最可靠的. ...

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

    本版积分规则

  • 8种家居环境很败“性” 2019-06-28
  • 2018年全军院校招生计划下达:计划招收学员3.05万名 2019-06-15
  • 晋城市举办干部素质提升工程第十八期专题讲座 2019-06-15
  • 抖音广告出现对英烈邱少云不敬内容 今日头条致歉 2019-06-13
  • 超半数巴西民众对世界杯不感兴趣--旅游频道 2019-06-12
  • 外交部举行中外媒体吹风会:王毅介绍上合组织青岛峰会情况 2019-06-12
  • 2018网络中国节·端午 2019-06-04
  • 韩媒:韩美商定暂停原定8月“乙支自由卫士”联演 2019-06-03
  • 重庆市公安局交通管理局互联网交通安全服务管理平台 2019-06-03
  • 俄侦察船穿越英吉利海峡 英国急派军舰战机监视 2019-05-28
  • 网购陷阱多 女子花3000元买5套化妆品只有2套是真的 2019-05-28
  • 环保约谈濂溪区主要负责同志 谢一平要求立行立改真抓真改 2019-05-25
  • 官宣!广东签约北京3冠功勋 大莫助拳阿联未来可期 2019-05-25
  • 党建第一责任与发展第一要务相融合br全面提升机关党建工作水平 2019-05-22
  • 卡纳瓦罗:对比赛结果不满意 晋级机会各占一半 2019-05-22
  • 360彩票老11选5遗漏数据 福彩3d四码组六的遗漏 360如何网上购买彩票 排列3玩法 安徽快3遗漏数据大全 老11选5开奖信息 北京11选5缩水软件 3d如何判断出组三 海南私彩有漏洞吗 黑龙江十一选五加减算式 20192019cba赛程辽宁 黑龙江十一选五遗漏号 足球竞彩分析网站 体彩大乐透开奖时间 赛马会免费资科大全