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
列印頁面
上一頁
下一頁
廣告

© . All rights reserved.