00:00:00  * ircretaryquit (Remote host closed the connection)
00:00:09  * ircretaryjoined
00:01:05  * tilgoviquit (Ping timeout: 272 seconds)
00:10:12  * contrahaxquit (Quit: Sleeping)
00:12:31  * ednapiranhaquit (Quit: Leaving...)
00:13:25  * contrahaxjoined
00:23:37  * tilgovijoined
00:42:22  * collypopsquit (Quit: Zzz)
00:44:20  * rockbot__quit (Remote host closed the connection)
00:45:40  * collypopsjoined
00:46:41  * h0kejoined
00:48:17  * collypopsquit (Remote host closed the connection)
00:49:02  * quijotejoined
00:49:02  * collypopsjoined
00:51:17  * h0kequit (Ping timeout: 240 seconds)
00:53:34  * quijotequit (Ping timeout: 245 seconds)
00:57:00  * contrahaxquit (Quit: Sleeping)
00:59:44  * phatedquit (Remote host closed the connection)
01:01:28  * rockbot__joined
01:22:19  * rockbot__quit (Remote host closed the connection)
01:25:12  * stagasquit (Ping timeout: 250 seconds)
01:28:30  * warbrettquit (Remote host closed the connection)
01:37:36  * rockbot__joined
01:39:07  * anandthakkerquit (Quit: anandthakker)
01:42:19  * rockbot__quit (Remote host closed the connection)
01:50:20  * quijotejoined
01:55:09  * quijotequit (Ping timeout: 260 seconds)
02:01:05  * thealphanerdquit (Quit: thealphanerd)
02:06:04  * phatedjoined
02:12:56  <substack>e/win 28
02:15:42  * zvquit (Ping timeout: 245 seconds)
02:16:13  * warbrettjoined
02:24:11  * warbrettquit (Remote host closed the connection)
02:24:59  * phatedquit (Remote host closed the connection)
02:33:24  * contrahaxjoined
02:41:40  * jxson_joined
02:44:22  * pfrazequit (Quit: Leaving)
02:44:46  * phatedjoined
02:44:52  * jxsonquit (Ping timeout: 258 seconds)
02:45:32  * thealphanerdjoined
02:46:24  * jxson_quit (Ping timeout: 258 seconds)
02:49:18  * h0kejoined
02:50:08  * domanicjoined
02:50:50  * quijotejoined
02:52:59  * thealphanerdquit (Quit: thealphanerd)
02:54:03  * h0kequit (Ping timeout: 265 seconds)
02:55:49  * quijotequit (Ping timeout: 260 seconds)
03:04:52  * domanicquit (Ping timeout: 250 seconds)
03:12:20  * Mso150joined
03:30:42  * Mso150quit (Ping timeout: 245 seconds)
03:34:03  * Mso150joined
03:34:46  * warbrettjoined
03:39:24  * warbrettquit (Ping timeout: 264 seconds)
03:40:56  * contrahaxquit
03:42:20  * contrahaxjoined
03:46:41  * therealkoopaquit (Remote host closed the connection)
03:51:36  * quijotejoined
03:51:53  * pfrazejoined
03:56:17  * Mso150quit (Ping timeout: 264 seconds)
03:56:22  * quijotequit (Ping timeout: 255 seconds)
03:58:39  * michaelrhodesjoined
03:58:46  * sindresorhus_changed nick to sindresorhus
03:59:16  * sindresorhuschanged nick to Guest31951
04:00:13  * therealkoopajoined
04:04:28  * warbrettjoined
04:05:33  * phatedquit (Remote host closed the connection)
04:05:56  * anvakajoined
04:07:43  * warbrettquit (Remote host closed the connection)
04:30:22  * pfrazequit (Quit: Leaving)
04:34:36  * ellellquit (Ping timeout: 244 seconds)
04:34:55  * ellelljoined
04:35:02  * karissaquit (Ping timeout: 244 seconds)
04:35:02  * mafintoshquit (Ping timeout: 244 seconds)
04:35:02  * tobiequit (Ping timeout: 244 seconds)
04:35:26  * karissajoined
04:35:33  * hackygoluckyquit (Ping timeout: 244 seconds)
04:36:01  * therealkoopaquit (Remote host closed the connection)
04:36:05  * wa7sonquit (Ping timeout: 244 seconds)
04:38:06  * wa7sonjoined
04:38:14  * hackygolucky__joined
04:39:11  * mafintoshjoined
04:39:22  * tobiejoined
04:43:01  * rockbot__joined
04:44:56  * rockbot__quit (Read error: Connection reset by peer)
04:44:58  * rockbo___joined
04:52:26  * quijotejoined
04:53:32  * h0kejoined
04:56:57  * quijotequit (Ping timeout: 245 seconds)
05:01:49  * h0kequit (Ping timeout: 240 seconds)
05:05:47  * therealkoopajoined
05:09:58  * h0kejoined
05:10:50  * therealkoopaquit (Ping timeout: 265 seconds)
05:16:07  * phatedjoined
05:18:14  * warbrettjoined
05:21:04  * phatedquit (Ping timeout: 245 seconds)
05:22:17  * warbrettquit (Ping timeout: 240 seconds)
05:24:00  * knownasilyaquit (Quit: Connection closed for inactivity)
05:30:50  * therealkoopajoined
05:34:56  * rockbo___quit (Remote host closed the connection)
05:35:14  * therealkoopaquit (Ping timeout: 250 seconds)
05:40:37  * anvakaquit (Remote host closed the connection)
05:41:11  * anvakajoined
05:45:25  * anvakaquit (Ping timeout: 258 seconds)
05:48:55  * thealphanerdjoined
05:53:09  * quijotejoined
05:57:49  * quijotequit (Ping timeout: 260 seconds)
06:05:08  * YsenGrimmquit (Ping timeout: 250 seconds)
06:06:33  * therealkoopajoined
06:06:53  * YsenGrimmjoined
06:11:32  * therealkoopaquit (Ping timeout: 256 seconds)
06:14:57  * therealkoopajoined
06:15:51  * tilgoviquit (Remote host closed the connection)
06:19:49  * therealkoopaquit (Ping timeout: 272 seconds)
06:22:27  * phatedjoined
06:38:21  * h0kequit (Remote host closed the connection)
06:40:29  * therealkoopajoined
06:41:22  * h0kejoined
06:45:13  * therealkoopaquit (Ping timeout: 258 seconds)
06:46:25  * h0kequit (Ping timeout: 272 seconds)
06:53:56  * quijotejoined
06:58:15  * DamonOehlmanquit (Ping timeout: 258 seconds)
06:58:37  * quijotequit (Ping timeout: 265 seconds)
07:04:23  * Maciek416quit (Remote host closed the connection)
07:06:37  * therealkoopajoined
07:13:18  * therealkoopaquit (Ping timeout: 256 seconds)
07:19:31  * jxsonjoined
07:29:03  * peutetrejoined
07:33:09  * nickleeflyjoined
07:33:25  * DamonOehlmanjoined
07:41:06  * phatedquit (Remote host closed the connection)
07:43:56  * DamonOehlmanquit (Ping timeout: 250 seconds)
07:46:27  * contrahaxchanged nick to _contrahax
07:51:45  * djcoinjoined
07:54:41  * quijotejoined
07:59:48  * quijotequit (Ping timeout: 264 seconds)
08:06:36  * therealkoopajoined
08:08:07  * robertkowalskiquit (Ping timeout: 272 seconds)
08:08:16  * robertkowalskijoined
08:09:35  * ITProjoined
08:10:33  * h0kejoined
08:11:17  * therealkoopaquit (Ping timeout: 264 seconds)
08:11:49  * thealphanerdquit (Quit: thealphanerd)
08:14:37  * h0kequit (Ping timeout: 240 seconds)
08:18:21  * quijotejoined
08:20:49  * therealkoopajoined
08:23:55  * jxsonquit (Remote host closed the connection)
08:25:17  * therealkoopaquit (Ping timeout: 245 seconds)
08:39:41  * therealkoopajoined
08:44:24  * therealkoopaquit (Ping timeout: 245 seconds)
08:55:19  * anandthakkerjoined
08:58:49  * aulaitquit (Excess Flood)
09:02:01  * therealkoopajoined
09:10:15  * aulaitjoined
09:10:37  * therealkoopaquit (Ping timeout: 240 seconds)
09:10:39  * Mso150joined
09:13:55  * h0kejoined
09:19:05  * h0kequit (Ping timeout: 264 seconds)
09:20:04  * michaelrhodesquit (Quit: Leaving.)
09:23:58  * quijotequit (Ping timeout: 255 seconds)
09:29:07  * stagasjoined
09:45:20  * thealphanerdjoined
10:20:32  <substack>mikolalysenko_: do you have any ideas about spatial partitioning schemes that minimize seeks to non-contiguous data?
10:21:09  <substack>in my case thinking up something that will work well with bittorrent for delivery
10:21:19  * quijotejoined
10:25:41  * quijotequit (Ping timeout: 260 seconds)
10:29:33  * therealkoopajoined
10:35:09  * therealkoopaquit (Ping timeout: 244 seconds)
10:35:36  <anandthakker>substack: saw your tweet… k-d does seem like a reasonable bet for this. do you have reservations?
10:37:43  <substack>anandthakker: it looks like I would have to do a log scan of x and a log scan of y
10:37:49  <substack>and the locality for that is probably not great
10:38:13  <substack>I was looking at hilbert and z-order curves for this too
10:39:14  <substack>I could also just divide features into an ordinary grid with a hash for coarse lookups
10:39:17  <substack>or a quadtree
10:39:43  <substack>but quadtrees didn't seem to index very well
10:44:28  <substack>but I guess even with a kd tree that is only a log number of extra updates
10:44:38  <anandthakker>huh, hilbert and z-order curves would be a fascinating approach to explore… although somehow my instinct is that it’s gonna be hard to beat the kd tree
10:44:44  <substack>and I could even hash the topmost nodes
10:45:07  <anandthakker>yah
10:45:34  <substack>ok I'll give this a spin
10:45:45  <substack>at the very least I'll have a sandbox up soonish to try different indexing schemes
10:45:45  <anandthakker>just curious, what kind of data is this?
10:45:50  <substack>maps
10:46:07  <substack>I want to stream open street maps data directly from bittorrent on-demand
10:46:19  <substack>using torrent-stream and later webtorrent
10:46:28  <anandthakker>oh, that is excellent
10:46:31  <substack>without needing to fetch the entire file
10:46:35  <anandthakker>yeah
10:46:37  <substack>so you can make ad-hoc extracts really easily
10:46:55  * quijotejoined
10:46:56  <substack>right now the data isn't indexed at all
10:47:00  <anandthakker>it would be amazing to use that for landsat data too
10:47:07  <substack>but it is up on bittorrent as xml and protobuf
10:47:23  <substack>yep! once the basic approach works you can layer whatever kind of data you want overtop
10:49:20  <substack>I also remember mikola did something cool with a voronoi-looking thing for fast (x,y) lookups
10:49:27  <substack>but I can't seem to find it
10:50:17  <anandthakker>hmm
10:50:50  <anandthakker>that’s interesting, but isn’t the map data in tiles?
10:51:01  <substack>the map data in open street maps is all vectors
10:51:13  <anandthakker>ah
10:51:22  <substack>I want to keep it as vectors because that will take up much less space and network
10:51:58  <anandthakker>yeah. not to mention it’s probably better to consume anyway
10:51:59  <substack>boundary cases make it a little trickier but I can use polygon clipping if the shapes are too large
10:52:12  <substack>or just use different indexes for differently-sized shapes
10:52:32  <substack>tmpvar already whipped up a pretty good clipping lib
10:52:40  <anandthakker>hmmm. i’m starting to be intrigued byt he voronoi idea...
10:52:49  <anandthakker>voronoi-tree?
10:54:00  <anandthakker>oh nice — i actually could use that polygon clipping thing for some geometry stuff i’m working on
10:57:44  <anandthakker>substack: actually wouldn’t the k-d/quad tree idea handle different sizes naturally?
10:57:46  <substack>https://www.npmjs.com/package/polygon.clip
10:58:42  <substack>anandthakker: I don't think it would, since kd trees are meant to handle points not bounding volumes or polygons
10:59:15  <substack>but one thing I could do is subdivide all line segments greater than a threshold distance
11:00:09  <substack>then I would only need to cast out that threshold distance when looking at a region to ensure that I wouldn't get lines intersecting the viewport
11:04:24  <anandthakker>the nodes of the tree are points, but they determine 2 regions (or 4 for quadtree), right? seems like that means it’s straightforward to generalize kd to index 2-d items by the smallest containing region
11:05:21  <anandthakker>oh unless you’re still trying to avoid the log lookup
11:08:21  <substack>that's true if I already have the log lookup
11:08:30  <substack>that would be a good place to do the checks for larger geometries
11:08:43  <substack>that's sort of what rtrees do
11:08:56  <substack>but the balancing on those seems quite complicated plus the additional space
11:13:17  * quijotequit (Ping timeout: 260 seconds)
11:14:38  <anandthakker>(ARGH: from your link to tmpvar, i found his vec2, line2, circle2… having just wasted time making my own (crappy) ones. i wish finding good packages was a bit easier.)
11:15:04  <anandthakker>(but anyway thanks ;), it’ll be nice to swap those in.)
11:16:16  <substack>vec2 isn't a great idea see https://github.com/tmpvar/polygon.clip.js/issues/7
11:16:47  * h0kejoined
11:17:07  <substack>much better to keep the data structures as native arrays or typed arrays
11:18:03  <anandthakker>oh, interesting. cool.
11:21:02  <anandthakker>hmm, alas the line and circle use vec2, also
11:21:57  * h0kequit (Ping timeout: 245 seconds)
11:24:45  <substack>I wonder if there is a better coordinate system I can translate wgs 84 into
11:24:54  <substack>to handle the distortion at the poles better
11:26:42  <krl>substack: http://oliverstickers.com/earth-octahedron.html
11:26:44  <krl>:)
11:27:09  * therealkoopajoined
11:27:11  * stagasquit (Quit: Bye)
11:29:18  <anandthakker>lol
11:32:18  * Mso150quit (Read error: Connection reset by peer)
11:33:24  * therealkoopaquit (Ping timeout: 256 seconds)
11:38:27  * thealphanerdquit (Quit: thealphanerd)
11:39:14  * quijotejoined
11:43:34  * quijotequit (Ping timeout: 250 seconds)
12:09:06  * hemanthjoined
12:11:13  * oldskirt_joined
12:14:27  * oldskirtquit (Ping timeout: 260 seconds)
12:15:24  * ins0mniaquit (Read error: Connection reset by peer)
12:15:25  * owenb____quit (Ping timeout: 260 seconds)
12:16:18  * jdenquit (Ping timeout: 260 seconds)
12:16:18  * ELLIOTTCABLEquit (Ping timeout: 260 seconds)
12:16:51  * trevnorrisquit (Ping timeout: 260 seconds)
12:16:51  * Guest31951quit (Ping timeout: 260 seconds)
12:18:11  * sindresorhusjoined
12:18:22  * owenb____joined
12:18:38  * ELLIOTTCABLEjoined
12:18:58  * trevnorrisjoined
12:19:56  * karissa_joined
12:20:06  * jdenjoined
12:20:11  * karissaquit (Ping timeout: 260 seconds)
12:20:11  * andreypopp_quit (Ping timeout: 260 seconds)
12:20:11  * Raynosquit (Ping timeout: 260 seconds)
12:20:16  * karissa_changed nick to karissa
12:20:30  * jbenetquit (Ping timeout: 260 seconds)
12:20:31  * addisonjquit (Ping timeout: 260 seconds)
12:20:31  * insertcoffeequit (Ping timeout: 260 seconds)
12:20:51  * jbenetjoined
12:20:56  * therealkoopajoined
12:21:03  * tanepiper___quit (Ping timeout: 260 seconds)
12:21:18  * insertcoffeejoined
12:21:18  * Raynosjoined
12:21:43  * andreypopp_joined
12:21:53  * addisonjjoined
12:22:14  * nrwquit (Ping timeout: 260 seconds)
12:22:21  * rvaggquit (Ping timeout: 260 seconds)
12:23:46  * nrwjoined
12:23:59  * gorhgorh_joined
12:25:35  * rvaggjoined
12:25:55  * tanepiper___joined
12:29:27  * jaz303_joined
12:31:15  * gorhgorhquit (*.net *.split)
12:31:15  * gausbyquit (*.net *.split)
12:31:15  * jaz303quit (*.net *.split)
12:40:31  * nickleeflyquit (Quit: Connection closed for inactivity)
12:48:54  * gausbyjoined
12:49:19  * therealkoopaquit (Ping timeout: 272 seconds)
12:50:49  * therealkoopajoined
12:54:25  * hemanthquit (Quit: This computer has gone to sleep)
12:55:19  * hemanthjoined
13:11:03  * gorhgorh_quit (Quit: leaving)
13:11:28  * gorhgorhjoined
13:25:42  * toddself_zzchanged nick to toddself
13:25:50  * toddselfquit
13:50:24  * knownasilyajoined
14:21:45  * therealk_joined
14:22:23  * hemanth_joined
14:22:28  * tmpvar___joined
14:22:48  * toddselfjoined
14:24:21  <mikolalysenko_>substack: you can use a range tree
14:24:47  <mikolalysenko_>substack: or turn whatever data structure you like into a b-tree by expanding it out a couple of levels
14:30:13  * hemanthquit (*.net *.split)
14:30:13  * therealkoopaquit (*.net *.split)
14:30:13  * tmpvar__quit (*.net *.split)
14:30:22  * tmpvar___changed nick to tmpvar__
14:30:58  * hemanth_quit (Quit: This computer has gone to sleep)
14:31:56  <mikolalysenko_>so, I'd probably use either an r-tree or a range tree
14:38:08  <mikolalysenko_>re coordinates on a sphere, I think using 3d coordinates is a better solution
14:38:33  <mikolalysenko_>at least for nearest neighbor / bounding circle queries
14:39:14  <mikolalysenko_>you can reformulate the problem of locating all points in a great circle as intersecting the points with a halfspace
14:42:11  <krl>mikolalysenko_: interesting!
14:42:31  <krl>i've been thinking about doing basic geolocation stuff, and 3d coordinates sound like a very interesting approach
14:42:47  <mikolalysenko_>what sort of queries are you interested in doing?
14:42:59  <mikolalysenko_>like closest point, knn, circle range?
14:43:05  <krl>circle range
14:43:10  <krl>+ closest
14:43:13  <mikolalysenko_>ah, then here is what you do
14:43:26  <mikolalysenko_>take the points on the earth, map them to the spherical 3d coordinate
14:43:30  <mikolalysenko_>then compute the convex hull
14:44:03  <mikolalysenko_>then you can answer each of these queries in log(n) time overhead (+ number of returned items for halfspace) by reducing them to a linear programming query
14:44:08  <krl>another restraint: starting with zero points, and having low insertion cost
14:44:10  <mikolalysenko_>which you can solve using dobkin-kirkpatrick
14:44:20  <mikolalysenko_>I wouldn't bother doing incremental insertion
14:44:25  <mikolalysenko_>just do it in a batch
14:44:30  <krl>not possible in this case
14:44:37  <mikolalysenko_>why not?
14:44:51  <krl>because it's for people registering their position
14:44:58  <krl>and i want to start small, and be able to scale
14:45:04  <mikolalysenko_>so you can use techniques like log structured merging
14:45:19  <mikolalysenko_>where you build a pool of data structures, then merge them together when they get filled up
14:45:30  * hemanthjoined
14:45:40  <mikolalysenko_>I have a video about this, one second
14:45:42  <krl>i had been thinking of starting with a quadtree tetrahedon, and do subdivisions
14:45:57  <substack>cool thanks!
14:46:07  <mikolalysenko_>first part of this should cover it: https://www.youtube.com/watch?v=QUQ6FT8gTMU&list=PLESnaHRvLM-72xIXf8dL2EOqN8UgAZMj7&index=18
14:46:28  <krl>with 3d-coordinates, an octtree might work as well
14:46:31  <substack>have been reading papers and poking at osm extract scripts all night
14:46:53  <krl>or just bsp
14:47:02  <mikolalysenko_>well, bsp might not be very fast
14:47:11  <mikolalysenko_>though you can speed up location using fingering
14:47:18  <mikolalysenko_>also quadtrees are not great for point location
14:47:28  <mikolalysenko_>you need to at least apply compression to them
14:47:42  <mikolalysenko_>are you trying to locate points in regions, or locate closest points to query points?
14:47:46  <mikolalysenko_>these are different problems
14:47:59  <krl>1. locate the point closest to point A
14:48:15  <krl>2. locate the 10 points closest to point A
14:48:22  <krl>i guess that's what i need
14:48:26  <mikolalysenko_>ok
14:48:46  <mikolalysenko_>if you want to get something working asap, you can try this library: https://github.com/mikolalysenko/static-kdtree
14:48:54  <mikolalysenko_>it is static, but that shouldn't stop you
14:49:03  <mikolalysenko_>what you do is you merge the data structures together
14:49:29  <mikolalysenko_>basically you have a list of trees, run the query on those trees independently and then merge the results
14:49:39  <mikolalysenko_>if you get too many trees, then you combine them
14:50:17  <krl>i'm thinking of building this on ethereum
14:50:32  <krl>so it has to be really cheap, and can't really have expensive edge cases
14:50:48  <mikolalysenko_>so I would not bother building the index and storing that in ethereum
14:51:05  <mikolalysenko_>if your data set is small enough brute force might be ok
14:51:43  <mikolalysenko_>however I don't have a good mental model of what is expensive in ethereum and what is cheap, since I haven't studied it carefully yet
14:52:05  <mikolalysenko_>if it is like a normal distributed system, then I would say just build the index separately
14:52:13  <mikolalysenko_>or build multiple indices and merge results
14:52:35  <mikolalysenko_>but I think it is a little weird in that computations are billed by the operation or something, which is strange to me
14:52:43  <krl>the idea relies on having all positions stored in a datastructure on ethereum
14:52:57  <krl>it's a strange new world for suer
14:52:58  <krl>sure
14:53:20  <mikolalysenko_>can you perform random access in this data structure cheaply?
14:53:34  <mikolalysenko_>or are accesses performed in bulk
14:53:39  <krl>it's basically a key-value store
14:53:47  <mikolalysenko_>ok
14:53:48  <krl>for each program running in the net
14:54:41  <mikolalysenko_>are programs billed by wall-clock time, or by the number of cycles in some ethereum vm?
14:54:59  <mikolalysenko_>so if I access data in ethereum which is local, is that cheaper than accessing data on a remote machine?
14:56:36  <krl>cycles
14:56:46  <krl>also, no remote access possible
14:57:26  <mikolalysenko_>is the key value store mutable or immutable?
14:58:03  <krl>mutable from the view of the current transaction
14:58:27  <mikolalysenko_>ok, and are these points ever deleted, or are they only inserted?
14:58:54  <krl>they could be deleted
14:59:04  <krl>but it's not a hard requirement
14:59:13  <krl>they probably should though
14:59:21  <krl>no use having lots of bad points sticking around
14:59:35  <krl>also, you get credits back by freeing up space
15:01:19  <mikolalysenko_>interesting
15:01:30  <mikolalysenko_>you could maybe use some sort of dynamic convex hull algorithm here
15:01:38  <mikolalysenko_>which would probably work, but it might be complicated
15:02:00  <mikolalysenko_>though I am now wondering if the fact that all points live on a sphere can be used to simplify it a bit
15:02:18  <krl>mikolalysenko_: thanks for the github link btw, saved it
15:02:46  <mikolalysenko_>a compressed octree could also work
15:03:24  <mikolalysenko_>though that is more useful for approximate nearest neighbor queries
15:03:30  <mikolalysenko_>but it might be good enough for this purpose
15:03:42  <mikolalysenko_>you could try this: https://www.ics.uci.edu/~eppstein/pubs/EppGooSun-SoCG-05.pdf
15:03:50  <krl>compressed means?
15:04:27  * toddselfchanged nick to toddself_zz
15:05:07  <krl>ah, it says in the pdf
15:05:07  <mikolalysenko_>one problem with quadtrees is that they get to big
15:05:09  <krl>thx
15:05:27  <mikolalysenko_>specifically the height of a quadtree is about log(spread)
15:05:39  <mikolalysenko_>where spread is the ratio of the distance between the farthest pair of points and the closest pair
15:05:56  <mikolalysenko_>also log(spread) > log(n)
15:06:19  <mikolalysenko_>which means that stuff which takes log(spread) time is going to be slow
15:06:27  <mikolalysenko_>in the worst case, log(spread) can be infinite
15:06:49  <mikolalysenko_>best case it hits about log(n) (for uniformly distributed points)
15:08:22  <mikolalysenko_>compressed quadtrees solve this problem by removing empty nodes in the tree
15:08:31  <mikolalysenko_>kind of like how patricia/radix tries compress tries down
15:08:46  <krl>i see
15:08:48  <mikolalysenko_>you can basically think of a compressed quadtree as something like a compressed trie encoding of a quadtree
15:09:00  <krl>yes i was worried that i would run into splits that would just create loads of empty nodes
15:09:09  <krl>with lots of points in one place
15:09:15  <mikolalysenko_>exactly
15:09:18  * peutetrequit (Ping timeout: 256 seconds)
15:09:39  <mikolalysenko_>so one perspective on quadtrees is that they are actually tries on z-order interleavings of the bits of the points
15:09:55  <mikolalysenko_>here is a wiki page with pictures: https://en.wikipedia.org/wiki/Z-order_curve
15:10:14  <mikolalysenko_>compressed quadtrees then are the same as crit-bit tries on these z-order interleavings
15:11:05  * toddself_zzchanged nick to toddself
15:17:02  <krl>i think i heard of like 2 new trees in this conversation :D
15:17:42  * pfrazejoined
15:18:24  <mikolalysenko_>there are other ways to solve this though, but they might not work so well in ethereum
15:18:50  <krl>at this time i just want something simple that actually scales reasonably
15:19:09  <mikolalysenko_>compressed octree might be the easiest solution
15:19:35  <mikolalysenko_>but the best solution would be a dynamic convex hull + point location structure
15:20:23  <mikolalysenko_>another possibility is just binning the points
15:20:53  <mikolalysenko_>make a grid of all points on the surface of the earth and then just search in some adjacent bins
15:21:07  <mikolalysenko_>getting the bin size right is the trick though
15:22:11  <mikolalysenko_>can you use c++ in ethereum?
15:22:21  <mikolalysenko_>if so this data structure would work: http://doc.cgal.org/latest/Convex_hull_3/#Convex_hull_3Dynamic
15:23:12  <mikolalysenko_>though generally making things dynamic if you only care about queries is a lot of extra headache and maybe not worth it
15:23:35  <mikolalysenko_>having fast/small static data structures and merging results tends to perform better in practice
15:24:54  * tmpvar__quit (Changing host)
15:24:54  * tmpvar__joined
15:27:47  <krl>mikolalysenko_: no c++
15:27:57  <krl>they use custom bytecode
15:28:23  <krl>and you really need domain specific languages with zero overhead
15:28:39  <krl>but "all points" on the surface of earth?
15:28:52  <krl>that's an infinite amount afaik ;)
15:29:23  <mikolalysenko_>well, given the adversarial programming environment it might be better to just do something really simple and get on with it
15:29:40  <mikolalysenko_>I think that compressed octree is a good bet
15:30:45  <mikolalysenko_>it should give acceptable performance and is relatively easy to implement in either static/dynamic forms
15:31:01  <krl>i'm starting to think so too
15:31:26  <krl>never thought about using 3d coordinates, thanks for the idea!
15:31:38  <krl>i'll look at the skip structure too
15:31:48  <krl>not sure if it's needed
15:32:09  <mikolalysenko_>skip is only needed if you want dynamic
15:35:14  <krl>dynamic in what sense?
15:37:04  <mikolalysenko_>dynamic means point set changes (that is you want to insert/delete points)
15:39:04  <krl>yes i do
15:39:09  <krl>but you don't need skips for that
15:40:08  <krl>i just realized noone implemented sin/cos/tan in EVM yet :D
15:41:22  <mikolalysenko_>ah, you are right
15:41:39  <mikolalysenko_>just spaced out a bit, trying to do 2 things at once
15:41:55  <krl>actually, that's not a problem at all
15:42:03  <krl>that does not need to happen at the evm level
15:42:12  <krl>you can just submit your points as 3d coords
15:42:29  <krl>and check the distance to origo, not to allow points in the sky or below ground
15:42:58  <krl>*phew* ;)
15:45:19  <mikolalysenko_>getting the distance right can be a bit tricky though
15:46:07  <mikolalysenko_>since it needs a square root and a divide
15:46:22  <mikolalysenko_>though I am now wondering if you can side step this using homogeneous coordinates
15:46:26  * CoderPuppyjoined
15:46:43  <mikolalysenko_>alternatively, you could just use fp and round it
15:47:43  * Maciek416joined
15:48:24  * cpupquit (Ping timeout: 256 seconds)
15:50:08  <krl>fp?
15:50:21  <krl>no need for rounding, word size is 256 bit :)
15:51:36  <mikolalysenko_>you still need to round since square roots are irrational
15:51:48  <mikolalysenko_>or you can use galois extensions, but it gets messy
15:55:54  <krl>oh, square root might be the problem yes
15:57:08  <mikolalysenko_>you can use oriented projective geometry, but not sure how this would work with octrees
16:01:18  * pfrazequit (Remote host closed the connection)
16:04:40  * pfrazejoined
16:05:05  <krl>i just need to implement square root in bytecode, should be a fun challenge
16:08:43  * ednapiranhajoined
16:10:45  * Maciek416quit (Remote host closed the connection)
16:11:12  * Maciek416joined
16:15:45  * hemanthquit (Quit: This computer has gone to sleep)
16:21:58  * peutetrejoined
16:30:22  * ins0mniajoined
16:40:21  * thealphanerdjoined
17:01:49  * thealphanerdquit (Quit: thealphanerd)
17:02:39  * warbrettjoined
17:03:15  * thealphanerdjoined
17:04:00  * thealphanerdquit (Client Quit)
17:04:36  * pfrazequit (Remote host closed the connection)
17:06:28  * warbrettquit (Remote host closed the connection)
17:07:26  * rockbot__joined
17:11:36  * pfrazejoined
17:18:36  * rockbot__quit (Remote host closed the connection)
17:20:36  * rockbot__joined
17:25:14  * rockbot__quit (Ping timeout: 245 seconds)
17:26:21  * h0kejoined
17:31:05  * h0kequit (Ping timeout: 264 seconds)
17:37:42  * thealphanerdjoined
17:38:27  * peutetrequit (Quit: peutetre)
17:40:06  * ITProquit (Read error: Connection reset by peer)
17:40:28  * ITProjoined
17:40:34  * quijotejoined
17:40:52  * ITProchanged nick to Guest58797
17:43:02  * phatedjoined
17:44:13  * toddselfchanged nick to toddself_zz
17:45:37  * warbrettjoined
17:46:00  * rockbot__joined
17:49:32  * phatedquit (Ping timeout: 258 seconds)
18:08:29  * shamajoined
18:16:16  * phatedjoined
18:16:27  * tilgovijoined
18:20:26  * jxsonjoined
18:26:16  * djcoinquit (Quit: WeeChat 1.0.1)
18:31:53  <mikolalysenko_>substack: you could speed this up a lot using a binary search
18:31:55  <mikolalysenko_>https://github.com/substack/point-at-length
18:32:04  <mikolalysenko_>here is what you do in 2 steps:
18:32:17  <mikolalysenko_>1. compute the length along the curve for each vertex, store this in a table
18:32:39  <mikolalysenko_>2. to get the segment containing the point at length 2, binary search on this table to find the segment containing the point
18:32:55  <mikolalysenko_>then you just apply interpolation/whatever you like to get the position of the point
18:33:25  <mikolalysenko_>using bisection for the last bit
18:33:33  <mikolalysenko_>(if it is a polynomial curve)
18:34:06  * insertcoffeequit (Ping timeout: 244 seconds)
18:36:04  <mikolalysenko_>for more detail re splines/polynomials: http://homepage.cs.uiowa.edu/~kearney/pubs/CurvesAndSurfacesArcLength.pdf (though you don't need this for straight line/circular arcs)
18:44:10  * Mso150joined
18:45:44  * quijotequit (Ping timeout: 265 seconds)
18:46:16  * toddself_zzchanged nick to toddself
19:15:52  * phatedquit (Remote host closed the connection)
19:16:27  * phatedjoined
19:16:46  * jxsonquit (Read error: Connection reset by peer)
19:17:35  * jxsonjoined
19:18:40  * _contrahaxchanged nick to contrahax
19:21:01  * phatedquit (Ping timeout: 265 seconds)
19:22:34  * oldskirt_changed nick to oldskirt
19:27:41  * quijotejoined
19:28:48  * h0kejoined
19:30:46  * peutetrejoined
19:32:16  * quijotequit (Ping timeout: 258 seconds)
19:33:43  * h0kequit (Ping timeout: 255 seconds)
19:33:54  * jcrugzz_changed nick to jcrugzz
19:35:33  * contrahaxchanged nick to _contrahax
19:37:28  * phatedjoined
19:43:51  * ednapira_joined
19:43:59  * ednapiranhaquit (Read error: Connection reset by peer)
19:44:47  * _contrahaxquit (Quit: Sleeping)
19:54:28  * Maciek416quit (Remote host closed the connection)
19:55:05  * Maciek416joined
19:56:53  * pfalleno1quit (Remote host closed the connection)
19:57:08  * pfallenopjoined
19:58:29  * domanicjoined
20:21:24  * ednapira_changed nick to ednapiranha
20:22:29  * toddselfchanged nick to toddself_zz
20:28:21  * quijotejoined
20:30:44  * h0kejoined
20:32:04  * soldairjoined
20:32:56  * quijotequit (Ping timeout: 244 seconds)
20:34:22  * toddself_zzchanged nick to toddself
20:35:22  * h0kequit (Ping timeout: 255 seconds)
20:41:09  * quijotejoined
20:41:27  * rockbot__quit (Remote host closed the connection)
20:46:05  * quijotequit (Ping timeout: 264 seconds)
21:05:54  * Mso150_yjoined
21:06:25  * Mso150quit (Ping timeout: 264 seconds)
21:10:09  * peutetrequit (Quit: peutetre)
21:11:12  * Mso150_y_ajoined
21:11:40  * tilgoviquit (Ping timeout: 250 seconds)
21:12:06  * Mso150_yquit (Ping timeout: 250 seconds)
21:23:26  * peutetrejoined
21:26:39  * peutetrequit (Client Quit)
21:30:39  * tilgovijoined
21:32:59  * h0kejoined
21:33:30  * hackygolucky__changed nick to hackygolucky
21:35:12  * tilgoviquit (Ping timeout: 256 seconds)
21:37:41  * h0kequit (Ping timeout: 264 seconds)
21:41:53  * quijotejoined
21:45:58  * domanicquit (Ping timeout: 256 seconds)
21:46:26  * quijotequit (Ping timeout: 258 seconds)
21:52:54  * DamonOehlmanjoined
22:19:11  * DamonOehlmanquit (Ping timeout: 250 seconds)
22:19:23  * ryan_ramagejoined
22:22:05  * toddselfchanged nick to toddself_zz
22:24:17  * Mso150_y_aquit (Ping timeout: 240 seconds)
22:29:07  <substack>mikolalysenko_: hadn't gotten to the memoization stuff I could do with that yet, was just trying to get it close enough to the native browser svg results
22:30:05  * ednapiranhaquit (Read error: Network is unreachable)
22:30:27  * DamonOehlmanjoined
22:30:42  * ednapiranhajoined
22:38:46  * soldairquit (Quit: Page closed)
22:42:40  * quijotejoined
22:47:13  * quijotequit (Ping timeout: 255 seconds)
22:58:23  * tilgovijoined
23:00:48  * therealk_quit (Remote host closed the connection)
23:03:22  * rockbot__joined
23:09:53  * zvjoined
23:15:31  * therealkoopajoined
23:31:43  * rockbot__quit (Remote host closed the connection)
23:35:05  * h0kejoined
23:40:26  * h0kequit (Ping timeout: 256 seconds)
23:42:39  * rockbot__joined
23:43:26  * quijotejoined
23:48:37  * quijotequit (Ping timeout: 272 seconds)
23:49:41  * tilgoviquit (Ping timeout: 264 seconds)
23:51:56  * therealkoopaquit (Remote host closed the connection)
23:52:35  * therealkoopajoined
23:54:06  * tilgovijoined
23:56:37  * therealkoopaquit (Ping timeout: 240 seconds)
23:56:46  * phatedquit (Remote host closed the connection)