Divide area into polygons

Hello everyone. Supposing there is a square area (x,y coordinates) given by the user is it possible to divide the area into non overlapping polygons (let's say 8 polygons for example) and then check which polygon contains a single pair of coordinates? In the meantime i am trying to figure it out and if there is any progress I will post it as a comment. Any help is most welcome. Thanks in advance.

Answer 1

[Steven Lord]

Many different ways.

• Slice the square into 8 rectangles with horizontal cuts.
• Slice the square into 8 rectangles with vertical cuts.
• Slice the square into 4 smaller squares with one horizontal and one vertical cut, then divide each square into two pieces with a single cut each.
• Do some other series of 3 cuts that achieves the upper bound of 7 in the lazy caterer's sequence then make one cut that divides one of the pieces in two.

What requirements do you have on the polygons into which you want to cut the square?

[Paschalis Garouniatis]

Thank you for your response. I have attached an example (done with voronoi function i suppose) of what i want to achieve. X1, X2, ...XN should be the final polygons and then I need to extract the vertices of each polygon.

[Steven Lord]

That picture comes from this example. The "Computing the Voronoi Diagram" section of that example discusses how to get the Voronoi vertices. Use the elements of each cell in the R output to index into rows of the V output to get the coordinates.

[Paschalis Garouniatis]

For the inner polygons it's ok but for the outer ones I need 2 more vertices. Polygon X7 for example. The vertices from the R variable are 1, 3 and 4. However V1 is infinite. Is there a way to create vertices for this polygon at the points that there is intersection of the plot and axis (let them be A(-4, -2) and B(-4, 0.3) roughly estimating). Also for X12 I need 3 more vertices (one of them is (-4, -4) ).

[Paschalis Garouniatis]

After many trials to create polygons I ended up dividing the area into smaller squares and then use the voroinoilimit function in order to obtain the vertices.