src/image/geometry.jsjavascript
import {
REAL_WORLD_EPSILON,
REAL_WORLD_EXPONENT,
precisionRound
} from '../math/number.js';
import {getIdentityMat33} from '../math/matrix.js';
import {Point3D, Point} from '../math/point.js';
import {Vector3D} from '../math/vector.js';
import {Index} from '../math/index.js';
import {getBasicStats} from '../math/stats.js';
import {logger} from '../utils/logger.js';
import {Size} from './size.js';
import {Spacing} from './spacing.js';
import {BooleanResult} from '../utils/result.js';
import {arrayMap} from '../utils/array.js';
import {Matrix33} from '../math/matrix.js';
// direction epsilon, when comparing orientations (for example
// of slices of the same series or of an image and its segmentation):
// Image Orientation (Patient) is a DS that can be written with only
// 5 decimals, leading to rounding differences of 1e-5
export const DIRECTION_EPSILON = 1e-4;
// number of spatial dimensions
export const SPATIAL_DIMS = 3;
// volume dimension index
export const VOLUME_DIM_INDEX = SPATIAL_DIMS;
/**
* @import {SourcedNumberValue} from '../math/types.js';
* @import {VolumeId} from './types.js';
*/
/**
* @callback comparePointFn
* @param {Point3D} a The first point.
* @param {Point3D} b The first point.
* @returns {number} >0 to sort a after b, <0 to sort a before b,
* 0 to not change order.
*/
/**
* Get a point compare function using Z coordinate difference.
* Compares de-oriented points using the input orientation inverse.
*
* @param {Matrix33} orientation The orientation matrix.
* @returns {comparePointFn} The point compare function.
*/
export function getComparePoint3D(orientation) {
const invOrientation = orientation.getInverse();
return function (point1, point2) {
const p1 = invOrientation.multiplyPoint3D(point1);
const p2 = invOrientation.multiplyPoint3D(point2);
return p1.getZ() - p2.getZ();
};
}
/**
* Get the closest of a list of origins to an input point, and the
* signed residual between the point and that origin, projected onto
* the slice-stacking direction (the orientation's 3rd column, ie its
* normal). A positive residual means the point is 'ahead of' (in the
* codirectional sense) the closest origin along that direction, a
* negative (or zero) residual means it is 'at or behind' it.
*
* @param {Point3D} point3D The point to locate.
* @param {Point3D[]} origins The origins to search.
* @param {Matrix33} orientation The geometry orientation.
* @returns {{index: number, normalResidual: number}} The closest
* origin's index in the input list and the normal-projected
* residual to it.
*/
function getClosestOriginResidual(point3D, origins, orientation) {
const index = point3D.getClosest(origins);
const normal = new Vector3D(
orientation.get(0, 2),
orientation.get(1, 2),
orientation.get(2, 2)
);
const normalResidual = point3D.minus(origins[index]).dotProduct(normal);
return {index, normalResidual};
}
/**
* Sorted volume ids and the values derived from them.
*
* @typedef {object} VolumeIdsData
* @property {VolumeId[]} volumeIds The volume ids, sorted by id.
* @property {number[]} values The sorted ids.
* @property {number} tolerance The id matching tolerance: half the
* smallest gap between ids (0.5 for a single id).
*/
/**
* Get the index of the closest value of a sorted list.
*
* @param {number[]} values The sorted values.
* @param {number} value The value to locate.
* @returns {number} The index of the closest value.
*/
function getClosestValueIndex(values, value) {
let res = 0;
for (let i = 1; i < values.length; ++i) {
if (Math.abs(values[i] - value) < Math.abs(values[res] - value)) {
res = i;
}
}
return res;
}
/**
* 2D/3D Geometry class.
*/
export class Geometry {
/**
* Array of origins.
*
* @type {Point3D[]}
*/
#origins;
/**
* Data size.
*
* @type {Size}
*/
#size;
/**
* Data spacing.
*
* @type {Spacing}
*/
#spacing;
/**
* Time points: the time (a volume id or, without source, a frame
* index) and its origins, indexed by time id.
*
* @type {Map<number, {time: VolumeId, origins: Point3D[]}>}
*/
#times = new Map();
/**
* Initial time.
*
* @type {VolumeId|undefined}
*/
#initialTime;
/**
* Volume ids cache, null if not computed (cleared at each time
* change), undefined if the times are not volume ids.
*
* @type {VolumeIdsData|undefined|null}
*/
#volumeIdsData = null;
/**
* Data orientation.
*
* @type {Matrix33}
*/
#orientation = getIdentityMat33();
/**
* @param {Point3D[]} origins The object origins.
* @param {Size} size The object size.
* @param {Spacing} spacing The object spacing.
* @param {Matrix33} [orientation] The object orientation (3*3 matrix,
* default to 3*3 identity).
* @param {VolumeId} [time] Optional time: a volume id or, without
* source, a frame index (for example `{id: {value: 2}}`).
*/
constructor(origins, size, spacing, orientation, time) {
this.#origins = origins;
this.#size = size;
this.#spacing = spacing;
if (typeof time !== 'undefined') {
this.#setTime(time, origins.slice());
this.#initialTime = time;
}
// check input orientation
if (typeof orientation !== 'undefined') {
this.#orientation = orientation;
}
}
/**
* Store a time and its origins.
*
* @param {VolumeId} time The time: a volume id or, without source,
* a frame index.
* @param {Point3D[]} origins The time origins.
* @throws {Error} If the time does not have a number id.
*/
#setTime(time, origins) {
if (typeof time?.id?.value !== 'number') {
throw new Error(
'Geometry time must be an object with a number id, ' +
'for example {id: {value: 2}}');
}
this.#times.set(time.id.value, {time, origins});
this.#volumeIdsData = null;
}
/**
* Clone the geometry.
*
* @returns {Geometry} A clone of this geometry.
*/
clone() {
return new Geometry(
this.#origins.slice(),
new Size(this.#size.getValues()),
new Spacing(this.#spacing.getValues()),
new Matrix33(this.#orientation.getValues()),
this.#initialTime
);
}
/**
* Get the time that was passed at construction.
*
* @returns {VolumeId|undefined} The time.
*/
getInitialTime() {
return this.#initialTime;
}
/**
* Set the initial time.
*
* @param {VolumeId} time The new time: a volume id or, without
* source, a frame index.
*/
setInitialTime(time) {
if (typeof this.#initialTime !== 'undefined') {
this.#times.delete(this.#initialTime.id.value);
}
this.#setTime(time, this.#origins.slice());
this.#initialTime = time;
}
/**
* Set the associated values of the volume ids, for example once
* guessed after load (see dicomVolume getVolumeValues).
*
* @param {SourcedNumberValue[]} values The associated values, one per
* volume id, in volume id order.
* @throws {Error} If the number of values is not the number of
* volume ids.
*/
setVolumeValues(values) {
const volumeIds = this.#getVolumeIdsData()?.volumeIds;
if (volumeIds?.length !== values.length) {
throw new Error('Expected one value per volume id');
}
for (let i = 0; i < volumeIds.length; ++i) {
const time = volumeIds[i];
const res = {...time, value: values[i]};
this.#times.set(time.id.value,
{time: res, origins: this.#times.get(time.id.value).origins});
if (this.#initialTime === time) {
this.#initialTime = res;
}
}
this.#volumeIdsData = null;
}
/**
* Get the volume ids: the time of each volume, sorted by ascending
* id, the array index being the volume index. Times are volume
* ids if their id has a source.
*
* @returns {VolumeId[]|undefined} The volume ids, undefined if the
* times are not volume ids.
*/
getVolumeIds() {
return this.#getVolumeIdsData()?.volumeIds.slice();
}
/**
* Get the sorted volume ids data, computed once per time change.
*
* @returns {VolumeIdsData|undefined} The data, undefined if the
* times are not volume ids.
*/
#getVolumeIdsData() {
if (this.#volumeIdsData !== null) {
return this.#volumeIdsData;
}
const volumeIds = [...this.#times.values()]
.map(item => item.time)
.sort((a, b) => a.id.value - b.id.value);
if (volumeIds.length === 0 ||
volumeIds.some(time => typeof time.id.source === 'undefined')) {
this.#volumeIdsData = undefined;
} else {
const values = volumeIds.map(volumeId => volumeId.id.value);
let minGap = Infinity;
for (let i = 1; i < values.length; ++i) {
minGap = Math.min(minGap, values[i] - values[i - 1]);
}
this.#volumeIdsData = {
volumeIds,
values,
tolerance: values.length > 1 ? minGap / 2 : 0.5
};
}
return this.#volumeIdsData;
}
/**
* Set the volume ids of a geometry without times (for example a
* resampled one): the volumes all have the current origins.
*
* @param {VolumeId[]} volumeIds The volume ids, sorted by ascending
* id, one per volume (fourth dimension).
*/
setVolumeIds(volumeIds) {
this.#times.clear();
for (const time of volumeIds) {
this.#setTime(time, this.#origins.slice());
}
this.#initialTime = volumeIds[0];
}
/**
* Get the index of a volume id.
*
* @param {number} id The volume id.
* @returns {number} The volume index, -1 if not found.
*/
getVolumeIndex(id) {
const data = this.#getVolumeIdsData();
if (typeof data === 'undefined') {
return -1;
}
// ids are tag values: only allow float noise
const tolerance = 1e-9 * Math.max(1, Math.abs(id));
return data.values.findIndex(
item => Math.abs(item - id) <= tolerance);
}
/**
* Check if the volume of this geometry can follow the one of another
* geometry: both volume ids have the same origin and the input
* volume id value is one of this geometry.
*
* @param {Geometry} geometry The geometry to follow.
* @param {number} value The volume id value to follow.
* @returns {boolean} True if the volume can follow.
*/
canSyncVolume(geometry, value) {
const sourceId = geometry.getVolumeIds()?.[0];
const targetId = this.getVolumeIds()?.[0];
if (typeof sourceId === 'undefined' || typeof targetId === 'undefined') {
return false;
}
return sourceId.id.source === targetId.id.source &&
sourceId.id.tagKey === targetId.id.tagKey &&
this.getVolumeIndex(value) !== -1;
}
/**
* Check if the fourth dimension index to world conversion uses
* volume ids: if there are volume ids, one per volume.
*
* @returns {VolumeIdsData|undefined} The volume ids data if they
* are used.
*/
#getConversionVolumeIds() {
const data = this.#getVolumeIdsData();
if (typeof data === 'undefined' ||
this.#size.length() < 4 ||
data.values.length !== this.#size.get(3)) {
return undefined;
}
return data;
}
/**
* Convert a volume index into a volume id. Out of range indices
* are extrapolated from the closest step between ids so that
* the conversion can be inverted.
*
* @param {number} index The volume index.
* @param {VolumeIdsData} data The volume ids data.
* @returns {number} The volume id.
*/
#volumeIndexToId(index, data) {
const volumeIds = data.values;
const last = volumeIds.length - 1;
let res;
if (index < 0) {
const step = last > 0 ? volumeIds[1] - volumeIds[0] : 1;
res = volumeIds[0] + index * step;
} else if (index > last) {
const step = last > 0 ? volumeIds[last] - volumeIds[last - 1] : 1;
res = volumeIds[last] + (index - last) * step;
} else {
res = volumeIds[index];
}
return res;
}
/**
* Convert a volume id into a volume index: the index of the
* closest id, -1 before the first and the number of volumes
* after the last (further than the tolerance).
*
* @param {number} volumeId The volume id.
* @param {VolumeIdsData} data The volume ids data.
* @returns {number} The volume index.
*/
#volumeIdToIndex(volumeId, data) {
const values = data.values;
if (volumeId <= values[0] - data.tolerance) {
return -1;
}
if (volumeId >= values[values.length - 1] + data.tolerance) {
return values.length;
}
return getClosestValueIndex(values, volumeId);
}
/**
* Get the total number of slices.
* Can be different from what is stored in the size object
* during a volume with time points creation process.
*
* @returns {number} The total count.
*/
getCurrentTotalNumberOfSlices() {
if (this.#times.size === 0) {
return this.#origins.length;
}
let count = 0;
for (const item of this.#times.values()) {
count += item.origins.length;
}
return count;
}
/**
* Check if a time point has associated slices.
*
* @param {number} time The time id to check.
* @returns {boolean} True if slices are present.
*/
hasSlicesAtTime(time) {
return this.#times.has(time);
}
/**
* Get the number of slices stored for time points preceding
* the input one.
*
* @param {number} time The time id to check.
* @returns {number|undefined} The count.
*/
getCurrentNumberOfSlicesBeforeTime(time) {
if (this.#times.size === 0) {
return undefined;
}
// times are stored in ascending order
let count = 0;
for (const [key, item] of this.#times) {
if (key < time) {
count += item.origins.length;
}
}
return count;
}
/**
* Check that all time points have the same origins as the
* initial time point (same number and same values in the
* same order).
*
* @returns {BooleanResult} Result with success set to true if
* the time origins are consistent.
*/
checkTimeOrigins() {
// no time points to compare to
if (typeof this.#initialTime === 'undefined') {
return new BooleanResult(true);
}
for (const [key, item] of this.#times) {
const timeOrigins = item.origins;
if (timeOrigins.length !== this.#origins.length) {
return {
success: false,
message: `Different number of slices for time ${key}: ` +
`${timeOrigins.length} vs ${this.#origins.length}`
};
}
for (let i = 0; i < timeOrigins.length; ++i) {
if (!timeOrigins[i].equals(this.#origins[i])) {
return {
success: false,
message: `Different origin for time ${key} at slice ${i}`
};
}
}
}
return new BooleanResult(true);
}
/**
* Get the object origin.
* This should be the lowest origin to ease calculations (?).
*
* @returns {Point3D} The object origin.
*/
getOrigin() {
return this.#origins[0];
}
/**
* Get the object origins.
*
* @returns {Point3D[]} The object origins.
*/
getOrigins() {
return this.#origins;
}
/**
* Sort origins by Z position ascending.
*/
sortOrigins() {
this.#origins.sort(getComparePoint3D(this.#orientation));
}
/**
* Check if a point is in the origin list.
*
* @param {Point3D} point3D The point to check.
* @param {number} [tol] Optional number comparison tolerance
* defaults to Number.EPSILON.
* @returns {boolean} True if in list.
*/
includesOrigin(point3D, tol) {
for (let i = 0; i < this.#origins.length; ++i) {
if (this.#origins[i].isSimilar(point3D, tol)) {
return true;
}
}
return false;
}
/**
* Get the object size.
* Warning: the size comes as stored in DICOM, meaning that it could
* be oriented.
*
* @param {Matrix33} [viewOrientation] The view orientation (optional).
* @returns {Size} The object size.
*/
getSize(viewOrientation) {
let res = this.#size;
if (viewOrientation && typeof viewOrientation !== 'undefined') {
let values = getOrientedArray3D(
[
this.#size.get(0),
this.#size.get(1),
this.#size.get(2)
],
viewOrientation);
values = values.map(Math.abs);
res = new Size(values.concat(this.#size.getValues().slice(3)));
}
return res;
}
/**
* Calculate slice spacing from origins and replace current
* if needed.
*/
updateSliceSpacing() {
const geoSliceSpacing = getSliceGeometrySpacing(this.#origins);
// update local if needed
if (typeof geoSliceSpacing !== 'undefined') {
// 1 is default
if (this.#spacing.get(2) !== 1 &&
this.#spacing.get(2) !== geoSliceSpacing) {
logger.debug(`Using geometric spacing ${ geoSliceSpacing
} instead of tag spacing ${this.#spacing.get(2)}`);
}
const values = this.#spacing.getValues();
values[2] = geoSliceSpacing;
this.#spacing = new Spacing(values);
}
}
/**
* Get the object spacing.
* Warning: the spacing comes as stored in DICOM, meaning that it could
* be oriented.
*
* @param {Matrix33} [viewOrientation] The view orientation (optional).
* @returns {Spacing} The object spacing.
*/
getSpacing(viewOrientation) {
let res = this.#spacing;
if (viewOrientation && typeof viewOrientation !== 'undefined') {
let orientedValues = getOrientedArray3D(
[
this.#spacing.get(0),
this.#spacing.get(1),
this.#spacing.get(2)
],
viewOrientation);
orientedValues = orientedValues.map(Math.abs);
res = new Spacing(orientedValues);
}
return res;
}
/**
* Get the image spacing in real world.
*
* @returns {Spacing} The object spacing.
*/
getRealSpacing() {
// asOneAndZeros to not change spacing values...
return this.getSpacing(
this.#orientation.getInverse().asOneAndZeros()
);
}
/**
* Get the object orientation.
*
* @returns {Matrix33} The object orientation.
*/
getOrientation() {
return this.#orientation;
}
/**
* Get the slice position of an origin in the current slice layout.
* Slice indices increase with decreasing origins (high index -> low origin),
* this simplified the handling of reconstruction since it means
* the displayed data is in the same 'direction' as the extracted data.
* As seen in the getOrigin method, the main origin is the lowest one.
* This implies that the index to world and reverse method do some flipping
* magic...
*
* Limitation: the codirectional (before/after) refinement below is a
* strict sign check on the normal-projected residual, with no
* tolerance - unlike worldToIndex's magnitude-based half-spacing
* gate. That is safe for this method's one real caller
* (Image#appendSlice, which only ever compares exact, already-known
* slice origins - a clean, large residual, never close to zero),
* but this method should not be used for an arbitrary point with a
* large in-plane offset from its closest origin (eg a click
* position): float noise in that offset, amplified by a
* lower-precision orientation (eg gantry-tilt direction cosines
* with few decimal digits), can flip the sign of a residual that
* should be exactly zero. Use worldToIndex (or a plain
* Point3D#getClosest) instead for that case.
*
* @param {Point3D} origin The origin to locate.
* @param {number} [time] Optional time id.
* @returns {number} The slice index.
*/
getSliceIndex(origin, time) {
// cannot use this.worldToIndex(origin).getK() directly: unlike
// this method, it can fall back to an out-of-range extrapolated
// index, which is not a valid insertion point here...
let localOrigins = this.#origins;
if (typeof time !== 'undefined') {
localOrigins = this.#times.get(time).origins;
}
// find the closest origin and how far past (or before) it the
// input origin is, along the slice-stacking direction
const closest = getClosestOriginResidual(
origin, localOrigins, this.#orientation);
// positive residual: origin is past the closest origin, so it
// belongs to the next slice index; zero or negative: it belongs
// to (or is before) the closest origin's own index
const sliceIndex = closest.normalResidual > 0
? closest.index + 1 : closest.index;
return sliceIndex;
}
/**
* Check if another geometry is compatible with this one, ie that
* slices with these geometries can be merged into one volume.
*
* @param {Geometry} rhs The geometry to check.
* @returns {BooleanResult} Result with success set to true if
* the geometry is compatible.
*/
canAppendSlice(rhs) {
// check size
const rhsSize = rhs.getSize();
if (rhsSize.get(2) !== 1) {
return {
success: false,
message: 'Cannot append more than one slice'
};
}
const size = this.getSize();
if (size.get(0) !== rhsSize.get(0)) {
return {
success: false,
message: 'Cannot append a slice with different number of columns'
};
}
if (size.get(1) !== rhsSize.get(1)) {
return {
success: false,
message: 'Cannot append a slice with different number of rows'
};
}
// check orientation
if (!this.getOrientation().isSimilar(
rhs.getOrientation(), DIRECTION_EPSILON)) {
return {
success: false,
message: 'Cannot append a slice with different orientation'
};
}
// check origin
const canAppendOrigin =
this.canAppendOrigin(rhs.getOrigin(), rhs.getInitialTime()?.id.value);
if (!canAppendOrigin.success) {
return canAppendOrigin;
}
return new BooleanResult(true);
}
/**
* Check if an origin can be appended to this geometry.
*
* @param {Point3D} origin The origin to append.
* @param {number} [time] Optional time id.
* @returns {BooleanResult} Result with success set to true if
* the origin is compatible.
*/
canAppendOrigin(origin, time) {
// equal callback
const equalToOrigin = function (element) {
return element.equals(origin);
};
const initialValue = this.#initialTime?.id.value;
if (typeof time !== 'undefined' && time !== initialValue) {
// check if not already in list
if (this.#times.has(time)) {
const found = this.#times.get(time).origins.find(equalToOrigin);
if (typeof found !== 'undefined') {
return {
success: false,
message: 'Cannot append same time origin twice'
};
}
}
} else {
// check if not already in list
const found = this.#origins.find(equalToOrigin);
if (typeof found !== 'undefined') {
return {
success: false,
message: 'Cannot append same origin twice'
};
}
}
return new BooleanResult(true);
}
/**
* Append an origin to the geometry.
*
* @param {Point3D} origin The origin to append.
* @param {number} index The index at which to append.
* @param {number} [time] Optional time id.
*/
appendOrigin(origin, index, time) {
// check if possible
const canAppend = this.canAppendOrigin(origin, time);
if (!canAppend.success) {
throw new Error(canAppend.message);
}
// add in origin array
if (typeof time !== 'undefined') {
this.#times.get(time).origins.splice(index, 0, origin);
}
if (typeof time === 'undefined' ||
time === this.#initialTime?.id.value) {
this.#origins.splice(index, 0, origin);
// increment second dimension
const values = this.#size.getValues();
values[2] += 1;
this.#size = new Size(values);
}
}
/**
* Append a frame to the geometry.
*
* @param {Point3D} origin The origin to append.
* @param {VolumeId} time The frame time: a volume id or, without
* source, a frame index.
*/
appendFrame(origin, time) {
// add origin to list
this.#setTime(time, [origin]);
// increment third dimension
const sizeValues = this.#size.getValues();
const spacingValues = this.#spacing.getValues();
if (sizeValues.length === 4) {
sizeValues[3] += 1;
} else {
sizeValues.push(2);
spacingValues.push(1);
}
this.#size = new Size(sizeValues);
this.#spacing = new Spacing(spacingValues);
}
/**
* Get a string representation of the geometry.
*
* @returns {string} The geometry as a string.
*/
toString() {
return `Origin: ${ this.getOrigin()
}, Size: ${ this.getSize()
}, Spacing: ${ this.getSpacing()
}, Orientation: ${this.getOrientation()}`;
}
/**
* Check for equality.
*
* @param {Geometry} rhs The object to compare to.
* @returns {boolean} True if both objects are equal.
*/
equals(rhs) {
return rhs !== null &&
typeof rhs !== 'undefined' &&
this.getOrigin().equals(rhs.getOrigin()) &&
this.getSize().equals(rhs.getSize()) &&
this.getSpacing().equals(rhs.getSpacing()) &&
this.getOrientation().equals(rhs.getOrientation());
}
/**
* Check for similarity for origin and orientation, equality
* for size and spacing.
*
* @param {Geometry} rhs The object to compare to.
* @param {number} [tol] Optional number comparison tolerance,
* defaults to Number.EPSILON.
* @returns {boolean} True if both objects are equal.
*/
isSimilar(rhs, tol) {
return rhs !== null &&
typeof rhs !== 'undefined' &&
this.getOrigin().isSimilar(rhs.getOrigin(), tol) &&
this.getSize().equals(rhs.getSize()) &&
this.getSpacing().equals(rhs.getSpacing()) &&
this.getOrientation().isSimilar(rhs.getOrientation(), tol);
}
/**
* Check that a point is within bounds.
*
* @param {Point} point The point to check.
* @returns {boolean} True if the given coordinates are within bounds.
*/
isInBounds(point) {
return this.isIndexInBounds(this.worldToIndex(point));
}
/**
* Check that a index is within bounds.
*
* @param {Index} index The index to check.
* @param {number[]} [dirs] Optional list of directions to check.
* @returns {boolean} True if the given coordinates are within bounds.
*/
isIndexInBounds(index, dirs) {
return this.getSize().isInBounds(index, dirs);
}
/**
* Get the geometrical range, ie the minimum and maximum
* positions.
*
* @returns {Point[]} The min and max positions.
*/
getRange() {
const nDims = this.getSize().length();
const minValues = new Array(nDims);
minValues.fill(0);
const minIndex = new Index(minValues);
const maxIndex = new Index(this.getSize().getValues());
return [
this.indexToWorld(minIndex),
this.indexToWorld(maxIndex)
];
}
/**
* Convert an index into world coordinates.
*
* @param {Index} index The index to convert.
* @returns {Point} The corresponding point.
*/
indexToWorld(index) {
// apply spacing
// (spacing is oriented, apply before orientation)
const spacing = this.getSpacing();
const orientedPoint3D = new Point3D(
index.get(0) * spacing.get(0),
index.get(1) * spacing.get(1),
index.get(2) * spacing.get(2)
);
// de-orient
const point3D = this.getOrientation().multiplyPoint3D(orientedPoint3D);
// keep >3d values
const values = index.getValues();
// volume index to volume id
const volumeIds = this.#getConversionVolumeIds();
if (values.length > 3 && typeof volumeIds !== 'undefined') {
values[3] = this.#volumeIndexToId(values[3], volumeIds);
}
const origin = this.getOrigin();
values[0] = origin.getX() + point3D.getX();
values[1] = origin.getY() + point3D.getY();
values[2] = origin.getZ() + point3D.getZ();
// return point
return new Point(values);
}
/**
* Convert a 3D point into world coordinates.
*
* @param {Point3D} point The 3D point to convert.
* @returns {Point3D} The corresponding world 3D point.
*/
pointToWorld(point) {
// apply spacing
// (spacing is oriented, apply before orientation)
const spacing = this.getSpacing();
const orientedPoint3D = new Point3D(
point.getX() * spacing.get(0),
point.getY() * spacing.get(1),
point.getZ() * spacing.get(2)
);
// de-orient
const point3D = this.getOrientation().multiplyPoint3D(orientedPoint3D);
// return point3D
const origin = this.getOrigin();
return new Point3D(
origin.getX() + point3D.getX(),
origin.getY() + point3D.getY(),
origin.getZ() + point3D.getZ()
);
}
/**
* Convert world coordinates into an index.
*
* Always returns an index, even for a point outside the geometry:
* this does not itself mean the point is in bounds, use
* isIndexInBounds/isInBounds for that. In-plane (row/column), an
* out-of-bounds point extrapolates freely (eg -5 or size+12). On the
* scroll axis, a point close to a real per-slice origin snaps to it;
* further away, it is pinned to just past the first/last known
* origin (ie the origins array length, or -1) rather than left to
* drift arbitrarily far via linear extrapolation - except when there
* are few or no real origins to compare against (eg a root geometry
* with only its first slice known), where it still falls back to
* that unclamped extrapolation.
*
* @param {Point} point The point to convert.
* @returns {Index} The corresponding index.
*/
worldToIndex(point) {
// compensate for origin
// (origin is not oriented, compensate before orientation)
const origin = this.getOrigin();
const point3D = new Point3D(
point.get(0) - origin.getX(),
point.get(1) - origin.getY(),
point.get(2) - origin.getZ()
);
// orient
const orientedPoint3D =
this.getOrientation().getInverse().multiplyPoint3D(point3D);
// keep >3d values
const values = point.getValues();
// volume id to volume index
const volumeIds = this.#getConversionVolumeIds();
if (values.length > 3 && typeof volumeIds !== 'undefined') {
values[3] = this.#volumeIdToIndex(values[3], volumeIds);
}
// apply spacing and floor for the in-plane (row/column) axes
// (precisionRound to avoid float number inaccuracies)
const spacing = this.getSpacing();
values[0] = Math.floor(precisionRound(
orientedPoint3D.getX() / spacing.get(0),
REAL_WORLD_EXPONENT
));
values[1] = Math.floor(precisionRound(
orientedPoint3D.getY() / spacing.get(1),
REAL_WORLD_EXPONENT
));
// scroll axis: prefer the nearest true per-slice origin over linear
// extrapolation from origin[0] when the position is actually close
// to one (within half a slice spacing, projected along the normal)
// - robust to per-slice origin drift/divergence regardless of
// slice count, unlike the naive arithmetic below on its own.
// Falls back to that arithmetic result when no real origin is
// that close, which correctly preserves both "genuinely out of
// bounds" and "this geometry only has some of its origins
// populated so far, extrapolate the rest" (eg a multi-frame DICOM
// root geometry with no per-frame position data, see
// dicomGeometry.js#getRootGeometry).
const naiveZ = Math.floor(precisionRound(
orientedPoint3D.getZ() / spacing.get(2),
REAL_WORLD_EXPONENT
));
values[2] = naiveZ;
const origins = this.getOrigins();
if (origins.length > 0) {
const closest = getClosestOriginResidual(
point.get3D(), origins, this.getOrientation());
if (Math.abs(closest.normalResidual) < spacing.get(2) / 2) {
values[2] = closest.index;
} else if (closest.index === origins.length - 1 &&
closest.normalResidual > 0 && values[2] < origins.length) {
// unambiguously past the last real origin (the residual is a
// full slice spacing or more, so its sign is not float-noise
// sensitive the way a near-zero one would be): naiveZ must not
// be allowed to land back inside the origins we actually have
// data for, regardless of any drift in its own arithmetic
values[2] = origins.length;
} else if (closest.index === 0 &&
closest.normalResidual < 0 && values[2] >= 0) {
// symmetric guard for the near side, before the first origin
values[2] = -1;
}
}
// return index
return new Index(values);
}
/**
* Convert world coordinates into an point.
*
* @param {Point} point The world point to convert.
* @returns {Point3D} The corresponding point.
*/
worldToPoint(point) {
// compensate for origin
// (origin is not oriented, compensate before orientation)
const origin = this.getOrigin();
const point3D = new Point3D(
point.get(0) - origin.getX(),
point.get(1) - origin.getY(),
point.get(2) - origin.getZ()
);
// orient
const orientedPoint3D =
this.getOrientation().getInverse().multiplyPoint3D(point3D);
// keep >3d values
const values = point.getValues();
// apply spacing and round
const spacing = this.getSpacing();
values[0] = orientedPoint3D.getX() / spacing.get(0);
values[1] = orientedPoint3D.getY() / spacing.get(1);
values[2] = orientedPoint3D.getZ() / spacing.get(2);
// return index
return new Point3D(values[0], values[1], values[2]);
}
} // class Geometry
/**
* Get the oriented values of an input 3D array.
*
* @param {number[]} array3D The 3D array.
* @param {Matrix33} orientation The orientation 3D matrix.
* @returns {number[]} The values reordered according to the orientation.
*/
export function getOrientedArray3D(array3D, orientation) {
// values = orientation * orientedValues
// -> inv(orientation) * values = orientedValues
return orientation.getInverse().multiplyArray3D(array3D);
}
/**
* Get the raw values of an oriented input 3D array.
*
* @param {number[]} array3D The 3D array.
* @param {Matrix33} orientation The orientation 3D matrix.
* @returns {number[]} The values reordered to compensate the orientation.
*/
export function getDeOrientedArray3D(array3D, orientation) {
// values = orientation * orientedValues
return orientation.multiplyArray3D(array3D);
}
/**
* Get the slice spacing from the difference in the Z directions
* of input origins.
*
* @param {Point3D[]} origins An array of Point3D.
* @returns {number|undefined} The spacing.
*/
export function getSliceGeometrySpacing(origins) {
// check origins
if (origins.length <= 1) {
return;
}
const spacings = [];
for (let i = 0; i < origins.length - 1; ++i) {
const origin1 = origins[i];
const origin2 = origins[i + 1];
const sliceSpacing = origin1.getDistance(origin2);
if (sliceSpacing === 0) {
throw new Error(`Zero slice spacing ${
origin1.toString() } ${origin2.toString()}`);
}
spacings.push(sliceSpacing);
}
// use rounded mean value as spacing
const stats = getBasicStats(spacings);
const spacing = precisionRound(stats.mean, 4);
// warn if non constant
if (stats.stdDev > REAL_WORLD_EPSILON) {
logger.warn(`Varying slice spacing, value: ${ spacing
} (mean: ${ stats.mean
}, min: ${ stats.min
}, max: ${ stats.max
}, stdDev: ${stats.stdDev})`);
}
return spacing;
}
/**
* Volume ids to copy onto a merged geometry.
*
* A geometry qualifies when it has one id per volume and that count
* is the merged volume count. Copying them keeps world positions
* (volume ids) convertible back to volume indices.
*
* @param {Geometry} geometry The input geometry.
* @param {number|undefined} volumeCount The merged volume count.
* @returns {VolumeId[]|undefined} The ids to copy.
*/
function getVolumeIdsForMerge(geometry, volumeCount) {
if (typeof volumeCount !== 'number' ||
geometry.getSize().length() < 4 ||
geometry.getSize().get(3) !== volumeCount) {
return;
}
const volumeIds = geometry.getVolumeIds();
if (typeof volumeIds === 'undefined' ||
volumeIds.length !== volumeCount) {
return;
}
return volumeIds;
}
/**
* Check that two volume id lists match.
*
* @param {VolumeId[]} ids0 The first list.
* @param {VolumeId[]} ids1 The second list.
* @returns {boolean} True when source, tag and value match in order.
*/
function sameVolumeIds(ids0, ids1) {
if (ids0.length !== ids1.length) {
return false;
}
for (let i = 0; i < ids0.length; ++i) {
const id0 = ids0[i].id;
const id1 = ids1[i].id;
if (id0.value !== id1.value ||
id0.source !== id1.source ||
id0.tagKey !== id1.tagKey) {
return false;
}
}
return true;
}
/**
* Merge two geometries into one using the merge size and
* smallest resolution.
* Volume ids are kept when one input defines them for the merged
* volume count, or both define the same ids. A 3D overlay then
* does not drop the 4D underlay volume index.
* WARNING: needs to be called with the final geometries.
*
* @param {Geometry} geometry1 The first geometry.
* @param {Geometry} geometry2 The second geometry.
* @returns {Geometry} The merged geometry.
*/
export function mergeGeometries(geometry1, geometry2) {
const orientation = geometry1.getOrientation();
// check input
if (!orientation.isSimilar(
geometry2.getOrientation(), DIRECTION_EPSILON)) {
throw new Error('Cannot merge geometries with different orientation');
}
const invOrientation = orientation.getInverse();
const minByIndex = function (array1, array2) {
return arrayMap(array1, array2, Math.min);
};
const maxByIndex = function (array1, array2) {
return arrayMap(array1, array2, Math.max);
};
const newSpacing = new Spacing(minByIndex(
geometry1.getSpacing().getValues(),
geometry2.getSpacing().getValues()
));
const deorient = function (item) {
return invOrientation.multiplyPoint3D(item.get3D());
};
const range1 = geometry1.getRange().map(deorient);
const range2 = geometry2.getRange().map(deorient);
const minRangeValues = minByIndex(
range1[0].getValues(),
range2[0].getValues()
);
const maxRangeValues = maxByIndex(
range1[1].getValues(),
range2[1].getValues()
);
let sizeValues = [];
for (let i = 0; i < minRangeValues.length; ++i) {
sizeValues.push(Math.round(
Math.abs(maxRangeValues[i] - minRangeValues[i]) / newSpacing.get(i)
));
}
// handle extra dims
const maxSize = maxByIndex(
geometry1.getSize().getValues(),
geometry2.getSize().getValues()
);
sizeValues = sizeValues.concat(maxSize.slice(3));
const newSize = new Size(sizeValues);
const newOrigins = [];
for (let i = 0; i < newSize.get(2); ++i) {
const values = minRangeValues.slice();
values[2] = minRangeValues[2] + i * newSpacing.get(2);
const origin = new Point3D(values[0], values[1], values[2]);
newOrigins.push(orientation.multiplyPoint3D(origin));
}
const merged = new Geometry(
newOrigins,
newSize,
newSpacing,
orientation
);
const volumeCount = newSize.length() > 3 ? newSize.get(3) : undefined;
const volumeIds1 = getVolumeIdsForMerge(geometry1, volumeCount);
const volumeIds2 = getVolumeIdsForMerge(geometry2, volumeCount);
if (typeof volumeIds1 !== 'undefined' &&
typeof volumeIds2 !== 'undefined') {
if (sameVolumeIds(volumeIds1, volumeIds2)) {
merged.setVolumeIds(volumeIds1);
}
} else if (typeof volumeIds1 !== 'undefined') {
merged.setVolumeIds(volumeIds1);
} else if (typeof volumeIds2 !== 'undefined') {
merged.setVolumeIds(volumeIds2);
}
return merged;
}