I have a bounding box of 1000m x 1000m. I randomly generate 10000 points (sites) inside it. Now, how can I create 'n' polygons (geometries) within the bounding box based on a given constrain.

The constrain could be anything. For example:

  1. number of sites inside each polygon are same for all polygons
  2. sum of distances from points inside the geometry to the centroid of geometry are same for all polygons
  3. let's say, I assign a weight to each site then constrain i sum of weights inside each polygon are same for all polygons
  4. area of each polygon is same
  5. etc.

Is there a way to generate such a geometry?

P.S. -- would be great if someone can also point me in the right direction and then give down vote.

  • $\begingroup$ Yes, but the best way depends on what the particular constraint is, so you need to be more specific. What's the actual problem you're trying to solve? $\endgroup$
    – Dan Hulme
    Commented Jul 15, 2017 at 12:27
  • $\begingroup$ Thanks @DanHulme, let's say, I would like to have it for first constrain. I am a novice in this area so probably, not even sure if I am looking in the right direction. $\endgroup$
    – novice
    Commented Jul 15, 2017 at 12:47
  • $\begingroup$ If you edit the question to show just a single question, it will be better received and it will be easier for people to write good answers. You can then post the other points as separate questions later. $\endgroup$ Commented Jul 16, 2017 at 16:12

1 Answer 1


It is possible to generate geometry from constraints. However, some of your constraints are hard to formulate as continuous functions that can be minimized or maximized. Also the ones that can be formulated this way have a staggering number of dimensions making gradient descents quite costly.

This means, you can not use a gradient descent method to find the solution. In turn this makes the problem computationally harder to do as the only way to do so is by trying a number of solutions.

So you would need to take some points by initial condition then solve for the constraints that can be made continuous. And then reevaluate if no solution is found. So some genetic algorithm should work fine, although it would be very inefficient.

But more likely your looking for some sort of clustering solutions. But if i were to do this with this vague instructions (which would surely fail) i would start by building a voronoi diagram, as it would help me find the connectivity.


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