Pregunta Encontrar una colocación estable de una forma irregular (no convexa)


Dada una imagen de una forma bidimensional irregular (no convexa), ¿cómo podría calcular todas las formas en que podría permanecer estable en una superficie plana? Por ejemplo, si la forma es un rectángulo cuadrado perfecto, seguramente tendrá 4 formas en que sea estable. Un círculo, por otro lado, no tiene una orientación estable o cada punto tiene una orientación estable.

EDITAR: Hay un pequeño juego llamado Disidente (Cuidado, juego adictivo por delante) que parece cercano a lo que quiero. Advirtió que cortaba un trozo de madera, caería al suelo y se colocaría de manera estable.

EDITAR: Al final, el enfoque que tomé es calcular el centro de masa (de la forma) y calcular el casco convexo (usando OpenCV), y luego recorrer cada par de vértices. Si el centro de masa cae sobre la línea formada por los 2 vértices, se considera estable; de ​​lo contrario, no.


10
2018-06-19 03:42


origen


Respuestas:


Primero encuentra su centro de masa (CM). Una posición estable es aquella en la que el CM será mayor si haces una ligera rotación Ahora mira el casco, la región convexa más pequeña que encierra la forma:

Convex Hull y Center of Mass http://walkytalky.net/extern/hull.png

Si el casco es un polígono, entonces una posición estable es aquella en la que la forma descansa en uno de los lados, y el CM está directamente sobre ese lado (no necesariamente sobre el punto medio del lado, solo en algún lugar sobre él).

Si el casco tiene curvas (es decir, si la forma tiene curvas que tocan el casco), se les debe dar un tratamiento especial. La forma será estable cuando descansa sobre un borde curvo si el CM está directamente sobre el punto más bajo de la curva, y el radio de la curva en ese punto es mayor que la altura del CM.

Ejemplos:

  1. Un rectángulo. El casco es simplemente el rectángulo, y el CM está en el centro. La forma es estable en cada uno de los cuatro lados.
  2. Un rectángulo con los lados ahuecados, pero las esquinas siguen intactas. El casco sigue siendo el rectángulo original, y el CM está cerca de donde solía estar. Los cuatro lados del casco aún son estables (es decir, aún puedes descansar la forma en cualquier esquina).
  3. Un circulo. El CM está en el centro, el casco es el círculo. No hay posiciones estables, ya que el radio de la curva siempre es igual a la altura del CM. Dale un ligero toque, y rodará.
  4. Una elipse El CM está en el centro, el casco es la forma. Ahora hay dos posiciones estables.
  5. Un semicírculo. El CM está en algún lugar en el eje de simetría, el casco es la forma. Dos posiciones estables.
  6. Una media luna semicircular estrecha. El casco es un semicírculo, el CM está fuera de la forma (pero dentro del casco). Dos posiciones estables.

Ilustración de los ejemplos http://walkytalky.net/extern/stable.png

(La posición de la elipse marcada con una X es inestable, porque la curvatura es menor que la distancia al centro de masa.)


9
2018-06-19 04:02



nota: esta respuesta asume que tu forma es un polígono apropiado.

Para nuestros propósitos, definiremos una posición de equilibrio como una donde el centro de masa está directamente encima de un punto que se encuentra entre los puntos de contacto con el suelo más a la izquierda y más a la derecha del objeto (suponiendo que el suelo es una superficie plana perpendicular a la fuerza de la gravedad). Esto funcionará en todos los casos, para todas las formas.

Tenga en cuenta que, este es en realidad el definición física del equilibrio rotacional, como consecuencia de la cinemática rotacional newtoniana.

Para un polígono apropiado, si eliminamos los casos en que se encuentran en un único vértice, esta definición es equivalente a una posición estable.

Por lo tanto, si tiene una gravedad descendente directa, primero encuentre las partes más a la izquierda y más a la derecha que están tocando el suelo.

Luego, calcula tu centro de masa. Para un polígono con vértices conocidos y densidad uniforme, este problema se reduce a encontrar el Centroide (sección relevante)

Luego, suelta una línea de tu CoM; si la intersección del CoM y el suelo está entre esos dos valores x, está en equilibrio.

Si su punto más a la izquierda y el punto más a la derecha coinciden (es decir, en un objeto redondo), esto todavía se mantendrá; solo recuerda tener cuidado con tus comparaciones de puntos flotantes.

Tenga en cuenta que esto también se puede usar para medir "qué tan estable" es un objeto; esta medida es la distancia máxima que puede recorrer el centro de masa antes de que ya no se encuentre dentro del rango de los dos puntos de contacto.

EDITAR: ingenioso diagrama hecho a toda prisa

Diagrama http://img52.imageshack.us/img52/9506/1276930988102131dc.png

Entonces, ¿cómo puedes usar esto para encontrar todas las maneras en que puede sentarse en una mesa? Ver:


EDITAR

El enfoque programable

En lugar de la tarea computacionalmente costosa de rotar la forma, intente esto en su lugar.

La representación de tu forma en tu programa probablemente debería tener una lista de todos los vértices.

Encuentra los vértices de tu forma casco convexo (básicamente, su forma, pero con todos los vértices cóncavos - vértices que son "empujados" - eliminados).

Luego itere a través de cada par de vértices adyacentes en su casco convexo (es decir, si tuviera los vértices A, B, C, D, iteraría a través de AB, BC, CD, DA)

Haz esta prueba:

  1. Dibuja una línea UN a través de los dos vértices que se prueban
  2. Dibuja una línea perpendicular a UNpasando por CoM do.
  3. Encuentra la intersección de las dos líneas (álgebra simple)
  4. Si el valor y de la intersección está entre el valor y de los dos vértices, es estable. Si los valores y son todos iguales, compare los valores x.

Eso debería hacer el truco.

Aquí hay un ejemplo de la prueba que se está ejecutando en un par de vértices:

Ejemplo de prueba http://img17.imageshack.us/img17/918/stabled.png

Si su forma no está representada por sus vértices en su estructura de datos, entonces debe tratar de convertirlos. Si se trata de algo así como un círculo o una elipse, puede usar la heurística para adivinar la respuesta (un círculo tiene infinitas posiciones de equilibrio, una elipse 4, aunque solo dos puntos "estables"). Si se trata de una forma irregular curva y tambaleante, deberá proporcionar su estructura de datos para poder ayudar de una manera relacionada con el programa, en lugar de solo proporcionar heurística caso por caso.


3
2018-06-19 03:49



Estoy seguro de que este no es el algoritmo más eficiente, pero es una idea.

Si puede ordenar los vertículos del polígono (suponiendo que tiene un número finito de vértices), simplemente itere sobre pares adyacentes de vértices y registre el ángulo en el que descansa mediante alguna forma de simulación. Habrá orientaciones duplicadas para que se asiente en el caso de formas extrañas, como las estrellas, pero puede acomodarse a eso haciendo un seguimiento de la rotación en reposo.


0