Centers of Polygons in OPL
Ryan J. O'Neil has written an interesting post on cent Here is an example used by Ryan. The polygon is defined by the set of its vertices in clockwise order around the polygon. V = {(1,1), (2,5), (5,4), (6,2), (4,1)}
Figure credit: Ryan J. O'Neil The Chebyshev center (x,y) maximizes the minimum of the distances to the edges of the polygon. There are 3 decision variables the radius of the circle: r, and the two coordinates of its center: x, and y. The crux of the problem is to express that r is smaller than the distances between the center and the lines defined by two consecutive vertices. Let (x_{1}, y_{1}) , and (x_{2}, y_{2}) be two consecutive vertices. We define dx = x_{2} - x_{1}, and dy = y_{2} - y_{1}. Let (x,y) be a point in the polygon. We define two vectors, e = (dy, -dx), and v = (x - x_{1}, y - y_{1}). The point is on the line defined by the two vertices if and only if e . v = 0 More generally, all the points in the polygon satisfy the constraint e . v >= 0 Let l be the L2 norm of the vector e: l = sqrt(dx^{2} + dy^{2}) The distance d of the point (x,y) to the line is d = (e/l) . v We then want to state that r is less than this distance, i.e. r * l <= e. v i.e. r * l <= dy*(x-x_{1}) - dx*(y - y_{1}) The following model states the above constraint for each edge of the polygon.
tuple vertex { Solving this model yields
r = 1.7466;
Figure credit: Ryan J. O'Neil So far, we have implemented in OPL a model equivalent to the one Ryan described in his post. After presenting his model, Ryan asked this question: in certain circumstances, such as rectangles, the Chebyshev center is ambiguous. How might one get around this ambiguity? One way to answer is to add a secondary objective that favors points that are at equal distance of all vertices if possible. A simple way to implement it is to add the sum of squared distances of the Chebyshev center to vertices. This sum is minimized when all distances are equal if possible. As we want to use this as a secondary objective to break ties, we add it with a small multiplier, eg 1/100. The problem is now a mixed integer quadratic problem. Fortunately, the quadratic part is definite positive (always positive) as it is a sum of squares. Therefore, the problem is a convex optimization problem with a single minimum. Here is the resulting model. It yields the same result as before (up to the default display precision) for the polygon Ryan used, and it yields the intuitive center when used with a rectangle.
tuple vertex { Update on Feb 11. Note that we could also just keep the quadratic part of the objective, i.e. minimize the sum of squared distances to vertices. This is the Fréchet mean of the vertices. It is computed by the following model
tuple vertex { Solving this model yields
Note that the Fréchet mean is skewed towards areas where vertices are close to each other. In the above example it is a bit to the right of where I would place the center of the polygon. A better way could be to use the alternate definition of Chebyshev center, which is the center of the smallest circle containing the polygon. It is not difficult to see that it yield the intuitive center for rectangles. The crux of the problem is simply to state that the radius is this time greater than the distances of the center to the vertices. The following model expresses this.
tuple vertex { Solving this model yields
We have described three ways to compute the center of a (convex) polygon, namely:
Which one is best depends on your taste. The latter two are possible answers to Ryan's question given they give a non ambiguous answer for rectangles. Note that we can blend various definitions by combining them via the objective function, as we did when adding 1/100 of the Fréchet mean to the inner chebyshev center objective. Acknowledgements I want to thank my colleagues Vincent Beraudier and Pierre Bonami for their advice on how to model these problems.. |