DSA - 几何算法

上一页
下一页

几何算法被定义为用于解决与几何形状及其属性相关的问题的程序。这些算法可以应用于点、线、多边形和其他几何图形等形状。我们可以在计算机图形学、计算机辅助设计、机器人技术和地理信息系统等各个领域找到其应用。

与几何算法相关的问题

可以使用几何算法解决的一些常见问题包括：

  • 它可以用于解决不同多边形的面积，例如三角形、矩形等。

  • 我们可以使用几何算法来查找两条线的交点。

  • 计算凸包问题。

  • 查找不同几何形状内部的点。

  • 几何算法可以解决多边形三角剖分问题。

重要的几何算法

一些重要的几何算法包括：

  • Graham扫描算法

  • 扫描线算法

Graham扫描算法

Graham扫描算法由Ronald Graham于1972年提出。该算法主要用于解决凸包问题和最大距离问题。它的应用也可以在其他领域看到，例如图像处理、机器人技术、配送系统等等。

以下步骤解释了Graham扫描算法的工作原理：

  • 首先，找到y坐标最小的点。如果多个点共享最低的y坐标，则选择x坐标最低的点。

  • 根据其余点相对于最低点的极角对它们进行排序。

  • 对点排序后，从最低点和其他两个附加点开始。这三个点构成凸包的初始部分。

  • 对于每个新点，确定从前两个点出发是否构成左转或右转。如果是右转，则倒数第二个点不在凸包内。

  • 重复此过程，直到遇到左转集。

示例

以下示例以实际方式演示了Graham扫描算法的工作原理。

C C++ Java Python
#include <stdio.h>
#include <stdlib.h>
// Structure for a point
struct Point2D {
    int x, y;
};
// Global variable for the initial point
struct Point2D initialPoint;
// Function to get the second top element
struct Point2D getSecondTop(struct Point2D Stack[], int* top) {
    return Stack[(*top)-1];
}
// Function to calculate square of distance between two points
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);
}
// Function to find orientation of ordered triplet of points
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;
}
// Function to compare two points
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;
}
// Function to compute the convex hull
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;
    }
    // Swapping
    struct Point2D temp = points[0];
    points[0] = points[min];
    points[min] = temp;
    // Initial point
    initialPoint = points[0];
    // Sort array of points
    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;
    // Stack to store the points on the convex hull
    struct Point2D Stack[n];
    int top = -1;
    // Push the first three points into the stack
    Stack[++top] = points[0];
    Stack[++top] = points[1];
    Stack[++top] = points[2];
    // For the rest of the points
    for (int i = 3; i < m; i++) {
        while (getOrientation(getSecondTop(Stack, &top), Stack[top], points[i]) != 2)
            top--;
        Stack[++top] = points[i];
    }
    // Print the point
    while (top != -1) {
        struct Point2D p = Stack[top--];
        printf("(%d, %d)\n", 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;
// structure for a point 
struct Point2D {
    int x, y;
};
// initial point
Point2D initialPoint;
// Function to get the next top element 
Point2D getSecondTop(vector<Point2D> &Stack) {
    return Stack[Stack.size()-2]; 
}
// Function to calculate square of distance between two points
int calcDistSq(Point2D p1, Point2D p2) {
    return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
}
// Function to find orientation of ordered triplet of points
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; 
    // checking clock or counterclock wise
    return (val > 0)? 1: 2; 
}
// Function to compare two points
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;
}
// Function to compute the convex hull 
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;
    }
    // swapping
    swap(points[0], points[min]); 
    // initial point
    initialPoint = points[0]; 
    // Sort array of points
    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; 
    // stack to store the points on the convex hull
    vector<Point2D> Stack; 
    // Push the first three points into the stack
    Stack.push_back(points[0]); 
    Stack.push_back(points[1]);
    Stack.push_back(points[2]);
    // For the rest of the points
    for (int i = 3; i < m; i++) { 
        while (getOrientation(getSecondTop(Stack), Stack.back(), points[i]) != 2)
            Stack.pop_back(); 
        Stack.push_back(points[i]); 
    }
    // Print the point
    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.*;
// class to represent points with x and y coordinates
class Cords {
    int xCoord, yCoord;
    // Constructor 
    Cords(int x, int y) {
        this.xCoord = x;
        this.yCoord = y;
    }
}
// class to find the convex hull 
public class ConvexHullFinder {
    // initial point
    Cords initialPoint;
    // Method to get the next to top element
    Cords getSecondTop(Stack<Cords> stack) {
        Cords temp = stack.pop();
        Cords result = stack.peek();
        stack.push(temp);
        return result;
    }
    // Method to swap two points
    void swapPoints(Cords p1, Cords p2) {
        Cords temp = p1;
        p1 = p2;
        p2 = temp;
    }
    // Method to calculate the square of the distance between two points
    int distanceSquare(Cords p1, Cords p2) {
        return (p1.xCoord - p2.xCoord)*(p1.xCoord - p2.xCoord) + (p1.yCoord - p2.yCoord)*(p1.yCoord - p2.yCoord);
    }
    // Method to find the orientation of an ordered triplet of points
    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; 
        // checking clock or counterclock wise
        return (value > 0)? 1: 2; 
    }
    // Method to check if two points have same slope 
    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);
    }
    // method to calculate convex hull 
    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;
            }
        }
        // Swapping
        swapPoints(points[0], points[min]);
        // initial point
        initialPoint = points[0];
        // Sort array of points
        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;
                }
            }
        });
        // Create a stack and push the first three points into it
        Stack<Cords> stack = new Stack<>();
        stack.push(points[0]);
        stack.push(points[1]);
        stack.push(points[2]);
        // keep removing top of stack while we get a clockwise turn
        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]);
        }
        // print result
        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

# Class to represent points with x and y coordinates
class Cords:
    def __init__(self, x, y):
        self.xCoord = x
        self.yCoord = y

# Class to find the convex hull
class ConvexHullFinder:
    # Initial point
    initialPoint = None

    # Method to get the next to top element
    def getSecondTop(self, stack):
        return stack[-2]

    # Method to swap two points
    def swapPoints(self, p1, p2):
        return p2, p1

    # Method to calculate the square of the distance between two points
    def distanceSquare(self, p1, p2):
        return (p1.xCoord - p2.xCoord)**2 + (p1.yCoord - p2.yCoord)**2

    # Method to find the orientation of an ordered triplet of points
    def findOrientation(self, p, q, r):
        value = (q.yCoord - p.yCoord) * (r.xCoord - q.xCoord) - (q.xCoord - p.xCoord) * (r.yCoord - q.yCoord)
        if value == 0: return 0
        return 1 if value > 0 else 2

    # Method to check if two points have same slope
    def sameSlope(self, p1, p2, p3):
        return (p2.yCoord - p1.yCoord) * (p3.xCoord - p2.xCoord) == (p3.yCoord - p2.yCoord) * (p2.xCoord - p1.xCoord)

    # Method to calculate convex hull
    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
        # Swapping
        points[0], points[min] = self.swapPoints(points[0], points[min])
        # Initial point
        self.initialPoint = points[0]
        # Sort array of points
        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))
        # Create a stack and push the first three points into it
        stack = []
        stack.append(points[0])
        stack.append(points[1])
        stack.append(points[2])
        # Keep removing top of stack while we get a clockwise turn
        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])
        # Print result
        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)

扫描线算法

扫描线算法用于解决涉及沿特定方向移动的对象的动态集合的几何和其他问题。假设一条垂直线（称为扫描线）从左到右穿过平面。当扫描线遇到线段的端点时，我们跟踪每个时间点哪些线段相交。通过分析交互，我们可以有效地解决各种问题。

以下是扫描线算法涉及的步骤：

  • 扫描线从问题空间的一端开始，向另一端移动。

  • 在规则的间隔内，算法更新一个合适的数据结构，具体取决于问题。根据扫描线位置的当前配置，它计算距离、交点、面积或其他所需的输出。

  • 最终的数据结构或累积结果提供了问题的解决方案。

示例

以下是说明扫描线算法在各种编程语言中的示例。

C C++ Java Python
#include <stdio.h>
#include <math.h>
// Structure to represent a coordinate
typedef struct {
   double a, b;
} Coordinate;
// Structure to represent a line segment
typedef struct {
   Coordinate start, end;
} Segment;
// Function to check if two line segments intersect
int checkIntersection(Segment s1, Segment s2) {
   // 
   return 0; 
}
// Function to find the intersection point of two line segments
Coordinate findIntersection(Segment s1, Segment s2) {
   // coordinates of the start and end points of the first line segment
   double a1 = s1.start.a, b1 = s1.start.b;
   double a2 = s1.end.a, b2 = s1.end.b;
   // coordinates of the start and end points of the second line segment
   double a3 = s2.start.a, b3 = s2.start.b;
   double a4 = s2.end.a, b4 = s2.end.b;
   // Calculate the denominator of the intersection formula
   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 the denominator is zero, the lines are parallel
   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() {
   // line segments
   Segment s1 = { { 1, 2 }, { 3, 2 } };
   Segment s2 = { { 2, 1 }, { 2, 3 } };
   // If the line segments intersect
   if (checkIntersection(s1, s2)) {
      // Find the intersection point
      Coordinate c = findIntersection(s1, s2);
      printf("Intersection point: (%f, %f)\n", c.a, c.b);
   } else {
      printf("Segments do not intersect\n");
   }
   return 0;
}

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// structure to represent a coordinate
struct Coordinate {
   double a, b;
};
// structure to represent a line segment
struct Segment {
   Coordinate start, end;
};
// Function to check if two line segments intersect
bool checkIntersection(Segment s1, Segment s2)
{
    //
}
// Function to find the intersection point of two line segments
Coordinate findIntersection(Segment s1, Segment s2) {
   // coordinates of the start and end points of the first line segment
   double a1 = s1.start.a, b1 = s1.start.b;
   double a2 = s1.end.a, b2 = s1.end.b;
   // coordinates of the start and end points of the second line segment
   double a3 = s2.start.a, b3 = s2.start.b;
   double a4 = s2.end.a, b4 = s2.end.b;
   // Calculate the denominator of the intersection formula
   double denominator = (b4 - b3) * (a2 - a1) - (a4 - a3) * (b2 - b1);
   // Calculate the numerators of the intersection formula
   double numerator1 = (a4 - a3) * (b1 - b3) - (b4 - b3) * (a1 - a3);
   double numerator2 = (a2 - a1) * (b1 - b3) - (b2 - b1) * (a1 - a3);
   // If the denominator is zero, the lines are parallel
   if (denominator == 0) {
      return { INFINITY, INFINITY };
   }
   double u = numerator1 / denominator;
   double v = numerator2 / denominator;
   // If u and v are both between 0 and 1, the line segments intersect
   if (u >= 0 && u <= 1 && v >= 0 && v <= 1) {
      // Calculate the coordinates of the intersection point
      double a = a1 + u * (a2 - a1);
      double b = b1 + u * (b2 - b1);
      return { a, b };
   }
   // If u or v is not between 0 and 1, the line segments do not intersect
   return { INFINITY, INFINITY };
}
int main(){
   // line segments
   Segment s1 = { { 1, 2 }, { 3, 2 } };
   Segment s2 = { { 2, 1 }, { 2, 3 } };
   // If the line segments intersect
   if (checkIntersection(s1, s2)) {
      // Find the intersection point
      Coordinate c = findIntersection(s1, s2);
      // Print the intersection point
      cout << "Intersection point: (" << c.a << ", " << c.b << ")" << endl;
   } else {
      cout << "Segments do not intersect" << endl;
   }
   return 0;
}

public class Main {
   // Class to represent a coordinate
   static class Coordinate {
      double a, b;
      Coordinate(double a, double b) {
         this.a = a;
         this.b = b;
      }
   }
   // Class to represent a line segment
   static class Segment {
      Coordinate start, end;
      Segment(Coordinate start, Coordinate end) {
         this.start = start;
         this.end = end;
      }
   }
   // Method to check if two line segments intersect
   static boolean checkIntersection(Segment s1, Segment s2) {
      return false; 
   }
   // Method to find the intersection point of two line segments
   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 to represent a coordinate
class Coordinate:
    def __init__(self, a, b):
        self.a = a
        self.b = b
# Class to represent a line segment
class Segment:
    def __init__(self, start, end):
        self.start = start
        self.end = end
# Function to check if two line segments intersect
def checkIntersection(s1, s2):
    # Implement intersection checking algorithm here
    return False  # Placeholder return statement
# Function to find the intersection point of two line segments
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
打印页面
上一页
下一页
广告