[机器学习]搜索碰撞点以及反向微调退避（0619）

在$initialize\_trees$函数的几何布局算法中，核心机制是通过“从远及近搜索碰撞点，再反向微调退避”来为新增的圣诞树找到紧邻现有树群的最短合法距离。设当前已放置的树集合为 $P=\{p_1,p_2,\dots,p_k\}$，每棵树有其多边形 $A_i$。待放置的新树初始位于极坐标 $(R,\theta)$，其中 $R=20$（单位：缩放前的抽象距离），$\theta$ 由加权随机角度生成，方向向量 $v=(\cos\theta,\sin\theta)$。算法沿射线 $p(t)=t\cdot v$（$t\in[0,R]$）以步长 $\Delta_{\text{in}}=0.5$ 向前扫描，寻找第一个使 $A_{\text{new}}(t)$与任一 $A_i$发生真相交（intersects 且不仅为 touches）的临界半径 $t_c$。若存在 $t_c$，则退回到 $t_c-\Delta_{\text{in}}$（即最后一个无碰撞位置），然后以步长 $\Delta_{\text{out}}=0.05$向外微调，直到再次刚好脱离碰撞，得到最终半径 $t_f$。该过程等价于求解方程：

$$t_f = \inf\{ t \ge t_c - \Delta_{\text{in}} \mid \forall i,\; A_{\text{new}}(t) \cap A_i = \emptyset \;\lor\; A_{\text{new}}(t) \text{ touches } A_i \}$$

由于多边形为凸包（圣诞树简化形状），交点检测可由STRtree加速至 $O(\log k)$。若整个扫描过程未发现任何碰撞（即 $t_f=0$ 时仍安全），则新树置于原点。为增强稳健性，算法重复10次独立随机角度尝试，选择其中 $t_f$ 最小的位置（即最贴近现有树群的方案），从而在保持紧凑布局的同时兼顾随机多样性。最终整个配置的外接正方形边长由所有树的并集边界确定，

$$\text{side_length} = \max(\max x - \min x,\; \max y - \min y)$$

这为后续迭代缩放提供了归一化基准。

def initialize_trees(num_trees, existing_trees=None): """ This builds a simple, greedy starting configuration, by using the previous n-tree placements, and adding more tree for the (n+1)-tree configuration. We place a tree fairly far away at a (weighted) random angle, and the bring it closer to the center until it overlaps. Then we back it up until it no longer overlaps. You can easily modify this code to build each n-tree configuration completely from scratch. """ if num_trees == 0: return [], Decimal('0') if existing_trees is None: placed_trees = [] else: placed_trees = list(existing_trees) num_to_add = num_trees - len(placed_trees) if num_to_add > 0: unplaced_trees = [ ChristmasTree(angle=random.uniform(0, 360)) for _ in range(num_to_add)] if not placed_trees: # Only place the first tree at origin if starting from scratch placed_trees.append(unplaced_trees.pop(0)) for tree_to_place in unplaced_trees: placed_polygons = [p.polygon for p in placed_trees] tree_index = STRtree(placed_polygons) best_px = None best_py = None min_radius = Decimal('Infinity') # This loop tries 10 random starting attempts and keeps the best one for _ in range(10): # The new tree starts at a position 20 from the center, at a random vector angle. angle = generate_weighted_angle() vx = Decimal(str(math.cos(angle))) vy = Decimal(str(math.sin(angle))) # Move towards center along the vector in steps of 0.5 until collision radius = Decimal('20.0') step_in = Decimal('0.5') collision_found = False while radius >= 0: px = radius * vx py = radius * vy candidate_poly = affinity.translate( tree_to_place.polygon, xoff=float(px * scale_factor), yoff=float(py * scale_factor)) # Looking for nearby objects possible_indices = tree_index.query(candidate_poly) # This is the collision detection step if any((candidate_poly.intersects(placed_polygons[i]) and not candidate_poly.touches(placed_polygons[i])) for i in possible_indices): collision_found = True break radius -= step_in # back up in steps of 0.05 until it no longer has a collision. if collision_found: step_out = Decimal('0.05') while True: radius += step_out px = radius * vx py = radius * vy candidate_poly = affinity.translate( tree_to_place.polygon, xoff=float(px * scale_factor), yoff=float(py * scale_factor)) possible_indices = tree_index.query(candidate_poly) if not any((candidate_poly.intersects(placed_polygons[i]) and not candidate_poly.touches(placed_polygons[i])) for i in possible_indices): break else: # No collision found even at the center. Place it at the center. radius = Decimal('0') px = Decimal('0') py = Decimal('0') if radius < min_radius: min_radius = radius best_px = px best_py = py tree_to_place.center_x = best_px tree_to_place.center_y = best_py tree_to_place.polygon = affinity.translate( tree_to_place.polygon, xoff=float(tree_to_place.center_x * scale_factor), yoff=float(tree_to_place.center_y * scale_factor), ) placed_trees.append(tree_to_place) # Add the newly placed tree to the list all_polygons = [t.polygon for t in placed_trees] bounds = unary_union(all_polygons).bounds minx = Decimal(bounds[0]) / scale_factor miny = Decimal(bounds[1]) / scale_factor maxx = Decimal(bounds[2]) / scale_factor maxy = Decimal(bounds[3]) / scale_factor width = maxx - minx height = maxy - miny # this forces a square bounding using the largest side side_length = max(width, height) return placed_trees, side_length