algorithm

简单多边形的判定

在实际工作中,需要在照片上选定一个范围,这个范围是个多边形,并且是个简单多边形,我们需要判定是否是个合法的简单多边形,主要判定的是任意两边不能交叉。

# 判断两条线段相交

我们可以借助向量的知识来判断两个线段是否相交。二维向量的叉乘(cross product)的几何意义是以两向量为邻边的平行四边形的面积。此外,定义两个向量 a, b。 当 aXb < 0, b 对应的线段,在 a 的顺时针方向。当 aXb = 0时, a 与 b 共线。当 aXb > 0,b 在 a 的逆时针方向。 如果两条线段相交,那必然一条线段的终点和起点,在另外一条线段的两侧。

# 判断多边形两边是否相交

简单并且暴力的方法是检测任意两边是否有交点,在复杂度不高的情况下可以使用这种方法。但是显然是有更优解的,目前比较有名的两个算法是 The Bentley-Ottmann AlgorithmThe Shamos-Hoey Algorithm。算法的细节请查看下方的参考,我就不详细描述了。

# 简单多边形判定的实现

export interface Point {
  x: number;
  y: number;
}

export interface Line {
  start: Point;
  end: Point;
}

function samePoint(p1: Point, p2: Point) {
  if (p1.x === p2.x && p1.y === p2.y) {
    return true;
  } else {
    return false;
  }
}

function signedArea(p1: Point, p2: Point, p3: Point) {
  return (p1.x - p3.x) * (p2.y - p3.y) > (p2.x - p3.x) * (p1.y - p3.y);
}

function intersectLine(l1: Line, l2: Line) {
  // consecutive edge return false
  if (
    samePoint(l1.start, l2.start) ||
    samePoint(l1.start, l2.end) ||
    samePoint(l1.end, l2.start) ||
    samePoint(l1.end, l2.end)
  ) {
    return false;
  }
  return (
    signedArea(l1.start, l2.start, l2.end) !==
      signedArea(l1.end, l2.start, l2.end) &&
    signedArea(l1.start, l1.end, l2.start) !==
      signedArea(l1.start, l1.end, l2.end)
  );
}

export function intersectPolygon(points: Array<Point>) {
  const len = points.length;
  for (let i = 0; i < len - 1; i++) {
    for (let j = i + 1; j < len; j++) {
      const l1: Line = {
        start: points[i],
        end: points[(i + 1) % len]
      };
      const l2: Line = {
        start: points[j],
        end: points[(j + 1) % len]
      };

      if (intersectLine(l1, l2)) {
        return true;
      }
    }
  }

  return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

# 总结

简单多边形判定的本质是任意两边是否相交,如果是邻边的话就直接跳过。在复杂度不高的情况下,可以直接使用遍历的方法来实现。

# 参考

Intersections of a Set of Segments

Line Segment Intersection Algorithm

shamos-hoey

使用最小费用最大流模型解决酒店管理收益最大化问题

最近老师布置个作业,很没有头绪,于是各种咨询,大家的解决方案是使用最小费用最大流模型来求解,于是我便花了 3 天时间来理解这个算法.

# 问题描述

问题很简单,你有一个只有 5 个房间的酒店,然后本周会有 18 个订单到来,怎样接受订单可以使本周的收益达到最大值.也就是把这 18 个订单填写到一个 5*7 的表格里 怎么填收益最大,订单要么接受要么拒绝,也可以说是典型的 01 背包问题吧,但用动态规划不好抽象出来状态转移方程,所以我还是选择用最大流来做.每个订单包含 3 个信息:每晚付的房费,从周几开始入住,入住几天.

# 抽象数据模型

因为题目要求是球最大收益,而流模型是最小费用,所以我们把收益取相反数即可.关键是建立容量和权值,因为房间的数量是 5,所以限制源点和汇点的容量是 5,权值是 0.然后中间设置 8 个点,产生 7 条边,每条边代表每天的流,权值为 0,容量为无穷大.这里我们不能简单的连接点来设置订单的边,因为有相同的起始日期和结束日期的订单.这样会造成冲突,如何解决冲突呢? 我们可以在订单的边上再加一个顶点来进行区分.模型图如下所示: model 顶点 11 和顶点 16 是重复边的订单,对应的是第一个订单和第 6 个订单.源码和输入数据可以在文章末尾看到.

# 查找增广路径

这里我们使用Ford–Fulkerson算法来计算每次的增广路径.

# 路径的查找

每次增广路径的查找都需要得到最小权值的路径.查找路径使用的是SPFA算法.

# 第一次查找增广路径

model

# 第一次查找增广路径

model

以此类推求出最后的结果~

# 参考:

Source code

Ford–Fulkerson