# Generate random not overlapping triangles
**URL:** https://discourse.processing.org/t/generate-random-not-overlapping-triangles/25875
**Category:** Coding Questions
**Created:** [December 1, 2020, 9:19pm UTC](https://discourse.processing.org/t/generate-random-not-overlapping-triangles/25875 "2020-12-01T21:19:08Z")
**Posts on this page:** 10
**Page:** 1
### Author:  [@nktlst](https://discourse.processing.org/u/nktlst)
#### Post date: [December 1, 2020, 9:19pm UTC](https://discourse.processing.org/t/generate-random-not-overlapping-triangles/25875/1 "2020-12-01T21:19:08Z")
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
1. Generate first triangle
2. 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.
Example of what i need attached.
---
### Author:  [@paulgoux](https://discourse.processing.org/u/paulgoux)
#### Post date: [December 1, 2020, 10:03pm UTC](https://discourse.processing.org/t/generate-random-not-overlapping-triangles/25875/2 "2020-12-01T22:03:38Z")
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.
---
### Author:  [@nktlst](https://discourse.processing.org/u/nktlst)
#### Post date: [December 1, 2020, 10:15pm UTC](https://discourse.processing.org/t/generate-random-not-overlapping-triangles/25875/3 "2020-12-01T22:15:19Z")
thnx @paulgoux! i will play with Delaunay algorithm closely.
---
### Author:  [@solub](https://discourse.processing.org/u/solub)
#### Post date: [December 2, 2020, 3:55pm UTC](https://discourse.processing.org/t/generate-random-not-overlapping-triangles/25875/4 "2020-12-02T15:55:30Z")
Hi @nktlst,
If you decide to use Delaunay triangulation I would suggest to either:
- rotate **slightly** the triangles (not too much to avoid overlap)
- sample 3 equidistant points along the edges of the current triangles in order to create new _offset_ triangles
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](https://www.youtube.com/watch?v=flQgnCUxHlw) 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.
---
### Author:  [@nktlst](https://discourse.processing.org/u/nktlst)
#### Post date: [December 2, 2020, 9:02pm UTC](https://discourse.processing.org/t/generate-random-not-overlapping-triangles/25875/5 "2020-12-02T21:02:34Z")
@solub thank you for such detailed explanation! im impressed and trying to do this… 😀
---
### Author:  [@paulgoux](https://discourse.processing.org/u/paulgoux)
#### Post date: [December 13, 2020, 8:10pm UTC](https://discourse.processing.org/t/generate-random-not-overlapping-triangles/25875/6 "2020-12-13T20:10:56Z")
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.
---
### Author:  [@paulgoux](https://discourse.processing.org/u/paulgoux)
#### Post date: [December 14, 2020, 5:08am UTC](https://discourse.processing.org/t/generate-random-not-overlapping-triangles/25875/7 "2020-12-14T05:08:09Z")
heres the github
> **[paulgoux/voronoi](https://github.com/paulgoux/voronoi)**
>
> voronoi and delauny generator. Contribute to paulgoux/voronoi development by creating an account on GitHub.
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.
---
### Author:  [@nktlst](https://discourse.processing.org/u/nktlst)
#### Post date: [December 25, 2020, 8:45pm UTC](https://discourse.processing.org/t/generate-random-not-overlapping-triangles/25875/8 "2020-12-25T20:45:12Z")
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?
---
### Author:  [@paulgoux](https://discourse.processing.org/u/paulgoux)
#### Post date: [December 25, 2020, 10:00pm UTC](https://discourse.processing.org/t/generate-random-not-overlapping-triangles/25875/9 "2020-12-25T22:00:39Z")
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.
---
### Author:  [@solub](https://discourse.processing.org/u/solub)
#### Post date: [December 26, 2020, 7:24pm UTC](https://discourse.processing.org/t/generate-random-not-overlapping-triangles/25875/10 "2020-12-26T19:24:09Z")
> [@nktlst](#):
>
> is it right that i have to start from voronoi center point, and then build my triangle with same center point?
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](https://discourse.processing.org/t/triangulation-libraries-issue-unwanted-edge/25964/20).
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