[Java] equals & hashCode su campi double, come fare?

[banryu79]

Ciao,
sto leggendo delle primitive geometriche da un file dxf in formato testo (linee, archi di cerchio e cerchi) le cui coordiante cartesiane sono espresse in termini di numeri reali.

Uso questi valori reali come stato di un paio di classi primitive nella mia applicazione (Point e Bounds).
Altre entità della mia applicazione sono definite in termini di Point e usano Bounds (ho classi del tipo Line, Arc, Circle).

Ogni entità è in grado di restituire il Bounds di se stessa.

Devo implementare i metodi equals e hashCode in modo consistente perchè i Point vengono poi usati come chiavi in altre strutture dati (JGraphT) e algoritmi relativi. Il probelma è che il confronto dei diversi valori delle coordinate (double) deve tenere conto del fatto che vengnono considerate solamente N cifre rilevanti dopo la virgola o comunque di un valore "epsilon" di tolleranza.

Fin qui nessun problema nell'implementare il metodo equals, ma come si potrebbe implementare il metodo hashCode in modo consistente?

[wingman87]

Se si considerassero solo N cifre dopo la virgola non ci sarebbero problemi, è la tolleranza che crea problemi, giusto?

[WarDuck]

L'hash lo calcoli comunque sui valori troncati no?

[banryu79]

Se si considerassero solo N cifre dopo la virgola non ci sarebbero problemi, è la tolleranza che crea problemi, giusto?



L'hash lo calcoli comunque sui valori troncati no?


Grazie per le domande.
Allora: sia il considerare solo N cifre dopo la virgola che la tolleranza sono un problema per l'hash.
Il fatto è che io non "tronco" o arrotondo i valori reali che leggo dal file dxf: questi valori vengono memorizzati come stato delle mie entità senza essere toccati.

Se la "sorgente" di questi valori double fosse unica e da me controllata (ad esempio solo il file dxf in input), non avrei nessun problema (non avrei bisogno di tenere conto di alcuna tolleranza o di dover fare nessun troncamento).

Invece un'altra sorgente di questi valori, oltre al file dxf (che in pratica stabilisce le coordinate iniziali delle entità prima di qualsiasi elaborazione) è la classe java.awt.geom.Arc2D.Double.

Mi spiego:
Io ho un'interfaccia Entity che rappresenta una mia primitiva geometrica.
Una Entity è anche una Drawable e una Boundable, interfaccia che rappresenta un'entità in grado di fornire il suo Bounds.

Line, Arc e Circle sono implementazioni di Entity, dunque sono anche Drawable/Boundable.

Per Line, definita da due soli Point, basta poco per implementare il metodo che si occupa del rendering, e altrettanto poco per implementare quello che soddisfa il contratto di Boundable fornendo Bounds.

Per Arc invece non è così banale.
Arc è definito, geometricamente, in termini di tre Point (centro, inizio, fine) un double (il raggio) e un boolean (antiorario/oriario).
Essendo pigro, per il rendering ho pensato di sfruttare Arc2D.Double, così una entità Arc istanzia sempre una entità Arc2D che usa per il rendering.
Poi c'è il problema del calcolo del Bounds.
Anche qui, vorrei sfruttare il metodo getBounds2D di Arc2D senza dover stare io a fare i calcoli (almeno per il momento).

E qui c'è il problema.
Immaginate di avere un arco "Pippo" con centro[X0,Y0] punto iniziale[X100,Y0] e finale[X0Y100], raggio[100] e verso antiorario[true].

Ora il Bounds restituito da un Arco così definito dovrebbe essere:
minX[0], minY[0], width[100], height[100].

Capita invece che il corrispondete Arc2D per "Pippo" mi calcoli un Bounds del tipo:
minX[-2.8421709430404007E-14], minY[0], width[100], height[100.00000000000003].
E questo causa il fallimento della mia unit test, perchè l'uguaglianza (e di conseguenza l'hashCode) tra due Bounds è definita in base all'uguaglianza dei quattro valori [minX, minY, width e height] che sono di tipo double.

A questo punto ho pensato, per le classi Point e Bounds (che sono le primitive definite in termini di valori reali) di dover introdurre una tolleranza oppure il fatto di considerare solo N cifre dopo la virgola* durante la comparazione dei valori per il metodo equals: ma per rendere consistente il metodo hashCode come fareste?

Secondo voi è sbagliato da qualche punto di vista il fatto che per Arc mi appoggi a una classe di Java2D (per il rendering e per il calcolo dei Bounds), dato che è questo fatto ad avermi portato a casa il problema?

* le sole N cifre sono accettabilissime perchè lo scopo di tutta l'applicazione è produrre in output dei percorsi di taglio per una macchina CNC e tre decimali di precisione dopo la virgola sono assolutamente più che sufficienti per la tecnologia che sto lavorando.

[banryu79]

Per ora ho risolto introducendo una classe astratta Primitive che fornisce un metodo per calcolare il valore arrotondato di un floating point che verrà usato nei metodi equals e hashCode delle sottoclassi.

Point e Bounds estendono Primitive e usano questo servizio.

Quello che fa Primitive è questo:

public abstract class Primitive
{
[...snip]


private static final int RELEVANT_DIGITS = 3;

private static final double ROUND_FACTOR = Math.pow(10, RELEVANT_DIGITS);

protected static long round(double floatValue) {
return Math.round(floatValue * ROUND_FACTOR);
}
}


E Bounds, ad esempio, la usa così:

public final class Bounds extends Primitive implements Entity
{
private double minX, minY, maxX, maxY;

[snip]

@Override
public boolean equals(Object obj) {
if (obj instanceof Bounds) {
Bounds other = (Bounds) obj;
return Bounds.round(minX) == Bounds.round(other.minX) &&
Bounds.round(minY) == Bounds.round(other.minY) &&
Bounds.round(maxX) == Bounds.round(other.maxX) &&
Bounds.round(maxY) == Bounds.round(other.maxY);
}

return false;
}

@Override
public int hashCode() {
long rMinX = Bounds.round(minX);
long rMaxX = Bounds.round(maxX);
long rMinY = Bounds.round(minY);
long rMaxY = Bounds.round(maxY);

int hash = 7;
hash = 97 * hash + (int) (rMinX ^ (rMinX >>> 32));
hash = 97 * hash + (int) (rMinY ^ (rMinY >>> 32));
hash = 97 * hash + (int) (rMaxX ^ (rMaxX >>> 32));
hash = 97 * hash + (int) (rMaxY ^ (rMaxY >>> 32));
return hash;
}
}

[wingman87]

La soluzione che immaginavo è quella che hai adottato, quindi secondo me, almeno per quanto riguarda la logica, va bene. Forse è opinabile il fatto di aver integrato il metodo statico in una classe astratta per poi farla estendere a un altro oggetto... anzi... ripensandoci mi sembra proprio sbagliato :D Secondo me dovresti lasciare quel metodo in una classe di utility, anche perché qualora Arc2D & company dovessero estendere qualche altro oggetto, non potrebbero perché estendono già Primitive.

Inoltre mi chiedevo un'altra cosa: il raggio lo calcoli basandoti sul centro e uno degli altri due punti oppure lo richiedi come parametro aggiuntivo? Non è ridondante?

E infine il calcolo del bound dell'arco mi sembra fattibile, almeno mi sembra, intuitivamente, anche se forse non saprei come ottimizzarlo a livello di prestazioni.

[banryu79]

Intanto grazie ancora una volta per le domande: sono un'occasione per riflettere. Farlo sempre e solo da soli (quando lo faccio :D) dopo un po' diventa pesante e riduttivo.


Forse è opinabile il fatto di aver integrato il metodo statico in una classe astratta per poi farla estendere a un altro oggetto... anzi... ripensandoci mi sembra proprio sbagliato :D Secondo me dovresti lasciare quel metodo in una classe di utility, anche perché qualora Arc2D & company dovessero estendere qualche altro oggetto, non potrebbero perché estendono già Primitive.

Le uniche due classi "primitive" che avrò in questa applicazione sono appunto Point e Bounds. Non ne avrò altre.
Per Point e Bounds non c'è il problema del dover forse estendere qualche altra classe (avevo considerato questo aspetto).
In più sono classi final, quindi nessuno le estenderà (non centra con la questione, ma è per dire che so già per certo che sono le "primitive minime" per quanto riguarda il dominio delle entità geometriche per questa applicazione).

In effetti ero indeciso se realizzare una classe "esterna" di utility oppure fare come ho fatto (con la stessa tecnica Primitive fornisce anche un metodo statico che usa un DecimalFormatter all'uopo per formattare i floating point value delle coordinate in maniera consistente).

Accertato il fatto che Point e Bounds non hanno la neccessità di estendere alcuna altra classe, tra la soluzione con la classe utility e quella della classe astratta contenitore di funzionalità statiche comuni, quale sceglieresti?

A me l'idea che Point e Bounds denotino dei tipi Primitive mi piace perchè esprime il fatto che appunto sono i "tipi primitivi" della mia applicazione. E la faccenda dell'arrotondamento delle coordinate riguarda proprio le entità primitive che uso.

Poi mi piace poter invocare i metodi statici di una Primitive nella forma Point.round(x)/Point.format(x) oppure Bounds.round(y)/Bounds.format(y) a seconda del contesto locale (Point/Bounds) in cui vengono usati.

Inoltre mi chiedevo un'altra cosa: il raggio lo calcoli basandoti sul centro e uno degli altri due punti oppure lo richiedi come parametro aggiuntivo? Non è ridondante?

Sì, dati i punti iniziale/finale dell'arco e il verso di rotazione poi basterebbe solo il centro oppure il raggio per definire completamente e univocamente un arco di cerchio.
Però una entità arco definita da un CAD e codificata nel formato dxf viene memorizzata con entrambe le infomazioni; preferisco leggerle e tenerle entrambe perchè a seconda del contesto in cui uso poi gli archi mi è più comodo usare ora l'uno ora l'altro e preferisco il costo rappresentato dal dover memorizzare un double in più piuttosto che quello del dover eseguire altri calcoli a runtime per ricavarmi l'uno o l'altro valore.
Questo perchè il numero totale di entità contemporaneamente presenti durante un tipico run dell'applicazione è ridicolmente basso e quindi il double in più in memoria non da fastidio a nessuno.


E infine il calcolo del bound dell'arco mi sembra fattibile, almeno mi sembra, intuitivamente, anche se forse non saprei come ottimizzarlo a livello di prestazioni.

Beh, a dire il vero avrei una mia classe del tipo Vector2D già usata in un'altro progetto, e con il vettori ci fai un sacco di belle cose in modo efficiente, anche supplire le info mancanti per ricavare il bounding box dell'arco (al momento rappresentate dalla mancanza dei valori di angolo iniziale e angolo finale dell'arco nella circonferenza).
Adesso non la uso perchè sto cercando di implementare le funzionalità che mi servono in modo graduale e "minimale" usando solo lo stretto neccessario, in questa fase. Più tardi, se servirà, supplirò.
@EDIT: se di un arco conosci il punto iniziale e quello finale, il verso (orario/antiorario) e conosci (ricavi) i quattro quadranti della circonferenza su cui giace l'arco, con i vettori puoi calcolre semplicemente il boundi box, evitando operazioni trigonometriche tipo cos e sin, riducendo tutto a poche semplici addizioni e moltiplicazioni.

[wingman87]

Secondo me la classe Primitive in un certo senso è già una classe utility, puoi già usare i suoi metodi statici facendo riferimento a essa, e, al di là del fatto che è astratta e non ho capito perché (ma forse la risposta è nel codice che hai "snippato"), l'estenderla aggiunge solo la possibilità di utilizzare i suoi metodi con una diversa sintassi.
Legare in questo modo le classi riduce il disaccoppiamento, che in generale è un male, però come sempre dipende...
Personalmente terrei una classe utility separata ma, visto e considerato quanto hai detto, credo che sia solo una scelta personale.

[banryu79]

Personalmente terrei una classe utility separata ma, visto e considerato quanto hai detto, credo che sia solo una scelta personale.

Incontrato un caso che non avevo previsto per cui è meglio fare come hai detto (che era anche più corretto dal punto di vista logico, come osservavi) cioè implementare quelle funzionalità come classe utility.
Grazie dei consigli :)