我正在使用Alberto Santini的解决方案来获取基于项目索引的螺旋网格引用。
算法：在从原点开始的离散二维网格上迭代遍历外螺旋
这不是被接受的解决方案，但是它最适合我的需求，因为它避免了使用循环。
它工作得很好，但现在我想做相反的事情。根据已知的x和y坐标返回位置的索引。
这是作为返回给定位置周围物品的前提条件。
它工作得很好，但现在我想做相反的事情。根据已知的x和y坐标返回位置的索引。
这是作为返回给定位置周围物品的前提条件。
3个回答
8
Pascal代码：
if y * y >= x * x then begin
p := 4 * y * y - y - x;
if y < x then
p := p - 2 * (y - x)
end
else begin
p := 4 * x * x - y - x;
if y < x then
p := p + 2 *(y - x)
end;
描述：左上角的半对角线（0-4-16-36-64）包含平方层数（4 * 层数^2）。外部if语句定义层数，并在左上半平面的相应行或列中找到（前）结果。内部if语句纠正镜像位置的结果。
- MBo
1
完美。非常简洁。谢谢。 - ricick
0
我不知道是否有一个简洁的数学方程来推导您想要的内容，但我有一个解决方案，每个查询计算您想要的内容所需的时间为O(1)。没有像您想要的那样的循环。
我的方法：
(i) 对于任何给定的点(x,y)，找出位于边长为(2*a-1)的正方形内的点的数量，其中a=Max(|x|, |y|)。这些是内部点。即，在所有未包括当前螺旋线的螺旋线中所处的点的数量。
这实际上就是(2*a-1)*(2*a-1)
例如：考虑以下图表：
y
|
|
16 15 14 13 12
17 4 3 2 11
-- 18 5 0 1 10 --- x
19 6 7 8 9
20 21 22 23 24
|
|
对于点（2,1），a = 2。内部点标记为0、1、2、3、4、5、6、7、8 - 边长为3的正方形。
(ii) 现在计算位于当前螺旋线上的点。螺旋线有4个“拐角”点 -
(a) 起始点（当前螺旋线开始的地方）
(b) 点（a，a）
(c) 点（-a，a）
(d) 点（-a，-a）
因此，我计算每对这样的点之间的元素数量[即，在（a）和（b）、（b）和（c）、（c）和（d）之间]，以便所有这些元素都在所需输入点之前落在螺旋序列中。这可以通过简单的点坐标相减来完成。
这个值加上内部点的数量将给出您需要的答案。
我不确定我是否解释得很清楚。如果您需要任何澄清或进一步解释，请告诉我。
附上我编写的JAVA代码，用于测试我的逻辑。很抱歉它不是非常优雅，但它能够正常工作 :P
import java.io.IOException;
import java.util.Scanner;
class Pnt
{
int x, y;
public Pnt( int _x, int _y )
{
x = _x;
y = _y;
}
}
public class Spiral
{
static int interior( Pnt p ) // returns points within interior square of side length MAX( x, y ) - 1
{
int a = Math.max( Math.abs( p.x ), Math.abs( p.y ));
return ( 2*a - 1 )*( 2*a - 1 );
}
static Pnt startPnt( Pnt p ) // first point in that spiral
{
int a = Math.max( Math.abs( p.x ), Math.abs( p.y ));
// last pnt in prev spiral = [ a-1, -( a-1 ) ]
// next pnt = [ a, -( a-1 ) ]
return new Pnt( a, -( a-1 ));
}
static int offSetRow1( Pnt pStart, Pnt p )
{
return ( p.y - pStart.y ) + 1;
}
static int solve( Pnt curr )
{
// check location of curr
// It may lie on 1st row, 2nd row, 3rd or 4th row
int a = Math.max( Math.abs( curr.x ), Math.abs( curr.y ));
int off=0;
int interiorCnt = interior( curr );
Pnt start = startPnt( curr );
if( ( curr.x == a ) && ( curr.y >= start.y ) ) // row 1
{
off = offSetRow1( start, curr );
return off+interiorCnt;
}
if( curr.y == a ) // row 2
{
Pnt start2 = new Pnt( a, a );
int off1 = offSetRow1( start, start2 );
// now add diff in x-coordinates
int off2 = start2.x - curr.x;
off = off1 + off2;
return off+interiorCnt;
}
if( curr.x == -a ) // row 3
{
Pnt start2 = new Pnt( a, a );
int off1 = offSetRow1( start, start2 );
// now add diff in x-coordinates
Pnt start3 = new Pnt( -a, a );
int off2 = start2.x - start3.x;
// now add diff in y co-ordinates
int off3 = start3.y - curr.y;
off = off1 + off2 + off3;
return off+interiorCnt;
}
else // row 4
{
Pnt start2 = new Pnt( a, a );
int off1 = offSetRow1( start, start2 );
// now add diff in x-coordinates
Pnt start3 = new Pnt( -a, a );
int off2 = start2.x - start3.x;
// now add diff in y co-ordinates
int off3 = start3.y - curr.y;
Pnt start4 = new Pnt( -a, -a );
// add diff in x co-ordinates
int off4 = curr.x - start4.x;
off = off1 + off2 + off3 + off4;
return interiorCnt + off;
}
}
public static void main( String[] args ) throws IOException
{
Scanner s = new Scanner( System.in );
while( true )
{
int x = s.nextInt();
int y = s.nextInt();
Pnt curr = new Pnt( x, y );
System.out.println( solve( curr ));
}
}
}
- arya
0
我想加入我的函数，因为它比上一个解决方案更简洁，但比第一个更复杂。 我的代码不是将索引相邻，而是选择循环/层次结构，其中下一个循环的第一个索引始终在同一轴上。
就像这样：
23 24 9 10 11 +y
22 8 1 2 12
21 7 0 3 13
20 6 5 4 14
19 18 17 16 15 -y
-x +x
它有设置方向，并使用较小的vec2值作为这些东南西北轴的偏移量
func translate_vector2_to_spiral_index(vec2):
#layer is the ring level the position is on
var layer = max(abs(vec2.x),abs(vec2.y))
if layer == 0:
return 0
#the total interior positions before the edge
var base_index = 0
var i = 0
while i < layer:
base_index += 8 * i
i+=1
var current_layer_total = 8 * i
#non_axis spaces at each corner (not directly any nesw axis)
var non_axis_spaces = (current_layer_total - 4)/4
#direct axes spaces on this layer
var N = 1
var E = N + non_axis_spaces + 1
var S = E + non_axis_spaces + 1
var W = S + non_axis_spaces + 1
var spiral_index = base_index
if abs(vec2.x) > abs(vec2.y):
if vec2.x < 0:
spiral_index+=W
spiral_index += vec2.y
elif vec2.x > 0:
spiral_index+=E
spiral_index -= vec2.y
else:
if vec2.y < 0:
spiral_index+=S
elif vec2.y > 0:
spiral_index+=N
#abs(y) must be equivalent to layers if x is 0
else:
if vec2.y < 0:
spiral_index+=S
spiral_index -= vec2.x
elif vec2.y > 0:
spiral_index
var x = N
x += vec2.x
#if x goes into the negative on the iteration axis (N) it's a subtraction from the layer total
if vec2.x < 0:
x = current_layer_total + 1 + vec2.x
spiral_index += x
else:
if vec2.x < 0:
spiral_index+=W
elif vec2.x > 0:
spiral_index+=E
#abs(x) must be equivalent to layers if y is 0
return spiral_index
可能有一种方法可以缩短这个过程，但我想先把它放出来。
- DED
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接