文档章节

使用java写的Sutherland_Hodgeman多边形裁剪算法

侯禹
 侯禹
发布于 2014/05/24 00:18
字数 731
阅读 1845
收藏 6

点的类,相信大家已经非常熟悉了

package pow;
/*点的类*/
public class Point {
	public double x;
	public double y;
	public Point(double x,double y){
		this.x = x;
		this.y = y;
	}
	public Point(){
		this.x = 0;
		this.y = 0;
	}
	public void setX(double x){
		this.x = x;
	}
	public void setY(double y){
		this.y = y;
	}
	public double getX(){
		return this.x;
	}
	public double getY(){
		return this.y;
	}
}

向量的类(线)

package pow;
/*向量的类*/
public class Vector {
	Point start;
	Point end;
	public Vector(Point start,Point end){
		this.start = start;
		this.end = end;
	}
}

算法主题,把数据写死了,大家可以把数据更改为输入:

package pow;

import java.util.ArrayList;
import java.util.List;

public class pow {
	public static void main(String[] arg){
		//初始化赋值过程
		List<Point> points = new ArrayList<Point>();
		Point point = new Point(0,0);
		points.add(point);
		point = new Point(7,2);
		points.add(point);
		point = new Point(5,9);
		points.add(point);
		point = new Point(3,8);
		points.add(point);
		point = new Point(0,1);
		points.add(point);
		List<Vector> vectors = new ArrayList<Vector>();
		vectors.add(new Vector(new Point(8,0), new Point(8,6)));
		vectors.add(new Vector(new Point(8,6), new Point(1,6)));
		vectors.add(new Vector(new Point(1,6), new Point(1,0)));
		vectors.add(new Vector(new Point(1,0), new Point(8,0)));
		
		//利用算法求出切割后的顶点集合,代表新的多边形
		List<Point> result = Sutherland_Hodgeman(points,vectors);
		//将所有的节点打印出来
		for(int k=0;k<result.size();k++){
			System.out.println(result.get(k).getX()+"|"+result.get(k).getY());
		}
	}
	//裁剪算法
	public static List<Point> Sutherland_Hodgeman(List<Point> points,List<Vector> vectors){
		List<Point> result = new ArrayList<Point>();
		List<Point> cur = new ArrayList<Point>();
		
		int vectorsSize = vectors.size();
		int pointSize = points.size();
		
		Point S = points.get(pointSize-1);
		//初始化操作的集合
		for(int i=0;i<pointSize;i++){
			result.add(points.get(i));
		}

		boolean flag;
		for(int j=0;j<vectorsSize;j++){
			//flag = false表示在内侧,flag = true表示在外侧
			if(isInside(S,vectors.get(j)))
				flag = false;
			else
				flag = true;
			int resultSize = result.size();
			for(int i=0;i<resultSize;i++){
				//证明其在当前vector的内
				if(isInside(result.get(i),vectors.get(j))){
					//如果前一个点在vector的外侧,那么将他们的交点加入到结果集中
					if(flag){
						flag = false;
						cur.add(Intersection(S, result.get(i), vectors.get(j).start, vectors.get(j).end));
					}
					//并将当前节点加入到结果集中
					cur.add(result.get(i));
				}
				else{
					//前一个点在外侧吗?
					if(!flag){
						flag = true;
						//如果前一个点在vector的内侧,那么将他们的交点加入到结果集中
						cur.add(Intersection(S, result.get(i), vectors.get(j).start, vectors.get(j).end));
					}
				}
				//更新首次比较的节点
				S = result.get(i);
			}
			//将本次结果拷贝出来,作为下次对比的样本,并将本次结果进行清空
			int resultLen = result.size();
			result.clear();
			for(int i=0;i<resultLen;i++){
				result.add(cur.get(i));
			}
			cur.clear();
		}
		return result;
	}
	
	//求一个点是否在一条边的内侧,在点序为逆时针的时候(如果点在线上,也算在内侧)
	public static boolean isInside(Point p,Vector v){
		return Multi(p,v.start,v.end)>=0?true:false;
	}
	
	
	//求叉积p0->p1与p0->p2的叉积
	public static double Multi(Point p0,Point p1,Point p2){
		return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
	}
	
	public static Point Intersection(Point start0,Point end0,Point start1,Point end1){
		//由正弦定理推出
		double pX = (Multi(start0, end1, start1)*end0.x - Multi(end0, end1, start1)*start0.x)/
				(Multi(start0, end1, start1) - Multi(end0, end1, start1));
		double pY = (Multi(start0, end1, start1)*end0.y - Multi(end0, end1, start1)*start0.y)/
				(Multi(start0, end1, start1) - Multi(end0, end1, start1));
		return new Point(pX,pY);
	}
}


© 著作权归作者所有

侯禹
粉丝 96
博文 49
码字总数 34362
作品 0
海淀
程序员
私信 提问
Sutherland-Hodgman算法(多边形裁剪)

Sutherland-Hodgman算法 Sutherland-Hodgman算法也叫逐边裁剪法,该算法是萨瑟兰德(I.E.Sutherland)和霍德曼(Hodgman)在1974年提出的。这种算法采用了分割处理、逐边裁剪的方法。 一,基本...

长平狐
2013/12/25
2.2K
0
BAT等大厂Android面试书单和知识点清单

java是Android开发的基础,在BAT的初面中,会涉及到比较多的java基础知识,所以比较重要,下面我介绍的书籍内容是由浅到深。 1.Thinking in java:这本书被称为Java的三大圣经之一,虽然书比...

android自学
2018/07/25
0
0
kan-java, 一个能裁剪语法特性的java动态编译工具

'kan-java' 就是 '砍-java', 就是字面意思 这是一个java代码动态编译工具,也就是能够把String形式的java代码实时地编译为字节码的工具; “动态编译”工具,其实自jdk1.6发布以来,应该出现...

pf_miles
2015/03/28
185
0
Drools 6.2.0.Beta1 发布

Drools 6.2.0.Beta1 发布,此版本引入了一个新的 Drools Execution Server。更多内容请看这里。 Drools 是用 Java 语言编写的开放源码规则引擎,使用 Rete 算法对所编写的规则求值。Drools ...

叶秀兰
2014/08/17
2K
1
开源个人参考淘宝TDDL写的一个分库分表Sharding中间件Kamike.divide

现在过年在家里打扫卫生,顺便清理重构下代码,开源个人参考淘宝的TDDL分库分表思路写的一个分库分表中间件Kamike.divide. 分库分表这个是8月份左右跟淘宝的数据分析部门的架构师离哲交流的时...

Brin想写程序
2014/01/26
3.5K
5

没有更多内容

加载失败,请刷新页面

加载更多

Giraph源码分析(八)—— 统计每个SuperStep中参与计算的顶点数目

作者|白松 目的:科研中,需要分析在每次迭代过程中参与计算的顶点数目,来进一步优化系统。比如,在SSSP的compute()方法最后一行,都会把当前顶点voteToHalt,即变为InActive状态。所以每次...

数澜科技
今天
4
0
Xss过滤器(Java)

问题 最近旧的系统,遇到Xss安全问题。这个系统采用用的是spring mvc的maven工程。 解决 maven依赖配置 <properties><easapi.version>2.2.0.0</easapi.version></properties><dependenci......

亚林瓜子
今天
10
0
Navicat 快捷键

操作 结果 ctrl+q 打开查询窗口 ctrl+/ 注释sql语句 ctrl+shift +/ 解除注释 ctrl+r 运行查询窗口的sql语句 ctrl+shift+r 只运行选中的sql语句 F6 打开一个mysql命令行窗口 ctrl+l 删除一行 ...

低至一折起
今天
9
0
Set 和 Map

Set 1:基本概念 类数组对象, 内部元素唯一 let set = new Set([1, 2, 3, 2, 1]); console.log(set); // Set(3){ 1, 2, 3 } [...set]; // [1, 2, 3] 接收数组或迭代器对象 ...

凌兮洛
今天
4
0
PyTorch入门笔记一

张量 引入pytorch,生成一个随机的5x3张量 >>> from __future__ import print_function>>> import torch>>> x = torch.rand(5, 3)>>> print(x)tensor([[0.5555, 0.7301, 0.5655],......

仪山湖
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部