Hi! I trying to understand how this task can be solved:
I need generate number of triangles (any size) in any random place on sketch, but i need them not overlapping with each other and may be with constant distance from each other. Seems like this is not trivial challenge.
One of my ideas was
Generate first triangle
then i can check if first point (x1,y1) of next triangle is not in any already generated triangles… etc
3…
what i have to do for next x2,y2,x3,y3 points? if they not in any triangles it can still generate overlapping triangles.
Also found Delaunay triangulation algorithm, but seems its not match my needs, because generates triangles based on points and its looks like mesh not standalone triangles…
Please, share your thoughts.
Im newbie in Processing/Java, need a right path to move in coding with this task.
I know you said the delauny wouldnt work but i think its a pretty good approach. The circle packing algorithm essentially does what you are looking for but for one point only which i guess you could extend to three points or triangles.
With the delauny algorithm you make a mesh and providing that you can capture the vertices of each triangle you could then move them some random amount towards its own centre. This way you dont just get triangles with equidistant vertices to its neighbours.
This way you can break the symmetry inherent to a Delaunay triangulation (adjacent triangles have parallel edges) and have something that resembles your example picture.
Another thing to consider is the placement of your points. If you want the triangles to be more or less equidistant it may be useful to resort to Poisson Disk Sampling before triangulation.
Alternatively, you could:
compute a Voronoi diagram out of your point cloud
randomly scale down the Voronoi cells
sample 3 equidistant points along the edges of the cells to create a triangle
Then no need for rotation or extra-sampling since the dis-symmetry will appear naturally.
Of course that’s just one way of doing things. You could also use brute force methods with collision detection or resort to simple physics engines with rigid bodies and repulsion forces.
are you still working on this problem, I took an interest in it and made an attempt at finding a solution. 90% of the way there, I use my own delauny algorithm so it might not be as fast as others here are the results.
will post github later
Im currently working on the edge cases, (the black lines) in the diagram. The location for the center of the triangles can easily be calculated at this point, just need to add the code, then just a matter of choosing your preffered method to solve this problem. No voronoi as of yet but its a fairly easy step after all this.
The delauny centers are added to the arrayList delaunyCenters, in the main sketch tab. These are of the cell class, and contain a center point which can be called by cell.x,cell.y, and the vertices for the triangles found in the cells vertices array.
incidentally, I started this sketch using FX2D this was an old sketch I was revisiting and back before I could appreciate P2D I always made use of it, because I found it faster, however I now get a huge cpu load when using FX2D and I’m not sure why. The same code with P2D runs fine.
please note, that edge cases aren’t completely handled yet.
Im back to this exercise, and thinking about how i can calculate triangle and fit it inside voronoi cell. Voronoi cells have different count of sides… is it right that i have to start from voronoi center point, and then build my triangle with same center point?
In my example I never calculate the voronoi. I’m not making use of fortunes algorithm I’m just making use of line intersections, it does make use of a quad grid though to speed up the process. This will give you all center points and vertices of the triangles, though as I mentioned its not 100% accurate on the edges.
So just Delaunay. Which you can then use to calculate the voronoi.
Not exactly. You just need to sample 3 equidistant points along the edges of the Voronoi cells and draw triangles with it. You can use the dividePLine function I used in this other sketch.
For example:
tri = dividePLine(vertices, 3, true);
where:
vertices is a list of the vertices of a single Voronoi cell
3, the desired number of equidistant points
false/true, a boolean indicating whether the polyline (edges of the Voronoi cell) is closed or not
