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.

Before contest

Codeforces Round 977 (Div. 2, based on COMPFEST 16 - Final Round)

24:35:08

Register now »

Codeforces Round 977 (Div. 2, based on COMPFEST 16 - Final Round)

24:35:08

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 4009 |

2 | jiangly | 3839 |

3 | Radewoosh | 3646 |

4 | jqdai0815 | 3620 |

4 | Benq | 3620 |

6 | orzdevinwang | 3612 |

7 | Geothermal | 3569 |

8 | ecnerwala | 3494 |

9 | Um_nik | 3396 |

10 | gamegame | 3386 |

# | User | Contrib. |
---|---|---|

1 | Um_nik | 164 |

2 | -is-this-fft- | 162 |

3 | maomao90 | 159 |

3 | atcoder_official | 159 |

5 | cry | 158 |

5 | awoo | 158 |

7 | adamant | 155 |

8 | nor | 154 |

9 | TheScrasse | 153 |

10 | Dominater069 | 152 |

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.

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/05/2024 08:29:52 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

not necessarily convex

All CF rounds use Polygon.

Geometrical polygon :D

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

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

Generate some random points and find the convex hull :D

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

The following approach sounds fun. Generate convex polygon. Select arbitrary point

Oinside of it. Then for each side draw infinite triangle (or limited by your constraints for coords) throughOand border points of that side. After that generate random points in that triangle (randomize angle, randomize distance fromO, find the closest integer coordinate point to it), sort them by angle fromO, delete the side itself and connect points one by one including the original border points.I made a proof-of-concept and it suddenly worked pretty well. Probably I'll add it to Jngen soon.

Generate

npoints in general position (no three line are collinear). Collinearity condition is not necessary (and in some problems interesting testsshouldcontain non-collinear points) though it simplifies our life.Build any Hamiltonian cycle on those points (*).

While two intersecting segments exist, fix the crossing locally. Assume segments (

p_{i},p_{i + 1}) and (p_{j},p_{j + 1}) cross; then we reverse the part of the path betweeni+ 1 andj. 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.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.

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

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

Thanks, it works fine,