actionscript-3 - vectorial - mapa de bits de flash

Encontrar el centro de masa en un mapa de bits 2D

Question

Estoy codificando un juego, y me gustaría poder encontrar el centro de masa de una forma arbitraria en un mapa de bits en blanco y negro como este:

012345678 0.XX...... 1..XXX.... 2...XXX... 3..XXXXXXX 4...XXX...

Todas las "células" tienen el mismo peso. Las celdas diagonalmente adyacentes no se consideran conectadas, y la forma siempre será una única ya que ya está dividida por otra función antes de esto.

Solo se utilizará para imágenes de resolución razonablemente baja (tal vez 50x50 como máximo) y no es necesario que sea súper preciso, la velocidad es preferible.

Me da la sensación de que hay una forma adecuada de hacerlo, pero realmente no sé para qué buscarlo.

Estoy codificando esto en Actionscript 3, pero los ejemplos en cualquier idioma son apreciados, más aún si están hechos para ser entendidos por los humanos.

EDITAR: puede suponer que los datos se almacenan en la estructura de datos que considere más conveniente para su ejemplo. Estoy usando mapas de bits, ¡pero las matrices bidimensionales o incluso una sola matriz también están bien!

EDITAR: Este es el código que terminé usando, lo más probable es que lo haga más rápido, pero me parece muy legible:

// _bmp is a private BitmapData instance
public function getCenterOfMass():Point {
    var avg     :Point  = new Point(0, 0);
    var points  :uint   = 0;

    for (var ix:uint = 0; ix < _bmp.width; ix++) {
        for (var iy:uint = 0; iy < _bmp.height; iy++) {
            if (_bmp.getPixel(ix, iy) == ACTIVE_COLOR) {
                avg.x += ix;
                avg.y += iy;
                points++;
            }
        }
    }

    avg.x /= points;
    avg.y /= points;

    return avg;
}

Answer 1

Dependiendo de la naturaleza de su intérprete ActionScript y el procesamiento previo realizado en las formas, puede ver una mejora de velocidad (sobre el enfoque directo señalado por Yuval) al crear inicialmente una segunda copia del mapa de bits / matriz reflejada diagonalmente, luego usar funciones de manipulación de fila o cadena para sumar los puntos en cada fila y columna en pasos individuales. Esto sería O (2m n) en lugar de O (n n) [ver abajo], pero con más sobrecarga.

xSum = 0
ySum = 0
points = 0

for row in matrix
  ySum += rowX * countpoints(row)
  points += countpoints(row)
for row in mirroredmatrix
  xSum += rowX * countpoints(row)

return (xSum/points, ySum/points)

Donde countpoints () cuenta los puntos en una fila. Esto se basa en los puntos de conteo (que tiene O (n) tiempo de ejecución) que tienen un multiplicador constante menor que el tiempo de ejecución ingenuo (por lo tanto, "m" es el tiempo de ejecución de los puntos de conteo y "n" es el tiempo para que el intérprete ) La naturaleza de los puntos () depende de su método de almacenamiento, que puede implicar contar caracteres en una cadena, o bits en un campo de bits.

Answer 2

Puede contar el número de celdas contiguas, luego centrarse en las celdas con el recuento vecino más alto.

012345678 0 XX | 1 XXX | 2 XXX | 3 XXXXXXX| 4 XXX | 012345678 0 23 | 1 454 | 2 775 | 3 3686421| 4 454 |

En este ejemplo, podría usar la única celda con un 8 , como punto central.

Si creas varias celdas con el mismo número de vecinos, solo ejecutarías la rutina de recuento nuevamente, pero esta vez solo con las celdas de números altos.

Por ejemplo, imaginemos que las celdas que tenían 6 , 7 y 8 , en cambio, todas tenían ocho vecinos.

012345678 0 23 | 1 454 | 2 885 | 3 3888421| 4 454 | 012345678 0 -- | 1 --- | 2 XX- | 3 -XXX---| 4 --- | 012345678 0 -- | 1 --- | 2 34- | 3 -342---| 4 --- | 012345678 0 -- | 1 --- | 2 -X- | 3 --X----| 4 --- |

En el caso de un lazo simple, iría con el que estaba más cerca del centro. En este caso, sería el superior de los dos.

Nota: supongo que no estás usando esto para una simulación de física precisa.

Answer 3

¿Qué tal este algoritmo (código psuedo) basado en una matriz booleana como en su ejemplo?

xSum = 0
ySum = 0
points = 0

for point in matrix
    if point is marked
        xSum += pointX
        ySum += pointY
        points++

return (xSum/points, ySum/points)

Nada demasiado complicado, calcule dónde X es el más presente, lo mismo para Y, divida por el número de puntos que contó y obtendrá el centro de masa. Puede complicar aún más esto dando a ciertos puntos un peso diferente en el promedio, pero esta debería ser su dirección principal.

Esta pregunta me hizo pensar en una expansión de esta pregunta a la que no pude encontrar una buena respuesta. Publiqué la pregunta aquí: Encontrar cúmulos de masa en una matriz / mapa de bits