package com.sundablog.clipper;
import com.sundablog.clipper.Point.LongPoint;
import java.util.ArrayList;
import java.util.Collections;
/**
* Path类表示一个多边形路径，继承自ArrayList<LongPoint>
* 用于存储多边形顶点序列，并提供多边形相关的几何计算和操作功能
* 支持面积计算、点是否在多边形内判断、多边形清理等功能
*/
public class Path extends ArrayList<LongPoint> {
/**
* Join类表示路径中相邻点之间的连接
* 用于偏移算法中存储相邻点的连接信息
*/
static class Join {
/** 第一个输出点 */
OutPt outPt1;
/** 第二个输出点 */
OutPt outPt2;
/** 偏移点，用于计算圆角、斜接等效果 */
private LongPoint offPt;
/**
* 获取偏移点
* @return 偏移点坐标
*/
public LongPoint getOffPt() {
return offPt;
}
/**
* 设置偏移点
* @param offPt 偏移点坐标
*/
public void setOffPt( LongPoint offPt ) {
this.offPt = offPt;
}
}
/**
* OutPt类表示输出路径中的点
* 主要用于内部多边形操作，维护点之间的链接关系
*/
static class OutPt {
/**
* 获取具有最底部点的OutRec
* 用于确定正确的孔洞状态和多边形关系
* @param outRec1 第一个多边形记录
* @param outRec2 第二个多边形记录
* @return 包含最底部点的OutRec对象
*/
public static OutRec getLowerMostRec( OutRec outRec1, OutRec outRec2 ) {
// 确定哪个多边形片段具有正确的孔洞状态
if (outRec1.bottomPt == null) {
outRec1.bottomPt = outRec1.pts.getBottomPt();
}
if (outRec2.bottomPt == null) {
outRec2.bottomPt = outRec2.pts.getBottomPt();
}
final OutPt bPt1 = outRec1.bottomPt;
final OutPt bPt2 = outRec2.bottomPt;
// 比较Y坐标，选择Y值更大的点（更靠下）
if (bPt1.getPt().getY() > bPt2.getPt().getY()) {
return outRec1;
}
else if (bPt1.getPt().getY() < bPt2.getPt().getY()) {
return outRec2;
}
// Y坐标相同，比较X坐标
else if (bPt1.getPt().getX() < bPt2.getPt().getX()) {
return outRec1;
}
else if (bPt1.getPt().getX() > bPt2.getPt().getX()) {
return outRec2;
}
// X和Y坐标都相同，检查是否为单点多边形
else if (bPt1.next == bPt1) {
return outRec2;
}
else if (bPt2.next == bPt2) {
return outRec1;
}
// 使用更复杂的比较方法确定优先级
else if (isFirstBottomPt( bPt1, bPt2 )) {
return outRec1;
}
else {
return outRec2;
}
}
/**
* 确定哪个底部点应该优先处理
* 当有多个相同坐标的底部点时使用
* @param btmPt1 第一个底部点
* @param btmPt2 第二个底部点
* @return 如果btmPt1应优先则返回true
*/
private static boolean isFirstBottomPt(OutPt btmPt1, OutPt btmPt2 ) {
// 获取btmPt1前一个不同的点
OutPt p = btmPt1.prev;
while (p.getPt().equals( btmPt1.getPt() ) && !p.equals( btmPt1 )) {
p = p.prev;
}
final double dx1p = Math.abs( LongPoint.getDeltaX( btmPt1.getPt(), p.getPt() ) );
// 获取btmPt1后一个不同的点
p = btmPt1.next;
while (p.getPt().equals( btmPt1.getPt() ) && !p.equals( btmPt1 )) {
p = p.next;
}
final double dx1n = Math.abs( LongPoint.getDeltaX( btmPt1.getPt(), p.getPt() ) );
// 获取btmPt2前一个不同的点
p = btmPt2.prev;
while (p.getPt().equals( btmPt2.getPt() ) && !p.equals( btmPt2 )) {
p = p.prev;
}
final double dx2p = Math.abs( LongPoint.getDeltaX( btmPt2.getPt(), p.getPt() ) );
// 获取btmPt2后一个不同的点（注意这里有一个bug：条件写错了，应该是!p.equals(btmPt2)）
p = btmPt2.next;
while (p.getPt().equals( btmPt2.getPt() ) && p.equals( btmPt2 )) {
p = p.next;
}
final double dx2n = Math.abs( LongPoint.getDeltaX( btmPt2.getPt(), p.getPt() ) );
// 比较斜率
if (Math.max( dx1p, dx1n ) == Math.max( dx2p, dx2n ) && Math.min( dx1p, dx1n ) == Math.min( dx2p, dx2n )) {
// 如果斜率相同，则使用面积方向来决定
return btmPt1.area() > 0;
}
else {
// 否则选择斜率更大的点
return dx1p >= dx2p && dx1p >= dx2n || dx1n >= dx2p && dx1n >= dx2n;
}
}
/** 索引标志 */
int idx;
/** 点坐标 */
private LongPoint pt;
/** 下一个点的引用 */
OutPt next;
/** 上一个点的引用 */
OutPt prev;
/**
* 创建当前点的副本并插入到链表中
* @param InsertAfter 是否插入到当前点之后
* @return 新创建的点
*/
public OutPt duplicate(boolean InsertAfter ) {
final OutPt result = new OutPt();
result.setPt( new LongPoint( getPt() ) ); // 复制坐标点
result.idx = idx;
// 根据InsertAfter参数决定插入位置
if (InsertAfter) {
result.next = next;
result.prev = this;
next.prev = result;
next = result;
}
else {
result.prev = prev;
result.next = this;
prev.next = result;
prev = result;
}
return result;
}
/**
* 查找多边形中Y坐标最大的点（最底部点）
* @return 最底部点
*/
OutPt getBottomPt() {
OutPt dups = null;
OutPt p = next;
OutPt pp = this;
// 遍历所有点，找到Y值最大的点
while (p != pp) {
if (p.getPt().getY() > pp.getPt().getY()) {
pp = p;
dups = null;
}
else if (p.getPt().getY() == pp.getPt().getY() && p.getPt().getX() <= pp.getPt().getX()) {
if (p.getPt().getX() < pp.getPt().getX()) {
dups = null;
pp = p;
}
else {
// 如果有相同坐标的点，记录下来
if (p.next != pp && p.prev != pp) {
dups = p;
}
}
}
p = p.next;
}
// 处理有多个相同坐标的底部点的情况
if (dups != null) {
while (dups != p) {
if (!isFirstBottomPt( p, dups )) {
pp = dups;
}
dups = dups.next;
while (!dups.getPt().equals( pp.getPt() )) {
dups = dups.next;
}
}
}
return pp;
}
/**
* 计算多边形点链表中的点数量
* @param pts 多边形点链表的起始点
* @return 点的数量
*/
public static int getPointCount( OutPt pts ) {
if (pts == null) return 0;
int result = 0;
OutPt p = pts;
do {
result++;
p = p.next;
}
while (p != pts); // 直到回到起点
return result;
}
/**
* 获取点坐标
* @return 点坐标对象
*/
public LongPoint getPt() {
return pt;
}
/**
* 反转多边形点之间的连接方向
* 用于改变多边形的环绕方向
*/
public void reversePolyPtLinks() {
OutPt pp1;
OutPt pp2;
pp1 = this;
do {
// 交换next和prev引用
pp2 = pp1.next;
pp1.next = pp1.prev;
pp1.prev = pp2;
pp1 = pp2;
}
while (pp1 != this); // 直到处理完所有点
}
/**
* 设置点坐标
* @param pt 新的点坐标
*/
public void setPt( LongPoint pt ) {
this.pt = pt;
}
/**
* 计算多边形的面积
* 使用多边形面积公式：A = 0.5 * Σ(x_i * y_{i+1} - x_{i+1} * y_i)
* @return 多边形面积，正值表示顺时针，负值表示逆时针
*/
private double area() {
OutPt op = this;
double a = 0;
do {
// 应用多边形面积计算公式
a = a + (double) (op.prev.getPt().getX() + op.getPt().getX()) * (double) (op.prev.getPt().getY() - op.getPt().getY());
op = op.next;
} while (op != this);
return a * 0.5;
}
}
/**
* OutRec类表示裁剪结果中的一个路径记录
* 存储多边形的点集合、是否为孔洞等信息
*/
static class OutRec {
/** 索引标识 */
int Idx;
/** 是否为孔洞 */
boolean isHole;
/** 是否为开放路径 */
boolean isOpen;
/** 左侧第一个多边形记录 */
OutRec firstLeft;
/** 多边形的点链表 */
private OutPt pts;
/** 最底部点 */
OutPt bottomPt;
/** 对应的多边形节点 */
PolyNode polyNode;
/**
* 计算多边形面积
* @return 多边形面积
*/
public double area() {
return pts.area();
}
/**
* 修复孔洞链接关系
* 确保firstLeft指向正确的外层多边形
*/
public void fixHoleLinkage() {
// 如果是最外层多边形或已经指向正确的firstLeft，则跳过
if (firstLeft == null || isHole != firstLeft.isHole && firstLeft.pts != null) {
return;
}
// 查找正确的外层多边形
OutRec orfl = firstLeft;
while (orfl != null && (orfl.isHole == isHole || orfl.pts == null)) {
orfl = orfl.firstLeft;
}
firstLeft = orfl;
}
/**
* 获取多边形点链表
* @return 点链表
*/
public OutPt getPoints() {
return pts;
}
/**
* 解析firstLeft引用链，找到有效的firstLeft
* @param firstLeft 起始firstLeft引用
* @return 有效的firstLeft引用
*/
public static OutRec parseFirstLeft( OutRec firstLeft ) {
// 跳过没有点集合的OutRec
while (firstLeft != null && firstLeft.getPoints() == null) {
firstLeft = firstLeft.firstLeft;
}
return firstLeft;
}
/**
* 设置多边形点链表
* @param pts 点链表
*/
public void setPoints( OutPt pts ) {
this.pts = pts;
}
}
/**
* 从点链表中排除指定点
* @param op 要排除的点
* @return 排除后的前一个点
*/
private static OutPt excludeOp(OutPt op ) {
final OutPt result = op.prev;
// 重新链接点，跳过op
result.next = op.next;
op.next.prev = result;
result.idx = 0;
return result;
}
/** 序列化版本ID */
private static final long serialVersionUID = -7120161578077546673L;
/**
* 默认构造函数
* 创建一个空的Path对象
*/
public Path() {
super();
}
/**
* 构造指定初始容量的Path对象
* @param cnt 初始容量
*/
public Path( int cnt ) {
super( cnt );
}
/**
* 计算多边形面积
* 使用多边形面积公式：A = 0.5 * Σ(x_i * y_{i+1} - x_{i+1} * y_i)
* @return 多边形面积，正值表示逆时针（外部多边形），负值表示顺时针（孔洞）
*/
public double area() {
final int cnt = size();
if (cnt < 3) {
return 0; // 少于3个点无法形成多边形
}
double a = 0;
for (int i = 0, j = cnt - 1; i < cnt; ++i) {
// 应用多边形面积计算公式
a += ((double) get( j ).getX() + get( i ).getX()) * ((double) get( j ).getY() - get( i ).getY());
j = i;
}
return -a * 0.5; // 负值调整，使逆时针多边形面积为正
}
/**
* 清理多边形，移除冗余点
* 使用默认的距离阈值（约sqrt(2)）
* @return 清理后的多边形
*/
public Path cleanPolygon() {
return cleanPolygon( 1.415 ); // 默认距离约为√2
}
/**
* 清理多边形，移除冗余点
* 移除距离太近的点和近似共线的点
* @param distance 距离阈值，小于此距离的点将被移除
* @return 清理后的多边形
*/
public Path cleanPolygon(double distance ) {
// distance = 距离阈值，小于此阈值的顶点将被移除
// 默认值~= sqrt(2)，当相邻或半相邻顶点的x和y坐标都在1单位内时，第二个顶点将被移除
int cnt = size();
if (cnt == 0) {
return new Path();
}
// 创建点链表
OutPt[] outPts = new OutPt[cnt];
for (int i = 0; i < cnt; ++i) {
outPts[i] = new OutPt();
}
// 初始化点链表，形成环形结构
for (int i = 0; i < cnt; ++i) {
outPts[i].pt = get( i );
outPts[i].next = outPts[(i + 1) % cnt];
outPts[i].next.prev = outPts[i];
outPts[i].idx = 0;
}
final double distSqrd = distance * distance;
OutPt op = outPts[0];
// 遍历并移除冗余点
while (op.idx == 0 && op.next != op.prev) {
// 1. 移除与前一个点太近的点
if (Point.arePointsClose( op.pt, op.prev.pt, distSqrd )) {
op = excludeOp( op );
cnt--;
}
// 2. 移除中间点，如果前一个和后一个点太近
else if (Point.arePointsClose( op.prev.pt, op.next.pt, distSqrd )) {
excludeOp( op.next );
op = excludeOp( op );
cnt -= 2;
}
// 3. 移除近似共线的点
else if (Point.slopesNearCollinear( op.prev.pt, op.pt, op.next.pt, distSqrd )) {
op = excludeOp( op );
cnt--;
}
else {
// 标记为已处理
op.idx = 1;
op = op.next;
}
}
// 少于3个点不能形成多边形，返回空路径
if (cnt < 3) {
cnt = 0;
}
// 构建结果路径
final Path result = new Path( cnt );
for (int i = 0; i < cnt; ++i) {
result.add( op.pt );
op = op.next;
}
outPts = null; // 帮助GC回收
return result;
}
/**
* 判断点是否在多边形内
* 使用射线法实现，支持复杂多边形和孔洞
* 基于论文："The Point in Polygon Problem for Arbitrary Polygons" by Hormann & Agathos
* @param pt 要判断的点
* @return 0表示点在外部，+1表示点在内部，-1表示点在边界上
*/
public int isPointInPolygon( LongPoint pt ) {
// 返回值：0表示外部，+1表示内部，-1表示在边界上
int result = 0;
final int cnt = size();
if (cnt < 3) {
return 0; // 少于3个点无法形成多边形
}
LongPoint ip = get( 0 );
for (int i = 1; i <= cnt; ++i) {
final LongPoint ipNext = i == cnt ? get( 0 ) : get( i );
// 检查点是否在顶点上或水平边上
if (ipNext.getY() == pt.getY()) {
if (ipNext.getX() == pt.getX() || ip.getY() == pt.getY() && ipNext.getX() > pt.getX() == ip.getX() < pt.getX()) {
return -1; // 在边界上
}
}
// 使用射线法计算点是否在多边形内
if (ip.getY() < pt.getY() != ipNext.getY() < pt.getY()) {
// 边跨越水平射线
if (ip.getX() >= pt.getX()) {
if (ipNext.getX() > pt.getX()) {
// 射线与边相交
result = 1 - result;
}
else {
// 计算交点，检查是否在射线上
final double d = (double) (ip.getX() - pt.getX()) * (ipNext.getY() - pt.getY()) - (double) (ipNext.getX() - pt.getX())
* (ip.getY() - pt.getY());
if (d == 0) {
return -1; // 在边界上
}
else if (d > 0 == ipNext.getY() > ip.getY()) {
// 射线与边相交
result = 1 - result;
}
}
}
else {
if (ipNext.getX() > pt.getX()) {
// 计算交点，检查是否在射线上
final double d = (double) (ip.getX() - pt.getX()) * (ipNext.getY() - pt.getY()) - (double) (ipNext.getX() - pt.getX())
* (ip.getY() - pt.getY());
if (d == 0) {
return -1; // 在边界上
}
else if (d > 0 == ipNext.getY() > ip.getY()) {
// 射线与边相交
result = 1 - result;
}
}
}
}
ip = ipNext;
}
return result;
}
/**
* 确定多边形的方向
* @return 如果是逆时针方向返回true，顺时针返回false
*/
public boolean orientation() {
return area() >= 0; // 面积为正表示逆时针
}
/**
* 反转多边形顶点顺序，改变多边形的环绕方向
*/
public void reverse() {
Collections.reverse( this );
}
/**
* 平移路径，将所有点按照指定偏移量移动
* @param delta 偏移量
* @return 平移后的新路径
*/
public Path TranslatePath(LongPoint delta ) {
final Path outPath = new Path( size() );
for (int i = 0; i < size(); i++) {
outPath.add( new LongPoint( get( i ).getX() + delta.getX(), get( i ).getY() + delta.getY() ) );
}
return outPath;
}
}
最后修改：2025 年 12 月 03 日
© 允许规范转载