99 lines
3.4 KiB
Python
99 lines
3.4 KiB
Python
"""问题一基线实现：网格采样 + 轴对齐包围盒（bbox）代理。
|
|
|
|
这是"先上手"的朴素做法，常见于直接对可行点打网格再读包围盒：
|
|
|
|
1. 在固定大框上按步长采样，保留满足全部角域约束的点；
|
|
2. 直径用包围盒对角线代理 —— 只要区域是斜的/细长的就会系统性高估；
|
|
3. 覆盖判断用"包围盒中心 + 代理直径"的圆 —— 因为包围盒自身对其中心对称，
|
|
该判据几乎恒为"能覆盖"，从而丢掉问题一真正要考的反例。
|
|
|
|
本实现刻意保留这些结构性缺陷，作为``optimal.py``的对照；它不读取最优实现的
|
|
任何中间量，两条代码路径完全独立。
|
|
"""
|
|
|
|
from __future__ import annotations
|
|
|
|
import math
|
|
from time import perf_counter
|
|
|
|
import numpy as np
|
|
|
|
from mcm26b.geometry.localization import Measurement, halfplanes
|
|
|
|
from project.common import Method
|
|
|
|
METHOD = Method(
|
|
key="baseline",
|
|
name="网格采样 + bbox 对角线代理",
|
|
kind="baseline",
|
|
note="轴对齐包围盒近似直径与覆盖，O(盒面积/步长²)，与参考解同分辨率",
|
|
)
|
|
|
|
BOX_M = 2600.0
|
|
STEP_M = 5.0
|
|
|
|
|
|
def solve_case(case: dict) -> dict:
|
|
start = perf_counter()
|
|
measurements = [Measurement(row["x"], row["y"], row["bearing_deg"],
|
|
row.get("half_angle_deg", 1.0))
|
|
for row in case["measurements"]]
|
|
planes = [plane for m in measurements for plane in halfplanes(m)]
|
|
|
|
xs = np.arange(-BOX_M, BOX_M + STEP_M, STEP_M)
|
|
grid_x, grid_y = np.meshgrid(xs, xs) # 行=y，列=x
|
|
mask = np.ones(grid_x.shape, dtype=bool)
|
|
for a, b, c in planes:
|
|
mask &= (a * grid_x + b * grid_y <= c)
|
|
|
|
result = _evaluate(mask, xs)
|
|
result["method"] = METHOD.key
|
|
result["runtime_ms"] = round((perf_counter() - start) * 1000.0, 4)
|
|
result["algorithm"] = METHOD.name
|
|
return result
|
|
|
|
|
|
def _evaluate(mask: np.ndarray, axis: np.ndarray) -> dict:
|
|
if not mask.any():
|
|
return _empty("empty")
|
|
# 可行点触到采样框边界 => 区域至少延伸到框外，判无界
|
|
if (mask[0, :].any() or mask[-1, :].any()
|
|
or mask[:, 0].any() or mask[:, -1].any()):
|
|
return _empty("unbounded")
|
|
|
|
rows, cols = np.nonzero(mask)
|
|
x_min, x_max = axis[cols].min(), axis[cols].max()
|
|
y_min, y_max = axis[rows].min(), axis[rows].max()
|
|
width, height = x_max - x_min, y_max - y_min
|
|
diameter = math.hypot(width, height) # 包围盒对角线代理
|
|
center = ((x_min + x_max) / 2.0, (y_min + y_max) / 2.0)
|
|
px = axis[cols]
|
|
py = axis[rows]
|
|
max_distance = float(np.max(np.hypot(px - center[0], py - center[1])))
|
|
return {
|
|
"status": "polygon" if mask.sum() >= 2 else "point",
|
|
"diameter_m": diameter,
|
|
"diameter_infinite": False,
|
|
"covers": bool(max_distance <= diameter / 2.0 + 1e-9),
|
|
"mec_radius_m": None,
|
|
"max_excess_m": round(max_distance - diameter / 2.0, 6),
|
|
"outside_vertex_count": None,
|
|
"vertex_count": int(mask.sum()),
|
|
"bbox_width_m": round(width, 3),
|
|
"bbox_height_m": round(height, 3),
|
|
"runtime_ms": None,
|
|
}
|
|
|
|
|
|
def _empty(status: str) -> dict:
|
|
return {
|
|
"status": status,
|
|
"diameter_m": None,
|
|
"diameter_infinite": status == "unbounded",
|
|
"covers": None,
|
|
"mec_radius_m": None,
|
|
"max_excess_m": None,
|
|
"outside_vertex_count": None,
|
|
"vertex_count": 0,
|
|
}
|