Pygorithm项目中的几何模块详解：从基础图形到碰撞检测

概述

Pygorithm项目的几何模块提供了一套完整的2D几何图形处理工具，涵盖了从基础向量运算到复杂多边形碰撞检测的各种功能。本文将深入解析该模块的核心组件和使用方法，帮助开发者快速掌握2D几何运算的关键技术。

核心组件介绍

1. 向量运算(Vector2)

Vector2类是几何模块的基础，封装了二维向量的基本运算：

from pygorithm.geometry import vector2

# 创建向量
v1 = vector2.Vector2(1, 2)
v2 = vector2.Vector2(3, 4)

# 向量加法
v3 = v1 + v2  # Vector2(4, 6)

# 向量点积
dot_product = v1.dot(v2)  # 11

# 向量归一化
normalized = v1.normalize()

Vector2类还支持叉积、旋转、投影等常见向量运算，是构建更复杂几何图形的基础。

2. 线段与轴对齐线段

几何模块提供了两种线段表示：

• Line2：任意方向的线段
• AxisAlignedLine：轴对齐线段(水平或垂直)

from pygorithm.geometry import line2, axisall

# 创建任意线段
line = line2.Line2(vector2.Vector2(0,0), vector2.Vector2(1,1))

# 创建水平线段
h_line = axisall.AxisAlignedLine(0, 10, 5, True)  # y=5, x从0到10

3. 多边形(Polygon2)

Polygon2类支持凸多边形的创建和操作：

from pygorithm.geometry import polygon2

# 创建正五边形
pentagon = polygon2.Polygon2.from_regular(5, 5)  # 5边形，半径5

# 自定义多边形(顶点必须按顺时针排列)
square = polygon2.Polygon2([(0,0), (1,0), (1,1), (0,1)])

# 旋转多边形
rotated_square = square.rotate(0.5)  # 旋转0.5弧度

核心算法解析

1. 分离轴定理(SAT)碰撞检测

Polygon2类实现了分离轴定理算法，用于检测两个凸多边形是否相交：

# 检测两个多边形是否相交
intersect, mtv = polygon2.Polygon2.find_intersection(poly1, poly2)

if intersect:
    distance, vector = mtv
    print(f"需要沿{vector}方向移动{distance}单位以分离多边形")

SAT算法通过在多边形所有边的法向量上进行投影，判断是否存在分离轴来检测碰撞。

2. 外推相交检测

extrapolated_intersection模块提供了预测性碰撞检测功能，可以计算移动物体未来的碰撞点：

from pygorithm.geometry import extrapolated_intersection

# 预测移动中的碰撞
result = extrapolated_intersection.extrapolated_intersection(
    moving_polygon, 
    stationary_polygon, 
    velocity_vector
)

if result.will_intersect:
    print(f"将在{result.distance}时间单位后碰撞")

3. 轴对齐矩形(Rect2)

Rect2类针对轴对齐矩形进行了优化，支持高效的边界框检测：

from pygorithm.geometry import rect2

# 创建矩形
rect = rect2.Rect2(0, 0, 10, 5)  # 左上角(0,0)，宽10，高5

# 快速碰撞检测
if rect.overlaps(other_rect):
    print("矩形相交")

实际应用示例

游戏开发中的碰撞检测

# 游戏对象基类
class GameObject:
    def __init__(self, position, polygon):
        self.position = position
        self.polygon = polygon
    
    def check_collision(self, other):
        # 考虑位置偏移后的多边形
        poly1 = self.polygon.translate(self.position)
        poly2 = other.polygon.translate(other.position)
        return polygon2.Polygon2.find_intersection(poly1, poly2)

# 使用示例
player = GameObject(vector2.Vector2(0,0), player_poly)
obstacle = GameObject(vector2.Vector2(5,5), obstacle_poly)

if player.check_collision(obstacle):
    print("碰撞发生!")

物理模拟中的运动预测

def simulate_movement(obj, target, obstacles):
    velocity = (target - obj.position).normalize() * SPEED
    for obstacle in obstacles:
        result = extrapolated_intersection.extrapolated_intersection(
            obj.polygon.translate(obj.position),
            obstacle.polygon.translate(obstacle.position),
            velocity
        )
        if result.will_intersect and result.distance < SAFE_THRESHOLD:
            # 调整速度避免碰撞
            velocity = calculate_avoidance_vector(velocity, result)
    return velocity

性能优化建议

1. 使用Rect2进行粗检测：在复杂场景中，先用轴对齐矩形进行快速筛选，再对可能碰撞的对象使用精确的多边形检测。

2. 减少多边形顶点数：碰撞检测的复杂度与顶点数成正比，在精度允许的情况下尽量减少顶点。

3. 利用空间分区：对于大量静态对象，使用四叉树等空间分区结构减少检测次数。

总结

Pygorithm的几何模块提供了从基础到高级的2D几何处理能力，特别适合游戏开发、物理模拟和计算机图形学应用。通过掌握向量运算、多边形操作和碰撞检测算法，开发者可以构建出高效可靠的几何处理系统。