计算机图形学：多边形交点及实现

🕗 发布于 2024-11-27 11:13 直线相交交点计算机图形学

文章目录

一、原理推导和公式说明

1.1 两条线段求交的数学原理

设有两条线段 $A B$ 和 $C D$ ，它们的端点坐标分别为 $A(x_a, y_a)$ , $B(x_b, y_b)$ 和 $C(x_c, y_c)$ , $D(x_d, y_d)$ 。要找出这两条线段是否相交，我们可以使用参数方程和行列式的概念。

首先，

线段 $A B$ 的方程：
$\begin{cases} x = x_a + t(x_b - x_a) \\ y = y_a + t(y_b - y_a) \end{cases}$
其中， $t$ 在 $[0, 1]$ 范围内变化，表示从点 $A$ 到点 $B$ 的相对位置。
线段 $C D$ 的方程：
$\begin{cases} x = x_c + u(x_d - x_c) \\ y = y_c + u(y_d - y_c) \end{cases}$
其中， $u$ 在 $[0, 1]$ 范围内变化，表示从点 $C$ 到点 $D$ 的相对位置。

要使两个方程组表示同一个点，则交点的参数应满足：

$\begin{cases} x_a + t(x_b - x_a) = x_c + u(x_d - x_c) \\ y_a + t(y_b - y_a) = y_c + u(y_d - y_c) \end{cases}$
整理后得
$\begin{cases} t(x_b-x_a)-u(x_d-x_c)=x_c-x_a \\ t(y_b-y_a)-u(y_d-y_c)=y_c-y_a \end{cases}$
因此，对于行列式
$\begin{vmatrix} x_b - x_a & x_d - x_c \\ y_b - y_a & y_d - y_c \end{vmatrix}$
有以下结论：

若 $d = 0$ ，则 $A B$ 和 $C D$ 重合或者平行。
若 $\neq 0$ ，则线段 $A B$ 和 $C D$ 不平行也不重合，有可能相交。求出两个线段所在的两条直线上交点对应的两个参数 $t, u$ 值:
$\frac{\begin{vmatrix} x_c - x_a & x_d - x_a \\ y_c - y_a & y_d - y_a \end{vmatrix}}{\text{d}}\\ u = \frac{\begin{vmatrix} x_b - x_a & x_b - x_c \\ y_b - y_a & y_b - y_c \end{vmatrix}}{\text{d}}$
如果 $t$ 和 $u$ 都在 $[0, 1]$ 区间内，那么交点位于两条线段上，线段相交；否则,交点在两线段或其中某一条线段的延长线上,这时仍然认为是两线段不相交。

1.2 推导过程

将线段表示为参数方程。
构造参数 $t$ 和 $u$ 的方程组。
通过行列式方法消去参数 $t$ 和 $u$ ，得到交点的坐标。
检查 $t$ 和 $u$ 是否在 $[0, 1]$ 区间内，以确定交点是否在两条线段上。

这就是两条线段求交的数学原理和公式推导。如果行列式 $d$ 为零，或者计算得到的 $t$ 和 $u$ 不在 [0, 1] 区间内，那么线段不相交。

二、代码设计与实现

2.1 点结构和多边形类定义

首先，定义了Point结构体来表示二维空间中的点，包含x和y两个坐标成员。

struct Point {
  double x, y;
};

Polygon类用于表示多边形，它包含一个vertices向量，存储多边形的顶点。类中还包含getEdge方法，用于获取多边形的某条边，以及getNumberOfEdges方法，返回多边形边的数量。

class Polygon {
public:
  std::vector<Point> vertices;

  Polygon(const std::vector<Point> &points) : vertices(points) {}

  std::pair<Point, Point> getEdge(int i) const {
    int nextIndex = (i + 1) % vertices.size();
    return {vertices[i], vertices[nextIndex]};
  }

  int getNumberOfEdges() const { return vertices.size(); }
};

2.2 线段交点的计算

两条线段的交点可以通过解线性方程组得到。首先，通过计算行列式来判断线段是否平行或共线：

$\cdot (C.y - D.y) - (B.y - A.y) \cdot (C.x - D.x)$
如果d的绝对值小于一个很小的阈值（例如1e-6），则认为线段平行或共线，没有交点。

如果线段不平行，可以通过求解以下方程得到交点参数t和u：
$\frac{(C.x - A.x) \cdot (C.y - D.y) - (C.y - A.y) \cdot (C.x - D.x)}{d}\\ u = \frac{(B.x - A.x) \cdot (C.y - A.y) - (B.y - A.y) \cdot (C.x - A.x)}{d}$
如果t和u都在区间[0, 1]内，则交点在线段上：
$\text{intersection}.x = A.x + t \cdot (B.x - A.x) \\ \text{intersection}.y = A.y + t \cdot (B.y - A.y)$

bool getLineSegmentIntersection(const Point &A, const Point &B, const Point &C,
                                const Point &D, Point &intersection) {
  double d = (B.x - A.x) * (C.y - D.y) - (B.y - A.y) * (C.x - D.x);
  if (std::abs(d) < 1e-6) {
    return false;
  }

  double t = ((C.x - A.x) * (C.y - D.y) - (C.y - A.y) * (C.x - D.x)) / d;
  double u = ((B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x)) / d;

  if (t >= 0.0 && t <= 1.0 && u >= 0.0 && u <= 1.0) {
    intersection.x = A.x + t * (B.x - A.x);
    intersection.y = A.y + t * (B.y - A.y);
    return true;
  }

  return false;
}

2.3 多边形交点的计算

对于两个多边形，程序遍历每条边的组合，使用getLineSegmentIntersection函数检查是否有交点。

std::vector<Point> getPolygonIntersections(const Polygon &poly_a,
                                           const Polygon &poly_b) {
  std::vector<Point> intersections;
  for (int i = 0; i < poly_a.getNumberOfEdges(); ++i) {
    for (int j = 0; j < poly_b.getNumberOfEdges(); ++j) {
      Point intersection;
      if (getLineSegmentIntersection(
              poly_a.getEdge(i).first, poly_a.getEdge(i).second,
              poly_b.getEdge(j).first, poly_b.getEdge(j).second, intersection)) {
          intersections.push_back(intersection);
      }
    }
  }
  return intersections;
}

三、完整代码示例

主函数创建了两个多边形poly_a和poly_b，并调用getPolygonIntersections函数来计算它们的交点。然后，输出交点信息。

#include <algorithm>
#include <iostream>
#include <vector>

// 定义一个表示二维点的结构体
struct Point {
  double x, y;
};

// 定义一个表示多边形的类
class Polygon {
public:
  std::vector<Point> vertices; // 存储多边形顶点的向量

  // 构造函数，接受一个点的向量来初始化多边形的顶点
  Polygon(const std::vector<Point> &points) : vertices(points) {}

  // 获取多边形的第i条边，返回一个包含两个端点的pair
  std::pair<Point, Point> getEdge(int i) const {
    int nextIndex = (i + 1) % vertices.size(); // 计算下一条边的索引，实现循环
    return {vertices[i], vertices[nextIndex]}; // 返回当前边的两个端点
  }

  // 获取多边形的边数
  int getNumberOfEdges() const { return vertices.size(); }
};

// 计算两条线段AB和CD的交点
bool getLineSegmentIntersection(const Point &A, const Point &B, const Point &C,
                                const Point &D, Point &intersection) {
  double d = (B.x - A.x) * (C.y - D.y) - (B.y - A.y) * (C.x - D.x);
  if (std::abs(d) < 1e-6) {
    // 如果行列式的绝对值很小，则认为线段平行或共线
    return false;
  }

  // 计算交点参数t和u
  double t = ((C.x - A.x) * (C.y - D.y) - (C.y - A.y) * (C.x - D.x)) / d;
  double u = ((B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x)) / d;

  // 检查交点是否在两条线段上
  if (t >= 0.0 && t <= 1.0 && u >= 0.0 && u <= 1.0) {
    // 如果t和u都在[0, 1]区间内，则交点在线段上
    intersection.x = A.x + t * (B.x - A.x);
    intersection.y = A.y + t * (B.y - A.y);
    return true;
  }

  // 如果交点不在线段上，则返回false
  return false;
}

// 计算两个多边形的所有交点
std::vector<Point> getPolygonIntersections(const Polygon &poly_a,
                                           const Polygon &poly_b) {
  std::vector<Point> intersections;
  for (int i = 0; i < poly_a.getNumberOfEdges(); ++i) {
    for (int j = 0; j < poly_b.getNumberOfEdges(); ++j) {
      Point intersection;
      if (getLineSegmentIntersection(poly_a.getEdge(i).first,
                                     poly_a.getEdge(i).second,
                                     poly_b.getEdge(j).first,
                                     poly_b.getEdge(j).second, intersection)) {
        intersections.push_back(intersection); // 将交点添加到结果中
      }
    }
  }
  return intersections; // 返回所有交点
}

// 主函数
int main() {
  // 定义两个多边形
  Polygon poly_a({{0, 0}, {0, 4}, {-4, 4}, {-4, 0}});
  Polygon poly_b({{-2, 2}, {-2, -2}, {2, -2}, {2, 2}});

  // 计算两个多边形的交点
  auto intersections = getPolygonIntersections(poly_a, poly_b);

  // 输出交点信息
  if (intersections.empty()) {
    std::cout << "No intersection" << std::endl;
  } else {
    std::cout << "Intersections:" << std::endl;
    for (const auto &pt : intersections) {
      std::cout << "(" << pt.x << ", " << pt.y << ")" << std::endl;
    }
  }
  return 0;
}

原文地址：https://blog.csdn.net/jianmo1993/article/details/144063056

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：利用HTML5和CSS来实现一个漂亮的表格样式
下一篇：[论文阅读]Synthetic Disinformation Attacks on Automated Fact Verification Systems

Spring |（四）IoC/DI配置管理第三方bean
掌握IOC/DI配置管理第三方bean。
阅读更多2024-11-27
oracle小技巧-解决特殊密码字符而导致的exp错误
在使用oracle数据库的时候，我们经常会利用exp工具对某些表进行导出。但有些时候，因我们用户密码为安全性设有特殊字符，导致exp导出时候报：“EXP-00056和ORA-12154”，今天我们就分
阅读更多2024-11-27
如何用通义灵码助力项目开发 | OceanBase obdiag 项目共建实践
借助通义灵码完成了OceanBase obdiag 项目的第一个PR，成为了 obdiag 项目的 contributor。本文是我的实践分享
阅读更多2024-11-27
过滤条件包含 OR 谓词，如何进行查询优化——OceanBase SQL 优化实践
在写SQL查询时，难以避免在过滤条件中使用OR 谓词，但其往往会导致索引利用效率下降的问题。本文将分享如何通过查询改写的2种方式进行优化。
阅读更多2024-11-27
HTTP代理是什么，主要用来干嘛？
综上所述，HTTP代理是一种重要的网络工具，具有广泛的应用场景和重要作用。通过了解HTTP代理的基本概念、工作原理和主要应用场景，我们可以更好地利用这一工具来满足自己的需求。同时，在选择HTTP代理服
阅读更多2024-11-27
使用argo workflow 实现springboot 项目的CI、CD
接下来的部分定义了工作流中的多个步骤 (steps)，这些步骤会按顺序执行。
阅读更多2024-11-27
RabbitMQ的预取值详解
预取值是指消费者从队列中获取的消息数量。默认情况下，RabbitMQ采用轮询分发机制，将消息均匀分配给各个消费者。然而，在实际应用中，消费者的处理速度可能各不相同，导致处理速度快的消费者空闲，而处理速
阅读更多2024-11-27
cuda conda yolov11 环境搭建
将cuDNN压缩包内对应的文件复制到本地bin、include、lib的文件夹中。
阅读更多2024-11-27
初级数据结构——二叉树题库（c++）
在上期（蓝色字体可以点进去）我们一起学习了初级数据结构——二叉树，那么这期我们来运用二叉树思想进行实战，巩固知识点。1.——965. 单值二叉树（蓝色字体可以点进去看原题）代码题解/*** int v
阅读更多2024-11-27
Linux——基础命令（1）
它主要受到Minix和Unix思想的启发，是一个基于POSIX的多用户、多任务、支持多线程和多CPU的操作系统。其功能为更改当前的工作目录，也是用户。mv 命令可以用来移动文件或目录，也可以给
阅读更多2024-11-27