Julia bindings #9
Comments
|
Hi 👋 It's awesome to hear that you're enjoying tg, and that you're seeing speedups in your Julia project! I'm curious how the porting of the natural indexing code went, particularly the construction function? The indexing building code in tg.c is pretty gnarly. You mentioned a build issue with 32 bit. I checked it on my side and it failed for me too. I push a fix so that it now compiles, at least with Thanks for sharing your project. I plan on watching its progress. |
|
The construction function was a bit gnarly to get through, but I did figure it out in the end. There are a couple of places where the loop runs backwards that were mainly where the confusion was, but it wasn't too bad. My implementation is slightly different from yours, since I can't actually represent arbitrary rings as edge lists efficiently (since in Julia we can have arbitrary representations of geometry in memory, including opaque C pointers), I just store the leaf level bounding rectangles ("extents"). At some point, I might change that - but I'm not sure how you handle the lines at the base level. Do you just reconstruct the bounding rects from each line segment every time? If so, I might be able to preprocess and store the index more efficiently. Also, I did a quick benchmark testing point-in-polygon from I also ran the benchmarks in a random order, to hopefully keep the branch predictor confused. If you look closely, you can kind of see the natural index structure too. Queries that are outside the polygon take significantly more time than queries inside the polygon, which is very interesting. This is using the For reference, here's a visualization for the runtime of the naive (checks all edges on the ring, no index acceleration) Hao-Sun algorithm on the same problem. It has the same characteristic of checks on the outside of the polygon being substantially longer than checks on the inside... |
The bounding rectangles are constructed only once. This happens when the points are processed during geometry construction. I scan the polygon points in a single pass, inflating the rectangles along the way. For the natural index, the leaf segments are in groups of 16. I call this value the 'spread', which is similar to a node size in a packed tree structure (like an STRtree). As each segment is processed, one leaf rectangle is inflated per group. These rectangles bubble up to inflate the parent rectangles, up to the root. All this happens on the single pass over the points. The other polygon properties are also calculated during the same pass, concave/convex, winding order, area, etc. Your visuals look really nice btw. I'm also wondering about the significant difference between the points-in vs points-out. 🧐 |
|
Yeah, I guess that's down to the algorithm? If the edge crosses the scanline unambiguously it could be a quick acceptance, but Hao Sun has so many conditions that it could be more computation if the case is more complex? |
|
Also, quick question - is it required to free the intermediate geometry constructs that are made when constructing a higher level geometry? Currently when constructing e.g. a multilinestring or a polygon I construct the linestrings / rings first and then use an array of pointers to those linestrings / rings to build the multilinestring / polygon. but this seems to cause a bit of a memory leak, so I'm wondering if I missed a |
|
Yes. The general rule is that for every TG uses reference counters for all allocations. The tg_geom_new_multilinestring only retains a reference to the lines. The ownership belongs to the caller. You should be calling tg_line_free for each line. After tg_geom_new_multilinestring but before returning from the function. |
|
Sweet, thanks for the pointer. Will make sure to do that then. |
I just stumbled across this package last week, and I love it! Very inspired by the natural indexing approach, ported and applied it to my own geometry library in Julia (GeometryOps.jl, PR still heavily in progress) and saw significant speedups.
I also wrapped
libtgin a Julia package TGGeometry.jl, compatible with Julia's GeoInterface.jl ecosystem, and the binary is being built on the https://binarybuilder.org/ infrastructure - if you want to access it, tarballs are available at this link, built on all non-32 bit platforms. I had some build issues on 32 bit.Pinging here to say hi and let you know that this now exists :D
The text was updated successfully, but these errors were encountered: