Question List in June, 2023

1、工作记录

工作内容不对外公开。

2、日常积累

#algrithom

2.1 判断某个数落在哪个区间

#include <iostream>
#include <vector>

std::vector<int> query(std::vector<float>& nums, float target){
    std::vector<int> result(2, -1);
    int low = 0, high = nums.size() - 1;
    // 边界条件
    if(nums.size() < 2) { return result; }
    if(target > nums.back()) {
        result[0] = high;
        result[1] = -1;
        return result;
    }
    // 寻找右边界
    while(low < high){
        int mid = low + (high - low) * 0.5;
        if(nums.at(mid) < target){ low = mid + 1; }
        else { high = mid; }
    }
    result[1] = high;
    // 寻找左边界
    high = nums.size();
    while(low < high){
        int mid = low + (high - low) * 0.5;
        if(nums.at(mid) > target){ high = mid; }
        else{ low = mid + 1; }
    }
    result[0] = low - 1;
    return result;
}

int main() {
    std::vector<float> nums = {0.9, 1.3, 2.4, 3.6, 4.3, 5.4, 6.2, 7.1};
    std::vector<int> result = query(nums, 2.5);
    std::cout << result[0] << "," << result[1] << std::endl;
    return 0;
}

2.2 计算几何

#计算几何

GC-06: 点是否在多边形内

template<class P>
bool is_point_in_polygon(P& point, std::vector<P>& polygon) {
  //A point is in a polygon if a line from the point to infinity crosses the polygon an odd number of times
  int i, j, nvert = points.size();
  bool c = false;
  // Starting with the edge from the last to the first node
  for(i = 0, j = nvert - 1; i < nvert; j = i++) {
    //If a line from the point into infinity crosses this edge
    if( // One point needs to be above, one below our y coordinate
        ( (polygon[i].y >= point.y ) != (polygon[j].y >= point.y) ) &&
        // ...and the edge doesn't cross our Y corrdinate before our x coordinate (but between our x coordinate and infinity)
        (point.x <= (polygon[j].x - polygon[i].x) * (point.y - polygon[i].y) / (polygon[j].y - polygon[i].y) + polygon[i].x)
      )
      c = !c;
  }
  return c;
}

2.3 布尔运算

实现几何布尔运算的 DICC 算法，求交集时对收集到的内侧边进行收集链接，求并集时对外侧边进行收集链接，求差集时只需要将其中一个多边形方向变为逆时针即可。主要包括四个步骤：

Direction 加方向：由多边形面积计算公式判定多边形方向；
Inter-Clip 剪边：线段求交，用交点集拆分线段；
Collection 收集边：经过剪边操作后，线段上的某点在多边形内，则线段在多边形内；
Connection 链接边：多边形内是连续的线段集，把收集到的边按顺时针方向首尾相连；

2.4 SQLite 给附加数据库建索引

#spatialite 附加数据库索引用 create index [idx name] on test.link; 这种形式会报 SQL 语句异常 Error: near ".": syntax error 错误，正确格式：

ATTACH DATABASE ':test:' AS TEST;
CREATE INDEX TEST.link_idx on link (...)

参考文献

Algorithms & Technologies. # Point in Polygon in C[EB/OL].
stackoverflow. # Point in Polygon Algorithm[EB/OL].
哔哩哔哩. # 多边形的布尔运算（上提出问题）[EB/OL].
哔哩哔哩. # 多边形的布尔运算（下解决方案）[EB/OL].
Kai Hormann. Efficient Clipping of Arbitrary Polygons[EB/OL].
John C,Tipper. Simple Robust Boolean Operations for Triangulated Surfaces[EB/OL].