3

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.

Pavel
  • 2,602
  • 1
  • 27
  • 34

2 Answers2

3

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.

ryanm
  • 2,979
  • 18
  • 22
  • Is there some more detail description of this? Looks nice. – Pavel Oct 17 '12 at 16:52
  • It's very similar to [force-directed graph layout](http://en.wikipedia.org/wiki/Force-based_algorithms_(graph_drawing)). Note that you will have no attractive forces between the points, only the constraint that all points lie within the polygon. – ryanm Oct 18 '12 at 08:01
  • It'll work most of the time, but not always. There are counterexamples. Lets say a polygon consists of two larger areas connected with a narrow snake-like "passage". Its easy to devise a shape of such "passage" so that repulsive forces could never "push" points through it. But I guess for most practical purposes, it will be good enough. – VividD Dec 31 '13 at 21:23
3

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.

Uniform refinement of a polygon with holes

Geom
  • 827
  • 4
  • 15
  • It is good method, I now using it via https://www.cs.cmu.edu/~quake/triangle.html. But, distribution of the points is not ideal. Thanks for answer. – Pavel Oct 17 '12 at 16:53