`d2xy[z]`, `xy[z]2d` functions, reference implementations in JS & C, demo JS application

[abetusk]

This resolves #7 by adding the d2xy, xy2d, d2xyz and xyz2d functions to the python2d.py and python3dpy, respectively. In addition, reference implementations were created for JS and C along with a small demo program that can be run in browser (using the JS reference implementation).

The d2xy[z] and xy[z]2d functions in Python were copied almost verbatim from the gilbert[23]d functions, adding "short-circuit" logic to check whether the query point or index was within bounds. Since the recursion focuses on a sub rectangle, we know all points in the sub branch of search will be restricted to that region and we know how far along the linear path we'll go. For the respective functions, we can either test to see if our query point is within the region and skip over it, incrementing the index as necessary, or test our query index to see if its within range, skipping over it as appropriate.

The "short-circuiting" makes each of the d2xy, xy2d, d2xyz and xyz2d functions effectively $O( \lg N )$.

I only have a vague understanding of the code, especially when it comes to edge cases, so extra caution should be used when reviewing the code.

For the Python scripts:

• gilbertd2xy, gilbertxy2d, gilbertd2xyz and gilbertxyz2d were added
• The respective "recursive" functions, allowing for state variables to be passed in, were created. Respectively: gilbertd2xy_r, gilbertxy2d_r, gilbertd2xyz_r and gilbertxyz2d_r were added
• For both the gilbert2d.py and gilbert3d.py programs, the default command line behavior should be identical in that calling it with width, height and depth, when appropriate, will still call the generator (gilbert[23]d) functions
• An extra command line option has been added to allow for an enumeration using the new functions. Here are some examples of their usage:

./python2d.py --op d2xy 13 14
...
./python2d.py --op xy2d 13 14
...
./python3d.py --op d2xyz 13 14 12
...
./python3d.py --op xyz2d 13 14 12
...

Both a C and JavaScript reference implementation, implementing the d2xy[z] and xy[z]2d functions. A Makefile has been provided to compile the C source (make to run and compile). I'm using Ubuntu 20.04.6 LTS so this might not work on other systems.

The C functions follow the Python functions closely. The JavaScript implementation returns an object with "x" and "y" components. Both are not very sophisticated in how they expose their functionality but they both make minimal assumptions and presumably should be able to be dropped into other projects with relative ease.

For all three variants (Python, C, JavaScript), a rudimentary, ad-hoc shell script is in the tests folder. The tests/runtests.sh script runs all three programs with all the different permutations (d2xy[z], xy[z]2d) and a list of pre-set width, height and depth, where appropriate, values. The results are compared to the "reference" implementation of the corresponding 2D/3D Python generator function.

The d2xy[z] functions enumerate the path in index order so can be compared directly. The xy[z]2d enumerate the points in x, y, and z, when appropriate, order, printing the index as the first number. For the 3D points, the output is sorted by the index (the first number) and then compared with the reference enumeration after the first, index, element has been discarded.

For example:

  diff \
    <( ./gilbert3d.py $x $y $z ) \
    <( ./gilbert3d.py --op xyz2d $x $y $z | sort -n | cut -f2- -d' ' )
...

A 2D only demo program is provided in the html directory which uses Two.js as an auxiliary library for the rendering and Skeleton CSS for styling. I think this is a nice addition so that folks can get an immediate sense of what the curve is and how different dimensions can affect its rendering. I'm sure you know this but for the sake of completeness, a quick-n-dirty web server can be run via python3 -m http.server in the html directory which you can then point your web browser to (localhost:8000) to see it in action.

Some various things that I think are nice:

• individually incrementing width and height to see how that affects the curve
• color/bw toggling
• SVG download
• presets, including some problematic configurations highlighting the jaggies (e.g. 15x12)

I would suggest trying to incorporate it into some sort of GitHub page and provide a link from the repository but that might need some file re-organization in addition to needing you to turn on that feature in the repository, so I'll leave it up to you if you're up for it.

I've made sure to label all non third party sources with a BSD-2-Clause in addition to assigning you as copyright owner.

Thank you for working through this problem and providing your source as libre/free! This seems like a pretty natural problem but finding a treatment of this problem that describes what's going on well, works in 2d and 3d, has an implementation and that has an implementation that is libre/free was surprisingly difficult. I think yours might be the only one.

[abetusk]

One more comment. I realize this got scoped creeped out of the initial #7 but my rationalizations are:

• The C implementation was straight forward and useful
• The JavaScript implementation was also useful pretty straight forward
• The demo program was easy to create and allows for easy understanding and appreciation of the project

So, I know it's probably more than was bargained for but I hope its an enhancement.

Regardless, thanks again for creating this repo!

[abetusk]

I just found a bug for a 2D 2x10. Let me look into it and update this PR when I have it fixed.

[jakubcerveny]

Abe, thank you very much for this contribution! I think the new functions can be really useful for others and I will be happy to merge this PR into the main repo.

Would you consider making these minor changes?

• Since the original intent for this repo is more documentational than "production", and the python code serves more or less as pseudocode too, I would move other language modules to a separate directory (let's say ports/?)
• The d2xy, xy2d, etc., functions are useful, but I feel they obscure a bit the original algorithms in gilbert2d.py and gilbert3d.py, that should be brief for documentation purposes. What do you think about moving them to gilbert_d2xy.py, gilbert_xy2d.py, gilbert_d2xyz.py and gilbert_xyz2d.py in the root directory?
• I would add an underscore to the function names: gilbertd2xy -> gilbert_d2xy etc.
• In files contributed by you, the copyright should be in your name, I think (or omitted, if you like).
• The html directory could maybe called demo (very cool BTW), though this is not critical.
• Would you mind adding a short section in README, with some appropriate name, that would describe the d2xy, xy2d, etc. modules?
• Ports and the demo could have very brief sections too.

Thanks again! Jakub

[abetusk]

I'm working on some bug fixing now but don't anticipate any big issues. I'll try to incorporate all those suggestions once the bugs are worked through.

[abetusk]

Hopefully I've fulfilled all the suggestions/requirements.

I'm not exactly sure what should be put in the README section so I just put down something I thought was minimally reasonable. Please let me know if it's not satisfactory and I'd be happy to change it.

I also put a link into the README for to a GitHub pages link. In order for that link to resolve you'll need to turn on that feature through the GitHub interface. You can see mine running here.

FYI, it turns out the bugs were because I didn't do the initial w>h check and, in C, integer divide truncates towards 0 whereas the algorithm needed the floor function. Tests are passing but I would still be wary as the tests are just small subset and aren't necessarily representative.

[jakubcerveny]

Thank you for the update! I think the new README sections are great.

I noted that the original gilbert[23]d.py are probably still not fully reverted?

[abetusk]

Dammit, I'm so sorry! I should have double checked.

I think the gilbert3d.py had been reverted but not the gilbert2d.py. Regardless, they should both be back to the original now.

[abetusk]

I've made a best effort approach to be consistent with what I think your intent was for whitespace consistency. I don't find your example code all that consistent with the critiques of my code so I made what I thought were reasonable assumptions about what you wanted the code to look like.

I usually strive for legibility as a priority, with code formatting only providing a suggestion rather than a hard and fast rule. I'm not always consistent, which is a valid critique, but I suspect you want consistency over some opinion, mine or otherwise, of legibility. I'm willing to comply with this type of request as I'm a guest here but I do have a few suggestions going forward:

• For pedantic styling type of requests, rather than blocking a pull request, formatting fixes can be done yourself with a warning that future PRs will be rejected unless your formatting rules are adhered to.
• Regardless of whether you want this done by a first time author of a PR or you do it yourself, provide a reference in the form of code, a document or some other guideline for code formatting (e.g. PEP8). Preferably this would be done in a CONTRIBUTING document in the repo itself but, barring that, this should be linked to when giving feedback about code formatting.

Blocking PRs due to minor issues, formatting or otherwise, causes a chilling effect to potential contributors. I've made this mistake in the past and my opinion, now, is that it's better to be forgiving on first time pull request with clear feedback about what the expectations are going forward rather than front load high expectations to begin with, especially for a project of this size. Larger projects might have a higher bar for contributions but also, presumably, have a more intentional expectation of what type of contributions they want.

[jakubcerveny]

Thank you, the formatting looks great now. You are right that without apriori contributor guidelines, it may not be appropriate to make these pedantic requests of a volunteer. My apologies. It wouldn't have been a blocker, and please feel free to ignore or contest any future requests you are not comfortable with.