Best way to store coordinates

[Kyle Wolfe]

What is the best way to store coordinates so that I can access them via some sort of an index? I'd like to mess with both x, y coordinates as well as x, y and z coordinates. It'd be great if the solution would allow for direct access to any coordinate based on any of those axis'

[Péter Szilágyi]

Hello,

  What do you mean by store? Persistent storage or internal data representation? And by index? Simply accessing the components, or some acceleration structure like in a database?

Cheers,

  Peter

PS: Maybe if you detail your use case a bit it would be simpler :)

On Sat, Nov 2, 2013 at 3:15 PM, Kyle Wolfe <kyle.a...@gmail.com> wrote:

What is the best way to store coordinates so that I can access them via some sort of an index? I'd like to mess with both x, y coordinates as well as x, y and z coordinates. It'd be great if the solution would allow for direct access to any coordinate based on any of those axis'

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Kyle Wolfe]

Sorry, store in memory. So within a slice? I'm used to PHP, so in PHP I'd only be able to point directly to one coordinate (the index or key) and I'd have to iterate over the rest.

[Péter Szilágyi]

Hi,

  Then yes, pretty much the same in Go too. A question might be how object or data oriented approach are you looking for? A very simple solution might be to have a coordinate structure:

type Coordinate struct {

  X, Y, Z float32

}

and then you could have a slice of these with indexed access to the elements and direct access to the components within: http://play.golang.org/p/47cE3Xlg0Z

Now if you store a loooot of coordinates, then you might omit the structure and store the components directly in slices, but do that only if you're confident you really need the performance over the complexity :)

Cheers,

  Peter

[Martin Schnabel]

you can use spatial data-structures for this task. like all the spatial
databases do:
http://en.wikipedia.org/wiki/Spatial_database#Spatial_index

i even found a R-tree package on godoc.org:
https://github.com/dhconnelly/rtreego

hope that helps

[luz...@gmail.com]

On Saturday, November 2, 2013 2:41:57 PM UTC+1, Péter Szilágyi wrote:

Now if you store a loooot of coordinates, then you might omit the structure and store the components directly in slices, but do that only if you're confident you really need the performance over the complexity :)

You're suggesting cargo cult programming.

a := []struct{ X, Y float32 }{{0, 1}, {2, 3}, {4, 5}}

x := a[2].X

and

a := []float32{0, 1, 2, 3, 4, 5}

x := a[4]

have exactly the same cost.

[Sebastien Binet]

do they?
I'd expect (w/o having looked at any assembly) that the former *may*
-depending on the compiler optimizations (or lack thereof)- copy the
whole struct{X,Y} before extracting the X data member.
ie:
// x := a[2].X
tmp := a[2]
x := tmp.X

(but it may as well just be my C++ injured brain...)

-s

[Péter Szilágyi]

Hi,

  I wasn't referring to base costs, but rather certain optimizations (I'm thinking along the SSE family) that may only be achieved using a flat layout over a structured one. The reason I have not explicitly specified the flat layout (i.e. mode of interweaving the coordinates) is because it would be highly use case dependent. Think along the lines of BLAS optimizations.

Cheers,

  Peter

--

[Marcus Holmes]

If you're storing something in every co-ordinate (like, say, game terrain), then you can do the coordinates with multi-dimensional arrays and just store the value. It's way too expensive if you have large swathes of empty co-ordinates though.

[luz...@gmail.com]

On Sunday, November 3, 2013 12:09:49 PM UTC+1, Sebastien Binet wrote:

do they?

Yes, both produce the same assembly language instructions.

I just confirmed it with "go tool 6g -S demo.go":

Struct slice access:

0028 MOVQ    a+-24(SP),BX

0029 CMPQ    AX,$2

0030 JHI     $1,33

0031 CALL    ,runtime.panicindex+0(SB)

0032 UNDEF   ,

0033 ADDQ    $16,BX

0034 MOVSS   (BX),X0

Flat slice access:

0028 MOVQ    a+-24(SP),BX

0029 CMPQ    AX,$4

0030 JHI     $1,33

0031 CALL    ,runtime.panicindex+0(SB)

0032 UNDEF   ,

0033 ADDQ    $16,BX

0034 MOVSS   (BX),X0

I'd expect (w/o having looked at any assembly) that the former *may*
-depending on the compiler optimizations (or lack thereof)- copy the
whole struct{X,Y} before extracting the X data member.
ie:
 // x := a[2].X
 tmp := a[2]
 x := tmp.X

(but it may as well just be my C++ injured brain...)

 I don't think that C++ compilers would do that.

[Kyle Wolfe]

Assuming I use a struct such as yours, and have a slice of many Coordinates, how would I return Coordinates that are between points? Ex. I want all Cooridnates with X between a and b, or Y between a and b, or multiple conditions.

[Péter Szilágyi]

If you want to query the points, then - as Martin pointed out - you'll need spatial data structures. As to which specific one, that will depend on your exact requirements and use case. You'll have to decide whether you want to modify the points or not, add/remove points or have a static geometry, etc. These questions will define whether a given structure is applicable or not for your specific scenario.

I'd suggest you familiarize yourself with the data structured linked by Martin. A few basic ones are the quadtree, octree and kd tree.

[Kevin Gillette]

The same semantic data, stored as a slice of []float32, or a []struct{x, y float32} or even a [][2]float32, will all have exactly the same bytes stored in memory. This means that the _potential_ for performance is identical. It's rather unfortunate when I see discussions about decomposing data just to work around lack of compiler optimizations in certain areas. Besides which, if you have a fixed data type, and "maximum power!!!" was already a concern, use of assembly would have been reasonable, and assembly is free to treat a []struct{x, y float32} as if it were a []float32 without conversion, or vice versa.