Es un punto dentro del hexágono regular

Question

Estoy buscando consejos sobre la mejor manera de proceder. Estoy tratando de encontrar si un punto dado A: (a, b) está dentro de un hexágono regular, definido con el centro O: (x, y) y el diámetro del círculo circunscrito.

Parece excesivo usar Ray-casting, o Winding-number para determinar esto, para un caso tan simple, y actualmente estoy buscando la opción de encontrar el ángulo (de horizontal) de la línea OA, y "normalizar" (probablemente no sea la palabra correcta) en uno de los 6 triángulos equiláteros y ver si este nuevo punto se encuentra dentro de este triángulo.

tengo la sensación de que me falta algo simple, y no hay una manera fácil (o si soy muy afortunado, una API de Java) para hacer esto de forma sencilla y eficiente.

Gracias por su ayuda.

Editar: El hexágono está orientado de modo que uno de los lados es plano con el horizontal.

Answer 1

Puede usar las ecuaciones para cada uno de los lados del hexágono; con ellos puedes averiguar si un punto dado está en el mismo semiplano que el centro del hexágono.

Por ejemplo, el lado superior derecho tiene la ecuación:

-sqrt(3)x - y + sqrt(3)/2 = 0 

Se conecta esto las coordenadas del punto y luego las coordenadas del centro. Si los resultados tienen el mismo signo, entonces el punto está en el semiplano de abajo a la izquierda (por lo que puede estar dentro del hexágono).

A continuación, repetir utilizando las ecuaciones de los otros lados.
Tenga en cuenta que este algoritmo funcionará para cualquier polígono convexo.

Answer 2

Parece que sabes solución general: "Se parece un exceso de usar ...". Así que aquí es mi idea:

Calcular la distancia del punto al centro y vamos a llamarlo l.

Luego puede compararlo con inradius (r) y circumradius (R). si l < r, el punto está dentro del hexágono, si l > R y luego afuera. Si es r < l < R, entonces tiene que verificar contra cada lado, respectivamente, pero dado que R - r es muy pequeño (13% de la longitud del lado del hex), la probabilidad de que tenga que hacer cálculos complejos es muy pequeña.

Las fórmulas se pueden encontrar aquí: http://mathworld.wolfram.com/Hexagon.html

Answer 3

primero habría que hacer si el punto está dentro del círculo inscrito (se puede calcular el radio del círculo inscrito fácilmente) o fuera del círculo circunscrito (que ya tiene).

El primero significa que el punto está en, este último significa que está fuera.

Estadísticamente, la mayoría de los puntos de entrada deben permitirá decidir sobre la base de las pruebas anteriormente indicados.

Para el peor de los casos (el punto está entre los círculos inscritos y circunscritos), creo que puede encontrar los dos vértices más cercanos al punto y luego ver en qué lado del segmento V1V2 está el punto (interior o externo, en relación con el centro O). Caso especial: el punto es igual a uno de los vértices => está.

Si tengo una idea más inteligente (o si alguna vez comenzaré realmente a aprender trigonometría), editaré la respuesta para hacerle saber :)

Answer 4

Si reduce el problema a la comprobación de {x = 0, y = 0, d = 1} en un solo cuadrante, puede hacerlo muy simple.

public boolean IsInsideHexagon(float x0, float y0, float d, float x, float y) { 
    float dx = Math.abs(x - x0)/d; 
    float dy = Math.abs(y - y0)/d; 
    float a = 0.25 * Math.sqrt(3.0); 
    return (dy <= a) && (a*dx + 0.25*dy <= 0.5*a); 
} 

• dy <= a comprueba que el punto está por debajo del borde horizontal.
• a*dx + 0.25*dy <= 0.5*a comprueba que el punto esté a la izquierda del borde derecho inclinado.

Para {x0 = 0, y0 = 0, d = 1}, los puntos de las esquinas serían (±0.25, ±0.43) y (±0.5, 0.0).

Answer 5

Restar la posición del centro del hexágono desde su punto P para obtener un vector V. Luego, tomar el producto escalar de V con los siguientes vectores, que corresponden a los tres pares de bordes opuestos del hexágono:

[0,1] ; the edges that are flat with the horizontal 
[cos(30),sin(30)] ; the upper-right and lower-left edges 
[cos(-30),sin(-30)] ; the lower-right and upper-left edges 

Si alguno de los productos dot es mayor en magnitud que la distancia desde el centro del hexágono a uno de sus bordes, entonces el punto no está dentro del hexágono.

Como referencia, el producto escalar de los vectores [a, b] y [c, d] es a * c + b * d.

El ángulo "30" de arriba es en grados;)

Answer 6

Esto es lo que he estado usando:

public bool InsideHexagon(float x, float y) 
{ 
    // Check length (squared) against inner and outer radius 
    float l2 = x * x + y * y; 
    if (l2 > 1.0f) return false; 
    if (l2 < 0.75f) return true; // (sqrt(3)/2)^2 = 3/4 

    // Check against borders 
    float px = x * 1.15470053838f; // 2/sqrt(3) 
    if (px > 1.0f || px < -1.0f) return false; 

    float py = 0.5f * px + y; 
    if (py > 1.0f || py < -1.0f) return false; 

    if (px - py > 1.0f || px - py < -1.0f) return false; 

    return true; 
} 

px y py son las coordenadas de x y y proyectadas sobre un sistema de coordenadas donde es mucho más fácil verificar los límites.

Answer 7

Lo que queremos es el código para averiguar si un punto está dentro de un polígono convexo, siendo un ejemplo de un caso particular de ese hexágono.

Aquí es una buena respuesta: https://stackoverflow.com/a/34689268/516188

hice modificar esa función para mi uso, encuentro mi versión más clara. Es mecanografiado (solo entrecierra los ojos y es javascript):

function vectorX(v: Vector): number { 
    return v[1].x - v[0].x; 
} 

function vectorY(v: Vector): number { 
    return v[1].y - v[0].y; 
} 

function crossProduct(v1: Vector, v2: Vector): number { 
    return vectorX(v1)*vectorY(v2) - vectorY(v1)*vectorX(v2); 
} 

function isInConvexPolygon(testPoint: Point, polygon: Polygon): boolean { 
    // https://stackoverflow.com/a/34689268/516188 
    if (polygon.length < 3) { 
     throw "Only supporting polygons of length at least 3"; 
    } 
    // going through all the edges around the polygon. compute the 
    // vector cross-product http://allenchou.net/2013/07/cross-product-of-2d-vectors/ 
    // to find out for each edge on which side of the edge is the point. 
    // if the point is on the same side for all the edges, it's inside 
    let initCrossIsPositive = undefined; 
    for (var i=0;i<polygon.length;i++) { 
     if (polygon[i].x === testPoint.x && 
      polygon[i].y === testPoint.y) { 
      // testPoint is an edge of the polygon 
      return true; 
     } 
     const curPointOnEdge = polygon[i]; 
     const nextPointOnEdge = polygon[(i+1)%polygon.length]; 
     const vector1 = <[Point,Point]>[curPointOnEdge, nextPointOnEdge]; 
     const vector2 = <[Point,Point]>[curPointOnEdge, testPoint]; 
     const cross = crossProduct(vector1, vector2); 
     if (initCrossIsPositive === undefined) { 
      initCrossIsPositive = cross > 0; 
     } else { 
      if (initCrossIsPositive !== (cross > 0)) { 
       return false; 
      } 
     } 
    } 
    // all the cross-products have the same sign: we're inside 
    return true; 
}