240 lines
8.0 KiB
Python
240 lines
8.0 KiB
Python
from __future__ import annotations
|
|
|
|
import math
|
|
from dataclasses import dataclass, field
|
|
from typing import Any, Callable, Protocol, TypeVar
|
|
|
|
|
|
MAX_LINES = 4
|
|
|
|
|
|
class PointLike(Protocol):
|
|
uid: int
|
|
x: float
|
|
y: float
|
|
row: int
|
|
col: int
|
|
|
|
|
|
PointT = TypeVar("PointT", bound=PointLike)
|
|
TypeVarT = TypeVar("TypeVarT")
|
|
|
|
|
|
@dataclass(frozen=True)
|
|
class UnfoldingSpec:
|
|
max_lines: int = MAX_LINES
|
|
neighbor_mode: str = "grid-8"
|
|
direction: str = "clockwise"
|
|
|
|
|
|
@dataclass(frozen=True)
|
|
class UnfoldingLineSummary:
|
|
line_id: int
|
|
led_count: int
|
|
block_count: int
|
|
|
|
|
|
@dataclass
|
|
class UnfoldingDescription:
|
|
max_lines: int = MAX_LINES
|
|
line_order: str = "clockwise"
|
|
block_order: str = "clockwise"
|
|
led_index_scope: str = "line"
|
|
block_size: int | None = None
|
|
block_counts: list[UnfoldingLineSummary] = field(default_factory=list)
|
|
|
|
@classmethod
|
|
def from_payload(cls, payload: Any) -> "UnfoldingDescription":
|
|
if not isinstance(payload, dict):
|
|
return cls()
|
|
|
|
max_lines = max(1, min(int(payload.get("max_lines", MAX_LINES)), MAX_LINES))
|
|
block_size = payload.get("block_size")
|
|
block_counts: list[UnfoldingLineSummary] = []
|
|
for item in payload.get("block_counts", []):
|
|
if isinstance(item, dict):
|
|
block_counts.append(
|
|
UnfoldingLineSummary(
|
|
line_id=int(item.get("line_id", 0)),
|
|
led_count=int(item.get("led_count", 0)),
|
|
block_count=int(item.get("block_count", 0)),
|
|
)
|
|
)
|
|
|
|
return cls(
|
|
max_lines=max_lines,
|
|
line_order=str(payload.get("line_order", "clockwise")),
|
|
block_order=str(payload.get("block_order", "clockwise")),
|
|
led_index_scope=str(payload.get("led_index_scope", "line")),
|
|
block_size=None if block_size is None else int(block_size),
|
|
block_counts=block_counts,
|
|
)
|
|
|
|
def to_payload(self) -> dict[str, Any]:
|
|
payload: dict[str, Any] = {
|
|
"max_lines": max(1, min(self.max_lines, MAX_LINES)),
|
|
"line_order": self.line_order,
|
|
"block_order": self.block_order,
|
|
"led_index_scope": self.led_index_scope,
|
|
"block_counts": [
|
|
{
|
|
"line_id": item.line_id,
|
|
"led_count": item.led_count,
|
|
"block_count": item.block_count,
|
|
}
|
|
for item in self.block_counts
|
|
],
|
|
}
|
|
if self.block_size is not None:
|
|
payload["block_size"] = self.block_size
|
|
return payload
|
|
|
|
def expected_block_count(self, led_count: int) -> int:
|
|
if led_count <= 0:
|
|
return 0
|
|
if self.block_size is None or self.block_size <= 0:
|
|
return 1
|
|
return math.ceil(led_count / self.block_size)
|
|
|
|
|
|
@dataclass(frozen=True)
|
|
class BlockDescriptor:
|
|
id: int
|
|
name: str
|
|
led_count: int
|
|
start_index: int
|
|
end_index: int
|
|
|
|
|
|
@dataclass(frozen=True)
|
|
class LineDescriptor:
|
|
id: int
|
|
name: str
|
|
block_count: int
|
|
led_count: int
|
|
blocks: list[BlockDescriptor] = field(default_factory=list)
|
|
|
|
|
|
@dataclass(frozen=True)
|
|
class UnfoldingSummary:
|
|
spec: UnfoldingSpec
|
|
lines: list[LineDescriptor]
|
|
|
|
|
|
def connected_groups(points: list[PointT]) -> list[list[PointT]]:
|
|
remaining = set(point.uid for point in points)
|
|
by_id = {point.uid: point for point in points}
|
|
groups: list[list[PointT]] = []
|
|
while remaining:
|
|
start = remaining.pop()
|
|
queue = [start]
|
|
group = [by_id[start]]
|
|
while queue:
|
|
current = by_id[queue.pop()]
|
|
for candidate_id in list(remaining):
|
|
candidate = by_id[candidate_id]
|
|
if are_neighbors(current, candidate):
|
|
remaining.remove(candidate_id)
|
|
queue.append(candidate_id)
|
|
group.append(candidate)
|
|
groups.append(group)
|
|
return sorted(groups, key=lambda group: min(point_sort_key(point) for point in group))
|
|
|
|
|
|
def order_points_clockwise(points: list[PointT]) -> list[PointT]:
|
|
if len(points) <= 2:
|
|
return sorted(points, key=point_sort_key)
|
|
|
|
center_x = sum(point.x for point in points) / len(points)
|
|
center_y = sum(point.y for point in points) / len(points)
|
|
ordered = sorted(
|
|
points,
|
|
key=lambda point: (
|
|
clockwise_angle(point, center_x, center_y),
|
|
distance_to_center(point, center_x, center_y),
|
|
point_sort_key(point),
|
|
),
|
|
)
|
|
ordered = ensure_clockwise(ordered)
|
|
return rotate_to_stable_start(ordered)
|
|
|
|
|
|
def order_blocks_clockwise(block_point_ids: list[list[int]], points_by_id: dict[int, PointT]) -> list[list[int]]:
|
|
non_empty = [block for block in block_point_ids if block]
|
|
if len(non_empty) <= 1:
|
|
return non_empty
|
|
|
|
line_points = [points_by_id[point_id] for block in non_empty for point_id in block]
|
|
center_x = sum(point.x for point in line_points) / len(line_points)
|
|
center_y = sum(point.y for point in line_points) / len(line_points)
|
|
|
|
def block_key(block: list[int]) -> tuple[float, float, int]:
|
|
block_points = [points_by_id[point_id] for point_id in block]
|
|
block_x = sum(point.x for point in block_points) / len(block_points)
|
|
block_y = sum(point.y for point in block_points) / len(block_points)
|
|
angle = (-math.atan2(block_y - center_y, block_x - center_x)) % math.tau
|
|
radius = math.hypot(block_x - center_x, block_y - center_y)
|
|
return angle, radius, min(block)
|
|
|
|
return sorted(non_empty, key=block_key)
|
|
|
|
|
|
def clockwise_sort(items: list[TypeVarT], points_for_item: Callable[[TypeVarT], list[PointLike]]) -> list[TypeVarT]:
|
|
if len(items) <= 1:
|
|
return items[:]
|
|
|
|
items_with_points = [(item, points_for_item(item), index) for index, item in enumerate(items)]
|
|
non_empty = [(item, points, index) for item, points, index in items_with_points if points]
|
|
empty = [(item, index) for item, points, index in items_with_points if not points]
|
|
if len(non_empty) <= 1:
|
|
return [item for item, _, _ in non_empty] + [item for item, _ in empty]
|
|
|
|
all_points = [point for _, points, _ in non_empty for point in points]
|
|
center_x = sum(point.x for point in all_points) / len(all_points)
|
|
center_y = sum(point.y for point in all_points) / len(all_points)
|
|
|
|
def item_key(item_data: tuple[TypeVarT, list[PointLike], int]) -> tuple[float, float, int]:
|
|
_, points, index = item_data
|
|
item_x = sum(point.x for point in points) / len(points)
|
|
item_y = sum(point.y for point in points) / len(points)
|
|
angle = (-math.atan2(item_y - center_y, item_x - center_x)) % math.tau
|
|
radius = math.hypot(item_x - center_x, item_y - center_y)
|
|
return angle, radius, index
|
|
|
|
return [item for item, _, _ in sorted(non_empty, key=item_key)] + [item for item, _ in empty]
|
|
|
|
|
|
def are_neighbors(a: PointLike, b: PointLike) -> bool:
|
|
return abs(a.row - b.row) <= 1 and abs(a.col - b.col) <= 1
|
|
|
|
|
|
def point_sort_key(point: PointLike) -> tuple[int, int, float, float, int]:
|
|
return point.row, point.col, point.x, point.y, point.uid
|
|
|
|
|
|
def clockwise_angle(point: PointLike, center_x: float, center_y: float) -> float:
|
|
return (-math.atan2(point.y - center_y, point.x - center_x)) % math.tau
|
|
|
|
|
|
def distance_to_center(point: PointLike, center_x: float, center_y: float) -> float:
|
|
return math.hypot(point.x - center_x, point.y - center_y)
|
|
|
|
|
|
def signed_area(points: list[PointLike]) -> float:
|
|
area = 0.0
|
|
for index, point in enumerate(points):
|
|
next_point = points[(index + 1) % len(points)]
|
|
area += point.x * next_point.y - next_point.x * point.y
|
|
return area / 2.0
|
|
|
|
|
|
def ensure_clockwise(points: list[PointT]) -> list[PointT]:
|
|
if len(points) < 3 or signed_area(points) <= 0:
|
|
return points
|
|
return [points[0], *reversed(points[1:])]
|
|
|
|
|
|
def rotate_to_stable_start(points: list[PointT]) -> list[PointT]:
|
|
start = min(range(len(points)), key=lambda index: point_sort_key(points[index]))
|
|
return [*points[start:], *points[:start]]
|