3

I am looking how to generate polygons in GeoJSON format with random locations (latitude, longitude), if I generate totally random set of points it will not produce valid polygons.

So my question is there a tool or algorithm that allows to generate valid polygons of specific size (radius?) inside of bounding box.

UPDATE#1

Here is more details to clarify my question: Desired polygons should consist of 30-60 points each and represent something similar to square. All generated polygons should not intersect with each other (no inner polygons either). All generated polygons should be placed within specified bounding box (border)

  • 1
    There are an infinite number of polygons that can be generated at any given location. Please refine your question to specify the shape(s) you want (convex/concave, number of vertices, regular/irregular, permitted rotation,...). – Vince Apr 1 '14 at 13:09
  • I updated my question, please take a look if it makes sense – endryha Apr 1 '14 at 16:32
  • 1
    "Similar to square" and "30-60 points" make this a very difficult problem. – Vince Apr 1 '14 at 16:54
  • Yeh, I understand, I already did an investigation around this, I think it will be sufficient to generate strict rectangles but with extra points on the edges, what do you think about this? – endryha Apr 1 '14 at 17:58
  • 2
    Your generation code would still need to retain a union of all previously generated shapes for exclusion of overlaps, and with enough of the "right" shapes, would produce an infinite loop, since no valid additional shapes could be generated. – Vince Apr 1 '14 at 18:03
3

I'd suggest you divide the problem into two parts:

  1. Generate a set of squares that represent the bounding boxes of each polygon ensuring they don't intersect. one way to do this would be generate a set of random points (1 per polygon) Put the first point into your master boundary. For each subsequent point, subdivide the box mid way along the closest axis to the previous point in the box. You will then have a set of differing size boxes each one with a single point in (You may want to consider a minimum size for the boxes)

  2. For each box generate your polygon using these bounding boxes. You could use something like http://web.engr.illinois.edu/~jeffe/open/randompoly.html

Part 1 ensures that there are no overlaps in the polygons generated. Part 2 could use any method of generating the polygon

Its quite a difficult problem so you would be better to divide and conquer!

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.