关于 Kafka 的一点思考

1. Kafka 消费者可能遇到的问题

Kafka 消息队列在消费时可能遇到两个问题:

  1. 消息重复(Producer 设置 acksall 可能会有重复数据)
  2. 消息乱序(网络延迟)

但是这两者在处理的时候却必须综合考虑,如果消息的生产者按顺序生产消息,消费者在消费的时候也会期望消息的有序性,但是如果消息发生了重复或者乱序,消费者是无法区分的,也就无法针对两种情况分别进行处理。

因此我们必须通过某些手段来区分和解决这些问题。

2. 解决思路

针对的业务场景不同,我们能够使用的手段也不尽相同,总体来说:

  1. 唯一标示
  2. 状态机机制
  3. 幂等的方法

2.1 唯一标识

生产者在生产消息的时候为每一条消息增加一个递增的、唯一的标识。消费者在消费之前首先查询数据库该消息是否已经消费,如果已经消费了则直接忽略。该手段用来处理重复的数据简单直接。

在唯一标识生成的时候还可以附加生成规则,比如 唯一标识 = 批次号 + 版本序号。对消息顺序有严格要求的场景,可以根据同一批次对消息进行缓存,等同一批次内的版本序号都齐了再进行处理。

2.2 状态机机制1

状态机机制针对于有严格状态流转的业务场景,比如工作流程的处理、资源状态的转换等等。业务流程本身可以表示成一个状态机。那么在生产数据的时候可以把目标实体的当前状态和目标状态写入消息中,消费的过程中通过消息的当前状态和实体实际的当前状态进行对比,如果一致再进行处理。

如果不一致可以通知上游重发,也可以针对业务场景设置不同策略。

2.3 幂等的方法2

幂等性:

HTTP方法的幂等性是指一次和多次请求某一个资源应该具有同样的副作用。同一个请求,发送一次和发送N次效果是一样的。

幂等性所表达的概念关注的是数学层面的运算和数值,并没有提及到数值的安全性问题。所以 RESTful 设计中将幂等性和安全性是作为两个不同的指标来衡量,如 POSTPUTGETDELETE 操作:

重要方法 安全 幂等
GET
DELETE
PUT
POST

因此,幂等性是系统的接口对外一种承诺(而不是实现),承诺只要调用接口成功,外部多次调用对系统的影响是一致的。声明为幂等的接口会认为外部调用失败是常态,并且失败之后必然会有重试。

对于消息队列的消费者也是类似的。HTTP 方法中相对于 POST 方法,PUT 方法是幂等的。从资源状态转换的角度来考虑或者从容错的角度出发,在某些应用场景下将处理流程进行改造。

既然 POST 方法意味着创建资源的实例,那么我们可以将 POST 方法尽量改造成 PUT 方法。比如:如果消费者从消息队列中读取消息来进行资源的创建,我们可以给每条消息增加唯一标识,创建资源的时候如果该唯一标识不存在则直接创建资源,否则进行全量的更新(类似 MySQLon duplicate key update 子句或者 Replace 语法)。ElasticSearch 可以通过 _index_type_id 组合确定唯一一条文档,如果在写入数据的时候三者重复了,那么ElasticSearch 会用新的文档完全覆盖老的文档。这也是通过 KafkaElasticSearch 中导入数据时避免重复数据的一个技巧。

其实不仅幂等的方法满足幂等性,唯一标识的方案、状态机机制同样满足了幂等的要求。这三种方案可以进行任意地组合以应对复杂的业务场景。

参考文章

  1. 消息队列设计精要
  2. 分布式系统接口幂等性
  3. 幂等性 个人理解及应用

Insert Or Update 后续

1. 问题描述

使用 insert … on duplicate key update 语法实现 insertOrUpdate 之后出现了几个新问题,首先给出测试代码:

DROP database if EXISTS test;
CREATE database test;

DROP TABLE if EXISTS test.person;
CREATE table test.person (
    id int not NULL PRIMARY KEY auto_increment,
    name VARCHAR(100) not NULL DEFAULT '' UNIQUE COMMENT '名字',
    age int not NULL DEFAULT 0 COMMENT '年龄',
    gender VARCHAR(20) NOT NULL DEFAULT '' COMMENT '性别',
    addresses text NOT NULL COMMENT '地址'
)ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_bin COMMENT='person';

MyBatis 语句:

<insert id="insertOrUpdate" useGeneratedKeys="true" keyProperty="id">
    insert into test.person
    (id, name, age, gender, addresses)
    VALUES
    <foreach collection="list" item="person" separator=",">
        (id, #{person.name}, #{person.age}, #{person.gender},
        #{person.addresses, typeHandler=com.note4code.test.persistence.typeHandler.GenericMapHandler})
    </foreach>
    on duplicate key update
    age = VALUES(age),
    gender = VALUES(gender),
    addresses = VALUES(addresses)
</insert>

Java 代码:

package com.note4code.test.service;

import com.note4code.test.domain.Address;
import com.note4code.test.domain.Gender;
import com.note4code.test.domain.Person;
import com.note4code.test.domain.Province;
import junit.framework.TestCase;
import org.assertj.core.util.Lists;
import org.assertj.core.util.Maps;
import org.junit.Before;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.context.SpringBootTest;
import org.springframework.test.context.junit4.SpringRunner;

import java.io.IOException;
import java.util.List;
import java.util.Map;

@RunWith(SpringRunner.class)
@SpringBootTest
public class PersonServiceTest extends TestCase{

  @Autowired
  private PersonService personService;

  private Person me;
  private Person you;
  private Person him;

  @Before
  public void initData() {
    Address address = new Address(Province.BEIJING, "北京", "学院路");
    Map<Province, Address> map = Maps.newHashMap(Province.BEIJING, address);

    this.me = new Person();
    this.me.setName("me");
    this.me.setAge(27);
    this.me.setGender(Gender.MALE);
    this.me.setAddresses(map);

    this.you = new Person();
    this.you.setName("you");
    this.you.setAge(25);
    this.you.setGender(Gender.FEMALE);
    this.you.setAddresses(map);

    this.him = new Person();
    this.him.setName("him");
    this.him.setAge(25);
    this.him.setGender(Gender.MALE);
    this.him.setAddresses(map);
  }

  @Test
  public void testForOnDuplicateKey() {
    personService.addPerson(me);
    int id = me.getId();

    me.setAge(28);
    List<Person> people = Lists.newArrayList(me, you, him);
    personService.addOrUpdate(people);
    assertTrue(id != me.getId());
  }
}

运行测试用例,得到的输出结果是:

people = [Person{id=2, name=’me’, age=28, gender=MALE, addresses={BEIJING=Address{province=BEIJING, city=’北京’, street=’学院路’}}}
, Person{id=0, name=’you’, age=25, gender=FEMALE, addresses={BEIJING=Address{province=BEIJING, city=’北京’, street=’学院路’}}}
, Person{id=0, name=’him’, age=25, gender=MALE, addresses={BEIJING=Address{province=BEIJING, city=’北京’, street=’学院路’}}}
]

另外,查询数据库可以得到:

mysql root@localhost:test> SELECT * from person;
+------+--------+-------+----------+--------------------------------------------------------------------+
|   id | name   |   age | gender   | addresses                                                          |
|------+--------+-------+----------+--------------------------------------------------------------------|
|    1 | me     |    28 | MALE     | {"BEIJING":{"province":"BEIJING","city":"北京","street":"学院路"}} |
|    2 | you    |    25 | FEMALE   | {"BEIJING":{"province":"BEIJING","city":"北京","street":"学院路"}} |
|    3 | him    |    25 | MALE     | {"BEIJING":{"province":"BEIJING","city":"北京","street":"学院路"}} |
+------+--------+-------+----------+--------------------------------------------------------------------+
3 rows in set
Time: 0.002s
mysql root@localhost:test> SELECT LAST_INSERT_ID();
+--------------------+
|   LAST_INSERT_ID() |
|--------------------|
|                 17 |
+--------------------+
1 row in set
Time: 0.001s

从上面的示例可以看出 3 个问题:

  1. 即使使用了 userGeneratedKeys = true 并指定了 keyProperty,只回写了第一行的主键。
  2. 回写的主键与数据库不一致。
  3. LAST_INSERT_ID() 的值发生了跳跃,按理来说应该是 3,但是变成了 17。

2. 疑问

看到这里其实很让人费解:

  1. 为什么只返回了一个主键?
  2. useGeneratedKeys 返回的主键不对那么到底是什么?
  3. 为什么 LAST_INSERT_ID() 发生了跳变?

首先从 userGeneratedKeys 说起:

useGeneratedKeys(仅对 insert 和 update 有用)这会令 MyBatis 使用 JDBC 的 getGeneratedKeys 方法来取出由数据库内部生成的主键(比如:像 MySQL 和 SQL Server 这样的关系数据库管理系统的自动递增字段),默认值:false。

引自 insert, update 和 delete

With older JDBC drivers for MySQL, you could always use a MySQL-specific method on theStatement interface, or issue the query SELECT LAST_INSERT_ID() after issuing an INSERT to a table that had an AUTO_INCREMENT key.

First, we demonstrate the use of the new JDBC 3.0 method getGeneratedKeys() which is now the preferred method to use if you need to retrieve AUTO_INCREMENT keys and have access to JDBC 3.0. The second example shows how you can retrieve the same value using a standard SELECT LAST_INSERT_ID() query. 

引自 Retrieving AUTO_INCREMENT Column Values through JDBC

也就是说 Mybatis 通过 useGeneratedKeys 返回的是 LAST_INSERT_ID()

接着说,那么为什么只回写了一个主键,并且还是错的呢?

If you insert multiple rows using a single INSERT statement, LAST_INSERT_ID() returns the value generated for the first inserted row only.

引自 LAST_INSERT_ID()LAST_INSERT_ID(expr)

按照上文的说法,批量插入只会返回插入的第一条数据的主键。第一次插入 me 这个对象之后 LAST_INSERT_ID() 返回 1。接着在插入 people 时首先是更新了 me 这行记录,而 LAST_INSERT_ID() 没有变。直到插入第二行 you 这个对象,此时 LAST_INSERT_ID() 返回 2,也就是批量插入后回写的主键值。这同时解释了为什么只回写了一个主键并且回写的主键与数据库没有对应上。

最后,关于 LAST_INSERT_ID() 的跳变,我也找到了一些参考资料:

  1. 官方文档:InnoDB AUTO_INCREMENT Lock Modes
  2. 其实这个说的更加简洁清楚:AUTO_INCREMENT 字段的GAP

Insert Or Update

1. MySQL 批量插入

有的时候会有这样的需求:

  1. 批量写入数据,但是数据可能存在主键或者唯一性索引的冲突写到一半就失败了。
  2. 每天批量更新表,新数据插入,旧数据更新。

于是我们不禁想到是否能实现一个 insertOrUpdate 方法呢?事实上,MySQL 给出了标准 SQL 的两种扩展来帮我们实现这种需求。

2. INSERT ... ON DUPLICATE KEY UPDATE

标准 SQL 的扩展,如果插入时遇到主键冲突或者唯一性约束不满足则会执行 update 操作,例如:

INSERT INTO table (a,b,c) VALUES (1,2,3)
  ON DUPLICATE KEY UPDATE c=c+1;

UPDATE table SET c=c+1 WHERE a=1;

支持多行插入:

INSERT INTO table (a,b,c) VALUES (1,2,3),(4,5,6)
  ON DUPLICATE KEY UPDATE c=VALUES(a)+VALUES(b);

ON DUPLICATE KEY UPDATE 子句中的 VALUES(a) 表示的是如果没有冲突将会插入 a 列的值,即 1 或者 4。

ON DUPLICATE KEY UPDATE 子句不适宜在有多个唯一性索引的表上使用。

参考:14.2.5.3 INSERT … ON DUPLICATE KEY UPDATE Syntax

3. Replace

Replace 是标准 SQL 的扩展,等价于 inserts/deletes and inserts

REPLACE [LOW_PRIORITY | DELAYED]
    [INTO] tbl_name
    [PARTITION (partition_name,...)]
    [(col_name,...)]
    {VALUES | VALUE} ({expr | DEFAULT},...),(...),...

REPLACE [LOW_PRIORITY | DELAYED]
    [INTO] tbl_name
    [PARTITION (partition_name,...)]
    SET col_name={expr | DEFAULT}, ...

REPLACE [LOW_PRIORITY | DELAYED]
    [INTO] tbl_name
    [PARTITION (partition_name,...)]
    [(col_name,...)]
    SELECT ...

所有列的值都从 Replace 语句中获取,无法从现有的行中获取值,如果有的列没有指定值那么会给定默认值。如果在指定值的时候使用了 SET col_name = col_name + 1 语句,等价于 SET col_name = DEFAULT(col_name) + 1

Replace 语句的返回值表示影响的行数,影响行数 = 删除的行数 + 插入的行数。对于单行的 Replace 操作,如果返回 1 表示仅仅插入了新的一行,如果大于 1 则表示删除了至少一行并插入了一行。

参考:14.2.8 REPLACE Syntax

3. 异同分析

从文档的说明来看,至少有两点差异:

  1. INSERT … ON DUPLICATE KEY UPDATE 在插入时可以使用现有行的值, Replace 不支持。
    mysql root@localhost:test> create table tb_table (a int not NULL PRIMARY key auto_increment, b int NOT NULL DEFAULT 0, c int NOT NULL DEFAULT 0)
    Query OK, 0 rows affected
    Time: 0.042s
    mysql root@localhost:test> insert into tb_table (a, b, c) VALUES (1,2,3);
    Query OK, 1 row affected
    Time: 0.024s
    mysql root@localhost:test> INSERT INTO tb_table (a, b, c) values (1,5,6) on  DUPLICATE KEY UPDATE b = values(b) + b;
    Query OK, 2 rows affected
    Time: 0.025s
    mysql root@localhost:test> SELECT * from tb_table;
    +-----+-----+-----+
    |   a |   b |   c |
    |-----+-----+-----|
    |   1 |   7 |   3 |
    +-----+-----+-----+
    1 row in set
    Time: 0.001s
    
  2. INSERT … ON DUPLICATE KEY UPDATE 在不满足主键约束或者唯一性约束的时候是更新操作,所以主键不会变。而 Replacedeletes inserts 也就是说老的记录会被删除,如果不指定主键值那么可能会破坏已有的外键关联(比如主键是自增产生,插入的时候不指定主键值)。
    mysql root@localhost:test> create table tb_table (a int not NULL PRIMARY key auto_increment, b int NOT NULL DEFAULT 0 unique, c int NOT NULL DEFAULT 0)
    Query OK, 0 rows affected
    Time: 0.027s
    mysql root@localhost:test> show create table tb_table;
    +----------+----------------+
    | Table    | Create Table   |
    |----------+----------------|
    | tb_table | CREATE TABLE `tb_table` (
     `a` int(11) NOT NULL AUTO_INCREMENT,
     `b` int(11) NOT NULL DEFAULT '0',
     `c` int(11) NOT NULL DEFAULT '0',
     PRIMARY KEY (`a`),
     UNIQUE KEY `b` (`b`)
    ) ENGINE=InnoDB DEFAULT CHARSET=utf8                |
    +----------+----------------+
    1 row in set
    Time: 0.020s
    mysql root@localhost:test> insert into tb_table (b,c) VALUES (2,3);
    Query OK, 1 row affected
    Time: 0.013s
    mysql root@localhost:test> SELECT * from tb_table;
    +-----+-----+-----+
    |   a |   b |   c |
    |-----+-----+-----|
    |   1 |   2 |   3 |
    +-----+-----+-----+
    1 row in set
    Time: 0.001s
    mysql root@localhost:test> replace into tb_table (b,c) values (2,4);
    Query OK, 2 rows affected
    Time: 0.023s
    mysql root@localhost:test> SELECT * from tb_table;
    +-----+-----+-----+
    |   a |   b |   c |
    |-----+-----+-----|
    |   2 |   2 |   4 |
    +-----+-----+-----+
    1 row in set
    Time: 0.001s
    mysql root@localhost:test> replace into tb_table (b,c) values (2,4),(3,5);
    Query OK, 3 rows affected
    Time: 0.007s
    mysql root@localhost:test> SELECT * from tb_table;
    +-----+-----+-----+
    |   a |   b |   c |
    |-----+-----+-----|
    |   3 |   2 |   4 |
    |   4 |   3 |   5 |
    +-----+-----+-----+
    2 rows in set
    Time: 0.001s
    mysql root@localhost:test> insert into tb_table (b,c) values (2,8) on  DUPLICATE KEY UPDATE c = VALUES(c);
    Query OK, 2 rows affected
    Time: 0.013s
    mysql root@localhost:test> SELECT * from tb_table;
    +-----+-----+-----+
    |   a |   b |   c |
    |-----+-----+-----|
    |   3 |   2 |   8 |
    |   4 |   3 |   5 |
    +-----+-----+-----+
    2 rows in set
    Time: 0.001s
    

Melkman算法

1. 问题描述

给定一组二维坐标的集合,求从这个集合中找出这些二维坐标的外围边界。经过查询,确定了这是一个二维凸包的问题,属于计算几何的范畴。

2. Melkman 算法

经过查询,发现二维凸包的解法有很多种,其中 Melkman 算法是其中比较好的解决方案。Melkman 算法在点排序后可以以 O(n) 的时间复杂度计算凸包。同时 Melkman 还是一种在线的算法,虽然我这里用不到这个特性。

Melkman 算法的大致思想是这样的:首先找出所有点集合中某一个维度上的最大或者最小值,然后按照顺时针或者逆时针的方向逐个遍历集合中剩余的点。要找出集合中最外围的点,有一个不变的特性必须要保持住:

假设 P_i,P_j,P_k 是凸包上逆时针方向上的连续 3 个点,那么它们必然保持一种左转的趋势,即:

    \[\overrightarrow{P_iP_j}\times\overrightarrow{P_jP_k}>0\]

如果用 (x_i,y_i),(x_j,y_j),(x_k,y_k) 来表示这三个点,亦即:

    \[\overrightarrow{P_iP_j}=(x_j-x_i,y_j-y_i)\]

    \[\overrightarrow{P_jP_k}=(x_k-x_j,y_k-y_j)\]

那么根据向量叉积公式必须满足:

    \[(x_j-x_i)<em>(y_k-y_j)-(x_k-x_j)</em>(y_j-y_i)>0\]

3. 算法描述

Melkman 算法使用双端队列来实现这个原理,假设双端队列为 D。所有队列操作可以用入队首、出队首、入队尾、出队尾来描述,实际操作过程可以描述为:

  1. 假设点集合的坐标可以表示为 (x,y),那么首先找出 x 值最小的点记为 P_0

  2. 然后选定一个方向,比如逆时针方向。然后计算所有剩余的每一个点 P_0P_x 形成的向量 \overrightarrow{P_0P_x}y 轴负方向的夹角。根据向量的点积公式计算出夹角之后根据夹角从小到大就行排序得到有序集合 S={P_0,P_1,P_2…P_{n-1}}

  3. 记某一时刻 D 的状态为:P_tP_{t-1}…P_0...P_{b-1}P_b ,对于 S 中的每一个点进行遍历:

    3.1 如果是 P_0 则首先将 P_0 入队尾,如果是 P_1 则入队尾,如果是 P_2 则入队首并且入队尾。

    3.2 假设遍历到当前节点 P_i
    ​ 3.2.1 如果 P_{b-1}P_bP_i 能保持左转特性则继续,否则 P_b 出队尾,如此往复直到 P_{b-m-1}P_{b-m}P_i 能够满足左转特性,P_i 入队尾。

    ​ 3.2.2 如果 P_iP_tP_{t-1} 能保持左转特性则继续,否则 P_t 出队首,如此往复直到 P_iP_{t-n}P_{t-n-1} 能够满足左转特性,P_i 入队首。

  4. 返回 D

4. 算法实现

首先给出数据结构,PointPolygon

Point.java

package com.xxx.dvp.rest.domain.model;

/**
 * User: wuzhiyu.
 * Date: 16/12/21.
 * Time: 15:18.
 */
public class Point {
  private double lng;
  private double lat;

  /* Constructors */

  /* Setters and Getters */
}

Polygon.java

package com.xxx.dvp.rest.domain.model;

import com.google.common.collect.Lists;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * The type Melkman polygon.
 */
public class Polygon {
  private List<Point> points;

  /* Constructors  */

  /* Setter and Getter */

  /**
   * Contains boolean.
   * 源代码来自 .NET Framework。多边形边界上的点不算多边形内
   *
   * @param point the melkman point
   * @return the boolean
   */
  public boolean contains(Point point) {
    int crossings = 0;
    for (int index = 0; index < getPoints().size() - 1; index++) {
      double slope = getPoints().get(index + 1).getSlope(
          getPoints().get(index));
      boolean cond1 = (getPoints().get(index).getLng() <= point.getLng())
          && (point.getLng() < getPoints().get(index + 1).getLng());
      boolean cond2 = (getPoints().get(index + 1).getLng() <= point.getLng())
          && (point.getLng() < getPoints().get(index).getLng());
      boolean above = ((point.getLng() - getPoints().get(index).getLng()) * slope
          + getPoints().get(index).getLat()) > point.getLat();
      if ((cond1 || cond2) && above) {
        crossings++;
      }
    }
    return (crossings % 2 != 0);
  }

  /**
   * On border boolean.
   *
   * @param point the point
   * @return the boolean
   */
  public boolean onBorder(Point point) {
    for (int index = 0; index < getPoints().size() - 1; index++) {
      double slope = getPoints().get(index + 1).getSlope(getPoints().get(index));
      double latOnLine = (point.getLng() - this.points.get(index).getLng()) * slope
          + this.points.get(index).getLat();
      if (latOnLine == point.getLat()) {
        return true;
      }
    }
    return false;
  }

  @Override
  public String toString() {
    return "Polygon{" + "points=" + points + '}';
  }
}

Melkman 算法:

package com.xxx.dvp.rest.domain.service;

import com.xxx.dvp.rest.domain.model.Boundary;
import com.xxx.dvp.rest.domain.model.Point;
import com.xxx.dvp.rest.domain.model.Polygon;
import com.xxx.dvp.rest.infra.persistence.conf.DataExampleConfig;
import com.fasterxml.jackson.databind.ObjectMapper;
import org.geojson.Feature;
import org.geojson.FeatureCollection;

import java.io.IOException;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Deque;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * User: wuzhiyu.
 * Date: 16/12/26.
 * Time: 10:45.
 */
public class PointService {

  public static void main(String[] argv) throws IOException {
    PointService pointService = new PointService();
    FeatureCollection collection = new FeatureCollection();
    String fileName = "cluster_%d.txt";

    for (int i = 0; i < 8; i++) {
      List<Point> points = DataExampleConfig.getPoints(String.format(fileName, i));
      Polygon polygon = pointService.getConvexHullWithMelkman(points);

      Boundary boundaryOfPolygon = GeoService.getBoundaryOfPolygon(polygon);
      Set<String> gridsOfPolygon = GridService.getGrids(boundaryOfPolygon);

      gridsOfPolygon = GridService.getGridsInPolygon(gridsOfPolygon, polygon);

      List<Point> edgeOfGrids = GridService.getEdgeOfGrids(gridsOfPolygon);

      Polygon newPolygon = new Polygon(edgeOfGrids);

      GridService.outputBoundaryGrids(boundaryOfPolygon);
      GridService.outputPoints(edgeOfGrids);

      Feature polygonFeature = GeoService.getPolygonFeature(newPolygon);

      collection.add(polygonFeature);

      List<Point> errorPoints = points.stream()
          .filter(point -> !polygon.contains(point))
          .filter(point -> !polygon.onBorder(point))
          .collect(Collectors.toList());
      System.out.println("errorPoints = " + errorPoints);
    }

    ObjectMapper objectMapper = new ObjectMapper();
    System.out.println(objectMapper.writeValueAsString(collection));
  }

  public Polygon getConvexHullWithMelkman(List<Point> pointList) {
    if (pointList.size() < 3) {
      return null;
    }

    sortByAngle(pointList);

    Deque<Point> deque = new ArrayDeque<>();

    pointList.forEach(point -> {
      switch (deque.size()) {
        case 0:
        case 1:
          deque.offerLast(point);
          return;
        case 2:
          deque.offerLast(point);
          deque.offerFirst(point);
          return;
        default:
          Point lastRightVertex = deque.pollLast();
          Point lastLeftVertex = deque.pollFirst();

          if (this.isLeftTurn(deque.peekLast(), lastRightVertex, point)
              && this.isLeftTurn(point, lastLeftVertex, deque.peekFirst())) {
            return;
          }

          while (!this.isLeftTurn(deque.peekLast(), lastRightVertex, point)) {
            lastRightVertex = deque.pollLast();
          }
          deque.offerLast(lastRightVertex);
          deque.offerLast(point);

          while (!this.isLeftTurn(point, lastLeftVertex, deque.peekFirst())) {
            lastLeftVertex = deque.pollFirst();
          }
          deque.offerFirst(lastLeftVertex);
          deque.offerFirst(point);
          return;
      }
    });

    return new Polygon(new ArrayList<>(deque));
  }

  private void sortByAngle(List<Point> pointList) {
    Point minLngPoint = pointList.stream()
        .min(Comparator.comparing(Point::getLng)).get();
    pointList.remove(minLngPoint);
    pointList.sort(new Comparator<Point>() {
      @Override
      public int compare(Point o1, Point o2) {
        return Double.compare(angleWithSouth(minLngPoint, o1),
            angleWithSouth(minLngPoint, o2));
      }
    });

    pointList.add(0, minLngPoint);
  }

  public boolean isLeftTurn(Point point1, Point point2, Point point3) {
    return crossProduct(point1, point2, point3) > 0;
  }

  public double crossProduct(Point point1, Point point2, Point point3) {
    double x1 = point2.getLng() - point1.getLng();
    double y1 = point2.getLat() - point1.getLat();
    double x2 = point3.getLng() - point2.getLng();
    double y2 = point3.getLat() - point2.getLat();
    return x1 * y2 - x2 * y1;
  }

  public double dotProduct(Point point1, Point point2, Point point3) {
    double x1 = point2.getLng() - point1.getLng();
    double y1 = point2.getLat() - point1.getLat();
    double x2 = point3.getLng() - point2.getLng();
    double y2 = point3.getLat() - point2.getLat();
    return x1 * x2 + y1 * y2;
  }

  public double angleWithSouth(Point point1, Point point2) {
    Point point = new Point(point1.getLng(), point1.getLat() + 1);
    return Math.acos(this.dotProduct(point, point1, point2)
        / (this.norm(point, point1) * this.norm(point1, point2)));
  }

  public double norm(Point point1, Point point2) {
    double deltaLat = point2.getLat() - point1.getLat();
    double deltaLng = point2.getLng() - point1.getLng();

    return Math.sqrt(deltaLat * deltaLat + deltaLng * deltaLng);
  }
}

上文的代码引用了一个依赖:

<!-- geojson -->
<dependency>
    <groupId>de.grundid.opendatalab</groupId>
    <artifactId>geojson-jackson</artifactId>
    <version>1.7</version>
</dependency>

输出的 json 结果可以在 geojson 做可视化展示。

5. 参考文献

  1. http://maxgoldste.in/melkman/
  2. http://w3.impa.br/~rdcastan/Cgeometry/
  3. 漫话二维凸包