Thank you Sébastien, I may use some of it (Orientation, etc) in the project. Having a Point.ID is the straightforwardest way to go anyway.
On Monday, August 28, 2017 at 4:03:44 PM UTC+2, Sebastien Binet wrote: > > Valentin, > > On Mon, Aug 28, 2017 at 3:58 PM, Val <dele...@gmail.com <javascript:>> > wrote: > >> @Jakob sorry what I wrote was confusing, I meant : vertices have strong >> identity (same pointer), and triangles are just keys for the map so they >> need to be very stable. A triangle pointer wouldn't solve the case. When I >> encounter 3 vertex pointers A, B, C, then I need a "key" to determine if >> triangle ABC (or CAB, etc.) is already in the map. >> >> @Axel indeed I had not taken into account that the GC may "change the >> pointers, while preserving ==" so basically yes ordering pointers looks >> unreliable. >> >> @Kulti checking equality of triangles by checking combinations of vertex >> equality would be interesting but it would make the program really super >> slow: instead of a O(1) map lookup, each existence check would cost O(n) to >> traverse all the existing triangles, which is too slow because we have 1M+ >> triangles. This is because we can't use Triangle as a map key when equality >> is computed by a func instead of ==. >> >> @Egon those are nice workarounds, thanks. X,Y,Z are weak, they change >> all the time. >> >> I will try to minimize code clutter, minimize memory and cpu overhead, >> maximize safety and readability. So I think the best tradeoff so far is to >> add a field Vertex.ID, because I have the chance to do it, though it does >> clutter a little a fundamental data structure of the whole program. >> > > not sure if that would help but, in the context of a Delaunay > triangulation, we had to implement a few things that sound like related to > your issue: > > - https://godoc.org/go-hep.org/x/hep/fastjet/internal/predicates > - https://godoc.org/go-hep.org/x/hep/fastjet/internal/delaunay > > hth, > -s > > > Thank you all for insights! >> >> On Monday, August 28, 2017 at 3:20:39 PM UTC+2, Axel Wagner wrote: >>> >>> FTR, I don't think ordering by pointer (no matter whether using unsafe >>> or not) is reliable and safe. The GC is free to move data around at any >>> point, including during your sort. >>> I don't think there are a lot of ways around that. You could basically >>> build your own allocator and add a way for it to return a reliable id. e.g. >>> it allocates a []Vertex and the id is the index of the vertex in that >>> slice. You can calculate it using unsafe by (roughly. No guarantees here. >>> Unsafe is subtle) >>> >>> func ID(v *Vertex) int { >>> i := int(uintptr(unsafe.Pointer(v))) - >>> int(uintptr(unsafe.Pointer(&Vertex[0]))) >>> if i < 0 || i > len(pool) { >>> panic("not pool-allocated") >>> } >>> return i >>> } >>> >>> (not that you need to take care to do both conversions in the same >>> expression, to satisfy the unsafe.Pointer >>> <https://godoc.org/unsafe#Pointer> rules). >>> >>> Apart from that, Egon gave a couple of good suggestions :) >>> >>> On Mon, Aug 28, 2017 at 3:02 PM, Jakob Borg <ja...@kastelo.net> wrote: >>> >>>> In that case, maybe use *Triangle pointers instead of Triangle values, >>>> and let that address be the identity for map purposes? Then the Vertex >>>> order etc doesn't matter any more. >>>> >>>> //jb >>>> >>>> > On 28 Aug 2017, at 14:03, Val <dele...@gmail.com> wrote: >>>> > >>>> > That's actually a clever idea, I had not thought of that when >>>> dismissing the vertex struct inspection. Thanks! >>>> > >>>> > But it turns out that X,Y,Z will change often during my program >>>> execution: vertices move, but their identity (and the triangles identity) >>>> must be strongly preserved. >>>> > >>>> > On Monday, August 28, 2017 at 1:42:35 PM UTC+2, Jakob Borg wrote: >>>> > On 28 Aug 2017, at 13:13, Val <dele...@gmail.com> wrote: >>>> > > >>>> > > To achieve this, I consider normalizing the triplet so that all >>>> keys of the map verify >>>> > > A < B < C >>>> > > for some arbitrary definition of < . This ensures that I can >>>> detect any Triangle already present as key in the map, regardless the >>>> order >>>> of its Vertex pointers. >>>> > >>>> > Can't you sort the Vertex slice by their X,Y,Z position? (You're then >>>> not relying on the coordinates for identity, only for order. This breaks >>>> for triangles that are actually lines or points, which may or may not be >>>> an >>>> issue and can be handled separately...) >>>> > >>>> > //jb >>>> > >>>> > -- >>>> > 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/d/optout. >>>> >>>> -- >>>> 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/d/optout. >>>> >>> >>> -- >> 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 <javascript:>. >> For more options, visit https://groups.google.com/d/optout. >> > > -- 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+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
