Programar un puntaje de circularidad

15

Su tarea es programar una función matemática s, que toma un conjunto finito Ade puntos no vacíos en el plano 2D, y genera un puntaje de circularidad s(A)que satisface las siguientes propiedades:

  1. Definitividad positiva : si hay un círculo o una línea recta que contiene todos los puntos de A, entonces s(A) = 0. De otra maneras(A) > 0
  2. Surjectividad: es surjective a los números reales no negativos, lo que significa que para cada número real no negativo rhay un subconjunto finito Adel plano tal que s(A) = r.

  3. Invariancia de traducción: s es invariante de traducción si s(A) = s(A + v)para cada vector vy para todos A.

  4. Invarianza de escala: s es invariante de escala, si s(A) = s(A * t)para todos t≠0y para todos A.

  5. Continuidad. sse dice que es continua si la función f(p) := s(A ∪ {p})(mapear un punto pa un número real) es continua usando el valor absoluto estándar en los números reales y la norma euclidiana estándar en los puntos del plano.

Hablando intuitivamente, esta puntuación de falta de circularidad puede considerarse como algo similar al coeficiente de correlación en la regresión lineal.

Detalles

Su función en teoría tiene que funcionar en los reales, pero para el propósito de este desafío puede usar números de coma flotante como sustituto. Proporcione una explicación de su envío y un argumento de por qué se mantienen esas cinco propiedades. Puede tomar dos listas de coordenadas o una lista de tuplas o formatos similares como entrada. Puede suponer que no se repite ningún punto en la entrada, es decir, todos los puntos son únicos.

falla
fuente
1
¿Podría agregar algunos casos de prueba?
Shaggy
¿Qué significa que un círculo contenga todos los puntos de A ?
H.PWiz
@ H.PWiz Considere un círculo como un subconjunto del plano 2d, el punto a está contenido en el círculo si es un elemento de este subconjunto.
defecto
@Shaggy No, eso no es posible ya sque no es único. Lo único para lo que podría hacer ejemplos es para s(A) = 0qué es trivial hacerlo usando la primera propiedad.
flawr
¿Puede nuestro programa cometer un error en probabilidad teóricamente cero? (la probabilidad real es distinta de cero porque el número de coma flotante es discreto) / ¿Permite que se ignore la imprecisión de coma flotante? Meta relevante .
usuario202729

Respuestas:

2

Python 2 con numpy, 116 bytes

from numpy import*
def f(x,y):a=linalg.lstsq(hstack((x,y,ones_like(x))),(x*x+y*y)/2);return a[1]/sum((x-a[0][0])**4)

Toma x e y como vectores de columna 2d y devuelve una matriz que contiene la respuesta. Tenga en cuenta que esto dará una matriz vacía para una línea perfectamente recta o con 3 o menos puntos. Creo que lstsq no da residuos si hay un ajuste perfecto.

Explicación

Esencialmente, esto encuentra el círculo de mejor ajuste y obtiene los residuos al cuadrado.

Queremos minimizar (x - x_center)^2 + (y - y_center)^2 - R^2. Se ve desagradable y no lineal, pero puede volver a escribir que a medida x_center(-2x) + y_center(-2y) + stuff = x^2 + y^2, donde el stuffsigue siendo desagradable y no lineal en términos de x_center, y_centery R, aunque no es necesario preocuparse por ello. Entonces podemos resolverlo [-2x -2y 1][x_center, y_center, stuff]^T = [x^2 + y^2].

Entonces podríamos retroceder R si realmente quisiéramos, pero eso no nos ayuda mucho aquí. Afortunadamente, la función lstsq puede darnos los residuos, que satisfacen la mayoría de las condiciones. Restar el centro y escalar (R^2)^2 = R^4 ~ x^4nos da invariancia traslacional y de escala.

  1. Esto es positivo definido porque los residuos al cuadrado no son negativos, y estamos dividiendo por un cuadrado. Tiende hacia 0 para círculos y líneas porque estamos ajustando un círculo.
  2. Estoy bastante seguro de que no es sobreyectivo, pero no puedo encontrar un buen límite. Si hay un límite superior, podemos asignar [0, límite) a los reales no negativos (por ejemplo, con 1 / (límite - respuesta) - 1 / límite) para algunos bytes más.
  3. Restamos el centro, por lo que es traslacionalmente invariable.
  4. Dividimos por x ** 4, lo que elimina la dependencia de la escala.
  5. Está compuesto de funciones continuas, por lo que es continuo.

fuente
¿Puedes elaborar lo que tu sumisión realmente está computando?
flawr
@flawr lo editó en.
Traté de probar esto en {(1, 0), (2, 0), (3, 0), (4, t)} para t → 0, pero f(array([[1.0],[2.0],[3.0],[4.0]]),array([[0.0],[0.0],[0.0],[t]]))parece darme array([ 0.00925926])todo lo que no sea cero t. (Sé que dijiste que esto se rompe para t = 0, pero el resultado al menos debería acercarse a 0 para t → 0.) ¿Lo estoy llamando mal?
Anders Kaseorg
2

Python, 124 bytes

lambda A:sum(r.imag**2/2**abs(r)for a in A for b in A for c in A for d in A if a!=d!=b!=c for r in[(a-c)*(b-d)/(a-d)/(b-c)])

Toma A como una secuencia de números complejos ( x + 1j*y), y resume Im ( r ) 2 /2 | r | para todas las relaciones cruzadas complejas r de cuatro puntos en A .

Propiedades

  1. Definitividad positiva. Todos los términos no son negativos, y todos son cero exactamente cuando todas las relaciones cruzadas son reales, lo que sucede cuando los puntos son colineales o cíclicos.

  2. Surjetividad Dado que la suma puede hacerse arbitrariamente grande agregando muchos puntos, la surjectividad seguirá a partir de la continuidad.

  3. Invariancia de traducción. La relación cruzada es invariante de traducción.

  4. Invarianza de escala. La relación cruzada es invariante de escala. (De hecho, es invariable en todas las transformaciones de Möbius).

  5. Continuidad. La razón doble es un mapa continuo al plano complejo extendido, y r ↦ Im ( r ) 2 /2 | r | (con ∞ ↦ 0) es un mapa continuo desde el plano complejo extendido hasta los reales.

(Nota: un mapa teóricamente más bonito con las mismas propiedades es r ↦ (Im ( r ) / ( C + | r | 2 )) 2 , cuyas líneas de contorno wrt los cuatro puntos de la relación cruzada son circulares. Si realmente necesita una medida poco circular, probablemente quieras esa).

Anders Kaseorg
fuente