Java: concepto de recopilación eficiente para objetos emparejados

Question

Me falta algún tipo de funcionalidad de recopilación para un problema específico.

Me gustaría comenzar con unas pocas información sobre los antecedentes del problema - tal vez hay una manera más elegante para resolverlo, que no termina en el problema específico que estoy atascado con:

I' m modelar una malla de volumen hecha de células tetraédricas (el análogo 2D sería una malla triangular). Dos tetraedros se consideran adyacentes si comparten una cara triangular (que ocupa tres vértices). Mi aplicación debe poder navegar de una celda a otra a través de su cara común.

Para cumplir con otros requisitos, tuve que dividir las caras en dos llamadas medias caras que comparten los mismos vértices pero que pertenecen a diferentes celdas y tienen orientación opuesta.

La aplicación tiene que ser capaz de hacer llamadas como esta (donde Face modelos de media cara):

Cell getAdjacentCell(Cell cell, int faceIndex) { 
    Face face = cell.getFace(faceIndex); 
    Face partnerFace = face.getPartner(); 
    if (partnerFace == null) return null; // no adjacent cell present 
    Cell adjacentCell = partnerFace.getCell(); 
    return adjacentCell; 
} 

La aplicación de la getPartner() -method es el método en cuestión. Mi enfoque es como sigue:

Face -Objetos pueden crear algún tipo de Signature -objeto inmutable que contiene simplemente el vértice-configuración, la orientación (en sentido horario (CW) o en sentido antihorario (CCW)) y un back-referencia al objeto Rostro de origen. Los objetos Face.Signature se consideran iguales (@Override equals()) si ocupan los mismos tres vértices, independientemente de su orientación y su celda asociada.

creé dos conjuntos en los Mesh -Objetos para contener todas las medias caras agrupadas por su orientación:

Set<Face.Signature> faceSignatureCcw = new HashSet<Face.Signature>(); 
Set<Face.Signature> faceSignatureCw = new HashSet<Face.Signature>(); 

Ahora estoy en condiciones de determinar si existe un socio ...

class Face { 
    public Face getPartner() { 
     if (this.getSignature().isCcw()) { 
      boolean partnerExists = this.getMesh().faceSignatureCw.contains(this); 
     } else { 
      boolean partnerExists = this.getMesh().faceSignatureCcw.contains(this); 
     } 
    } 
} 

... ¡pero Set no permite recuperar el objeto específico que contiene! Simplemente confirma que contiene un objeto que coincide con .equals().

(final de la información de fondo)

Necesito un -concepto Collection que proporciona las siguientes funcionalidades:

• añadir un Face -Objeto de la Colección (duplicados están prohibidos por la aplicación y por lo tanto, no puede ocurrir)
• recuperar el socio de la Colección para un Face dado -Object que .equals() pero tiene la orientación opuesta

Una posible (pero es muy lento) solución sería:

class PartnerCollection { 
    List<Face.Signature> faceSignatureCcw = new ArrayList<Face.Signature>(); 
    List<Face.Signature> faceSignatureCw = new ArrayList<Face.Signature>(); 

    void add(Face.Signature faceSignature) { 
     (faceSignature.isCcw() ? faceSignatureCw : faceSignatureCcw).add(faceSignature); 
    } 

    Face.Signature getPartner(Face.Signature faceSignature) { 
     List<Face.Signature> partnerList = faceSignature.isCcw() ? faceSignatureCw : faceSignatureCcw; 
     for (Face.Signature partnerSignature : partnerList) { 
      if (faceSignature.equals(partnerSignature)) return partnerSignature; 
     } 
     return null; 
    } 
} 

ser completa: La aplicación final tendrá que manejar cientos de miles de Face -Objetos en un entorno en tiempo real. Entonces, el rendimiento es un problema.

Gracias de antemano a cualquiera que al menos haya intentado seguirme hasta este punto :) Espero que haya alguien por ahí que tenga la idea correcta para resolver esto.

Answer 1

¿Hay algún problema con el uso de dos Map<Face.Signature, Face.Signature>?
¿Uno para cada dirección?

Eso es lo que haría. Prácticamente no tiene código.

Answer 2

Usando el diseño que tiene ahora, no hay forma de evitar que algo necesite iterar en algún lugar. La pregunta es, ¿dónde quieres que ocurra esa iteración? Le sugiero que haga esto:

List<Face.Signature> partnerList = faceSignature.isCcw() ? faceSignatureCw : faceSignatureCcw; 
    int idx = partnerList.indexOf(faceSignature); 
    if(idx == -1) 
     return null; 
    return partnerList.get(idx); 

También, siempre y cuando se está utilizando Lists, y saber que el tamaño inicial tendrá que ser bastante grande, que también podría decir, new ArrayList(100000) más o menos.

Por supuesto, este no es el único método, solo uno que garantiza que la iteración sea óptima.

EDITAR: Después de pensarlo un poco, creo que la estructura de datos ideal para esto sería una Lista enlazada a Octuply, que puede hacer que las cosas sean confusas, pero también muy rápidas (comparativamente).

Answer 3

Ya es tarde para la noche y no he preparado su pregunta por completo. Entonces, me disculpo si esto no tiene sentido, pero ¿ha considerado utilizar una estructura de datos de gráficos? Si la estructura de datos del gráfico es de hecho una posible solución, es posible que desee consultar jGraphT

Answer 4

¿Ha considerado simplemente darle a cada Face un miembro de datos asociado? Al igual que en,

public class Face 
{ 
    Face partner; 
    //whatever else 
} 

La construcción Face.Signature es un poco peludo y realmente no debería ser necesario. Si cada cara tiene un compañero (o suficientes objetos Face puede tener un socio que tenga sentido pensar que existe una relación - entre un Face y un socio Face), la conexión solo debe ser una variable de instancia. Si puede usar este enfoque, debería simplificar enormemente su código. De lo contrario, publique la razón por la que esto no funciona para usted, de modo que pueda seguir tratando de ayudarlo.