How to fill polygon with points regularly?

问题:

It is simple to fill rectangle: simply make some grid. But if polygon is unconditioned the task becomes not so trivial.
Probably "regularly" can be formulated as distance between each other point would be: R ± alpha. But I'm not sure about this.
Maybe there is some known algorithm to achieve this.
Added:
I need to generate net, where no large holes, and no big gathering of the points.

回答1:

Have you though about using a force-directed layout of the points?

Scatter a number of points randomly over the bounding box of your polygon, then repeatedly apply two simple rules to adjust their location:

1. If a point is outside of the polygon, move it the minimum possible distance so that it lies within, i.e.: to the closest point on the polygon edge.
2. Points repel each other with a force inversely proportional to the distance between them, i.e.: for every point, consider every other point and compute a repulsion vector that will move the two points directly apart. The vector should be large for proximate points and small for distant points. Sum the vectors and add to the point's position.

After a number of iterations the points should settle into a steady state with an even distribution over the polygon area. How quickly this state is achieved depends on the geometry of the polygon and how you've scaled the repulsive forces between the points.

回答2:

You can compute a Constrained Delaunay triangulation of the polygon and use a Delaunay refinement algorithm (search with this keyword).

I have recently implemented refinement in the Fade2D library, http://www.geom.at/fade2d/html/. It takes an arbitrary polygon without selfintersections as well as an upper bound on the radius of the circumcircle of each resulting triangle. This feature is not contained in the current release 1.02 yet, but I can compile the current development version for Linux or Win64 if you want to try that.