![[机器学习]搜索碰撞点以及反向微调退避（0619）](images/news1.jpg)
在$initialize\_trees$函数的几何布局算法中核心机制是通过“从远及近搜索碰撞点再反向微调退避”来为新增的圣诞树找到紧邻现有树群的最短合法距离。设当前已放置的树集合为 $P\{p_1,p_2,\dots,p_k\}$每棵树有其多边形 $A_i$。待放置的新树初始位于极坐标 $(R,\theta)$其中 $R20$单位缩放前的抽象距离$\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_f0$ 时仍安全则新树置于原点。为增强稳健性算法重复10次独立随机角度尝试选择其中 $t_f$ 最小的位置即最贴近现有树群的方案从而在保持紧凑布局的同时兼顾随机多样性。最终整个配置的外接正方形边长由所有树的并集边界确定$$\text{side_length} \max(\max x - \min x,\; \max y - \min y)$$这为后续迭代缩放提供了归一化基准。def initialize_trees(num_trees, existing_treesNone): This builds a simple, greedy starting configuration, by using the previous n-tree placements, and adding more tree for the (n1)-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(anglerandom.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, xofffloat(px * scale_factor), yofffloat(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, xofffloat(px * scale_factor), yofffloat(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, xofffloat(tree_to_place.center_x * scale_factor), yofffloat(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
[机器学习]搜索碰撞点以及反向微调退避（0619）
在$initialize\_trees$函数的几何布局算法中核心机制是通过“从远及近搜索碰撞点再反向微调退避”来为新增的圣诞树找到紧邻现有树群的最短合法距离。设当前已放置的树集合为 $P\{p_1,p_2,\dots,p_k\}$每棵树有其多边形 $A_i$。待放置的新树初始位于极坐标 $(R,\theta)$其中 $R20$单位缩放前的抽象距离$\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_f0$ 时仍安全则新树置于原点。为增强稳健性算法重复10次独立随机角度尝试选择其中 $t_f$ 最小的位置即最贴近现有树群的方案从而在保持紧凑布局的同时兼顾随机多样性。最终整个配置的外接正方形边长由所有树的并集边界确定$$\text{side_length} \max(\max x - \min x,\; \max y - \min y)$$这为后续迭代缩放提供了归一化基准。def initialize_trees(num_trees, existing_treesNone): This builds a simple, greedy starting configuration, by using the previous n-tree placements, and adding more tree for the (n1)-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(anglerandom.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, xofffloat(px * scale_factor), yofffloat(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, xofffloat(px * scale_factor), yofffloat(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, xofffloat(tree_to_place.center_x * scale_factor), yofffloat(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
