使用位运算在3D欧几里德坐标网格中找到点所在的八分之一。

huangapple go评论64阅读模式
英文:

Using bitwise operations for finding octant of point in 3D euclidean coordinate grid

问题

我们被赋予这样一个函数的怪物,它接受一个3D点列表,并返回对应于列表中每个八分之一的点在欧几里得三维坐标系中所占位置的八个值。

从numba导入jit
import numpy
时间

@jitnopython = True
def OctantPopCountpoints):
    assert points.shape [1] == 3
    计数器= numpy.zeros8dtype = numpy.uint32

    对于p中的p
        if p [0]lt; 0和p [1]lt; 0和p [2]lt; 0
            counters [7] + = 1
        elif p [0]lt; 0和p [1]lt; 0 and not p [2]lt; 0
            计数器[6] + = 1
        elif p [0]lt; 0 and not p [1]lt; 0 and p [2]lt; 0
            计数器[5] + = 1
        elif p [0]lt; 0 and not p [1]lt; 0 and not p [2]lt; 0
            计数器[4] + = 1
        elif not p [0]lt; 0 and p [1]lt; 0 and p [2]lt; 0
            计数器[3] + = 1
        elif not p [0]lt; 0 and p [1]lt; 0 and not p [2]lt; 0
            计数器[2] + = 1
        elif not p [0]lt; 0 and not p [1]lt; 0 and p [2]lt; 0
            计数器[1] + = 1
        else
            计数器[0] + = 1
    
    返回计数器

任务是编写一个执行与上述函数相同任务的函数,但不使用任何“if”语句。这是我的解决方案:

@jit(nopython = True)
def octant_count(points):
assert points.shape [1] == 3
计数器= numpy.zeros(8,dtype = numpy.uint32)
对于点中的点:
x_bit = int(point [0] > = 0)<< 0
y_bit = int(point [1] > = 0)<< 1
z_bit = int(point [2] > = 0)<< 2
octant = x_bit | y_bit | z_bit
计数器[octant] + = 1
返回计数器

例如,给定点p =(1,1,1),我们找到每个分量的符号,将它们位移到正确位置,将它们OR在一起得到8位数字,并将值增加到该数字的索引处。在p =(1,1,1)的情况下,八分之一将是“0b00000111”,在十进制中为7,因此具有全正分量的任何点都将放在第7个八分之一。我想要修复的是将点放入计数器变量中的位置。

在函数“OctantPopCount()”中,所有正分量的点都被放在第一个八分之一,而我的分配给它们第7个。

我可以采取哪些方法来修复这个问题呢?

有一些方法可以采取来修复这个问题。

英文:

We were given this monstrosity of a function that takes a list of 3D points, and returns a list of 8 values corresponding to how many points in the list occupy each octant of a euclidean three-dimensional coordinate system.

from numba import jit
import numpy
import time

@jit(nopython=True)
def OctantPopCount(points):
    assert points.shape[1] == 3
    counters = numpy.zeros(8, dtype=numpy.uint32)

    for p in points:
        if p[0]<0 and p[1]<0 and p[2]<0:
            counters[7] += 1
        elif p[0]<0 and p[1]<0 and not p[2]<0:
            counters[6] += 1
        elif p[0]<0 and not p[1]<0 and p[2]<0:
            counters[5] += 1
        elif p[0]<0 and not p[1]<0 and not p[2]<0:
            counters[4] += 1
        elif not p[0]<0 and p[1]<0 and p[2]<0:
            counters[3] += 1
        elif not p[0]<0 and p[1]<0 and not p[2]<0:
            counters[2] += 1
        elif not p[0]<0 and not p[1]<0 and p[2]<0:
            counters[1] += 1
        else:
            counters[0] += 1
    
    return counters

The task was to write a function that does the same task as the function above, but without using any if statements. Here's my solution:

@jit(nopython=True)
def octant_count(points):
assert points.shape[1] == 3
counters = numpy.zeros(8, dtype=numpy.uint32)
for point in points:
x_bit = int(point[0] >= 0) << 0
y_bit = int(point[1] >= 0) << 1
z_bit = int(point[2] >= 0) << 2
octant = x_bit | y_bit | z_bit
counters[octant] += 1
return counters

For instance, given a point p = (1,1,1), we find the sign of each component, bitshift them to the correct position, OR them together into an 8-bit number, and increment the value at the index of that number. In the context of p = (1,1,1), the octant will be 0b00000111, which in decimal is 7, so any point with all-positive components will be put in the 7th octant. What I want to fix is where the points are put in our counters variable.

In the function OctantPopCount(), a point with all positive components is placed in the first octant, while mine puts them in the 7th.

What are some approaches I can take to my implementation to fix this issue?

For some more context, here's the output for the functions, there's only a small difference between them.

points = numpy.random.random_sample((2000000, 3)) - 0.5
c1 = testOctantPopCountFunction(points, OctantPopCount)
c2 = testOctantPopCountFunction(points, octant_count)
print(points)
print(c1)
print(c2)
~/Code/Python/03 $ python3 octant.py 
Testing : OctantPopCount()
Elapsed time: 0.592 seconds
Testing : octant_count()
Elapsed time: 0.103 seconds
[[-0.4797098  -0.21997829  0.09571134]
[-0.37825091 -0.19411628 -0.11625388]
[ 0.06619321 -0.08700517  0.13289992]
...
[-0.36272187  0.15922689  0.49523957]
[-0.28635198  0.26316548  0.38360014]
[-0.06738298 -0.49668077  0.25451539]]
[249036 250663 250512 250304 248926 249827 250275 250457]
[250304 249827 250663 250275 250512 248926 249036 250457]

Edit:
Here's what ended up working, thank you to Michael Butscher for pointing out that I had to swap my 0th and second index. Here's the updated code, along with the result:

@jit(nopython=True)
def octant_count(points):
    assert points.shape[1] == 3
    counters = numpy.zeros(8, dtype=numpy.uint32)

    for point in points:
        x_bit = int(point[0] <= 0) << 2
        y_bit = int(point[1] <= 0) << 1
        z_bit = int(point[2] <= 0) << 0

        octant = x_bit | y_bit | z_bit
        counters[octant] += 1

    return counters
Testing : OctantPopCount()
Elapsed time: 0.604 seconds
Testing : octant_count()
Elapsed time: 0.103 seconds
[[ 0.05981696 -0.08365013 -0.1045997 ]
[ 0.02443854  0.08834479  0.29052881]
[-0.21792648  0.43560819 -0.03026412]
...
[ 0.39456249  0.19419522  0.3100608 ]
[-0.07657673  0.32627312  0.00498049]
[ 0.01845389 -0.26335805 -0.28143975]]
[249589 249817 249841 250896 249975 250613 249641 249628]
[249589 249817 249841 250896 249975 250613 249641 249628]

答案1

得分: 3

只使用与原始代码中相同的比较方式。(还要确保 x 位是结果中的位。)

for point in points:
    x_bit = int(point[0] < 0) << 2
    y_bit = int(point[1] < 0) << 1
    z_bit = int(point[2] < 0) << 0

    octant = x_bit | y_bit | z_bit
    counters[octant] += 1
英文:

Just use the same comparisons as in the original. (Also, make sure the x bit is the high-order bit in the result.)

for point in points:
x_bit = int(point[0] &lt; 0) &lt;&lt; 2
y_bit = int(point[1] &lt; 0) &lt;&lt; 1
z_bit = int(point[2] &lt; 0) &lt;&lt; 0
octant = x_bit | y_bit | z_bit
counters[octant] += 1

huangapple
  • 本文由 发表于 2023年5月11日 02:45:44
  • 转载请务必保留本文链接:https://go.coder-hub.com/76221693.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定