Блог пользователя Odin-

Автор Odin-, 6 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +25
  • Проголосовать: не нравится

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

All CF rounds use Polygon.

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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).

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Generate some random points and find the convex hull :D

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
6 лет назад, # |
Rev. 4   Проголосовать: нравится +35 Проголосовать: не нравится

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.

»
6 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

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.