DSA - 几何算法
几何算法被定义为用于解决与几何形状及其属性相关问题的过程。这些算法可以应用于点、线、多边形和其他几何图形。我们可以在计算机图形学、计算机辅助设计、机器人技术和地理信息系统等各个领域找到它的应用。
与几何算法相关的问题
一些可以使用几何算法解决的常见问题包括−
它可以用于求解不同多边形的面积，例如三角形、矩形等。
我们可以使用几何算法来求两条线的交点。
计算凸包问题。
在不同几何形状内寻找一个点。
几何算法可以解决多边形的三角剖分问题。
重要的几何算法
一些重要的几何算法是−
Graham 扫描算法
扫描线算法
Graham 扫描算法
Graham 扫描算法由 Ronald Graham 于 1972 年开发。该算法主要用于解决凸包问题和最大距离问题。它的应用也体现在其他领域，例如图像处理、机器人技术、配送系统等等。
以下步骤解释了 Graham Scan 算法的工作原理 −
首先，找到 y 坐标最小的点。如果多个点共享 y 坐标的最小值，则选择 x 坐标最小的点。
根据剩余点与最小点的极坐标角对它们进行排序。
对点进行排序后，从最小点和另外两个点开始。这三个点构成凸包的初始部分。
对于每个新点，确定从前两个点出发是左转还是右转。如果是右转，则倒数第二个点不在凸包内。
重复此过程，直到遇到左转路口。
示例
以下示例实际演示了 Graham Scan 算法的工作原理。
#include <stdio.h>
#include <stdlib.h>
// 点的结构体
struct Point2D {
int x, y;
};
// 初始点的全局变量
struct Point2D initialPoint;
// 获取第二个栈顶元素的函数
struct Point2D getSecondTop(struct Point2D Stack[], int* top) {
return Stack[(*top)-1];
}
// 计算两点间距离平方的函数
int calcDistSq(struct Point2D p1, struct Point2D p2) {
return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
}
// 用于查找有序三元组点方向的函数
int getOrientation(struct Point2D p, struct Point2D q, struct Point2D r) {
int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
if (val == 0) return 0;
return (val > 0)? 1: 2;
}
// 用于比较两点的函数
int comparePoints(const void *vp1, const void *vp2) {
struct Point2D *p1 = (struct Point2D *)vp1;
struct Point2D *p2 = (struct Point2D *)vp2;
int o = getOrientation(initialPoint, *p1, *p2);
if (o == 0)
return (calcDistSq(initialPoint, *p2) >= calcDistSq(initialPoint, *p1))? -1 : 1;
return (o == 2)? -1: 1;
}
// 计算凸包的函数
void computeConvexHull(struct Point2D points[], int n) {
int ymin = points[0].y, min = 0;
for (int i = 1; i < n; i++) {
int y = points[i].y;
if ((y < ymin) || (ymin == y && points[i].x < points[min].x))
ymin = points[i].y, min = i;
}
// 交换
struct Point2D temp = points[0];
points[0] = points[min];
points[min] = temp;
// 初始点
initialPoint = points[0];
// 对点数组进行排序
qsort(&points[1], n-1, sizeof(struct Point2D), comparePoints);
int m = 1;
for (int i=1; i<n; i++) {
while (i < n-1 && getOrientation(initialPoint, points[i], points[i+1]) == 0)
i++;
points[m] = points[i];
m++;
}
if (m < 3) return;
// 堆栈用于存储凸包上的点
struct Point2D Stack[n];
int top = -1;
// 将前三个点压入堆栈
Stack[++top] = points[0];
Stack[++top] = points[1];
Stack[++top] = points[2];
// 其余点
for (int i = 3; i < m; i++) {
while (getOrientation(getSecondTop(Stack, &top), Stack[top], points[i]) != 2)
top--;
Stack[++top] = points[i];
}
// 打印点
while (top != -1) {
struct Point2D p = Stack[top--];
printf("(%d, %d)
", p.x, p.y);
}
}
int main() {
struct Point2D points[] = {{0, 1}, {1, 2}, {2, 3}, {4, 5}, {0, 0}, {2, 1}, {3, 1}, {3, 3}};
int n = sizeof(points)/ sizeof(points[0]);
computeConvexHull(points, n);
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 点的结构
struct Point2D {
int x, y;
};
// 初始点
Point2D initialPoint;
// 获取下一个栈顶元素的函数
Point2D getSecondTop(vector<Point2D> &Stack) {
return Stack[Stack.size()-2];
}
// 计算两点间距离平方的函数
int calcDistSq(Point2D p1, Point2D p2) {
return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
}
// 用于查找有序三元组点方向的函数
int getOrientation(Point2D p, Point2D q, Point2D r) {
int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
if (val == 0) return 0;
// 检查顺时针还是逆时针
return (val > 0)? 1: 2;
}
// 用于比较两点的函数
int comparePoints(const void *vp1, const void *vp2) {
Point2D *p1 = (Point2D *)vp1;
Point2D *p2 = (Point2D *)vp2;
int o = getOrientation(initialPoint, *p1, *p2);
if (o == 0)
return (calcDistSq(initialPoint, *p2) >= calcDistSq(initialPoint, *p1))? -1 : 1;
return (o == 2)? -1: 1;
}
// 计算凸包的函数
void computeConvexHull(Point2D points[], int n) {
int ymin = points[0].y, min = 0;
for (int i = 1; i < n; i++) {
int y = points[i].y;
if ((y < ymin) || (ymin == y && points[i].x < points[min].x))
ymin = points[i].y, min = i;
}
// 交换
swap(points[0], points[min]);
// 初始点
initialPoint = points[0];
// 对点数组进行排序
qsort(&points[1], n-1, sizeof(Point2D), comparePoints);
int m = 1;
for (int i=1; i<n; i++) {
while (i < n-1 && getOrientation(initialPoint, points[i], points[i+1]) == 0)
i++;
points[m] = points[i];
m++;
}
if (m < 3) return;
// 堆栈用于存储凸包上的点
vector Stack;
// 将前三个点压入堆栈
Stack.push_back(points[0]);
Stack.push_back(points[1]);
Stack.push_back(points[2]);
// 对于其余点
for (int i = 3; i < m; i++) {
while (getOrientation(getSecondTop(Stack), Stack.back(), points[i]) != 2)
Stack.pop_back();
Stack.push_back(points[i]);
}
// 打印点
while (!Stack.empty()) {
Point2D p = Stack.back();
cout << "(" << p.x << ", " << p.y <<")" << endl;
Stack.pop_back();
}
}
int main() {
Point2D points[] = {{0, 1}, {1, 2}, {2, 3}, {4, 5}, {0, 0}, {2, 1}, {3, 1}, {3, 3}};
int n = sizeof(points)/ sizeof(points[0]);
computeConvexHull(points, n);
return 0;
}
import java.util.*;
// 用 x 和 y 坐标表示点的类
class Cords {
int xCoord, yCoord;
// 构造函数
Cords(int x, int y) {
this.xCoord = x;
this.yCoord = y;
}
}
// class to find the convex hull
public class ConvexHullFinder {
// 初始点
Cords initialPoint;
// 获取栈顶下一个元素的方法
Cords getSecondTop(Stack<Cords> stack) {
Cords temp = stack.pop();
Cords result = stack.peek();
stack.push(temp);
return result;
}
// 交换两个点的方法
void swapPoints(Cords p1, Cords p2) {
Cords temp = p1;
p1 = p2;
p2 = temp;
}
// 计算两点之间距离平方的方法
int distanceSquare(Cords p1, Cords p2) {
return (p1.xCoord - p2.xCoord)*(p1.xCoord - p2.xCoord) + (p1.yCoord - p2.yCoord)*(p1.yCoord - p2.yCoord);
}
// 查找有序三元组点方向的方法
int findOrientation(Cords p, Cords q, Cords r) {
int value = (q.yCoord - p.yCoord) * (r.xCoord - q.xCoord) - (q.xCoord - p.xCoord) * (r.yCoord - q.yCoord);
if (value == 0) return 0;
// 检查顺时针还是逆时针
return (value > 0)? 1: 2;
}
// 检查两点是否具有相同斜率的方法
boolean sameSlope(Cords p1, Cords p2, Cords p3) {
return (p2.yCoord - p1.yCoord) * (p3.xCoord - p2.xCoord) == (p3.yCoord - p2.yCoord) * (p2.xCoord - p1.xCoord);
}
// 计算凸包的方法
void calculateConvexHull(Cords points[], int n) {
int yMin = points[0].yCoord, min = 0;
for (int i = 1; i < n; i++) {
int y = points[i].yCoord;
if ((y < yMin) || (yMin == y && points[i].xCoord < points[min].xCoord)) {
yMin = points[i].yCoord;
min = i;
}
}
// 交换
swapPoints(points[0], points[min]);
// 初始点
initialPoint = points[0];
// 对点数组进行排序
Arrays.sort(points, new Comparator<Cords>() {
@Override
public int compare(Cords p1, Cords p2) {
if (sameSlope(initialPoint, p1, p2)) {
if (distanceSquare(initialPoint, p2) >= distanceSquare(initialPoint, p1)) {
return -1;
} else {
return 1;
}
}
if (findOrientation(initialPoint, p1, p2) == 2) {
return -1;
} else {
return 1;
}
}
});
// 创建一个堆栈并将前三个点推入其中
Stack<Cords> stack = new Stack<>();
stack.push(points[0]);
stack.push(points[1]);
stack.push(points[2]);
// 顺时针旋转时继续移除堆栈顶部
for (int i = 3; i < n; i++) {
while (stack.size() > 1 && findOrientation(getSecondTop(stack), stack.peek(), points[i]) != 2)
stack.pop();
stack.push(points[i]);
}
// 打印结果
while (!stack.empty()) {
Cords p = stack.peek();
System.out.println("(" + p.xCoord + ", " + p.yCoord + ")");
stack.pop();
}
}
public static void main(String[] args) {
// points
Cords points[] = {new Cords(0, 1), new Cords(1, 2), new Cords(2, 3), new Cords(4, 5),
new Cords(0, 0), new Cords(2, 1), new Cords(3, 1), new Cords(3, 3)};
int n = points.length;
ConvexHullFinder finder = new ConvexHullFinder();
finder.calculateConvexHull(points, n);
}
}
from functools import cmp_to_key
import math
# 用 x 和 y 坐标表示点的类
class Cords:
def __init__(self, x, y):
self.xCoord = x
self.yCoord = y
# 查找凸包的类
class ConvexHullFinder:
# 初始点
initialPoint = None
# 获取下一个顶点元素的方法
def getSecondTop(self, stack):
return stack[-2]
# 交换两个点的方法
def swapPoints(self, p1, p2):
return p2, p1
# 计算两点之间距离平方的方法
def distanceSquare(self, p1, p2):
return (p1.xCoord - p2.xCoord)**2 + (p1.yCoord - p2.yCoord)**2
# 查找有序三元组点方向的方法
def findOrientation(self, p, q, r):
value = (q.yCoord - p.yCoord) * (r.xCoord - q.xCoord) - (q.xCoord - p.xCoord) * (r.yCoord - q.yCoord)
如果 value == 0: 返回 0
如果 value > 0: 返回 1 否则返回 2
# 检查两点是否具有相同斜率的方法
def sameSlope(self, p1, p2, p3):
return (p2.yCoord - p1.yCoord) * (p3.xCoord - p2.xCoord) == (p3.yCoord - p2.yCoord) * (p2.xCoord - p1.xCoord)
# 计算凸包的方法
def calculateConvexHull(self, points):
n = len(points)
ymin = points[0].yCoord
min = 0
for i in range(1, n):
y = points[i].yCoord
if (y < ymin) or (ymin == y and points[i].xCoord < points[min].xCoord):
ymin = points[i].yCoord
min = i
# 交换
points[0], points[min] = self.swapPoints(points[0], points[min])
# 初始点
self.initialPoint = points[0]
# 对点数组进行排序
def compare(p1, p2):
if self.sameSlope(self.initialPoint, p1, p2):
if self.distanceSquare(self.initialPoint, p2) >= self.distanceSquare(self.initialPoint, p1):
return -1
else:
return 1
if self.findOrientation(self.initialPoint, p1, p2) == 2:
return -1
else:
return 1
points = sorted(points, key=cmp_to_key(compare))
# 创建一个堆栈并将前三个点压入其中
stack = []
stack.append(points[0])
stack.append(points[1])
stack.append(points[2])
# 顺时针旋转的同时，不断移除堆栈顶部
for i in range(3, n):
while len(stack) > 1 and self.findOrientation(self.getSecondTop(stack), stack[-1], points[i]) != 2:
stack.pop()
stack.append(points[i])
# 打印结果
while stack:
p = stack[-1]
print("(", p.xCoord, ", ", p.yCoord, ")")
stack.pop()
# Points
points = [Cords(0, 1), Cords(1, 2), Cords(2, 3), Cords(4, 5),
Cords(0, 0), Cords(2, 1), Cords(3, 1), Cords(3, 3)]
finder = ConvexHullFinder()
finder.calculateConvexHull(points)
输出
(0, 1) (4, 5) (3, 1) (0, 0)
扫描线算法
扫描线算法用于解决几何问题和其他涉及沿特定方向移动的动态对象集的问题。假设一条垂直线（称为扫描线）从左向右穿过平面。当扫描线遇到线段的端点时，我们会追踪在每个时间点哪些线段相交。通过分析相互作用，我们可以有效地解决各种问题。
以下是扫描线算法的步骤 −
扫描线从问题空间的一端开始，向另一端移动。
该算法会根据问题情况定期更新合适的数据结构。根据扫描线位置的当前配置，计算距离、交点、面积或其他所需输出。
最终的数据结构或累积结果提供了问题的解决方案。
示例
以下是使用各种编程语言演示扫描线算法的示例。
#include <stdio.h>
#include <math.h>
// 表示坐标的结构体
typedef struct {
double a, b;
} Coordinate;
// 表示线段的结构体
typedef struct {
Coordinate start, end;
} Segment;
// 用于检查两条线段是否相交的函数
int checkIntersection(Segment s1, Segment s2) {
//
return 0;
}
// 查找两条线段交点的函数
Coordinate findIntersection(Segment s1, Segment s2) {
// 第一条线段的起点和终点坐标
double a1 = s1.start.a, b1 = s1.start.b;
double a2 = s1.end.a, b2 = s1.end.b;
// 第二条线段的起点和终点坐标
double a3 = s2.start.a, b3 = s2.start.b;
double a4 = s2.end.a, b4 = s2.end.b;
// 计算交点公式的分母
double denominator = (b4 - b3) * (a2 - a1) - (a4 - a3) * (b2 - b1);
double numerator1 = (a4 - a3) * (b1 - b3) - (b4 - b3) * (a1 - a3);
double numerator2 = (a2 - a1) * (b1 - b3) - (b2 - b1) * (a1 - a3);
// 如果分母为零，则两条线平行
if (denominator == 0) {
return (Coordinate){ INFINITY, INFINITY };
}
double u = numerator1 / denominator;
double v = numerator2 / denominator;
if (u >= 0 && u <= 1 && v >= 0 && v <= 1) {
double a = a1 + u * (a2 - a1);
double b = b1 + u * (b2 - b1);
return (Coordinate){ a, b };
}
return (Coordinate){ INFINITY, INFINITY };
}
int main() {
// 线段
Segment s1 = { { 1, 2 }, { 3, 2 } };
Segment s2 = { { 2, 1 }, { 2, 3 } };
// 如果线段相交
if (checkIntersection(s1, s2)) {
// 找到交点
Coordinate c = findIntersection(s1, s2);
printf("Intersection point: (%f, %f)
", c.a, c.b);
} else {
printf("Segments do not intersect
");
}
return 0;
}
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// 表示坐标的结构体
struct Coordinate {
double a, b;
};
// 表示线段的结构体
struct Segment {
Coordinate start, end;
};
// 用于检查两条线段是否相交的函数
bool checkIntersection(Segment s1, Segment s2)
{
//
}
// 查找两条线段交点的函数
Coordinate findIntersection(Segment s1, Segment s2) {
// 第一条线段的起点和终点坐标
double a1 = s1.start.a, b1 = s1.start.b;
double a2 = s1.end.a, b2 = s1.end.b;
// 第二条线段的起点和终点坐标
double a3 = s2.start.a, b3 = s2.start.b;
double a4 = s2.end.a, b4 = s2.end.b;
// 计算交点公式的分母
double denominator = (b4 - b3) * (a2 - a1) - (a4 - a3) * (b2 - b1);
// 计算交点公式的分子
double numerator1 = (a4 - a3) * (b1 - b3) - (b4 - b3) * (a1 - a3);
double numerator2 = (a2 - a1) * (b1 - b3) - (b2 - b1) * (a1 - a3);
// 如果分母为零，则两条线段平行
if (denominator == 0) {
return { INFINITY, INFINITY };
}
double u = numerator1 / denominator;
double v = numerator2 / denominator;
// 如果 u 和 v 均介于 0 和 1 之间，则两条线段相交
if (u >= 0 && u <= 1 && v >= 0 && v <= 1) {
// 计算交点坐标
double a = a1 + u * (a2 - a1);
double b = b1 + u * (b2 - b1);
return { a, b };
}
// 如果 u 或 v 不在 0 和 1 之间，则线段不相交
return { INFINITY, INFINITY };
}
int main(){
// 线段
Segment s1 = { { 1, 2 }, { 3, 2 } };
Segment s2 = { { 2, 1 }, { 2, 3 } };s
// 如果线段相交
if (checkIntersection(s1, s2)) {
// 查找交点
坐标 c = findIntersection(s1, s2);
// 打印交点
cout << "Intersection point: (" << c.a << ", " << c.b << ")" << endl;
} else {
cout << "Segments do not intersect" << endl;
}
return 0;
}
public class Main {
// 表示坐标的类
static class Coordinate {
double a, b;
Coordinate(double a, double b) {
this.a = a;
this.b = b;
}
}
// 表示线段的类
static class Segment {
Coordinate start, end;
Segment(Coordinate start, Coordinate end) {
this.start = start;
this.end = end;
}
}
// 检查两条线段是否相交的方法
static boolean checkIntersection(Segment s1, Segment s2) {
return false;
}
// 寻找两条线段交点的方法
static Coordinate findIntersection(Segment s1, Segment s2) {
double a1 = s1.start.a, b1 = s1.start.b;
double a2 = s1.end.a, b2 = s1.end.b;
double a3 = s2.start.a, b3 = s2.start.b;
double a4 = s2.end.a, b4 = s2.end.b;
double denominator = (b4 - b3) * (a2 - a1) - (a4 - a3) * (b2 - b1);
double numerator1 = (a4 - a3) * (b1 - b3) - (b4 - b3) * (a1 - a3);
double numerator2 = (a2 - a1) * (b1 - b3) - (b2 - b1) * (a1 - a3);
if (denominator == 0) {
return new Coordinate(Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY);
}
double u = numerator1 / denominator;
double v = numerator2 / denominator;
if (u >= 0 && u <= 1 && v >= 0 && v <= 1) {
double a = a1 + u * (a2 - a1);
double b = b1 + u * (b2 - b1);
return new Coordinate(a, b);
}
return new Coordinate(Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY);
}
public static void main(String[] args) {
Segment s1 = new Segment(new Coordinate(1, 2), new Coordinate(3, 2));
Segment s2 = new Segment(new Coordinate(2, 1), new Coordinate(2, 3));
if (checkIntersection(s1, s2)) {
Coordinate c = findIntersection(s1, s2);
System.out.println("Intersection point: (" + c.a + ", " + c.b + ")");
} else {
System.out.println("Segments do not intersect");
}
}
}
import math
# 表示坐标的类
class Coordinate:
def __init__(self, a, b):
self.a = a
self.b = b
# 表示线段的类
class Segment:
def __init__(self, start, end):
self.start = start
self.end = end
# 函数用于检查两条线段是否相交
def checkIntersection(s1, s2):
# 在此处实现相交检查算法
return False # 占位符返回语句
# 函数用于查找两条线段的交点
def findIntersection(s1, s2):
a1, b1 = s1.start.a, s1.start.b
a2, b2 = s1.end.a, s1.end.b
a3, b3 = s2.start.a, s2.start.b
a4, b4 = s2.end.a, s2.end.b
denominator = (b4 - b3) * (a2 - a1) - (a4 - a3) * (b2 - b1)
numerator1 = (a4 - a3) * (b1 - b3) - (b4 - b3) * (a1 - a3)
numerator2 = (a2 - a1) * (b1 - b3) - (b2 - b1) * (a1 - a3)
if denominator == 0:
return Coordinate(math.inf, math.inf)
u = numerator1 / denominator
v = numerator2 / denominator
if 0 <= u <= 1 and 0 <= v <= 1:
a = a1 + u * (a2 - a1)
b = b1 + u * (b2 - b1)
return Coordinate(a, b)
return Coordinate(math.inf, math.inf)
# Test the functions
s1 = Segment(Coordinate(1, 2), Coordinate(3, 2))
s2 = Segment(Coordinate(2, 1), Coordinate(2, 3))
if checkIntersection(s1, s2):
c = findIntersection(s1, s2)
print(f"Intersection point: ({c.a}, {c.b})")
else:
print("Segments do not intersect")
输出
Segments do not intersect
