Cómo encontrar el punto más alejado de un conjunto determinado y su cuadro delimitador

Question

Tengo un cuadro delimitador y una cantidad de puntos dentro de él. Me gustaría agregar otro punto cuya ubicación esté más alejada de cualquier punto agregado anteriormente, así como también muy lejos de los bordes de la caja.

¿Existe una solución común para este tipo de cosas? ¡Gracias!

Answer 1

Aquí hay un pequeño programa de Mathematica.

Aunque solo hay dos líneas de código (!) probablemente necesite más en un lenguaje convencional, así como una biblioteca matemática capaz de encontrar el máximo de funciones.

Supongo que no dominas Mathematica, así que te explicaré y comentaré línea por línea.

Primero creamos una tabla con 10 puntos aleatorios en {0,1} x {0,1}, y le damos el nombre p.

p = Table[{RandomReal[], RandomReal[]}, {10}]; 

Ahora vamos a crear una función para maximizar:

f[x_, y_] = Min[ x^2, 
       y^2, 
       (1 - x)^2, 
       (1 - y)^2, 
       ((x - #[[1]])^2 + (y - #[[2]])^2) & /@ p]; 

Ja! ¡La sintaxis se volvió complicada! Vamos a explicar:

La función le da para cualquier punto en {0,1} x {0,1} la distancia mínima desde ese punto hasta nuestro conjunto p Y los bordes. Los primeros cuatro términos son las distancias a los bordes y el último (difícil de leer, lo sé) es un conjunto que contiene la distancia a todos los puntos.

Lo que haremos a continuación es maximizando esta función, por lo que obtendremos el punto donde la distancia mínima a nuestros objetivos es máxima.

Pero primero echemos un vistazo a f []. Si lo miras críticamente, verás que no es realmente la distancia, sino la distancia al cuadrado. Lo definí así, porque de esa manera la función es mucho más fácil de maximizar y los resultados son los mismos.

También tenga en cuenta que f [] no es una función "bonita". Si dibujamos en {0,1}, obtenemos algo como:

Es por eso que se necesita un paquete de matemáticas agradable para encontrar el máximo.

Mathematica es un paquete tan agradable, que podamos maximizar la cosa clara:

max = Maximize[{f[x, y], {0 <= x <= 1, 0 <= y <= 1}}, {x, y}]; 

Y eso es todo. La función Maximizar devuelve el punto y la distancia al cuadrado a su borde/punto más cercano.

HTH! Si necesita ayuda para traducir a otro idioma, deje un comentario.

Editar

Aunque no soy un C# persona, después de buscar referencias en SO y buscando en Google, llegó a esto:

Un paquete candidato es DotNumerics

Debe seguir el

file: \DotNumerics Samples\Samples\Optimization.cs 
Example header: 

    [Category("Constrained Minimization")] 
    [Title("Simplex method")] 
    [Description("The Nelder-Mead Simplex method. ")] 
    public void OptimizationSimplexConstrained() 

HTH: ejemplo proporcionado en el paquete siguiente!

Answer 2

El nombre del problema que resuelve es the largest empty sphere problem.

Se puede resolver fácilmente en O (n^4) en el avión. Simplemente considere todos los O (n^3) triples de puntos y calcule su circuncentro. Uno de estos puntos es tu punto deseado. (Bueno, en tu caso, también debes considerar "un lado" como uno de tus tres puntos, para que no solo encuentres circuncentros sino puntos un poco más generales, como equidistantes de dos puntos y un lado.)

Como indica el enlace de Wikipedia anterior, el problema también se puede resolver en el tiempo O (n log n) mediante el cálculo de un diagrama de Voronoi. Más específicamente, entonces su punto deseado es el circuncentro de uno de los triángulos en la triangulación de Delaunay de sus puntos (que es el dual del diagrama de Voronoi), del cual solo hay O (n). (De nuevo, para adaptarse exactamente a su problema, tendrá que considerar los efectos de los lados de la caja.)