算法课外思考题七

思考题

发布日期: 2023-07-10

文章字数: 1.6k

阅读时长: 7 分

问题一 Voronoi图及相关算法的调研报告

Voronoi图的定义和相关性质

Voronoi Diagram又称Thiessen Polygon，其数学描述如下：

设平面区域B上有一组离散点$\left(X_i, Y_j\right)(\mathrm{i}=1,2,3, \ldots, \mathrm{k} ; \mathrm{j}=1,2,3, \ldots, \mathrm{k}, \mathrm{k}$ 为离散点点数) ，将区域B用一组直线段分成k个互相邻接的多边形，使得：

每个多边形内含有且仅含有一个离散点；
若区域B上任意一点$\left(x^1, y^1\right)$位于含离散点$\left(x_i, y_j\right)$的多边形内，不等式$\sqrt{\left(x^1-x_i\right)^2+\left(y^1-y_j\right)^2}<\sqrt{\left(x^1-x_j\right)^2+\left(y^1-y_i\right)^2}$在$i\neq j$时恒成立；
若点$\left(x^1, y^1\right)$位于含离散点$\left(x_i, y_j\right)$的两个多边形的公共边上，则等式$\sqrt{\left(x^1-x_i\right)^2+\left(y^1-y_j\right)^2}=\sqrt{\left(x^1-x_j\right)^2+\left(y^1-y_i\right)^2}$成立

Voronoi图的特征如下：

每个泰森多边形内仅含有一个离散点数据
泰森多边形的点到相应离散点的距离最近
位于泰森多边形边上的点到其两边的离散点的距离相等

Voronoi图生成算法

使用分治法

VoronoiDiagram* partition(vector<point>& origin,int left,int right)
{
    if(right-left<3)
    {
        VoronoiDiagram* result=smallVD(origin,left,right);
        return result;
    }else{
        VoronoiDiagram* leftresult=partition(origin,left,(left+right)/2);
        VoronoiDiagram* rightresult=partition(origin,(left+right)/2+1,right);
        return mergeVD(leftresult,rightresult);
    }
}
VoronoiDiagram* mergeVD(VoronoiDiagram* left,VoronoiDiagram* right)
{
    VoronoiDiagram* result=new VoronoiDiagram();
    vector<Devidechain> devidechain;
    left->convex hull=getConvexHull(left->sites);    
    right->convex hull=getConvexHull(right->sites);
    tangentline(left->convex,right->convex hull,*leftMax,*leftMin,*rightMax,*rightMin);
    bool tobottom=false;
    do
    {
        chain=bisector(leftMax,rightMax);
        leftpoint=IntersectionPoint(leftMax,chain);
        rightpoint=IntersectionPoint(rightMax,chain);
        if(leftpoint.y>rightpoint.y){
            updateLeftSite();
        }else if(leftpoint.y<rightpoint.y){
            updateRightSite();
        }else{
            break;
        }
    }while(!tobottom);
    connectchain();
    result=(*right)+(*left);
    return result;
}

Lawson算法

建立一个大三角形，将所有数据点包围起来
向三角形中插入一点，将该点与三角形三个顶点项链，形成三个新的三角形
逐个对三角形进行空外接圆测试，用Lawson的局部优化过程进行优化（交换对角线保证Delaunay三角网的形成）

Bowyer-Watson算法

构造一个超级三角形，包含所有散点，放入三角形链表
将散点依次插入，在三角形链表中找出外接圆包含插入点的三角形，删除三角形的公共边，将插入点同三角形的顶点全部连接起来，完成一个点在Delaunay三角形链表中的插入
对新三角形进行优化，将形成的三角形放入Delaunay三角形链表
循环2.至所有散点插入完毕

Voronoi图的应用

计算最近邻问题

#include <iostream>
#include <vector>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Voronoi_diagram_2.h>

using namespace std;

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2 Point;
typedef CGAL::Voronoi_diagram_2<Kernel> Voronoi_diagram;

int main() {
  vector<Point> points = {{1, 2}, {3, 4}, {5, 6}, {7, 8}};
  Voronoi_diagram voronoi;
  voronoi.insert(points.begin(), points.end());

  Point query_point(2, 3);
  Voronoi_diagram::Locate_result locate_result = voronoi.locate(query_point);
  if (Voronoi_diagram::Face_handle fh = boost::get<Voronoi_diagram::Face_handle>(&*locate_result)) {
    Point closest_point = fh->dual()->point();
    cout << "Closest point: (" << closest_point.x() << ", " << closest_point.y() << ")" << endl;
  }

  return 0;
}

调用了CGAL库（计算几何算法库）

问题二

问题描述

前面已经学习在一维序列中某元素的查找算法，现若查找是在一个二维矩阵中进行，并且矩阵中行列均为升序排列，请给出相应查找算法并进行分析。

问题分析

方法一

采用逐行逐列的搜索方式，从矩阵的左下角开始搜索，直到找到元素或返回未找到

方法二

采用减治算法，也就是说采用二维的二分查找算法，找到矩阵的中心位置的元素，执行大小判断，然后在排除掉的剩余矩阵中继续进行查找

算法实现

#include<iostream>
#include<vector>
using namespace std;

void searchMatrix1(vector<vector<int>>& matrix, int target) {
	if (matrix.size() == 0 || matrix[0].size() == 0) {
		cout << "error" << endl;
		return;
	}
	int r = matrix.size();
	int c = matrix[0].size();
	int x = r - 1, y = 0;
	while (x >= 0 && y < c) {
		if (matrix[x][y] == target) {
			cout << "matrix[" << x+1 << "][" << y+1 << "]" << endl;
			return;
		}
		else if (matrix[x][y] < target) {
			y++;
		}
		else {
			x--;
		}
	}
	cout << "error" << endl;
}
void search(vector<vector<int>>& matrix, int target, int x1, int x2, int y1, int y2) {
	int mx = x1 + (x2 - x1) >> 1;
	int my = y1 + (y2 - y1) >> 1;
	if (matrix[mx][my] == target) {
		cout << "matrix[" << mx + 1 << "][" << my + 1 << "]" << endl;
		return;
	}
	else if (matrix[mx][my] < target) {
		search(matrix, target, mx + 1, x2, y1, my);
		search(matrix, target, x1, mx, my + 1, y2);
		search(matrix, target, mx + 1, x2, my + 1, y2);
	}
	else {
		search(matrix, target, x1, mx - 1, my, y2);
		search(matrix, target, mx, x2, y1, my - 1);
		search(matrix, target, x1, mx - 1, y1, my - 1);
	}
	cout << "error" << endl;
}
void searchMatrix2(vector<vector<int>>& matrix, int target) {
	int r = matrix.size();
	int c = matrix[0].size();
	int x1 = 0, y1 = 0, x2 = r - 1, y2 = c - 1;
	search(matrix,target,x1,x2,y1,y2);
}

int main() {
	vector<vector<int>> matrix = { {1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30} };
	searchMatrix1(matrix, 9);
	searchMatrix2(matrix, 9);
}