ecmadao

ecmadao 查看完整档案

北京编辑厦门大学  |  材料科学与工程 编辑心知科技  |  Node.js 全栈 编辑 github.com/ecmadao 编辑
编辑

开发者

个人动态

ecmadao 评论了文章 · 2018-06-22

前端单元测试探索

本文已发布在稀土掘金

转载请注明原文链接:https://github.com/ecmadao/Co...

虽然很多公司有自己的测试部门,而且前端开发大多不涉及测试环节,但鉴于目前前端领域的快速发展,其涉及面越来越广,前端开发者们必然不能止步于目前的状态。我觉得学会编写良好的测试,不仅仅有利于自己整理需求、检查代码,更是一个优秀开发者的体现。

首先不得不推荐两篇文章:

前端自动化测试探索

测试驱动开发(TDD)介绍中的误区

Intro

单元测试到底是什么?

需要访问数据库的测试不是单元测试

需要访问网络的测试不是单元测试

需要访问文件系统的测试不是单元测试

--- 修改代码的艺术

我们在单元测试中应该避免什么?

  • 太多的条件逻辑

  • 构造函数中做了太多事情

  • too many全局变量

  • too many静态方法

  • 无关逻辑

  • 过多外部依赖

TDD(Test-driven development)

测试驱动开发(TDD),其基本思路是通过测试来推动整个开发的进行。

  • 单元测试的首要目的不是为了能够编写出大覆盖率的全部通过的测试代码,而是需要从使用者(调用者)的角度出发,尝试函数逻辑的各种可能性,进而辅助性增强代码质量

  • 测试是手段而不是目的。测试的主要目的不是证明代码正确,而是帮助发现错误,包括低级的错误

  • 测试要快。快速运行、快速编写

  • 测试代码保持简洁

  • 不会忽略失败的测试。一旦团队开始接受1个测试的构建失败,那么他们渐渐地适应2、3、4或者更多的失败。在这种情况下,测试集就不再起作用

IMPORTANT

  • 一定不能误解了TDD的核心目的!

  • 测试不是为了覆盖率和正确率

  • 而是作为实例,告诉开发人员要编写什么代码

  • 红灯(代码还不完善,测试挂)-> 绿灯(编写代码,测试通过)-> 重构(优化代码并保证测试通过)

大致过程

  1. 需求分析,思考实现。考虑如何“使用”产品代码,是一个实例方法还是一个类方法,是从构造函数传参还是从方法调用传参,方法的命名,返回值等。这时其实就是在做设计,而且设计以代码来体现。此时测试为红

  2. 实现代码让测试为绿

  3. 重构,然后重复测试

  4. 最终符合所有要求:

    • 每个概念都被清晰的表达

    • Not Repeat Self

    • 没有多余的东西

    • 通过测试

BDD(Behavior-driven development)

行为驱动开发(BDD),重点是通过与利益相关者的讨论,取得对预期的软件行为的清醒认识,其重点在于沟通

大致过程

  1. 从业务的角度定义具体的,以及可衡量的目标

  2. 找到一种可以达到设定目标的、对业务最重要的那些功能的方法

  3. 然后像故事一样描述出一个个具体可执行的行为。其描述方法基于一些通用词汇,这些词汇具有准确无误的表达能力和一致的含义。例如,expect, should, assert

  4. 寻找合适语言及方法,对行为进行实现

  5. 测试人员检验产品运行结果是否符合预期行为。最大程度的交付出符合用户期望的产品,避免表达不一致带来的问题

测试的分类 & 测试工具

分类

  • API/Func UnitTest

    • 测试不常变化的函数逻辑

    • 测试前后端API接口

  • UI UnitTest

    • 页面自动截图

    • 页面DOM元素检查

    • 跑通交互流程

工具

mocha + chai的API/Func UnitTest

mocha是一套前端测试工具,我们可以拿它和其他测试工具搭配。

而chai则是BDD/TDD测试断言库,提供诸如expect这样的测试语法

initial

下面两篇文章值得一看:

Testing in ES6 with Mocha and Babel 6

Using Babel

setup
$ npm i mocha --save-dev
$ npm i chai --save-dev
Use with es6

babel 6+

$ npm install --save-dev babel-register
$ npm install babel-preset-es2015 --save-dev
// package.json
{
  "scripts": {
    "test": "./node_modules/mocha/bin/mocha --compilers js:babel-register"
  },
  "babel": {
    "presets": [
      "es2015"
    ]
  }
}

babel 5+

$ npm install --save-dev babel-core
// package.json
{
  "scripts": {
    "test": "./node_modules/mocha/bin/mocha --compilers js:babel-core/register"
  }
}
Use with coffeescript
$ npm install --save coffee-script
{
  "scripts": {
    "test": "./node_modules/mocha/bin/mocha --compilers coffee:coffee-script/register"
  }
}
Use with es6+coffeescript

After done both...

{
  "scripts": {
    "test": "./node_modules/mocha/bin/mocha --compilers js:babel-core/register,coffee:coffee-script/register"
  }
}
# $ mocha
$ npm t
$ npm test

chai

import chai from 'chai';

const assert = chai.assert;
const expect = chai.expect;
const should = chai.should();
foo.should.be.a('string');
foo.should.equal('bar');
list.should.have.length(3);
obj.should.have.property('name');

expect(foo).to.be.a('string');
expect(foo).to.equal('bar');
expect(list).to.have.length(3);
expect(obj).to.have.property('flavors');

assert.typeOf(foo, 'string');
assert.equal(foo, 'bar');
assert.lengthOf(list, 3);
assert.property(obj, 'flavors');

Test

测试的一个基本思路是,自身从函数的调用者出发,对函数进行各种情况的调用,查看其容错程度、返回结果是否符合预期。

import chai from 'chai';
const assert = chai.assert;
const expect = chai.expect;
const should = chai.should();

describe('describe a test', () => {

  it('should return true', () => {
      let example = true;
      // expect
      expect(example).not.to.equal(false);
      expect(example).to.equal(true);
      // should
      example.should.equal(true);
      example.should.be.a(boolen);
      [1, 2].should.have.length(2);
  });
  
  it('should check an object', () => {
    // 对于多层嵌套的Object而言..
    let nestedObj = {
        a: {
          b: 1
      }
    };
    let nestedObjCopy = Object.assign({}, nestedObj);
    nestedObj.a.b = 2;
    
    // do a function to change nestedObjCopy.a.b 
    expect(nestedObjCopy).to.deep.equal(nestedObj);
    expect(nestedObjCopy).to.have.property('a');
  });
});

AsynTest

Testing Asynchronous Code with MochaJS and ES7 async/await

mocha无法自动监听异步方法的完成,需要我们在完成之后手动调用done()方法

而如果要在回调之后使用异步测试语句,则需要使用try/catch进行捕获。成功则done(),失败则done(error)

// 普通的测试方法
it("should work", () =>{
  console.log("Synchronous test");
});
// 异步的测试方法
it("should work", (done) =>{
  setTimeout(() => {
    try {
        expect(1).not.to.equal(0);
        done(); // 成功
    } catch (err) {
        done(err); // 失败
    }
  }, 200);
});

异步测试有两种方法完结:done或者返回Promise。而通过返回Promise,则不再需要编写笨重的try/catch语句

it("Using a Promise that resolves successfully with wrong expectation!", function() {
    var testPromise = new Promise(function(resolve, reject) {
        setTimeout(function() {
            resolve("Hello World!");
        }, 200);
    });

    return testPromise.then(function(result){
        expect(result).to.equal("Hello!");
    });
});

mock

mock是一个接口模拟库,我们可以通过它来模拟代码中的一些异步操作

React单元测试

Test React Component

React组件无法直接通过上述方法进行测试,需要安装enzyme依赖。

$ npm i --save-dev enzyme
#
$ npm i --save-dev react-addons-test-utils

假设有这样一个组件:

// ...省略部分import代码
class TestComponent extends React.Component {
  constructor(props) {
    super(props);
    let {num} = props;
    this.state = {
      clickNum: num
    }
    this.handleClick = this.handleClick.bind(this)
  }

  handleClick() {
    let {clickNum} = this.state;
    this.setState({
      clickNum: clickNum + 1
    });
  }

  render() {
    let {clickNum} = this.state;
    return (
      <div className="test_component">
        {clickNum}
        <span onClick={this.handleClick}>点我加1</span>
      </div>
    )
  }
}

使用样例:

import React from 'react';
import {expect} from 'chai';
import {shallow} from 'enzyme';

import TestComponent from '../components/TestComponent';

describe('Test TestComponent', () => {
  // 创建一个虚拟的组件
  const wrapper = shallow(
      <TestComponent num={10} />/
  );

  /* 
  * 之后,我们可以:
  * 通过wrapper.state()拿到组件的state
  * 通过wrapper.instance()拿到组件实例,以此调用组件内的方法
  * 通过wrapper.find()找到组件内的子组件
  * 但是,无法通过wrapper.props()拿到组件的props
  */

  // 测试该组件组外层的class
  it('should render with currect wrapper', () => {
    expect(wrapper.is('.test_component')).to.equal(true);
  });

  // 测试该组件初始化的state
  it('should render with currect state', () => {
    expect(wrapper.state()).to.deep.equal({
      clickNum: 10
    });
  });

  // 测试组件的方法
  it('should add one', () => {
    wrapper.instance().handleClick();
    expect(wrapper.state()).to.deep.equal({
      clickNum: 11
    });
  });
});

Test Redux

redux身为纯函数,非常便于mocha进行测试

// 测试actions
import * as ACTIONS from '../redux/actions';

describe('test actions', () => {
  it('should return an action to create a todo', () => {
    let expectedAction = {
        type: ACTIONS.NEW_TODO,
        todo: 'this is a new todo'
    };
     expect(ACTIONS.addNewTodo('this is a new todo')).to.deep.equal(expectedAction);
  });
});
// 测试reducer
import * as REDUCERS from '../redux/reducers';
import * as ACTIONS from '../redux/actions';

describe('todos', () => {
  let todos = [];
  it('should add a new todo', () => {
      todos.push({
        todo: 'new todo',
        complete: false
    });
    expect(REDUCERS.todos(todos, {
        type: ACTIONS.NEW_TODO,
        todo: 'new todo'
    })).to.deep.equal([
      {
          todo: 'new todo',
          complete: false
      }
    ]);
  });
});
// 还可以和store混用
import { createStore, applyMiddleware, combineReducers } from 'redux';
import thunk from 'redux-thunk';
import chai from 'chai';
import thunkMiddleware from 'redux-thunk';
import * as REDUCERS from '../redux/reducers';
import defaultState from '../redux/ConstValues';
import * as ACTIONS from '../redux/actions'

const appReducers = combineReducers(REDUCERS);
const AppStore = createStore(appReducers, defaultState, applyMiddleware(thunk));
let state = Object.assign({}, AppStore.getState());

// 一旦注册就会时刻监听state变化
const subscribeListener = (result, done) => {
  return AppStore.subscribe(() => {
    expect(AppStore.getState()).to.deep.equal(result);
    done();
  });
};

describe('use store in unittest', () => {
  it('should create a todo', (done) => {
    // 首先取得我们的期望值
      state.todos.append({
        todo: 'new todo',
        complete: false
    });
    
    // 注册state监听
    let unsubscribe = subscribeListener(state, done);
    AppStore.dispatch(ACTIONS.addNewTodo('new todo'));
    // 结束之后取消监听
    unsubscribe();
  });
});

基于phantomjsselenium的UI UnitTest

PhantomJS是一个基于webkit的服务器端JavaScript API,即相当于在内存中跑了个无界面的webkit内核的浏览器。通过它我们可以模拟页面加载,并获取到页面上的DOM元素,进行一系列的操作,以此来模拟UI测试。但缺点是无法实时看见页面上的情况(不过可以截图)。

Selenium是专门为Web应用程序编写的一个验收测试工具,它直接运行在浏览器中。Selenium测试通常会调起一个可见的界面,但也可以通过设置,让它以PhantomJS的形式进行无界面的测试。

  • open 某个 url

  • 监听 onload 事件

  • 事件完成后调用 sendEvent 之类的 api 去点击某个 DOM 元素所在 point

  • 触发交互

  • 根据 UI 交互情况 延时 setTimeout (规避惰加载组件点不到的情况)继续 sendEvent 之类的交互

Getting started with Selenium Webdriver for node.js

查看原文

ecmadao 赞了文章 · 2017-09-06

最长回文子串——Manacher 算法

0. 问题定义

最长回文子串问题:给定一个字符串,求它的最长回文子串长度。

如果一个字符串正着读和反着读是一样的,那它就是回文串。下面是一些回文串的实例:

12321    a    aba    abba    aaaa   tattarrattat(牛津英语词典中最长的回文单词)

1. Brute-force 解法

对于最长回文子串问题,最简单粗暴的办法是:找到字符串的所有子串,遍历每一个子串以验证它们是否为回文串。一个子串由子串的起点和终点确定,因此对于一个长度为n的字符串,共有n^2个子串。这些子串的平均长度大约是n/2,因此这个解法的时间复杂度是O(n^3)。

2. 改进的方法

显然所有的回文串都是对称的。长度为奇数回文串以最中间字符的位置为对称轴左右对称,而长度为偶数的回文串的对称轴在中间两个字符之间的空隙。可否利用这种对称性来提高算法效率呢?答案是肯定的。我们知道整个字符串中的所有字符,以及字符间的空隙,都可能是某个回文子串的对称轴位置。可以遍历这些位置,在每个位置上同时向左和向右扩展,直到左右两边的字符不同,或者达到边界。对于一个长度为n的字符串,这样的位置一共有n+n-1=2n-1个,在每个位置上平均大约要进行n/4次字符比较,于是此算法的时间复杂度是O(n^2)。

3. Manacher 算法

对于一个比较长的字符串,O(n^2)的时间复杂度是难以接受的。Can we do better?

先来看看解法2存在的缺陷。

1) 由于回文串长度的奇偶性造成了不同性质的对称轴位置,解法2要对两种情况分别处理;
2) 很多子串被重复多次访问,造成较差的时间效率。

缺陷2)可以通过这个直观的小?体现:

char: a b a b a
  i : 0 1 2 3 4

当i==1,和i==2时,左边的子串aba分别被遍历了一次。

如果我们能改善解法2的不足,就很有希望能提高算法的效率。Manacher正是针对这些问题改进算法。

(1) 解决长度奇偶性带来的对称轴位置问题

Manacher算法首先对字符串做一个预处理,在所有的空隙位置(包括首尾)插入同样的符号,要求这个符号是不会在原串中出现的。这样会使得所有的串都是奇数长度的。以插入#号为例:

aba  ———>  #a#b#a#
abba ———>  #a#b#b#a#

插入的是同样的符号,且符号不存在于原串,因此子串的回文性不受影响,原来是回文的串,插完之后还是回文的,原来不是回文的,依然不会是回文。

(2) 解决重复访问的问题

我们把一个回文串中最左或最右位置的字符与其对称轴的距离称为回文半径。Manacher定义了一个回文半径数组RL,用RL[i]表示以第i个字符为对称轴的回文串的回文半径。我们一般对字符串从左往右处理,因此这里定义RL[i]为第i个字符为对称轴的回文串的最右一个字符与字符i的距离。对于上面插入分隔符之后的两个串,可以得到RL数组:

char:    # a # b # a #
 RL :    1 2 1 4 1 2 1
RL-1:    0 1 0 3 0 1 0
  i :    0 1 2 3 4 5 6

char:    # a # b # b # a #
 RL :    1 2 1 2 5 2 1 2 1
RL-1:    0 1 0 1 4 1 0 1 0
  i :    0 1 2 3 4 5 6 7 8

上面我们还求了一下RL[i]-1。通过观察可以发现,RL[i]-1的值,正是在原本那个没有插入过分隔符的串中,以位置i为对称轴的最长回文串的长度。那么只要我们求出了RL数组,就能得到最长回文子串的长度。

于是问题变成了,怎样高效地求的RL数组。基本思路是利用回文串的对称性,扩展回文串

我们再引入一个辅助变量MaxRight,表示当前访问到的所有回文子串,所能触及的最右一个字符的位置。另外还要记录下MaxRight对应的回文串的对称轴所在的位置,记为pos,它们的位置关系如下。

我们从左往右地访问字符串来求RL,假设当前访问到的位置为i,即要求RL[i],在对应上图,i必然是在po右边的(obviously)。但我们更关注的是,i是在MaxRight的左边还是右边。我们分情况来讨论。

1)当iMaxRight的左边

情况1)可以用下图来刻画:

我们知道,图中两个红色块之间(包括红色块)的串是回文的;并且以i为对称轴的回文串,是与红色块间的回文串有所重叠的。我们找到i关于pos的对称位置j,这个j对应的RL[j]我们是已经算过的。根据回文串的对称性,以i为对称轴的回文串和以j为对称轴的回文串,有一部分是相同的。这里又有两种细分的情况。

  1. j为对称轴的回文串比较短,短到像下图这样。

这时我们知道RL[i]至少不会小于RL[j],并且已经知道了部分的以i为中心的回文串,于是可以令RL[i]=RL[j]。但是以i为对称轴的回文串可能实际上更长,因此我们试着以i为对称轴,继续往左右两边扩展,直到左右两边字符不同,或者到达边界。

  1. j为对称轴的回文串很长,这么长:

这时,我们只能确定,两条蓝线之间的部分(即不超过MaxRight的部分)是回文的,于是从这个长度开始,尝试以i为中心向左右两边扩展,,直到左右两边字符不同,或者到达边界。

不论以上哪种情况,之后都要尝试更新MaxRightpos,因为有可能得到更大的MaxRight。

具体操作如下:

step 1: 令RL[i]=min(RL[2*pos-i], MaxRight-i)
step 2: 以i为中心扩展回文串,直到左右两边字符不同,或者到达边界。
step 3: 更新MaxRight和pos

2)当iMaxRight的右边

遇到这种情况,说明以i为对称轴的回文串还没有任何一个部分被访问过,于是只能从i的左右两边开始尝试扩展了,当左右两边字符不同,或者到达字符串边界时停止。然后更新MaxRightpos

(3) 算法实现

#Python
def manacher(s):
    #预处理
    s='#'+'#'.join(s)+'#'

    RL=[0]*len(s)
    MaxRight=0
    pos=0
    MaxLen=0
    for i in range(len(s)):
        if i<MaxRight:
            RL[i]=min(RL[2*pos-i], MaxRight-i)
        else:
            RL[i]=1
        #尝试扩展,注意处理边界
        while i-RL[i]>=0 and i+RL[i]<len(s) and s[i-RL[i]]==s[i+RL[i]]:
            RL[i]+=1
        #更新MaxRight,pos
        if RL[i]+i-1>MaxRight:
            MaxRight=RL[i]+i-1
            pos=i
        #更新最长回文串的长度
        MaxLen=max(MaxLen, RL[i])
    return MaxLen-1

(4) 复杂度分析

空间复杂度:插入分隔符形成新串,占用了线性的空间大小;RL数组也占用线性大小的空间,因此空间复杂度是线性的。
时间复杂度:尽管代码里面有两层循环,通过amortized analysis我们可以得出,Manacher的时间复杂度是线性的。由于内层的循环只对尚未匹配的部分进行,因此对于每一个字符而言,只会进行一次,因此时间复杂度是O(n)

4. 更多关于回文串的 fun facts(参考自维基百科)

4.1 人们在一座名为赫库兰尼姆的古城遗迹中,找到了一个好玩的拉丁语回文串:sator arepo tenet opera rotas。翻译成中文大概就是`一个叫做Arepo的播种者,他用力地扶(把)着车轮。这个串的每个单词首字母刚好组成了第一个单词,每个单词的第二个字母刚好组成了第二个单词...于是乎,如果写出酱紫,你会发现上下左右四个方向读起来是一样的。这个串被称为 Sator Square.

4.2 本文开头给出的单词tattarrattat,出现在爱尔兰作家詹姆斯·乔伊斯的小说《尤利西斯》,是敲门的意思。吉尼斯纪录的最长回文英文单词是detartrated,是个化学术语。另外,还有些已出版的英文回文小说(你们歪果仁真会玩),比如Satire: VeritasDr Awkward & Olson in Oslo等。

2015.11.9 更新。

可以采用动态规划,列举回文串的起点或者终点来解最长回文串问题,无需讨论串长度的奇偶性。
看下面的扎瓦代码,容易理解。

    public int longestPalindrome(String s) {
     int n=s.length();
     boolean[][] pal=new boolean[n][n];
     //pal[i][j] 表示s[i...j]是否是回文串
     int maxLen=0;
     for (int i=0;i<n;i++){  // i作为终点
         int j=i;    //j作为起点
         while (j>=0){
             if (s.charAt(j)==s.charAt(i)&&(i-j<2||pal[j+1][i-1])){
                 pal[j][i]=true;
                maxLen=Math.max(maxLen, i-j+1);
             }
             j--;
         }
     }
     return maxLen;
    }
查看原文

赞 80 收藏 105 评论 23

ecmadao 赞了文章 · 2017-09-02

数学美 之 判断线段相交的最简方法

首发于我的博客转载请注明出处


解析几何的巅峰
是 向量
那无关过程的狂妄与简洁
映射着大自然无与伦比的美

引子

如何判断两条直线是否相交?

这很容易。平面直线,无非就是两种关系:相交 或 平行。因此,只需判断它们是否平行即可。而直线平行,等价于它们的斜率相等,只需分别计算出它们的斜率,即可做出判断。

但倘若我把“直线”换成“线段”呢——如何判断两条线段是否相交?

这就有些难度了。和 直线 不同,线段 是有固定长度的,即使它们所属的两条直线相交,这两条线段也不一定相交。

也许你会说:分情况讨论不就行了嘛:

  • 先计算两条线段的斜率,判断是否平行。若平行,则一定不相交。

  • 若不平行,求出两条线段的直线方程,联立之,解出交点坐标。

  • 运用定比分点公式,判断交点是否在两条线段上。

的确,从理论上这是一个可行的办法,这也是人们手动计算时普遍采用的方法。

然而,这个方法并不怎么适用于计算机。原因如下:

  • 计算中出现了除法(斜率计算、定比分点),因此每次计算前都要判断除数是否为 0(或接近 0)。这很麻烦,严重干扰逻辑的表达。

  • 浮点精度丢失带来的误差。人类计算时可以采用分数,但计算机不行。计算机在储存浮点数时会有精度丢失的现象。一旦算法的计算量大起来,误差会被急剧放大,影响结果准确性。

  • 效率低下。浮点乘除会十分耗时,不适用于对实时性要求较高的生产环境(如 游戏)。

那么,有更好的方法?

当然有。

类型预定义

本文的算法将用 python 描述,主要用到两个数据类型:

# 点
class Point(object):

    def __init__(self, x, y):
        self.x, self.y = x, y

# 向量
class Vector(object):

    def __init__(self, start_point, end_point):
        self.start, self.end = start_point, end_point
        self.x = end_point.x - start_point.x
        self.y = end_point.y - start_point.y

先在此处说明。

问题分析

对于“判断两条直线是否相交”这个问题,我们之所以能迅速而准确地进行判断,是因为“相交”与“不相交”这两个状态有着明显的不同点,即 斜率是否相等

那么现在,为了判断两条线段是否相交,我们也要找出“相交”与“不相交”这两个状态的不同点。

假设现在有两条线段 AB 和 CD,我们画出它们之间的三种关系:

  1. 不相交

  2. 交点位于某条线段上

  3. 相交

其中,情况 1 为不相交,情况 2、3 为相交。

作出向量 AC、AD、BC、BD。

首先介绍一个概念: 向量有序对的旋转方向。这个概念指:对于共起点有序向量二元组(a, b),其旋转方向为 使 a 能够旋转一个小于 180 度的角并与 b 重合的方向,简记为 direct(a, b)。若 ab 反向共线,则旋转方向取任意值。

举个例子:图一中,direct(AC, AD) 为顺时针方向。

接下来我们要分析四个值:direct(AC, AD)direct(BC, BD)direct(CA, CB)direct(DA, DB)

  1. 对于图一,direct(AC, AD)direct(BC, BD) 都为顺时针,direct(CA, CB) 为逆时针,direct(DA, DB) 为顺时针。

  2. 对于图二,direct(AC, AD) 为顺时针,direct(BC, BD) 为任意方向,direct(CA, CB) 为逆时针,direct(DA, DB) 为顺时针。

  3. 对于图三,direct(AC, AD)direct(DA, DB) 为顺时针,direct(BC, BD)direct(CA, CB) 为逆时针。

不难发现,两条线段相交的充要条件是:direct(AC, AD) != direct(BC, BD)direct(CA, CB) != direct(DA, DB)。这便是“相交”与“不相交”这两个状态的不同点。

然而你可能会觉得:旋转方向这么一个虚无飘渺的东西,怎么用程序去描述啊?

再来看一幅图:

再来定义有向角:

有向角 <a, b> 为 向量a逆时针 旋转到与 向量b 重合所经过的角度。

不难看出,对于向量ab

  • direct(a, b) 为逆时针,则 0 <= <a, b> <= 180,从而 sin<a, b> >= 0

  • direct(a, b) 为顺时针,则 180 <= <a, b> <= 360,从而 sin<a, b> <= 0

这样一来,我们可以将旋转方向的问题转化为 求有向角正弦值 的问题。而这个问题,是很容易的。

如上图,记

$$ OA = (x_1, y_1), OB = (x_2, y_2) $$
$$ |OA| = r_1, |OB| = r_2 $$

$$ sin(\lt OA, OB\gt) $$
$$ = sin \theta $$
$$ = sin (\alpha - \beta) $$
$$ = sin \alpha cos \beta - sin \beta cos \alpha $$
$$ = \frac{(sin \alpha cos \beta - sin \beta cos \alpha) \cdot r_1 \cdot r_2}{r_1 \cdot r_2} $$
$$ = \frac{x_1 \cdot y_2 - x_2 \cdot y_1} {r_1 \cdot r_2} $$

而这里,我们要的只是 sin(<OA, OB>) 的符号,而 r1r2 又都是恒正的,因此只需判断 x1 * y2 - x2 * y1 的符号即可。

这个方法的数学背景是 叉乘,可以前往 Wikipedia 了解更多。

思路小结

  • 由点 A,B,C,D 计算出向量 AC,AD,BC,BD

  • 计算 sin(<AC, AD>) * sin(<BC, BD>)sin(<CA, CB>) * sin(<DA, DB>),若皆为非正数,则相交;否则,不相交。

实现

终于到代码部分了,想必大家都已不耐烦了吧。

在向量的辅助下,代码显得异常简单。

ZERO = 1e-9

def negative(vector):
    """取反"""
    return Vector(vector.end_point, vector.start_point)

def vector_product(vectorA, vectorB):
    '''计算 x_1 * y_2 - x_2 * y_1'''
    return vectorA.x * vectorB.y - vectorB.x * vectorA.y

def is_intersected(A, B, C, D):
    '''A, B, C, D 为 Point 类型'''
    AC = Vector(A, C)
    AD = Vector(A, D)
    BC = Vector(B, C)
    BD = Vector(B, D)
    CA = negative(AC)
    CB = negative(BC)
    DA = negative(AD)
    DB = negative(BD)

    return (vector_product(AC, AD) * vector_product(BC, BD) <= ZERO) \
        and (vector_product(CA, CB) * vector_product(DA, DB) <= ZERO)

一气呵成,没有恼人的除法,没有情况讨论,只是纯粹的简单运算。

查看原文

赞 11 收藏 33 评论 11

ecmadao 回答了问题 · 2017-05-11

解决有什么将网页转换为 PDF 的方法?(Node)

已通过 phantom 实现,速度上也没有很慢

关注 7 回答 4

ecmadao 赞了问题 · 2017-05-03

解决json web token过期后怎么搞

现在不是流行restful么,认证的时候用jwt,token有过期时间,有人说时间越短越好,
那过期后怎么认证,要在登录吗,过期时间多久比较好

关注 32 回答 10

ecmadao 关注了问题 · 2017-05-03

解决json web token过期后怎么搞

现在不是流行restful么,认证的时候用jwt,token有过期时间,有人说时间越短越好,
那过期后怎么认证,要在登录吗,过期时间多久比较好

关注 32 回答 10

ecmadao 提出了问题 · 2017-02-13

解决有什么将网页转换为 PDF 的方法?(Node)

需求如题,想请教有什么好的办法可以将网页转换为 PDF 吗?

目前经过调研,我目前发现的方法如下(使用 Node ):

这是我尝试的目前效果最好的方法,可以直接自行封装一个脚本,由前端调用 API 后触发。但渲染速度不尽人意,不过也应该有一些优化的空间。

// demo
const phantom = require('phantom');

(async function() {
    const instance = await phantom.create();
    const page = await instance.createPage();

    await page.property('viewportSize', {width: 1024, height: 600});
    const status = await page.open('https://stackoverflow.com/');
    console.log(`Page opened with status [${status}].`);

    await page.render('stackoverflow.pdf');
    console.log(`File created at [./stackoverflow.pdf]`);

    await instance.exit();
}());

生成网页截屏。但只能是 png、jpg、jpeg 形式,且无法滚屏截图,只能指定图片高度或者按照窗口大小截取(目前没有找到合适的方式)

// demo
var webshot = require('webshot');

webshot('google.com', 'google.png', function(err) {
  // screenshot now saved to google.png
});

暂时还没有尝试,看见在 stackoverflow 上有人推荐,也有人反馈说该库有很奇怪的 bug

相对于上面的方法,该库是在前端调用,将一个指定的 DOM 转为 base64 格式的图片,并可以保留其样式。但缺点很明显,由于是前端使用,在 DOM 数目较多时会有明显的卡顿,体验不好。

// demo
domtoimage.toJpeg(document.getElementById('my-node'))
    .then(function (dataUrl) {
        var link = document.createElement('a');
        link.download = 'my-image-name.jpeg';
        link.href = dataUrl;
        link.click();
    });

关注 7 回答 4

ecmadao 回答了问题 · 2017-01-25

解决npm install安装时忘记--save,后来怎么补,难道要重装一次吗

你在 package.json 里面把包写到 dependency 或者 devDependency 里就行了。因为实际上包的源文件已经下载到了你项目的 node_module 文件夹里面,在 package.json 里加上这句只是为了保证之后可以通过 npm i 安装上需要依赖的资源

关注 4 回答 3

ecmadao 分享了头条 · 2017-01-25

网站名称叫做 hacknical ,一个查看你 github 数据总结的网站,一键(通过 github )登录,然后抓取你的公开信息,整理好之后以数据可视化的形式展现出来。做它的初衷很简单,毕竟年末了,我想看看自己在 github 上都干了些什么。因为工作太忙,所以也没有成块的时间...

赞 16 收藏 14 评论 14

认证与成就

  • 获得 118 次点赞
  • 获得 11 枚徽章 获得 0 枚金徽章, 获得 1 枚银徽章, 获得 10 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

  • react-times

    一个基于React的时间选择组件,没有jQuery依赖

  • Coding-Guide

    一路下来的学习笔记,涉及到前端工程、产品与设计、文章翻译、Python、Node等

注册于 2015-04-02
个人主页被 1.4k 人浏览