420chan now has a web-based IRC client available, right here
Leave these fields empty (spam trap):
You can leave this blank to post anonymously, or you can create a Tripcode by using the float Name#Password
[*]Italic Text[/*]
[**]Bold Text[/**]
[~]Taimapedia Article[/~]
[%]Spoiler Text[/%]
>Highlight/Quote Text
[pre]Preformatted & Monospace text[/pre]
1. Numbered lists become ordered lists
* Bulleted lists become unordered lists


Community Updates

420chan now supports HTTPS! If you find any issues, you may report them in this thread
triangular tiling by snurrepupp - Sat, 13 May 2017 05:12:13 EST ID:LBUM/d2l No.36900 Ignore Report Quick Reply
File: 1494666733428.png -(17146B / 16.74KB, 375x286) Thumbnail displayed, click image for full size. 17146
I'm making a thing in C where I want to restrict screen positions to junctions on a triangular grid.

Got any ideas on a kind of data structure I could make?
The grid itself should be able to be relocated around on-screen if wanted.
I need it to allow me to get position of the nearest triangle junction, based on some input position.
Additionally, it should allow me to get positions of adjacent triangle junctions.

Any suggestions?
Jarvis Grandgold - Sat, 13 May 2017 16:44:55 EST ID:P6PS9CBz No.36903 Ignore Report Quick Reply
I'm not entirely sure what you mean when you say "triangle junctions". Do you mean to try and get the two closest triangles, or the closest adjacent triangle to the triangle that the input position lies within?

In any case, if the triangles are guaranteed to lie within a regular plane (like the image you showed) then you don't need any data-structures, you can simply procedurally pick the triangle. In the picture you showed the triangle's column would be (floor(iPosition.x / triangleWidth) ) and the triangle's row would be something like (floor(iPosition.y / triangleHeight + iPosition.x / triangleSlopeFactor) ). Getting adjacent triangles using this method should be straightforward because you can simply check the neighboring rows and columns of triangles to find adjacent ones.

If you are dealing with an arbitrary polygon soup of triangles (ie, not in a regular grid like in your picture) and you want to efficiently store the triangles for selection then you should use a spatial partitioning data structure, such as a quadtree/octree, a K-D tree, a BSP tree, or a hash-grid. Then for finding the closest triangle to the point you can walk the tree until you find the node that the input position belongs to and then do a brute-force test against all triangles within that same node (of course, if there are no triangles in that node then you have to search neighboring nodes, but getting neighboring nodes in a tree is very straightforward). For triangle adjacency, that's trickier for an arbitrary polygon soup. The geometric rules for triangle adjacency are that adjacent triangles must share at least one common vertex, so you should search for triangles that share at least one vertex with your current triangle.
Phyllis Lightdale - Mon, 15 May 2017 14:47:34 EST ID:9QSfnS0r No.36916 Ignore Report Quick Reply
I'd have a look for some 3D rendering toolkit based on OpenGL.
Even if you don't need 3D geometry dealing with triangular meshes is what they are made for.
Even if you don't actually use one it might give you plenty of insight.
snurrepupp - Sun, 21 May 2017 02:32:40 EST ID:LBUM/d2l No.36952 Ignore Report Quick Reply
1495348360874.png -(79765B / 77.90KB, 970x173) Thumbnail displayed, click image for full size.
I think I've been using the wrong approach to explaining + solving my problem.
That said, I think I can make use of some of your suggestions later, so thank you for the responses.

ATM I thinking about rewriting my whole thing, I could use some thoughts on that.
I'll put that at the end of this post.

I'm making a thing that should let one plot lines on an image - when printing out the image, cutting the outermost lines and folding it together, one should end up with a regular icosahedron. Basically a D20 paper die maker. While using it, it lets the user chose between possible triangles that are laid out by the program, in addition to allowing the user to undo previous triangles.

Image attachment is a generalized visualization of the problem I've been having.
Plus a screenshot, not related to any implementation issues, because why not.

My approach so far has been to use a structure for triangles that'll store its' radius and origin point. These are contained in another set of structures that links these triangle faces together in a net. Ultimately, this leads to having to use brute-force math and triangle look-ups when determining which possible triangles are valid, since the triangles should not form hexagons. This, in addition to running into problems with laying out triangles - upon the user removing a triangle - which I don't think I can circumvent.

I figure that the way to solve for these things would to model the icosahedron in terms of linked vertices (instead of faces). Then I could relate each vertex to a 2D coordinate, and each triangle to three vertices.

.. Would that approach make any sense, or would I be headed off on another dead-end algorithm adventure?
Phineas Sungerspear - Tue, 30 May 2017 01:02:30 EST ID:z/6RzCAH No.37008 Ignore Report Quick Reply

why not just keep track of the different vertices? if two triangles share vertices, they are adjacent
Cedric Droshkere - Wed, 31 May 2017 02:13:39 EST ID:P6PS9CBz No.37011 Ignore Report Quick Reply
I agree, if two triangles share a vertex then they must be adjacent. This is true in any number of dimensions.
Edward Dozzlebury - Sun, 04 Jun 2017 17:05:46 EST ID:z/6RzCAH No.37041 Ignore Report Quick Reply
i guess it depends on your definition of adjacent, but what i meant was, if they share two vertices, they must be adjacent.
snurrepupp - Mon, 05 Jun 2017 18:42:29 EST ID:LBUM/d2l No.37058 Ignore Report Quick Reply

Yeah. Touched briefly on using vertices in my prev post.
I'm in the process of redoing my not-strictly-D20-related shit to better accommodate vertices. Gonna have a go once that's done.

I guess I'll be back when I run into more trouble I can't work out.
Or alternatively, when I can provide a download link to the finished thingy.

Report Post
Please be descriptive with report notes,
this helps staff resolve issues quicker.