基于Y向连贯性算法的多边形扫描线生成（适用于凸多边形和凹多边形）【原理+java实现】 |
您所在的位置：网站首页 › 多边形的集合描述方法 › 基于Y向连贯性算法的多边形扫描线生成（适用于凸多边形和凹多边形）【原理+java实现】 |
基于Y向连贯性算法的多边形扫描线生成（适用于凸多边形和凹多边形）【原理+java实现】
|
文章目录
问题介绍原始方法Y向连贯性算法避免多次求交点如何避免多次排序如何实现代码实现效果测试
问题介绍
给定一个多边形，可能是凸多边形，也可能是凹多边形，现需要生成一系列线条将多边形描述出来，示例如下图 遇到这个问题，大家首先想到的方法可能是：使用一系列的竖线来和多边形进行相交，得到几个交点，然后将交点按照z轴坐标值进行升序排序，最后再以两个点为一组来形成扫描线。这样确实很容易理解，但是性能不好，因为需要多次求交点和多次对交点进行排序 Y向连贯性算法该算法主要就是用来解决上面提到的两个性能问题：多次求交点及多次排序。 避免多次求交点如何避免多次求交点呢？其实非常简单，就是利用直线函数 y=kx+b 的信息即可，例如x每增加1，y就增加 k 。如下面的例子，假如一开始就知道P点的坐标，那么线段与扫描线1、扫描线2的交点并不需要再去用直线相交公式计算，直接使用 y=kx+b 即可得到
如下图所示，当扫描线在x=[0,10]之间移动时，永远只有上下两个交点，且P2永远在P1上面，那只要x在[0,10]之间移动时，只需要根据直线的表达式来对两个点的坐标进行更新即可，不需要排序两个点。当x>10之后，有新的边和扫描线相交，这时候会出现更多的交点，此时才需要对交点进行排序，大大减少了排序的次数
首先需要维护一个边表，遍历多边形的每一条边，将边放到对应的桶中；第二步就是维护一个有效边集合，将y开始向右扫描移动，y的初始值是多边形所有点中最小的那个y，在移动的过程中，主要做一下三件事： 是否有边失效？当扫描线扫描不到时，边就失效，将其从有效边集合中移除是否有新的有效边加入？随着扫描线的移动，当扫描线会接触到新的线时，需要将其添加到有效边集合中，这时候会产生新的交点，注意此时需要重新排序了扫描线每沿着y轴移动距离deltaY，z就变化k*deltaY
【实体类：Edge，用于在边表和有效边集合中存储数据】 package com.dam.entity.sanLine; /** * @Author dam * @create 2023/9/15 14:38 */ public class Edge { public double z; public double yMax; /** * y加一时，z的增量 */ public double k; public Edge(double z, int yMax, double k) { this.z = z; this.yMax = yMax; this.k = k; } }【针对零件点集的纵向扫描线生成方法】 /** * 扫描线生成，使用连贯性算法 * * @param part */ private void vScanLineConstruct1(Part part) { List vSLineList = new ArrayList(); // 边表 HashMap edgeTable = new HashMap(); /* 边表构造 遍历每一条边，将边的信息放入到相应的桶中，即放入边的两点中y值较小的那个桶中 */ for (int i = 0; i |
【本文地址】