Skip to content

Main content

OPTICS Clustering Tool Source Code

Browse the implementation files for OPTICS Clustering Tool.
tool.ts typescript
import { parseFiniteNumberList } from '../../parse/numeric-dataset/tool';
import { parseFiniteNumber } from '../../parse/number/tool';
import { parseInteger } from '../../parse/integer/tool';

type OrderedPoint = {
	coreDistance: number | null;
	index: number;
	point: number[];
	reachabilityDistance: number | null;
};
const distance = (a: number[], b: number[]) =>
	Math.hypot(...a.map((value, index) => value - b[index]));

export const runOptics = (
	pointsInput: unknown,
	epsilonInput: unknown,
	minimumPointsInput: unknown
): string => {
	if (typeof pointsInput !== 'string') return '';
	const epsilon = parseFiniteNumber(epsilonInput);
	const minimumPoints = parseInteger(minimumPointsInput);
	const points = pointsInput
		.trim()
		.split(/\n+/)
		.map(parseFiniteNumberList);
	if (
		epsilon === null ||
		epsilon <= 0 ||
		minimumPoints === null ||
		minimumPoints < 2 ||
		points.length < minimumPoints ||
		points.length > 5_000 ||
		points.some((point) => !point) ||
		new Set(points.map((point) => point!.length)).size !== 1 ||
		points.length * (points[0]?.length ?? 0) > 1_000_000
	)
		return '';
	const values = points as number[][];
	const processed = new Set<number>();
	const reachability = Array<number>(values.length).fill(
		Infinity
	);
	const ordering: OrderedPoint[] = [];
	const neighbors = (index: number) =>
		values
			.map((point, other) => ({
				distance: distance(values[index], point),
				index: other
			}))
			.filter((candidate) => candidate.distance <= epsilon)
			.sort(
				(a, b) => a.distance - b.distance || a.index - b.index
			);
	const coreDistance = (nearby: { distance: number }[]) =>
		nearby.length >= minimumPoints
			? nearby[minimumPoints - 1].distance
			: Infinity;
	const expand = (start: number) => {
		const seeds = [start];
		while (seeds.length) {
			seeds.sort(
				(a, b) => reachability[a] - reachability[b] || a - b
			);
			const current = seeds.shift()!;
			if (processed.has(current)) continue;
			processed.add(current);
			const nearby = neighbors(current);
			const core = coreDistance(nearby);
			ordering.push({
				coreDistance: Number.isFinite(core)
					? Number(core.toPrecision(10))
					: null,
				index: current,
				point: values[current],
				reachabilityDistance: Number.isFinite(
					reachability[current]
				)
					? Number(reachability[current].toPrecision(10))
					: null
			});
			if (!Number.isFinite(core)) continue;
			for (const candidate of nearby)
				if (!processed.has(candidate.index)) {
					const updated = Math.max(core, candidate.distance);
					if (updated < reachability[candidate.index]) {
						reachability[candidate.index] = updated;
						if (!seeds.includes(candidate.index))
							seeds.push(candidate.index);
					}
				}
		}
	};
	for (let index = 0; index < values.length; index += 1)
		if (!processed.has(index)) expand(index);
	return JSON.stringify(
		{ epsilon, minimumPoints, ordering },
		null,
		2
	);
};

export const Tool: TypeTool = {
	name: 'OPTICS Clustering Tool',
	slug: 'clustering/optics',
	intro:
		'Order multidimensional points by density reachability with the OPTICS clustering algorithm.',
	tool: runOptics,
	i: [
		{
			example: '0,0\n0.1,0\n0,0.1\n5,5\n5.1,5\n5,5.1',
			label: 'Points',
			placeholder: 'One numeric point per line',
			render: 'textarea',
			type: 'text'
		},
		{
			example: '0.5',
			label: 'Maximum Radius',
			placeholder: 'Positive epsilon',
			type: 'number'
		},
		{
			example: '3',
			label: 'Minimum Points',
			placeholder: 'Core-neighborhood size',
			type: 'number'
		}
	],
	o: [
		{
			example: '{ "ordering": [] }',
			label: 'OPTICS Ordering',
			placeholder: 'Reachability ordering will appear here...',
			render: 'textarea',
			type: 'text'
		}
	],
	cite: [
		{
			title: 'OPTICS algorithm - Wikipedia',
			url: 'https://en.wikipedia.org/wiki/OPTICS_algorithm'
		}
	]
};
export default Tool;

Description

Browse the implementation files for OPTICS Clustering Tool.

References

  1. Tool.io on GitHub
  2. Tool.io TypeScript tools library

Similar or alternative tools