algorithm - 旋转椭圆中所有整个纬度/经度交叉点的最快算法？

Question

我正在为具有平行(但可旋转)投影的 2.5D 游戏开发图 block 引擎。瓦片是平面四边形，其顶点已根据相机位置和 x/y 旋转进行了调整和位置设置。没有偏航 (z)。用 Starling 编写引擎。

相机的可见区域可以描述为落在任意旋转和任意高度的固定宽度的椭圆内的网格区域。

我现在想做的是在必须投影它们之前获取落在屏幕空间内的图 block 列表，而不必针对缩放半径/sin/cos 测试每个坐标集。只要它大于半径，它就可以是脏集。但我正在寻找最少污染和最优化的解决方案。

Answer 1

如果我理解正确的话，这类似于填充问题。

您在椭圆上覆盖了一个矩形网格，并且您想要列出至少在椭圆内有一个角的图 block 。通过适当的缩放，这与扫描填充椭圆相同。

将椭圆置于其隐式形式 ax² + 2bxy + cy² + 2dx + 2ey + f = 0 中，坐标缩放/平移，以便网格点落在整数坐标处。您首先确定 y 值的有用范围。然后对于每条扫描线，您确定 x 的极值。

设 y 固定，您在 x 中有一个二次方程:ax² + 2(by + d)x + (cy² + 2ey + f ) = 0。

它的判别式是(by+d)- a(cy²+2ey+f) = (b²-ac)y² + 2(bd-ae)y + (d²-af)。

在 y 中求解这个二次方程可以得到 y 值的范围；取最小的天花板和最大的地板。

然后对于这个范围内的每个整数，求解x，你将得到水平范围。

[请注意，我对 At² + 2Bt + C= 0 形式的方程使用判别式 B²-AC。]