Odin-'s blog

Polygon Generator
By Odin-, 6 years ago, In English

Hello,

Can anyone share a polygon of n vertices generator (not necessarily convex) , and validator, its best if it was used in a previous CF round.

  • Vote: I like it
  • +25
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

jngen can generate you a convex polygon. I assume you wanted convex, did you actually?)

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

All CF rounds use Polygon.

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Slow generation: generate some random point and join them randomly. If two edges (a,b) and (c,d) intersect -> swap them to edges (a,c) and (b, d).

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I think this is likely to generate a set of non-intersecting polygons instead of one polygon with this method.

    → Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Generate some random points and find the convex hull :D

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Using this method with totally random points leads to really small amounts of points remaining.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The following approach sounds fun. Generate convex polygon. Select arbitrary point O inside of it. Then for each side draw infinite triangle (or limited by your constraints for coords) through O and border points of that side. After that generate random points in that triangle (randomize angle, randomize distance from O, find the closest integer coordinate point to it), sort them by angle from O, delete the side itself and connect points one by one including the original border points.

→ Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it +35 Vote: I do not like it

I made a proof-of-concept and it suddenly worked pretty well. Probably I'll add it to Jngen soon.

  1. Generate n points in general position (no three line are collinear). Collinearity condition is not necessary (and in some problems interesting tests should contain non-collinear points) though it simplifies our life.

  2. Build any Hamiltonian cycle on those points (*).

  3. While two intersecting segments exist, fix the crossing locally. Assume segments (pi, pi + 1) and (pj, pj + 1) cross; then we reverse the part of the path between i + 1 and j. Now we have edges (i + 1, j + 1) and (i, j) instead, all other edges remain unchanged, and the local intersection is fixed. Each reverse decreases the length of the path, so this process ends in finite number of iterations.

  4. Now we have a Hamiltonian cycle without self-crossings. It is the boundary of the desired polygon.

(*) How to select the initial cycle? I tried two ways. First, pick a random order. Second, build a 2-approximation to the traveling salesman problem (build an MST and write its vertices in DFS order, writing each vertex only when visiting it for the first time). In both approaches the "fixing" part runs in reasonable time (below 1 second) for 1000 points. Though the pictures are much more beautiful when the MST approximation is used.

Link to the code I used for generation. It is not well-tested and was not expected to be read by anyone, apologies. Jngen is required to run the code.

The first image shows random initial approximation, the second shows the MST one.

→ Reply
»
6 years ago, # |
  Vote: I like it +28 Vote: I do not like it

You can use cyaron (which is a project similar to jngen, Chinese, python) to generate a (simple) polygon:

from cyaron import *
print Polygon.simple_polygon(Vector.random(500, [400, 400], 2)).points
# Vector.random(500, [400, 400], 2) can generate a vector of 500 real pairs of [0,400]x[0,400]
# Polygon.simple_polygon can make a polygon from these points

It can create a polygon consists of 500 points with real coordinates [0,400]x[0,400] (the function can also work with integers, but it may fail at times so a double-check is needed). (This part of code is written by me, but the idea is not original)

generated polygon

The idea of it is basically choosing two points randomly, and divide the remaining points into two sets based on the side to the line. Then we need to implement a function that can make a path to connect the given points and start from and end with two selected points.

Say the set is S and the starting and ending point being A and B. Choose a random point (other than A and B) in S and choose a random point on the segment connecting A and B, say they're C and D. Divide the points into two sets based on the side to the line C and D, and recursively find two paths from A to C and C to D out of these two sets.

→ Reply