Sutherland–Hodgman 算法介绍(简单易懂)

这篇具有很好参考价值的文章主要介绍了Sutherland–Hodgman 算法介绍(简单易懂)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、算法介绍

二、算法描述

三、计算细节补充

四、算法总结


一、算法介绍

  我们使用Sutherland–Hodgman算法来裁剪多边形的边,一般是给你一个多边形顶点序列(P1,P2,P3,P4,…Pn)让你裁剪,最终裁剪掉裁剪多边形外部部分(下图黑框就是裁剪多边形)。像这样:

sutherland-hodgman裁剪算法,计算机图形学,c++,算法,图形渲染,图像处理
裁剪多边形示意图
sutherland-hodgman裁剪算法,计算机图形学,c++,算法,图形渲染,图像处理
裁剪多边形示意图

二、算法描述

  首先,我们需要了解多边形的各条边与裁剪线的位置关系,一共只有种:

① 仅输出顶点Pk

sutherland-hodgman裁剪算法,计算机图形学,c++,算法,图形渲染,图像处理

② 输出为空

sutherland-hodgman裁剪算法,计算机图形学,c++,算法,图形渲染,图像处理

③ 输出交点和Pk

sutherland-hodgman裁剪算法,计算机图形学,c++,算法,图形渲染,图像处理

④ 仅输出交点

sutherland-hodgman裁剪算法,计算机图形学,c++,算法,图形渲染,图像处理

  每次裁剪完,输出一个顶点序列,作为下一次裁剪的输入。于是我们便可以按照如下顺序,对多边形进行裁剪:

sutherland-hodgman裁剪算法,计算机图形学,c++,算法,图形渲染,图像处理

sutherland-hodgman裁剪算法,计算机图形学,c++,算法,图形渲染,图像处理

   综上,即可完成对多边形的裁剪。

三、计算细节补充

1、如何判断一个点,在裁剪多边形其中一条线的内部还是外部(可见侧还是不可见侧)

解:设你要拿来判断的裁剪多边形的其中一条线段,它的两个端点坐标分别是(x1,y1),(x2,y2),你要拿来判断的点的坐标为(x,y),则可以通过下列公式判断:

sutherland-hodgman裁剪算法,计算机图形学,c++,算法,图形渲染,图像处理

 如果 P < 0,则这个点位于线的右边

 如果 P = 0,则这个点位于线上

 如果 P > 0,则这个点位于线的左边

这个公式的使用前提是,题目给你提供的裁剪多边形的顶点序列是顺时针的,这样的话右边就是内部(可见侧),左边就是外部(不可见侧)

2、如何求得线段与裁剪多边形其中一条线段的交点

解:设线段两个端点为(x1,y1),(x2,y2),裁剪多边形其中一点线段两端点为(x3,y3),(x4,y4),则可以通过以下公式求解:

sutherland-hodgman裁剪算法,计算机图形学,c++,算法,图形渲染,图像处理

四、算法总结

代码如下,来源(Polygon Clipping | Sutherland–Hodgman Algorithm - GeeksforGeeks)

// C++ program for implementing Sutherland–Hodgman
// algorithm for polygon clipping
#include<iostream>
using namespace std;

const int MAX_POINTS = 20;

// Returns x-value of point of intersection of two
// lines
int x_intersect(int x1, int y1, int x2, int y2,
				int x3, int y3, int x4, int y4)
{
	int num = (x1*y2 - y1*x2) * (x3-x4) -
			(x1-x2) * (x3*y4 - y3*x4);
	int den = (x1-x2) * (y3-y4) - (y1-y2) * (x3-x4);
	return num/den;
}

// Returns y-value of point of intersection of
// two lines
int y_intersect(int x1, int y1, int x2, int y2,
				int x3, int y3, int x4, int y4)
{
	int num = (x1*y2 - y1*x2) * (y3-y4) -
			(y1-y2) * (x3*y4 - y3*x4);
	int den = (x1-x2) * (y3-y4) - (y1-y2) * (x3-x4);
	return num/den;
}

// This functions clips all the edges w.r.t one clip
// edge of clipping area
void clip(int poly_points[][2], int &poly_size,
		int x1, int y1, int x2, int y2)
{
	int new_points[MAX_POINTS][2], new_poly_size = 0;

	// (ix,iy),(kx,ky) are the co-ordinate values of
	// the points
	for (int i = 0; i < poly_size; i++)
	{
		// i and k form a line in polygon
		int k = (i+1) % poly_size;
		int ix = poly_points[i][0], iy = poly_points[i][1];
		int kx = poly_points[k][0], ky = poly_points[k][1];

		// Calculating position of first point
		// w.r.t. clipper line
		int i_pos = (x2-x1) * (iy-y1) - (y2-y1) * (ix-x1);

		// Calculating position of second point
		// w.r.t. clipper line
		int k_pos = (x2-x1) * (ky-y1) - (y2-y1) * (kx-x1);

		// Case 1 : When both points are inside
		if (i_pos < 0 && k_pos < 0)
		{
			//Only second point is added
			new_points[new_poly_size][0] = kx;
			new_points[new_poly_size][1] = ky;
			new_poly_size++;
		}

		// Case 2: When only first point is outside
		else if (i_pos >= 0 && k_pos < 0)
		{
			// Point of intersection with edge
			// and the second point is added
			new_points[new_poly_size][0] = x_intersect(x1,
							y1, x2, y2, ix, iy, kx, ky);
			new_points[new_poly_size][1] = y_intersect(x1,
							y1, x2, y2, ix, iy, kx, ky);
			new_poly_size++;

			new_points[new_poly_size][0] = kx;
			new_points[new_poly_size][1] = ky;
			new_poly_size++;
		}

		// Case 3: When only second point is outside
		else if (i_pos < 0 && k_pos >= 0)
		{
			//Only point of intersection with edge is added
			new_points[new_poly_size][0] = x_intersect(x1,
							y1, x2, y2, ix, iy, kx, ky);
			new_points[new_poly_size][1] = y_intersect(x1,
							y1, x2, y2, ix, iy, kx, ky);
			new_poly_size++;
		}

		// Case 4: When both points are outside
		else
		{
			//No points are added
		}
	}

	// Copying new points into original array
	// and changing the no. of vertices
	poly_size = new_poly_size;
	for (int i = 0; i < poly_size; i++)
	{
		poly_points[i][0] = new_points[i][0];
		poly_points[i][1] = new_points[i][1];
	}
}

// Implements Sutherland–Hodgman algorithm
void suthHodgClip(int poly_points[][2], int poly_size,
				int clipper_points[][2], int clipper_size)
{
	//i and k are two consecutive indexes
	for (int i=0; i<clipper_size; i++)
	{
		int k = (i+1) % clipper_size;

		// We pass the current array of vertices, it's size
		// and the end points of the selected clipper line
		clip(poly_points, poly_size, clipper_points[i][0],
			clipper_points[i][1], clipper_points[k][0],
			clipper_points[k][1]);
	}

	// Printing vertices of clipped polygon
	for (int i=0; i < poly_size; i++)
		cout << '(' << poly_points[i][0] <<
				", " << poly_points[i][1] << ") ";
}

//Driver code
int main()
{
	// Defining polygon vertices in clockwise order
	int poly_size = 3;
	int poly_points[20][2] = {{100,150}, {200,250},
							{300,200}};

	// Defining clipper polygon vertices in clockwise order
	// 1st Example with square clipper
	int clipper_size = 4;
	int clipper_points[][2] = {{150,150}, {150,200},
							{200,200}, {200,150} };

	// 2nd Example with triangle clipper
	/*int clipper_size = 3;
	int clipper_points[][2] = {{100,300}, {300,300},
								{200,100}};*/

	//Calling the clipping function
	suthHodgClip(poly_points, poly_size, clipper_points,
				clipper_size);

	return 0;
}

Sutherland–Hodgman算法的缺点:仅适用于凸多边形,对于凹多边形的裁剪将如图所示显示出一条多余的直线。

sutherland-hodgman裁剪算法,计算机图形学,c++,算法,图形渲染,图像处理
中间的蓝色线即为多余的直线

  如果想避免此问题,需要使用Weiler-Atherton算法,该算法可以避免残留。 文章来源地址https://www.toymoban.com/news/detail-794879.html

到了这里,关于Sutherland–Hodgman 算法介绍(简单易懂)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 从零开始学习 Java:简单易懂的入门指南之查找算法及排序算法(二十)

    ​ 也叫做顺序查找 ​ 说明:顺序查找适合于存储结构为数组或者链表。 基本思想 :顺序查找也称为线形查找,属于无序查找算法。从数据结构线的一端开始,顺序扫描,依次将遍历到的结点与要查找的值相比较,若相等则表示查找成功;若遍历结束仍没有找到相同的,表

    2024年02月10日
    浏览(42)
  • 【计算机图形学】裁剪算法(Cohen-Sutherland算法 & 中值分割算法 & Liang-Barsky算法)

    一 实验目的 编写直线段、多边形裁剪算法 熟悉Cohen-Sutherland算法、中值分割算法和Liang-Barsky算法的裁剪 二 实验算法理论分析 Cohen-Sutherland 算法:     中值分割算法: 与CS算法一样,首先对直线段端点进行编码,并把线段与窗口的关系一样分为3种情况:全在、完全不在、线

    2024年02月03日
    浏览(48)
  • C语言深度剖析,关于查找一个数组里面的最大值(max)、最小值(min)的通俗算法,简单易懂。采用比较法进行查找。

    这里采用了一个假设 假设第一个数为最大值,其他数与第一个数比较。 这个算法与上面求解最大值的方法相反。 1、首先,定义行和列。 用行标记来确定列的数量。 i 来表示行, j来表示列。 2、内嵌的for循环只打印一行所有列。 如,i=3时,此时j=3. 从1*3 遍历到3*3后内嵌循环

    2024年02月08日
    浏览(44)
  • 图像分类传统算法和深度学习算法简单介绍

    图像分类是计算机视觉领域的一项基本任务,旨在根据输入图像将其预测到一个或多个类别中。本文档将详细介绍一些常用的图像分类算法,包括传统方法和深度学习方法。 在深度学习技术兴起之前,计算机视觉领域的研究者们使用传统的机器学习方法来进行图像分类。这些

    2024年02月16日
    浏览(42)
  • 简单介绍一下YOLO算法发展历程

    前言: Hello大家好,我是小哥谈。 随着人工智能技术的发展,YOLO算法已经成为了一个热门话题。到目前为止,YOLO算法已经经历了多个版本的发展迭代,许多研究者对YOLO算法进行了改进和创新。为了让大家理解的更透彻,本文就由浅入深的向大家介绍YOLOv1到YOLOv5的发展历程,

    2024年02月05日
    浏览(53)
  • 安全算法(一):安全技术、加密的基础知识、哈希函数的简单介绍

    通过互联网交换数据时,数据要经过各种各样的网络和设备才能传到对方那里。数据在传输过程中有可能会经过某些恶意用户的设备,从而导致内容被盗取。 因此,要想安全地使用互联网,安全技术是不可或缺的。 传输数据时的四个问题:窃听、假冒、篡改、事后否认 窃听

    2024年02月04日
    浏览(46)
  • &和&&的区别(简单易懂)

    1.具有短路功能,而不具有短路功能。 2. 当运算符两侧的表达式的结果均为真时,整个运算结果才为真。 当操作符第一个表达式为 false时,结果为 false,并且不再计算第二个表达式。 (简单的表达就是:使用运算符,必须两侧的都是true,结果为真。使用运算符,重点看第一

    2023年04月26日
    浏览(96)
  • springboot中过滤器@WebFilter的使用以及简单介绍限流算法

    过滤器(Filter)实际上就是对web资源进行拦截,做一些处理后再交给下一个过滤器或servlet处理,通常都是用来拦截request进行处理的,也可以对返回的response进行拦截处理,大致流程如下图 一般情况下,我们针对一些敏感的参数,例如密码、身份证号等,给它加密,防止报文明文

    2024年02月03日
    浏览(36)
  • CDM—码分复用(简单易懂)

    · 码分复用简称 CDM · 可以实现多个用户 同时 使用 同样频率 进行通信 · 如何实现?—— 通过各用户的码序列进行区分。 2.1 表示 1、每个比特(0或1)以一组码序列发送 (m位编码将每位比特划分为m) 码片:一个数据信号(如逻辑1或0)通常要用多个编码信号来进行编码,

    2024年02月01日
    浏览(63)
  • 简单易懂的Transformer学习笔记

    1. 整体概述 2. Encoder         2.1 Embedding         2.2 位置编码                 2.2.1 为什么需要位置编码                 2.2.2 位置编码公式                 2.2.3 为什么位置编码可行         2.3 注意力机制         2.3.1 基本注意力机制  

    2024年02月14日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包