# Is there an algorithm that will fill any shape with points a given distance away from each other?

I would like to know if there is an algorithm that if I give a 2D polygon it will give me a set of 2D points. More specifically, those points should have M neighbors that are D apart. The shape is continually filled up with points until no new points can be found without exceeding the bounds of the polygon. The polygon can be given as set of vertices.

I could see an algorithm starting out with a point at the center of the polygon, and then adding a second point exactly the desired distance away. With those two points, another point equidistant to the two previous points could be found by finding the intersection of two circles with the two previous points as their centers and their radii the desired distance.

This gives two points, each of which can be added to a growing list of points. Each point keeps track of what points have been added as neighbor relative to it, and when it has M neighbors, it no longer tries to find any new neighbor. It also does not continue to look for more neighbors if no new neighbors can be found that don't leave the bounds of the polygon.

I am having some mental blocks and if anyone could suggest any leads I would greatly appreciate it. Thank you.

• What you have described looks like working solution, probably with some point in polygon test. But the given points may vary with initial starting point - do you have any constraints on that?
– Evil
Mar 28, 2016 at 21:10
• Not particularly, but I could set the starting point to always be the center of the shape. Thank you for the suggestion on the point in polygon test! Mar 28, 2016 at 22:05
• You are looking for something like this ? Another way is to create equilateral triangle tiling like this, plot your polygon and check which points are inside. If your resolution is e.g. one pixel big, you can check all possible starting points (shifts from the starting point)and check the optimal solution (more points? with rotations?). For testing not rotated polygon scanline will be effective.
– Evil
Mar 28, 2016 at 22:20
• Awesome! That definitely looks like it will work. Mar 28, 2016 at 22:35