Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Generating triangles from a random set of points

I have randomly generated some points on a JavaScript canvas I was wondering what the most efficient method would be to draw triangles connecting the points in a uniform fashion. The goal is to have the triangles fill the entire canvas without overlapping.


For a visual representation, here is an image of the points I have randomly generated across a canvas. As you can see I may have to modify the way I randomly place the points on the canvas.

points

And this is how I wish to draw the triangles.

enter image description here

like image 478
getmicah Avatar asked May 11 '17 03:05

getmicah


People also ask

How do you generate random points in a polygon?

The first step is to decompose the polygon into triangles. You can use the relative areas of the triangles to determine the probability that a random point is in each triangle. Finally, you can generate random points in the union of the triangles.

How do you generate random coordinates in Python?

randint() method. Python provides a random module to generate random numbers. To generate random numbers we have used the random function along with the use of the random. randint function.

How do you randomly select a point on a circle?

Generate Random Point in a Circle in C++Radius and x-y position of the center of the circle is passed into the class constructor. A point on the circumference of the circle is considered to be in the circle. The randPoint() returns x-position and y-position of the random point, in that order.


1 Answers

Thanks to @Phorgz & @GabeRogan for pointing me in the right direction. Delaunay Triangulation was definitely the way to go and it ended up being very fast, even when updating the canvas as an animation.

I did end up using the npm package faster-delaunay which uses the divide and conquer algorithm to triangulate the randomly generated points.

Here is a result of what I have drawn on the canvas that updates as the points move around the plane:

delaunay

like image 144
getmicah Avatar answered Oct 15 '22 13:10

getmicah