8

I am looking for a pseudo code logic that would find n equally sized areas in a given polygon. No space should be between or outside the matched areas. First valid match of areas should be returned.

Assuming following polygon [2,2, 3,1, 5,1, 5,4, 4,5, 2,3] as an input:

enter image description here

...and 3 as a parameter a valid output could be [ [2,2, 3,2, 3,3, 4,3, 4,5, 2,3], [2,2, 3,1, 5,1, 4,2, 4,3, 3,3, 3,2], [4,5, 4,2, 5,1, 5,4] ]:

enter image description here

Another valid output with parameter 3 is [ [3,4, 3,3, 4,3, 4,2, 3,2, 3,1, 2,2, 2,3], [4,3, 4,2, 3,2, 3,1, 5,1, 5,3], [3,4, 3,3, 5,3, 5,4, 4,5] ]:

enter image description here

Please note that areas don't have to share same center point. One or more areas may happen to fall right between other areas inside the polygon.

Here is another example of sample input/output.

Assuming following polygon [1,3, 1,1, 7,1, 7,2, 8,2, 8,3, 5,6, 4,6] as an input:

enter image description here

..and 5 as a parameter a valid output could be [ [1,3, 1,1, 3,1, 3,2, 4,3, 3,4, 3,3], [3,2, 3,1, 7,1, 7,2, 6,2, 6,3, 5,3, 5,2], [6,2, 8,2, 8,3, 6,5, 5,5, 5,4, 6,4], [1,3, 3,3, 3,4, 5,5, 6,4, 6,5, 7,5, 6,6, 5,6], [3,4, 4,3, 3,2, 5,2, 5,3, 6,3, 6,4, 5,4, 4,5] ]:

enter image description here

Following assumptions are made:

  • direction of all borders is divisible by 45

  • integer coordinates are used for all polygons

  • integer area of input polygon is always divisible by n

  • all polygons may be either convex or concave ones

  • solvable, meaning n areas can fit properly into the given polygon

  • 1
    Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask – gnat Feb 3 '16 at 16:51
  • You mean "equally sized" areas, not "equally distributed", I guess? – Doc Brown Feb 3 '16 at 16:52
  • @DocBrown you're so right, I knew I will get something wrong here. I definitely meant equally sized. Fixed – Sergey Lukin Feb 3 '16 at 16:53
  • Are your input polygons always convex, as in your example? – Doc Brown Feb 3 '16 at 16:55
  • @DocBrown Any format will work really, I just chose this format because I saw it somewhere and guessed it's the major one, but I would love to get corrected. – Sergey Lukin Feb 3 '16 at 16:57
6

Not solvable. I tried a number of methods until i realized it couldn't be done.

Assume a shape with area 4, which should be divided in 2 parts with area 2 each:

squares

The leftmost triangle and square must be part of shape 1, but it needs another triangle. The only place that could be taken from is the square to the right, but then the remainder is split in two regions.

  • 2
    Not solvable in general of course, but I guess the OP could be interested in an algorithm which solves the problem for each case where it can be solved, and otherwise outputs that it cannot be solved ;-) Gave you an upvote, either. – Doc Brown Feb 4 '16 at 16:56
  • Good catch. I didn't think about it. We could either add an assumption that area is valid as long it consists of path coordinates that are not intercepted by other areas which would result in [ [0,1, 2,1, 2,2, 3,2, 2,3, 2,2 1,2], [2,2, 2,0, 3,0, 3,2] ] either accept the fact that an exception is thrown in case the function iterated over all variants and didn't find a match. What do you think? – Sergey Lukin Feb 4 '16 at 17:03
  • For the sake of simplicity I've added an assumption that only solvable variations of polygon and number of areas are passed as an input. See my edit. Thank you – Sergey Lukin Feb 4 '16 at 17:18
6

As I said in my comment to Doc Browns (otherwise excellent) answer, there is a matter of choice of square->triangle division which makes it slightly harder to device an algorithm. Also, you don't have to make it serially, but can do it in parallell, as some of my suggestions show.

I made several heuristic approaches at first.

Voronoi: Choose N points (non-integer coordinates) in the shape, create a voronoi map. Let the points attract and repel each other with respect to their area (too large attracts, too small repels).

Useful for large A/N, easy to fall into local maxima.

Circle method: The goal is to remove problematic areas, and then to continue using another method.

Choose a point (non-integer) in the interior, and a radius r. The interior minus the circle will create k disconnected subregions. If any of the subregions are of size A/n, remove it. Also, if any is 2*A/n, it should be easy to split it, and remove them also. Lower the radius slightly, and continue (possibly use some binary search).

Problematic point growth: Begin using the method Doc Brown mentions, but since there are two choices at most edges, skip the graph and grow each region on the border in a way to create as few new problematic points as possible (problematic points=triangles only sharing one edge with the rest of the shape). E.g. when choosing new neighbors to include, add them in order of convexity (concave = negative convexity)

Ribbon growth: For almost convex or convex areas. Choose a point on the exterior edge, make a unit width ribbon follow the exterior edge until it has the right length, making sure to never create a new disconnected point. If necessary, skip the last triangles and make it grow slightly in width. Let the next ribbon follow where the last ended until the final area is of the right size.

Game-like or organic: Create N "countries". Put them in random spots. Let them grow organically. When they meet each other, the one with the smallest current area is the strongest and wins the triangle. Probably prone to local maxima?

3

The general strategy should be to remove the first piece of area A/n from your polygon P0 (where A is the total area), leaving you with a new polygon P1 of area A-A/n. Then repeat this producing a polygon P2, then P3, and after n repetitions, you have your solution. Note that it is possible at each step that you cannot find such a new piece where the remaining parts still form a connected polygon, in which you have to go back one step and try to find a another piece, or stop the algorithm without a result.

To construct such piece of size A/n, start by dividing up your polygon into "grid pieces". Any grid square inside the polygon forms such a piece, as well as any triangle shaped half-square where the border of the polygon divides the square into two halfs. You can utilize a point-in-polygon test for this, iterate over all half-squares inside the bounding box of the polygon and test if their midpoint is inside the given polygon (if both halfs of a square are contained, one can use the full square instead). Next, you create a planar graph, where each of the pieces define a vertice (with an "area" or "weight" of either 1 or 1/2). The edges of that graph are given by the neighboured pieces. This reduces your geometric problem to a graph problem, where you are looking for a connected sub-graph with vertices of total weight A/n , and the remaining graph is still connected.

The latter problem might be solved by a backtracking approach. Start with one vertice which can be removed from the graph without making it unconnected. You can pick the vertice randomly, if you like, or shuffle the list of all vertices randomly once, for reuse in the following steps. Now try to find a second vertice which is connected to the first one, which can be removed from the remaining graph without destroying its connectedness, too. If there are multiple possibilities, pick one randomly. For vertices representing a square, you can also allow a graph operation where you split up the square into two triangles (this creates new vertices of weight 1/2) by either one or the other possible way. This is only a little bit more complicated than just moving one vertice from the original graph to the sub-graph, but it should not be too difficult at all.

Repeat that until your subgraph reaches a total weight A/n, or you don't find another vertex. If that is the case, "backtrack" one level and try a different vertice first.

There are several ways to optimize this, for example, you have to pick a fast connectivity test for graphs. I guess you will find a lot of algorithms for this sub problem, use Google, or start here. It may be worth looking for an algorithm which can quickly verify if a connected graph is still connected when one vertex is removed.

Hope this helps.

  • This sounds just exactly what I needed. I've pictured this strategy in theory and it all makes sense to me so far, it's now time for me to put it into practice. I will report back when I'll have something to show. Thank you so much! – Sergey Lukin Feb 4 '16 at 18:27
  • I think there is a slight problem with this approach. For every square, there are two possible choices of triangles. To actually check all of them and guarantee a solution in case there is one, i guess you'd need to do it for all 2^n choices. – NiklasJ Feb 4 '16 at 19:44
  • @NiklasJ: you are correct, see my improved answer which takes this into account. – Doc Brown Feb 5 '16 at 7:51
  • @SergeyLukin: I changed my answer a little bit to take NiklasJ's comment into account. – Doc Brown Feb 5 '16 at 8:00

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.