100pah commented on code in PR #19941:
URL: https://github.com/apache/echarts/pull/19941#discussion_r1841860653
##########
src/util/jitter.ts:
##########
@@ -0,0 +1,129 @@
+import type Axis from '../coord/Axis';
+import type { AxisBaseModel } from '../coord/AxisBaseModel';
+import Axis2D from '../coord/cartesian/Axis2D';
+import type SingleAxis from '../coord/single/SingleAxis';
+import type SeriesModel from '../model/Series';
+import { makeInner } from './model';
+
+export function needFixJitter(seriesModel: SeriesModel, axis: Axis): boolean {
+ const { coordinateSystem } = seriesModel;
+ const { type: coordType } = coordinateSystem;
+ const baseAxis = coordinateSystem.getBaseAxis();
+ const { type: scaleType } = baseAxis.scale;
+ const seriesValid = coordType === 'cartesian2d'
+ && (scaleType === 'category' || scaleType === 'ordinal')
+ || coordType === 'single';
+
+ const axisValid = (axis.model as AxisBaseModel).get('jitter') > 0;
+ return seriesValid && axisValid;
+}
+
+export type JitterData = {
+ fixedCoord: number,
+ floatCoord: number,
+ r: number
+};
+
+const inner = makeInner<{ items: JitterData[] }, Axis2D | SingleAxis>();
+
+/**
+ * Fix jitter for overlapping data points.
+ *
+ * @param fixedAxis The axis whose coord doesn't change with jitter.
+ * @param fixedCoord The coord of fixedAxis.
+ * @param floatCoord The coord of the other axis, which should be changed with
jittering.
+ * @param radius The radius of the data point, considering the symbol is a
circle.
+ * @returns updated floatCoord.
+ */
+export function fixJitter(
+ fixedAxis: Axis2D | SingleAxis,
+ fixedCoord: number,
+ floatCoord: number,
+ radius: number
+): number {
+ if (fixedAxis instanceof Axis2D) {
+ const scaleType = fixedAxis.scale.type;
+ if (scaleType !== 'category' && scaleType !== 'ordinal') {
+ return floatCoord;
+ }
+ }
+ const axisModel = fixedAxis.model as AxisBaseModel;
+ const jitter = axisModel.get('jitter');
+ const jitterOverlap = axisModel.get('jitterOverlap');
+ const jitterMargin = axisModel.get('jitterMargin') || 0;
+ if (jitter > 0) {
+ if (jitterOverlap) {
+ return fixJitterIgnoreOverlaps(floatCoord, jitter);
+ }
+ else {
+ return fixJitterAvoidOverlaps(fixedAxis, fixedCoord, floatCoord,
radius, jitter, jitterMargin);
+ }
+ }
+ return floatCoord;
+}
+
+function fixJitterIgnoreOverlaps(floatCoord: number, jitter: number): number {
+ return floatCoord + (Math.random() - 0.5) * jitter;
Review Comment:
I think also need to clamp with the coordinate system boundary, otherwise
the invalid outcome coords will cause that some points can not be draw and hard
to be discovered by developers. The same goes for the overlap processing.
##########
src/util/jitter.ts:
##########
@@ -0,0 +1,129 @@
+import type Axis from '../coord/Axis';
+import type { AxisBaseModel } from '../coord/AxisBaseModel';
+import Axis2D from '../coord/cartesian/Axis2D';
+import type SingleAxis from '../coord/single/SingleAxis';
+import type SeriesModel from '../model/Series';
+import { makeInner } from './model';
+
+export function needFixJitter(seriesModel: SeriesModel, axis: Axis): boolean {
+ const { coordinateSystem } = seriesModel;
+ const { type: coordType } = coordinateSystem;
+ const baseAxis = coordinateSystem.getBaseAxis();
+ const { type: scaleType } = baseAxis.scale;
+ const seriesValid = coordType === 'cartesian2d'
+ && (scaleType === 'category' || scaleType === 'ordinal')
+ || coordType === 'single';
+
+ const axisValid = (axis.model as AxisBaseModel).get('jitter') > 0;
+ return seriesValid && axisValid;
+}
+
+export type JitterData = {
+ fixedCoord: number,
+ floatCoord: number,
+ r: number
+};
+
+const inner = makeInner<{ items: JitterData[] }, Axis2D | SingleAxis>();
+
+/**
+ * Fix jitter for overlapping data points.
+ *
+ * @param fixedAxis The axis whose coord doesn't change with jitter.
+ * @param fixedCoord The coord of fixedAxis.
+ * @param floatCoord The coord of the other axis, which should be changed with
jittering.
+ * @param radius The radius of the data point, considering the symbol is a
circle.
+ * @returns updated floatCoord.
+ */
+export function fixJitter(
+ fixedAxis: Axis2D | SingleAxis,
+ fixedCoord: number,
+ floatCoord: number,
+ radius: number
+): number {
+ if (fixedAxis instanceof Axis2D) {
+ const scaleType = fixedAxis.scale.type;
+ if (scaleType !== 'category' && scaleType !== 'ordinal') {
+ return floatCoord;
+ }
+ }
+ const axisModel = fixedAxis.model as AxisBaseModel;
+ const jitter = axisModel.get('jitter');
+ const jitterOverlap = axisModel.get('jitterOverlap');
+ const jitterMargin = axisModel.get('jitterMargin') || 0;
+ if (jitter > 0) {
+ if (jitterOverlap) {
+ return fixJitterIgnoreOverlaps(floatCoord, jitter);
+ }
+ else {
+ return fixJitterAvoidOverlaps(fixedAxis, fixedCoord, floatCoord,
radius, jitter, jitterMargin);
+ }
+ }
+ return floatCoord;
+}
+
+function fixJitterIgnoreOverlaps(floatCoord: number, jitter: number): number {
+ return floatCoord + (Math.random() - 0.5) * jitter;
+}
+
+function fixJitterAvoidOverlaps(
+ fixedAxis: Axis2D | SingleAxis,
+ fixedCoord: number,
+ floatCoord: number,
+ radius: number,
+ jitter: number,
+ margin: number
+): number {
+ const store = inner(fixedAxis);
+ if (!store.items) {
+ store.items = [];
+ }
+ const items = store.items;
+
+ const floatA = placeJitterOnDirection(items, fixedCoord, floatCoord,
radius, jitter, margin, 1);
+ const floatB = placeJitterOnDirection(items, fixedCoord, floatCoord,
radius, jitter, margin, -1);
+ let minFloat = Math.abs(floatA - floatCoord) < Math.abs(floatB -
floatCoord) ? floatA : floatB;
+ if (Math.abs(minFloat - floatCoord) > jitter / 2) {
+ // If the new item is moved too far, then give up.
+ // Fall back to random jitter.
+ minFloat = fixJitterIgnoreOverlaps(floatCoord, jitter);
+ }
+
+ items.push({ fixedCoord, floatCoord: minFloat, r: radius });
+ return minFloat;
+}
+
+function placeJitterOnDirection(
+ items: JitterData[],
+ fixedCoord: number,
+ floatCoord: number,
+ radius: number,
+ jitter: number,
+ margin: number,
+ direction: 1 | -1
+) {
+ // Check for overlap with previous items.
+ let y = floatCoord;
+ for (let i = 0; i < items.length; i++) {
+ const item = items[i];
+ const dx = fixedCoord - item.fixedCoord;
+ const dy = y - item.floatCoord;
+ const d2 = dx * dx + dy * dy;
+ const r = radius + item.r + margin;
+ if (d2 < r * r) {
+ // Overlap. Try to move the new item along otherCoord direction.
+ const newY = item.floatCoord + Math.sqrt(r * r - dx * dx) *
direction;
+ if (direction > 0 && newY > y || direction < 0 && newY < y) {
+ y = newY;
+ i = 0; // Back to check from the first item.
Review Comment:
I think if the `items` is ordered by floatCoord, the backtracking (`i = 0`)
here is not necessary. With this backtracking, the entire algorithm could
degraded to O(n^3) in the worst case. But without it, it can keep O(n^2).
Just have a try, to modify it (with a linked list and sort in ascending
order by floatCoord):
```ts
export type JitterData = {
fixedCoord: number;
floatCoord: number;
r: number;
next: JitterData | null;
prev: JitterData | null;
};
// Items is a circular linked list, in the ascending order by floatCoord.
const inner = makeInner<{ items: JitterData }, Axis2D | SingleAxis>();
function fixJitterAvoidOverlaps(
fixedAxis: Axis2D | SingleAxis,
fixedCoord: number,
floatCoord: number,
radius: number,
jitter: number,
margin: number
): number {
const store = inner(fixedAxis);
if (!store.items) {
store.items = {
fixedCoord: -1,
floatCoord: -1,
r: -1,
next: null, // head of a link list
prev: null, // tail of a link list
};
store.items.next = store.items;
store.items.prev = store.items;
}
const items = store.items;
const overlapA = placeJitterOnDirection(items, fixedCoord, floatCoord,
radius, jitter, margin, 1);
const overlapB = placeJitterOnDirection(items, fixedCoord, floatCoord,
radius, jitter, margin, -1);
const overlapResult = Math.abs(overlapA.resultCoord - floatCoord) <
Math.abs(overlapB.resultCoord - floatCoord)
? overlapA : overlapB;
let minFloat = overlapResult.resultCoord;
if (Math.abs(minFloat - floatCoord) > jitter / 2) {
// If the new item is moved too far, then give up.
// Fall back to random jitter.
minFloat = fixJitterIgnoreOverlaps(floatCoord, jitter);
}
// Insert to store
const insertBy = overlapResult.insertBy;
const resultDirection = overlapResult.direction;
const pointer1 = resultDirection > 0 ? 'next' : 'prev';
const pointer2 = resultDirection > 0 ? 'prev' : 'next';
const newItem: JitterData = {
fixedCoord: fixedCoord,
floatCoord: overlapResult.resultCoord,
r: radius,
next: null,
prev: null,
};
newItem[pointer1] = insertBy[pointer1];
newItem[pointer2] = insertBy;
insertBy[pointer1][pointer2] = newItem;
insertBy[pointer1] = newItem;
return minFloat;
}
function placeJitterOnDirection(
items: JitterData,
fixedCoord: number,
floatCoord: number,
radius: number,
jitter: number,
margin: number,
direction: 1 | -1
): {
resultCoord: number;
insertBy: JitterData;
direction: 1 | -1;
} {
// Check for overlap with previous items.
let y = floatCoord;
const pointer1 = direction > 0 ? 'next' : 'prev';
let insertBy = items;
let item = items[pointer1];
while (item !== items) {
const dx = fixedCoord - item.fixedCoord;
const dy = y - item.floatCoord;
const d2 = dx * dx + dy * dy;
const r = radius + item.r + margin;
if (d2 < r * r) {
// Overlap. Try to move the new item along otherCoord direction.
y = item.floatCoord + Math.sqrt(r * r - dx * dx) * direction;
insertBy = item;
if (Math.abs(y - floatCoord) > jitter / 2) {
// If the new item is moved too far, then give up.
// Fall back to random jitter.
return {resultCoord: Number.MAX_VALUE, insertBy, direction};
}
}
item = item[pointer1];
}
return {resultCoord: y, insertBy, direction};
}
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
