2
$\begingroup$

I need to place a given finite set of points within maximum distance of each other on 2D, constrained by a convex boundary, on Python.

Honestly, I'm kind of lost. I have the explicit function to be minimized, but I'm not sure which algorithm I should use to adjust the points recursively. I thought of experimenting with clustering but I'm not sure if this would work.

And, more importantly, I have no idea how to bound the space.

Unfortunately, the convex boundary isn't a rectangle as well; it looks like this:

enter image description here

$\endgroup$
3
  • 1
    $\begingroup$ This sounds like a problem in the constrained optimization class. The constraints come from the domain shape, one just needs to produce the objective function, like $\sqrt(\sum(r_i-r_j)^2/N)$, or something like that, and put it in the standard optimization solver in Python. This problem is difficult to solve for a large number of points, but perhaps some simplified formulation could be found, using the physics intuition etc. What is the purpose of this distribution of points? $\endgroup$ May 24 at 23:08
  • $\begingroup$ Thanks for the input! I'm going to use it to simulate phoneme distributions. $\endgroup$ Jun 8 at 19:00
  • $\begingroup$ While it is clear what maximizing the distance between two points inside a (convex, bounded) region should mean, a careful definition is needed for extending this problem to more points. @Cesareo has articulated a max-min objective function, which seems natural and fairly robust. But other choices are possible. $\endgroup$
    – hardmath
    Jul 6 at 22:20

1 Answer 1

1
$\begingroup$

Giving a region $\Omega(p)$ and a set of $n$ points $p_i,\ i = 1,\cdots, n$ the problem can be stated as a maximization one.

$$ \max\left(\min_{i\ne j} \|p_i-p_j\|\right),\ \ \text{such that}\ \ \forall k,\ p_k\in \Omega(p) $$

One way to tackle this problem is by using Evolutive Strategies (CMA-ES). Follows a setup in python

n = 7
penality = 10000000000000


ae = 2
be = 1.1442

def feasible(x, y):
    xa = x / ae
    yb = y / be
    dif1 = xa * xa + yb * yb - 1
    dif2 = -(x + 1)

    if  dif1 < 0 and dif2 < 0:
        return 0
    else:
        return max(dif1,dif2)



def objective(p):
    dist_min = 100000
    for i in range(n):
        xi = p[2*i]
        yi = p[2*i+1]
        fi = feasible(xi, yi) 
    
        if fi > 0:
            return penality
        for j in range(i):
            xj = p[2*j]
            yj = p[2*j+1]
        
            fj = feasible(xj, yj)
            if fj > 0:
                return penality
            dx = xi - xj
            dy = yi - yj
            dist = np.sqrt(dx*dx + dy*dy)
             
            if dist < dist_min:
                dist_min = dist  
            
                
    return -dist_min



import numpy as np
import matplotlib.pyplot as plt
from cmaes import CMA

best_value = 100000000
best = []

if __name__ == "__main__":
    optimizer = CMA(mean = np.zeros(2*n), sigma = 0.45)

    for generation in range(4000):
        solutions = []
        for _ in range(optimizer.population_size):
            x = optimizer.ask()
            value = objective(x)
            if value < best_value:
                best.append([generation,-value])
                best_value = value
                x_best = x
            solutions.append((x, value))
        optimizer.tell(solutions)
    
print(best)
print(x)

X = []
Y = []
for i in range(n):
    X.append(x_best[2*i])
    Y.append(x_best[2*i+1])

print(X)
print(Y)

angle = np.linspace( 0 , 2 * np.pi , 150 ) 

radius = 2

xc = ae * np.cos( angle ) 
yc = be * np.sin( angle ) 
xs = [-1, -1]
ys = [-1,  1]

(figure, axes) = plt.subplots( 1 ) 

axes.plot( xc, yc, color = 'b' ) 
axes.plot( xs, ys, color = 'b' )
axes.scatter(X,Y,marker = 'o', color = 'k' )
axes.set_aspect( 1 ) 
plt.show()

enter image description here

$\endgroup$

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.