精华内容
下载资源
问答
  • 计算机能画一条线段(数学意义上)吗?并不能。不管多短的一条线段,都包含实数集上的无数个点,计算机能做的是尽可能多地采样,描更多的点,让人眼难以看出其中的不连续性。已知 x,yx,y 分别为坐标轴上的两点,下式...

    计算机能画一条线段(数学意义上)吗?并不能。不管多短的一条线段,都包含实数集上的无数个点,计算机能做的是尽可能多地采样,描更多的点,让人眼难以看出其中的不连续性。

    已知 x,y 分别为坐标轴上的两点,下式为采样公式,

    x=(1p)x+py,p[0,1]

    p在整个 [0,1]闭区间上取值,可得到介于端点 x,y 之间的值,因为向量 (xx)=p(yx) 平行于向量 yx,又因为二者共享同一端点 x,故三者共线。

    import numpy as np
    import matplotlib.pyplot as plt
    
    def main():
        x0, x1 = [1, 1], [2, 2]
        for p in np.linspace(0, 1, 1000):
            plt.plot((1-p)*x0[0]+p*x1[0], (1-p)*x0[1]+p*x1[1], '.', c='k')
        plt.plot(x0[0], x0[1], 'o', ms=10)
        plt.plot(x1[0], x1[1], 'o', ms=10)
        plt.show()
    if __name__ == '__main__':
        main()


    20160108133959645

    我们不妨对该公式做一次简单推导,如图所示:


    这里写图片描述

    x⃗ z⃗ z⃗ y⃗  共线,不妨令

    x⃗ z⃗ =k(z⃗ y⃗ )x⃗ +ky⃗ =(1+k)z⃗ z⃗ =11+kx⃗ +k1+ky⃗ 11+kλ,11+k1z⃗ =λx⃗ +(1λ)y⃗ 
    展开全文
  • * 判断由x3, y3定义的是否在由x1, y1 和 x2, y2定义的直线上(不是线段)? * @param x1 - 直线的第的x坐标 * @param y1 - 直线的第的y坐标 * @param x2 - 直线的第二个的x坐标 *
    public class LineAndPoint {
        
        /**
         * 判断由x3, y3定义的点是否在由x1, y1 和 x2, y2定义的直线上(不是线段)?
         * @param x1 - 直线的第一个点的x坐标
         * @param y1 - 直线的第一个点的y坐标
         * @param x2 - 直线的第二个点的x坐标
         * @param y2 - 直线的第二个点的y坐标
         * @param x3 - 要判断的点的x坐标
         * @param y3 - 要判断的点的y坐标
         * @param delta - 误差范围
         * @return true or false.
         */
        public static boolean ifPointOnLine(float x1, float y1, float x2, float y2, float x3, float y3, float delta) {
            float xa = x2 - x1;
            float ya = y2 - y1;
            float xb = x3 - x1;
            float yb = y3 - y1;
            return (Math.abs(yb / xb - ya / xa) <= delta);
        }
        
        /**
         * 判断由x3, y3定义的点是否在由x1, y1 和 x2, y2定义的线段之上?
         * @param x1 - 线段的第一个端点的x坐标
         * @param y1 - 线段的第一个端点的y坐标
         * @param x2 - 线段的第二个端点的x坐标
         * @param y2 - 线段的第二个端点的y坐标
         * @param x3 - 要判断的点的x坐标
         * @param y3 - 要判断的点的y坐标
         * @param delta - 误差范围
         * @return true or false.
         */
        public static boolean ifPointOnSegment(float x1, float y1, float x2, float y2, float x3, float y3, float delta) {
            float xa = x2 - x1;
            float ya = y2 - y1;
            float xb = x3 - x1;
            float yb = y3 - y1;
            return (Math.abs(yb / xb - ya / xa) <= delta
                    && Math.min(x1, x2) <= x3
                    && Math.max(x1, x2) >= x3
                    && Math.min(y1, y2) <= y3
                    && Math.max(y1, y2) >= y3);
        }
        
        /**
         * 判断由x3, y3定义的点是否在由x1, y1 和 x2, y2定义的直线上(不是线段)?
         * @param x1 - 直线的第一个点的x坐标
         * @param y1 - 直线的第一个点的y坐标
         * @param x2 - 直线的第二个点的x坐标
         * @param y2 - 直线的第二个点的y坐标
         * @param x3 - 要判断的点的x坐标
         * @param y3 - 要判断的点的y坐标
         * @param delta - 误差范围
         * @return true or false.
         */
        public static boolean ifPointOnLine(double x1, double y1, double x2, double y2, double x3, double y3, double delta) {
            double xa = x2 - x1;
            double ya = y2 - y1;
            double xb = x3 - x1;
            double yb = y3 - y1;
            return (Math.abs(yb / xb - ya / xa) <= delta);
        }
        
        /**
         * 判断由x3, y3定义的点是否在由x1, y1 和 x2, y2定义的线段之上?
         * @param x1 - 线段的第一个端点的x坐标
         * @param y1 - 线段的第一个端点的y坐标
         * @param x2 - 线段的第二个端点的x坐标
         * @param y2 - 线段的第二个端点的y坐标
         * @param x3 - 要判断的点的x坐标
         * @param y3 - 要判断的点的y坐标
         * @param delta - 误差范围
         * @return true or false.
         */
        public static boolean ifPointOnSegment(double x1, double y1, double x2, double y2, double x3, double y3, double delta) {
            double xa = x2 - x1;
            double ya = y2 - y1;
            double xb = x3 - x1;
            double yb = y3 - y1;
            return (Math.abs(yb / xb - ya / xa) <= delta
                    && Math.min(x1, x2) <= x3
                    && Math.max(x1, x2) >= x3
                    && Math.min(y1, y2) <= y3
                    && Math.max(y1, y2) >= y3);
        }
    }
    
    展开全文
  • 判断两条线段是否相交

    千次阅读 2012-03-06 22:48:36
    为了确定两条线段是否相交,要检查每个线段是否跨越了包含另线段的直线。 给定个线段p1p2,如果p1位于某直线的一边, 而p2位于直线的另一边,则称线段p1p2跨越了该直线。如果p1和p2 就落在该直线的话,即...

    为了确定两条线段是否相交,要检查每个线段是否跨越了包含另一线段的直线。 给定一个线段p1p2,如果点p1位于某一直线的一边, 而点p2位于直线的另一边,则称线段p1p2跨越了该直线。如果p1和p2 就落在该直线的话,即出现边界情况。两条线段相交, 当且仅当下面两个条件中有一个成立,或同时成立:

    1)每个线段都跨越包含了另一线段的直线。

    2)一个线段的某一端点位于另一线段上。

    代码如下:

    
    
    bool segments_intersect (Point p1, Point p2, Point p3, Point p4) {
        int d1, d2, d3, d4;
        d1 = direction(p3, p4, p1);
        d2 = direction(p3, p4, p2);
        d3 = direction(p1, p2, p3);
        d4 = direction(p1, p2, p4);
        if (((d1 < 0 && d2 > 0) || (d1 > 0 && d2 < 0)) && ((d3 < 0 && d4 > 0) || (d3 > 0 && d4 < 0)))
            return true;
        else if (d1 == 0 && on_segment(p3, p4, p1))
            return true;
        else if (d2 == 0 && on_segment(p3, p4, p2))
            return true;
        else if (d3 == 0 && on_segment(p1, p2, p3))
            return true;
        else if (d4 == 0 && on_segment(p1, p2, p4))
            return true;
        else
            return false;
    }
    
    int direction (Point p0, Point p1, Point p2) {
        return ((p2.x - p0.x)*(p1.y - p0.y) - (p1.x - p0.x)*(p2.y - p0.y));
    }
    
    bool on_segment (Point p0, Point p1, Point p2) {
        int minx, maxx, miny, maxy;
        minx = min(p0.x, p1.x);
        maxx = max(p0.x, p1.x);
        miny = min(p0.y, p1.y);
        maxy = max(p0.y, p1.y);
        if (p2.x >= minx && p2.x <= maxx && p2.y >= miny && p2.y <= maxy)
            return true;
        else
            return false;
    }


    展开全文
  • 都说两点确定一条直线,那么设计一个直线类Line,需要通过两个点Point对象来确定。Line类具体要求如下: 1)定义两个Point对象p1,p2; 2)写出有参构造方法,传递两个对象值给p1,p2 3)为p1,p2写出setters,和...
  • 所谓几何, 最基本的当然就是坐标, 从坐标中我们可以知道位置和方向,比如:一个点就是一个位置,两点确定一条直线,从某点指向另一点的有向线段所在的直线是一向量。要处理几何题,我们又不得不涉及到叉积和点积...

      计算几何中,判断线段是否相交是最基本的题目。 所谓几何, 最基本的当然就是坐标, 从坐标中我们可以知道位置和方向,比如:一个点就是一个位置,两点确定一条直线,从某点指向另一点的有向线段所在的直线是一向量。要处理几何题,我们又不得不涉及到叉积和点积, 判断线段相交就要用到叉积。

      下面先讲讲相交的形式:

      说到线段, 我们很自然想到直线,判断两条直线是否相交只需判断它们斜率是否相等,相等就为平行或重合, 不等就相交(注:判断相交我们不采用除法,因为除法容易产生浮点误差,当两条直线斜率接近时,很容易出错。 事实上,几乎所有几何题都不建议采用除法)。

      线段相交有两种形式:

        规范相交非规范相交 。 区别就是交点是否是其中一条线段的端点,不是的是规范相交。

      叉积的概念: 设向量 a(x1, y1) 、 b(x2, y2) ;

            a x b = x1*y2 - x2*y1; (与数学中的叉积不太一样)

      判断线段相交比较繁琐,主要就是判断异侧:

        我们以一条线段的一端点为起点,沿着线段方向看去(一条射线),在左手边为逆时针方向,右手边为顺时针方向。如果另一线段两端点分别在这一线段的两侧,那么线段可能相交(也可能在线段外),否则不可能相交。对另一线段采用相同方法就可判断出是否相交了。

         这个过程主要通过叉积来判断: 叉积大于 0 ,在点在向量的顺时针方向,小于 0 , 在逆时针方向 ; 等于 0, 端点在直线上。

     

      具体实现:

        设:线段 a :P1(x1, y1)、P2(x2, y2)      线段 b: Q1(x3, y3)、Q2(x4, y4)

        d1 ====>   (P2 - P1) x (Q1 - P1) (叉积)

        d2 ====>   (P2 - P1) x (Q2 - P1) (叉积)

        d3 ====>   (Q2 - Q1) x (P1 - Q1) (叉积)

        d4 ====>   (Q2 - Q1) x (P2 - P1) (叉积)

      

      首先,先判断端点是否在另一线段上。

      然后,我们只需判断 d1 * d2 < 0  并且 d3 * d4 < 0 便可判断线段相交。

       

      

     1 #define cs const
     2 #define cp const P&
     3 #define op operator
     4 const  double eps = 1e-8;
     5 inline int sig(double x) {return (x>eps)-(x<-eps);}
     6 
     7 struct P{
     8     double x, y;
     9     void in() { scanf("%lf%lf", &x, &y); }
    10     P(double x=0.0, double y=0.0) : x(x), y(y) {}
    11 
    12     P op-(cp a)cs { return P(x-a.x, y-a.y); }
    13     double op^(cp a)cs { return x*a.y - y*a.x; }    //叉积
    14     double op*(cp a)cs {return x*a.x + y*a.y;}
    15 
    16     double cross(P a, P b) { return (a-*this) ^ (b-*this); }
    17     double dot(P a, P b)  { return (a-(*this)) * (b-(*this)); }
    18     bool on_seg(P a, P b) { return !sig(cross(a, b)) && sig(dot(a, b)) <= 0; }//判断是否在点上
    19 };
    20 
    21 bool seg(P a, P b, P c, P d) { //判断相交(a - b)线段 、(c - d)线段
    22     if(a.on_seg(c, d) || b.on_seg(c, d) || c.on_seg(a, b) || d.on_seg(a, b))
    23         return true;
    24     return sig(a.cross(b, c)*a.cross(b, d)) < 0 && sig(c.cross(d, a)*c.cross(d, b)) < 0;
    25 }

     

     

     

    训练题:杭电oj 1086 :

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1086

     

     

    转载于:https://www.cnblogs.com/Duahanlang/archive/2013/05/11/3073434.html

    展开全文
  • 《直线、射线、线段和角》教学设计执教:陆品荣一、教学目标1、知识与技能:经历画图、观察和交流等活动,认识射线、直线及相互间的联系,能区分线段、射线、直线,了解两点确定一条直线,体会两点间所有连线中线段...
  • 前言 \(NOIP\)结束之后,我下定决心来好好学习一些省选算法了。 计算几何应该是一个比较复杂的算法吧,虽然出现得较少,但还是蛮实用的。 接着上一次学习的点与向量·...//存储直线上两点坐标,两点确定一条直线 ...
  • 判断线段两两相交

    千次阅读 2014-04-24 19:06:19
    如果比较快的判断堆线段是否两两相交,可用以下方法: ...意思就是说,如果两条线段分别确定的矩形不想交,则这两条线段一定不想交。 如果,分别给出两条线段的起始坐标,具体实现,可以这
  • 快速确定两个点集的可分性,先分别对两个点集求凸包,再判断两个凸包上的线段是否有相交,这里点的数量比较少,直接遍历即可,如果发现有相交,两点集不可分。 (这里用int来存点的时候,线段跨立实验时这题的数据...
  • 线段上格的个数

    千次阅读 2015-03-18 17:31:46
    线段上格点的个数 题目描述 给定平面上的两个格点P1=(x1,y1)和P2=(x2,y2),线段P1P2上,除P1和P2以外一共有几个格点并打印出格点坐标? 限制条件: -1000000000 输入 ...1、两点确定一条直线,
  • 线段覆盖问题

    2019-08-20 19:53:59
    线段覆盖 给定x轴上的N(0<N<100)条线段,每个线段由它的二个端点a_I和b_I确定,I=1,2,……N....所谓的内部公共是指一个同时属于条线段且至少在其中一条线段的内部(即除去端点的部分)。 输入...
  • 题目描述Description 给定x轴上的N(0<N<100)条线段,每个线段由它的二个端点a_I和b_I确定,I=1,2,……N....有些线段之间会相互交叠或...所谓的内部公共是指一个同时属于条线段且至少在其中一条线段...
  • 1214 线段覆盖

    2019-01-02 13:47:29
    题目描述 Description  给定x轴上的N(0&lt;N&lt;100)条线段,每个线段由它的二个端点a_I和b_I确定,I=1,2,……N...所谓的内部公共是指一个同时属于条线段且至少在其中一条线段的内部(即除去端点...
  • Codevs1214 线段覆盖

    2018-11-17 11:20:39
    题目描述 Description: 给定x轴上的N(0&lt;N&lt;100)条线段,每个线段由它的二个端点a_I和b_I确定,I=1,2...所谓的内部公共是指一个同时属于条线段且至少在其中一条线段的内部(即除去端点的部分)...
  • 2.经过两点有且只有一条直线,即:两点确定一条直线。四.线段的性质:所有连结两点的线中,线段最短,即:两点之间线段最短。常见考法(1)确定直线、线段的个数;(2)求线段的长度。误区提醒求线段长度时考虑不周而...
  • codevs1214 线段覆盖

    2017-06-22 17:57:00
    题目描述Description 给定x轴上的N(0<N<100)条线段,每个线段由它的二个端点a_I和b_I确定,I=1,2,……N....所谓的内部公共是指一个同时属于条线段且至少在其中一条线段的内部(即...
  • Problem D: 平面上的点和线——Point类、Line类 (VII)Time Limit: 1 Sec Memory Limit: 128 ...Description在数学上,平面直角坐标系上的点用X轴和Y轴上的两个坐标值唯一确定,两点确定一条线段。现在我们封装一个“Poi
  • Codevs 1214 线段覆盖

    2016-10-23 11:25:29
    1214 线段覆盖题目描述 Description给定x轴上的N(0)条线段,每个线段由它的二个端点a_I和b_I确定,I=1,2,……N....所谓的内部公共是指一个同时属于条线段且至少在其中一条线段的内部(即除去端点的部分)
  • Problem D: 平面上的点和线——Point类、Line类 (IV) Time Limit: 1 Sec Memory Limit: 128 MB ...在数学上,平面直角坐标系上的点用X轴和Y轴上的两个坐标值唯一确定,两点确定一条线段。现在
  • (VI)Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 5479 Solved: 2522[Submit][Status][Web Board]Description在数学上,平面直角坐标系上的点用X轴和Y轴上的两个坐标值唯一确定,两点确定一条线段。现在我们...
  • Problem E: 平面上的点和线——Point类、Line类 (V) Time Limit: 1 Sec Memory Limit: 128 MB ...在数学上,平面直角坐标系上的点用X轴和Y轴上的两个坐标值唯一确定,两点确定一条线段。现在我
  • (VII)Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 3696 Solved: 2536[Submit][Status][Web Board]Description在数学上,平面直角坐标系上的点用X轴和Y轴上的两个坐标值唯一确定,两点确定一条线段。...

空空如也

空空如也

1 2 3 4 5 ... 15
收藏数 285
精华内容 114
关键字:

两点确定一条线段