algorithm - semicirculo - ¿Qué algoritmo puedo usar para determinar puntos dentro de un semicírculo?

rectangulo inscrito en un semicirculo

Question

Tengo una lista de puntos bidimensionales y quiero obtener cuál de ellos cae dentro de un semicírculo.

Originalmente, la forma del objetivo era un rectángulo alineado con los ejes xey. Entonces, el algoritmo actual ordena los pares por sus coordenadas X y búsquedas binarias al primero que podría caer dentro del rectángulo. Luego itera sobre cada punto secuencialmente. Se detiene cuando choca con uno que está más allá del límite superior X e Y del rectángulo objetivo.

Esto no funciona para un semicírculo ya que no se puede determinar un límite x / y efectivo superior / inferior para él. El semicírculo puede tener cualquier orientación.

En el peor de los casos, encontraré el valor mínimo de una dimensión (digamos x) en el semicírculo, búsqueda binaria en el primer punto que está más allá y luego probaré los puntos secuencialmente hasta superar el límite superior de esa dimensión. Básicamente prueba el valor de puntos de una banda completa en la grilla. El problema es que esto terminará verificando muchos puntos que no están dentro de los límites.

Answer 1

"Quizás puedan forzarlo brutalmente ya que tienen una GPU completa dedicada a ellos".

Si tiene una GPU a su disposición, entonces hay más formas de hacerlo. Por ejemplo, usando un buffer de esténcil:

• borre el buffer de esténcil y configure la operación del esténcil para incrementar
• renderiza tu semicírculo en el buffer de esténcil
• renderiza tus puntos
• vuelve a leer los píxeles y verifica los valores en tus puntos
• los puntos que están dentro del semicírculo se habrían incrementado dos veces.

Este artículo describe cómo se pueden usar los búferes de stencil en OpenGL.

Answer 2

Aquí hay parte de una función que escribí, obtienes un arco de disparo de cono para un arma en un juego basado en fichas.

float lineLength;
float lineAngle;
for(int i = centerX - maxRange; i < centerX + maxRange + 1; i++){
    if(i < 0){
        continue;
    }
    for(int j = centerY -  maxRange; j < centerY + maxRange + 1; j++){
        if(j < 0){
            continue;
        }

        lineLength = sqrt( (float)((centerX - i)*(centerX - i)) + (float)((centerY - j)*(centerY - j)));
        lineAngle = lineAngles(centerX, centerY, forwardX, forwardY, centerX, centerY, i, j);

        if(lineLength < (float)maxRange){
            if(lineAngle < arcAngle){
                if( (float)minRange <= lineLength){ 
                    AddToHighlightedTiles(i,j);
                }
            }
        }
    }
}

Las variables deben ser autoexplicativas y la función de ángulos de línea toma 2 líneas y encuentra el ángulo entre ellas. El forwardX y el forwardY son solo un mosaico en la dirección correcta desde el centro X e Y en función del ángulo al que apunta. Estos se pueden obtener fácilmente con una declaración de cambio.

float lineAngles(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4){
    int a = x2 - x1;
    int b = y2 - y1;
    int c = x4 - x3;
    int d = y4 - y3;

    float ohSnap = ( (a * c) + (b * d) )/(sqrt((float)a*a + b*b) * sqrt((float)c*c + d*d) );
    return acos(ohSnap) * 180 / 3.1415926545f;
}

Answer 3

La forma más rápida de hacerlo dependerá de sus datos típicos. Si tienes datos del mundo real para mirar, hazlo primero. Cuando los puntos están fuera del semicírculo, ¿suele ser porque están fuera del círculo? ¿Son sus semicírculos rebanadas de pastel típicamente finas?

Hay varias formas de hacer esto con vectores. Puede escalar el círculo a un círculo unitario y usar productos cruzados y observar los vectores resultantes. Puede usar productos punto y ver cómo el punto prospectivo aterriza en los otros vectores.

Si quieres algo realmente fácil de entender, primero asegúrate de que esté dentro del círculo, luego obtén el ángulo y asegúrate de que esté entre el ángulo de los dos vectores que dictan el semicírculo.

Editar: Había olvidado que un semicírculo siempre es medio círculo. Estaba pensando en cualquier sección arbitraria de un círculo.

Ahora que he recordado qué es un semicírculo, así es como lo haría. Es similar a la solución de stbuton, pero representa el semicírculo de manera diferente.

Yo representaría el semicírculo como el vector unitario que divide el semicírculo. Puedes obtenerlo fácilmente desde cualquiera de los vectores que indican el límite del semicírculo (porque están a 90 grados de la representación) al intercambiar x e y y anular uno de ellos.

Ahora solo cruzas el vector creado al restar el punto que se va a probar desde el centro del círculo. El signo de z te dice si el punto está en el semicírculo, y la longitud de z se puede comparar con el radio.

Hice toda la física para Cool Pool (de Sierra Online). Todo se hace en vectores y está lleno de puntos y cruces. Las soluciones de vectores son rápidas. Cool Pool pudo correr con un P60 e hizo descansos razonables e incluso giro.

Nota: para las soluciones en las que está comprobando sqrt (x x + y y), ni siquiera haga el sqrt. En cambio, mantén el cuadrado del radio y compáralo con eso.

Answer 4

Primero, traduzca y gire el semicírculo de modo que un extremo esté en el eje X negativo, y el otro extremo en el eje X positivo, centrado en el origen (por supuesto, no lo va a traducir ni rotar) , obtendrá los números apropiados que traducirían y rotarán, y los usará en el próximo paso).

Entonces, puedes tratarlo como un círculo, ignorando todos los valores y negativos, y simplemente probar usando la raíz cuadrada de la suma de los cuadrados de X e Y, y ver si es menor o igual al radio.

Answer 5

Puedes encontrar puntos en un círculo y puntos en un lado de una determinada pendiente, ¿verdad?

Solo combina los dos.

Answer 6

Si hay un algoritmo estándar para hacer esto, estoy seguro de que alguien más se le ocurrirá, pero si no: puede intentar ordenar los puntos por distancia desde el centro del círculo e iterar solo aquellos cuya distancia es menor que la radio del semicírculo. O si calcular la distancia es caro, trataría de encontrar el cuadro delimitador del semicírculo (o incluso el cuadrado delimitador del círculo del que forma parte el semicírculo) e iterar sobre los puntos en ese rango. Hasta cierto punto, depende de la distribución de los puntos, es decir, ¿espera que la mayoría de ellos o solo una pequeña fracción caiga dentro del semicírculo?

Answer 7

Supongo que alguien encontró la misma solución que yo aquí, pero no tengo ningún código que mostrar, ya que está muy lejos en mi memoria ...

Lo haría por pasos ...
1. Me gustaría ver si estoy dentro de un círculo ... si es así, mira en qué lado del círculo.
2. Dibujando un vector normal que proviene del vector hecho por la semiesfera. Podría saber si estoy detrás o frente al vector ... y si sabes de qué lado es la semiesfera y de qué lado es el vacío ... Será bastante fácil de encontrar si estás dentro del semi esfera. Tienes que hacer el producto de punto.

No estoy seguro de si es lo suficientemente claro, pero la prueba no debería ser tan difícil de hacer ... Al final tienes que buscar un valor negativo o positivo ... si es 0 estás en el vector de la semiesfera, así que depende de usted decir si está afuera o dentro de la semiesfera.

Answer 8

• traducir el centro del arco al origen
• calcular el ángulo entre el eje de ordenadas y los puntos extremos de los radios de semicírculo
• traducir el punto en cuestión por el mismo dx, dy

• calcular la distancia desde el origen hasta la x, y del punto traducida, si d> radio del círculo / eliminar el arco

  • calcular el ángulo entre el eje de ordenadas y el punto final
  • si el ángulo no está entre el arco inicial y el final del semicírculo, elimine

  la reposición de puntos debe estar dentro del semicírculo

Answer 9

Parece que un esquema simple funcionará aquí.

1. Reduzca la cantidad de puntos en el conjunto, calculando primero el casco convexo. Solo los puntos en el casco convexo contribuirán a cualquier interacción con cualquier forma de contorno convexa. Por lo tanto, conserve solo el subconjunto de puntos en el perímetro del casco.

2. Se puede argumentar fácilmente que el semicírculo delimitador de radio mínimo debe tener un borde (dos puntos) del casco convexo coincidente a lo largo del diámetro del semicírculo. Es decir, si un borde del casco no se encuentra en el diámetro, entonces existe un semicírculo diferente con un diámetro más pequeño que contiene el mismo conjunto de puntos.

3. Pruebe cada borde en secuencia. (Un casco convexo a menudo tiene relativamente pocos bordes, por lo que esto irá rápidamente). Ahora se convierte en un simple problema de minimización en 1-d. Si elegimos asumir que el borde en cuestión se encuentra en el diámetro, entonces simplemente necesitamos encontrar el centro de la esfera. Debe estar a lo largo de la línea actual que consideramos que es el diámetro. Entonces, en función de la posición del punto a lo largo del diámetro actual, simplemente encuentre el punto que se encuentra más alejado del centro nominal. Al minimizar esa distancia, encontramos el radio del semicírculo mínimo a lo largo de esa línea como un diámetro.

Ahora, simplemente elija el mejor de los semicírculos que se encuentran sobre todos los bordes del casco convexo.

Answer 10

Si sus puntos tienen coordenadas enteras, la solución más rápida puede ser una tabla de búsqueda. Como un semicírculo es convexo, para cada coordenada y, obtienes un rango fijo de x, por lo que cada entrada en tu tabla de búsqueda da coordenadas X máximas y mínimas.

Por supuesto, todavía necesita precalcular la tabla, y si su semicírculo no está fijo, puede estar haciendo mucho. Dicho esto, esto es básicamente una parte de lo que se hubiera hecho una vez para formar un semicírculo: la forma completa se representaría como una serie de tramos horizontales llamando repetidamente a una función de trazado de líneas horizontales.

Para calcular los tramos en primer lugar (si necesita hacerlo de forma repetida), probablemente quiera buscar una copia antigua de la Programación Zen de Gráficos de Michael Abrash. Eso describía el algoritmo de línea conocido de Bresenhams y el algoritmo de círculo de Hardenburgh no tan conocido. No debería ser demasiado difícil combinar las versiones orientadas al rango de los dos para calcular rápidamente los tramos de un semicírculo.

IIRC, Hardenburgh usa x ^ 2 + y ^ 2 = radio ^ 2, pero explota el hecho de que estás pasando por tramos para evitar el cálculo de las raíces cuadradas, creo que usa el hecho de que (x + 1) ^ 2 = x ^ 2 + 2x + 1 y (y-1) ^ 2 = y ^ 2 - 2y + 1, manteniendo los valores de ejecución para x, y, x ^ 2 y (radio ^ 2 - y ^ 2), por lo que cada paso solo requiere una comparación (es la corriente x ^ 2 + y ^ 2 muy grande) y algunas adiciones. Se realiza solo por un octante (la única forma de garantizar pasos de un solo píxel) y se extiende al círculo completo a través de la simetría.

Una vez que tenga los tramos del círculo completo, debería ser fácil usar Bresenhams para cortar la mitad que no desea.

Por supuesto, solo harías todo esto si estás absolutamente seguro de que lo necesitas (y que puedes trabajar con números enteros). De lo contrario, quédate con stbuton.

Answer 11

Comprobar si un punto está dentro o fuera de un semicírculo (o un rectángulo para el caso) es una operación de tiempo constante.

Verificando N puntos que se encuentran dentro o fuera de un semicírculo o rectángulo es O (N).

La clasificación de tus N puntos es O (N * lg (N)).

Es asintóticamente más rápido probar todos los puntos de forma secuencial que clasificar y luego realizar un sacrificio rápido de los puntos en función de una búsqueda binaria.

Este puede ser uno de esos momentos en los que lo que parece rápido y lo que es rápido son dos cosas diferentes.

EDITAR

También hay una forma absolutamente simple de probar la contención de un punto en el semicírculo sin rechinar con rotaciones, transformaciones y similares.

Represente el semicírculo como dos componentes:

• un segmento de línea del punto a a b que representa el diámetro del semicírculo
• una orientación de izquierda o derecha para indicar que el semicírculo está a la izquierda o derecha del segmento de línea ab cuando se viaja de aa b

Puede explotar la regla de la mano derecha para determinar si el punto está dentro del semicírculo.

Luego, un pseudocódigo para probar si el punto p está en el semicírculo como:

procedure bool is_inside:
    radius = distance(a,b)/2
    center_pt = (a+b)/2    
    vec1 = b - center_pt
    vec2 = p - center_pt
    prod = cross_product(vec1,vec2) 
    if orientation == ''left-of''
        return prod.z >= 0 && distance(center_pt,p) <= radius
    else
        return prod.z <= 0 && distance(center_pt,p) <= radius

Este método tiene el beneficio adicional de no usar ninguna función trigonométrica y puedes eliminar todas las raíces cuadradas al comparar con la distancia cuadrada. También puede acelerarlo almacenando en caché el cómputo "vec1", el cálculo del radio, el cálculo de center_pt y reordenar algunas de las operaciones para liberar el fianza anticipadamente. Pero estaba tratando de ir por claridad.

El ''cross_product'' devuelve un valor (x, y, z). Comprueba si el componente z es positivo o negativo. Esto también se puede acelerar al no usar un producto cruzado verdadero y solo calcular el componente z.