2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Evil Mar 28 '16 at 21:10
  • $\begingroup$ 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! $\endgroup$ – Sebastian Freeman Mar 28 '16 at 22:05
  • $\begingroup$ 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. $\endgroup$ – Evil Mar 28 '16 at 22:20
  • $\begingroup$ Awesome! That definitely looks like it will work. $\endgroup$ – Sebastian Freeman Mar 28 '16 at 22:35
0
$\begingroup$

Are you looking for something like this?

Another way is to create equilateral triangle tiling like this‌​, plot your polygon and check which points are inside. Of course it is not needed to actually plot it, just store it in memory.
If your resolution is e.g. one pixel big, you can check all possible starting points shifts from the starting point to find better solution.
To find optimal solution also rotation would be needed, or different approach.
If you decide that not rotated version is sufficient, the ray casting algorithm (also known as scanline test) for testing point inside polygon would be very effective, because all points in a row form line, so in one longer pass you can test whole row.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.