bounds.ts 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515
  1. import {
  2. ExcalidrawElement,
  3. ExcalidrawLinearElement,
  4. Arrowhead,
  5. ExcalidrawFreeDrawElement,
  6. } from "./types";
  7. import { distance2d, rotate } from "../math";
  8. import rough from "roughjs/bin/rough";
  9. import { Drawable, Op } from "roughjs/bin/core";
  10. import { Point } from "../types";
  11. import {
  12. getShapeForElement,
  13. generateRoughOptions,
  14. } from "../renderer/renderElement";
  15. import { isFreeDrawElement, isLinearElement } from "./typeChecks";
  16. import { rescalePoints } from "../points";
  17. // x and y position of top left corner, x and y position of bottom right corner
  18. export type Bounds = readonly [number, number, number, number];
  19. // If the element is created from right to left, the width is going to be negative
  20. // This set of functions retrieves the absolute position of the 4 points.
  21. export const getElementAbsoluteCoords = (
  22. element: ExcalidrawElement,
  23. ): Bounds => {
  24. if (isFreeDrawElement(element)) {
  25. return getFreeDrawElementAbsoluteCoords(element);
  26. } else if (isLinearElement(element)) {
  27. return getLinearElementAbsoluteCoords(element);
  28. }
  29. return [
  30. element.x,
  31. element.y,
  32. element.x + element.width,
  33. element.y + element.height,
  34. ];
  35. };
  36. export const pointRelativeTo = (
  37. element: ExcalidrawElement,
  38. absoluteCoords: Point,
  39. ): Point => {
  40. return [absoluteCoords[0] - element.x, absoluteCoords[1] - element.y];
  41. };
  42. export const getDiamondPoints = (element: ExcalidrawElement) => {
  43. // Here we add +1 to avoid these numbers to be 0
  44. // otherwise rough.js will throw an error complaining about it
  45. const topX = Math.floor(element.width / 2) + 1;
  46. const topY = 0;
  47. const rightX = element.width;
  48. const rightY = Math.floor(element.height / 2) + 1;
  49. const bottomX = topX;
  50. const bottomY = element.height;
  51. const leftX = 0;
  52. const leftY = rightY;
  53. return [topX, topY, rightX, rightY, bottomX, bottomY, leftX, leftY];
  54. };
  55. export const getCurvePathOps = (shape: Drawable): Op[] => {
  56. for (const set of shape.sets) {
  57. if (set.type === "path") {
  58. return set.ops;
  59. }
  60. }
  61. return shape.sets[0].ops;
  62. };
  63. const getMinMaxXYFromCurvePathOps = (
  64. ops: Op[],
  65. transformXY?: (x: number, y: number) => [number, number],
  66. ): [number, number, number, number] => {
  67. let currentP: Point = [0, 0];
  68. const { minX, minY, maxX, maxY } = ops.reduce(
  69. (limits, { op, data }) => {
  70. // There are only four operation types:
  71. // move, bcurveTo, lineTo, and curveTo
  72. if (op === "move") {
  73. // change starting point
  74. currentP = data as unknown as Point;
  75. // move operation does not draw anything; so, it always
  76. // returns false
  77. } else if (op === "bcurveTo") {
  78. // create points from bezier curve
  79. // bezier curve stores data as a flattened array of three positions
  80. // [x1, y1, x2, y2, x3, y3]
  81. const p1 = [data[0], data[1]] as Point;
  82. const p2 = [data[2], data[3]] as Point;
  83. const p3 = [data[4], data[5]] as Point;
  84. const p0 = currentP;
  85. currentP = p3;
  86. const equation = (t: number, idx: number) =>
  87. Math.pow(1 - t, 3) * p3[idx] +
  88. 3 * t * Math.pow(1 - t, 2) * p2[idx] +
  89. 3 * Math.pow(t, 2) * (1 - t) * p1[idx] +
  90. p0[idx] * Math.pow(t, 3);
  91. let t = 0;
  92. while (t <= 1.0) {
  93. let x = equation(t, 0);
  94. let y = equation(t, 1);
  95. if (transformXY) {
  96. [x, y] = transformXY(x, y);
  97. }
  98. limits.minY = Math.min(limits.minY, y);
  99. limits.minX = Math.min(limits.minX, x);
  100. limits.maxX = Math.max(limits.maxX, x);
  101. limits.maxY = Math.max(limits.maxY, y);
  102. t += 0.1;
  103. }
  104. } else if (op === "lineTo") {
  105. // TODO: Implement this
  106. } else if (op === "qcurveTo") {
  107. // TODO: Implement this
  108. }
  109. return limits;
  110. },
  111. { minX: Infinity, minY: Infinity, maxX: -Infinity, maxY: -Infinity },
  112. );
  113. return [minX, minY, maxX, maxY];
  114. };
  115. const getBoundsFromPoints = (
  116. points: ExcalidrawFreeDrawElement["points"],
  117. ): [number, number, number, number] => {
  118. let minX = Infinity;
  119. let minY = Infinity;
  120. let maxX = -Infinity;
  121. let maxY = -Infinity;
  122. for (const [x, y] of points) {
  123. minX = Math.min(minX, x);
  124. minY = Math.min(minY, y);
  125. maxX = Math.max(maxX, x);
  126. maxY = Math.max(maxY, y);
  127. }
  128. return [minX, minY, maxX, maxY];
  129. };
  130. const getFreeDrawElementAbsoluteCoords = (
  131. element: ExcalidrawFreeDrawElement,
  132. ): [number, number, number, number] => {
  133. const [minX, minY, maxX, maxY] = getBoundsFromPoints(element.points);
  134. return [
  135. minX + element.x,
  136. minY + element.y,
  137. maxX + element.x,
  138. maxY + element.y,
  139. ];
  140. };
  141. const getLinearElementAbsoluteCoords = (
  142. element: ExcalidrawLinearElement,
  143. ): [number, number, number, number] => {
  144. let coords: [number, number, number, number];
  145. if (element.points.length < 2 || !getShapeForElement(element)) {
  146. // XXX this is just a poor estimate and not very useful
  147. const { minX, minY, maxX, maxY } = element.points.reduce(
  148. (limits, [x, y]) => {
  149. limits.minY = Math.min(limits.minY, y);
  150. limits.minX = Math.min(limits.minX, x);
  151. limits.maxX = Math.max(limits.maxX, x);
  152. limits.maxY = Math.max(limits.maxY, y);
  153. return limits;
  154. },
  155. { minX: Infinity, minY: Infinity, maxX: -Infinity, maxY: -Infinity },
  156. );
  157. coords = [
  158. minX + element.x,
  159. minY + element.y,
  160. maxX + element.x,
  161. maxY + element.y,
  162. ];
  163. } else {
  164. const shape = getShapeForElement(element) as Drawable[];
  165. // first element is always the curve
  166. const ops = getCurvePathOps(shape[0]);
  167. const [minX, minY, maxX, maxY] = getMinMaxXYFromCurvePathOps(ops);
  168. coords = [
  169. minX + element.x,
  170. minY + element.y,
  171. maxX + element.x,
  172. maxY + element.y,
  173. ];
  174. }
  175. return coords;
  176. };
  177. export const getArrowheadPoints = (
  178. element: ExcalidrawLinearElement,
  179. shape: Drawable[],
  180. position: "start" | "end",
  181. arrowhead: Arrowhead,
  182. ) => {
  183. const ops = getCurvePathOps(shape[0]);
  184. if (ops.length < 1) {
  185. return null;
  186. }
  187. // The index of the bCurve operation to examine.
  188. const index = position === "start" ? 1 : ops.length - 1;
  189. const data = ops[index].data;
  190. const p3 = [data[4], data[5]] as Point;
  191. const p2 = [data[2], data[3]] as Point;
  192. const p1 = [data[0], data[1]] as Point;
  193. // We need to find p0 of the bezier curve.
  194. // It is typically the last point of the previous
  195. // curve; it can also be the position of moveTo operation.
  196. const prevOp = ops[index - 1];
  197. let p0: Point = [0, 0];
  198. if (prevOp.op === "move") {
  199. p0 = prevOp.data as unknown as Point;
  200. } else if (prevOp.op === "bcurveTo") {
  201. p0 = [prevOp.data[4], prevOp.data[5]];
  202. }
  203. // B(t) = p0 * (1-t)^3 + 3p1 * t * (1-t)^2 + 3p2 * t^2 * (1-t) + p3 * t^3
  204. const equation = (t: number, idx: number) =>
  205. Math.pow(1 - t, 3) * p3[idx] +
  206. 3 * t * Math.pow(1 - t, 2) * p2[idx] +
  207. 3 * Math.pow(t, 2) * (1 - t) * p1[idx] +
  208. p0[idx] * Math.pow(t, 3);
  209. // Ee know the last point of the arrow (or the first, if start arrowhead).
  210. const [x2, y2] = position === "start" ? p0 : p3;
  211. // By using cubic bezier equation (B(t)) and the given parameters,
  212. // we calculate a point that is closer to the last point.
  213. // The value 0.3 is chosen arbitrarily and it works best for all
  214. // the tested cases.
  215. const [x1, y1] = [equation(0.3, 0), equation(0.3, 1)];
  216. // Find the normalized direction vector based on the
  217. // previously calculated points.
  218. const distance = Math.hypot(x2 - x1, y2 - y1);
  219. const nx = (x2 - x1) / distance;
  220. const ny = (y2 - y1) / distance;
  221. const size = {
  222. arrow: 30,
  223. bar: 15,
  224. dot: 15,
  225. triangle: 15,
  226. }[arrowhead]; // pixels (will differ for each arrowhead)
  227. let length = 0;
  228. if (arrowhead === "arrow") {
  229. // Length for -> arrows is based on the length of the last section
  230. const [cx, cy] = element.points[element.points.length - 1];
  231. const [px, py] =
  232. element.points.length > 1
  233. ? element.points[element.points.length - 2]
  234. : [0, 0];
  235. length = Math.hypot(cx - px, cy - py);
  236. } else {
  237. // Length for other arrowhead types is based on the total length of the line
  238. for (let i = 0; i < element.points.length; i++) {
  239. const [px, py] = element.points[i - 1] || [0, 0];
  240. const [cx, cy] = element.points[i];
  241. length += Math.hypot(cx - px, cy - py);
  242. }
  243. }
  244. // Scale down the arrowhead until we hit a certain size so that it doesn't look weird.
  245. // This value is selected by minimizing a minimum size with the last segment of the arrowhead
  246. const minSize = Math.min(size, length / 2);
  247. const xs = x2 - nx * minSize;
  248. const ys = y2 - ny * minSize;
  249. if (arrowhead === "dot") {
  250. const r = Math.hypot(ys - y2, xs - x2) + element.strokeWidth;
  251. return [x2, y2, r];
  252. }
  253. const angle = {
  254. arrow: 20,
  255. bar: 90,
  256. triangle: 25,
  257. }[arrowhead]; // degrees
  258. // Return points
  259. const [x3, y3] = rotate(xs, ys, x2, y2, (-angle * Math.PI) / 180);
  260. const [x4, y4] = rotate(xs, ys, x2, y2, (angle * Math.PI) / 180);
  261. return [x2, y2, x3, y3, x4, y4];
  262. };
  263. const getLinearElementRotatedBounds = (
  264. element: ExcalidrawLinearElement,
  265. cx: number,
  266. cy: number,
  267. ): [number, number, number, number] => {
  268. if (element.points.length < 2 || !getShapeForElement(element)) {
  269. // XXX this is just a poor estimate and not very useful
  270. const { minX, minY, maxX, maxY } = element.points.reduce(
  271. (limits, [x, y]) => {
  272. [x, y] = rotate(element.x + x, element.y + y, cx, cy, element.angle);
  273. limits.minY = Math.min(limits.minY, y);
  274. limits.minX = Math.min(limits.minX, x);
  275. limits.maxX = Math.max(limits.maxX, x);
  276. limits.maxY = Math.max(limits.maxY, y);
  277. return limits;
  278. },
  279. { minX: Infinity, minY: Infinity, maxX: -Infinity, maxY: -Infinity },
  280. );
  281. return [minX, minY, maxX, maxY];
  282. }
  283. const shape = getShapeForElement(element) as Drawable[];
  284. // first element is always the curve
  285. const ops = getCurvePathOps(shape[0]);
  286. const transformXY = (x: number, y: number) =>
  287. rotate(element.x + x, element.y + y, cx, cy, element.angle);
  288. return getMinMaxXYFromCurvePathOps(ops, transformXY);
  289. };
  290. // We could cache this stuff
  291. export const getElementBounds = (
  292. element: ExcalidrawElement,
  293. ): [number, number, number, number] => {
  294. let bounds: [number, number, number, number];
  295. const [x1, y1, x2, y2] = getElementAbsoluteCoords(element);
  296. const cx = (x1 + x2) / 2;
  297. const cy = (y1 + y2) / 2;
  298. if (isFreeDrawElement(element)) {
  299. const [minX, minY, maxX, maxY] = getBoundsFromPoints(
  300. element.points.map(([x, y]) =>
  301. rotate(x, y, cx - element.x, cy - element.y, element.angle),
  302. ),
  303. );
  304. return [
  305. minX + element.x,
  306. minY + element.y,
  307. maxX + element.x,
  308. maxY + element.y,
  309. ];
  310. } else if (isLinearElement(element)) {
  311. bounds = getLinearElementRotatedBounds(element, cx, cy);
  312. } else if (element.type === "diamond") {
  313. const [x11, y11] = rotate(cx, y1, cx, cy, element.angle);
  314. const [x12, y12] = rotate(cx, y2, cx, cy, element.angle);
  315. const [x22, y22] = rotate(x1, cy, cx, cy, element.angle);
  316. const [x21, y21] = rotate(x2, cy, cx, cy, element.angle);
  317. const minX = Math.min(x11, x12, x22, x21);
  318. const minY = Math.min(y11, y12, y22, y21);
  319. const maxX = Math.max(x11, x12, x22, x21);
  320. const maxY = Math.max(y11, y12, y22, y21);
  321. bounds = [minX, minY, maxX, maxY];
  322. } else if (element.type === "ellipse") {
  323. const w = (x2 - x1) / 2;
  324. const h = (y2 - y1) / 2;
  325. const cos = Math.cos(element.angle);
  326. const sin = Math.sin(element.angle);
  327. const ww = Math.hypot(w * cos, h * sin);
  328. const hh = Math.hypot(h * cos, w * sin);
  329. bounds = [cx - ww, cy - hh, cx + ww, cy + hh];
  330. } else {
  331. const [x11, y11] = rotate(x1, y1, cx, cy, element.angle);
  332. const [x12, y12] = rotate(x1, y2, cx, cy, element.angle);
  333. const [x22, y22] = rotate(x2, y2, cx, cy, element.angle);
  334. const [x21, y21] = rotate(x2, y1, cx, cy, element.angle);
  335. const minX = Math.min(x11, x12, x22, x21);
  336. const minY = Math.min(y11, y12, y22, y21);
  337. const maxX = Math.max(x11, x12, x22, x21);
  338. const maxY = Math.max(y11, y12, y22, y21);
  339. bounds = [minX, minY, maxX, maxY];
  340. }
  341. return bounds;
  342. };
  343. export const getCommonBounds = (
  344. elements: readonly ExcalidrawElement[],
  345. ): [number, number, number, number] => {
  346. if (!elements.length) {
  347. return [0, 0, 0, 0];
  348. }
  349. let minX = Infinity;
  350. let maxX = -Infinity;
  351. let minY = Infinity;
  352. let maxY = -Infinity;
  353. elements.forEach((element) => {
  354. const [x1, y1, x2, y2] = getElementBounds(element);
  355. minX = Math.min(minX, x1);
  356. minY = Math.min(minY, y1);
  357. maxX = Math.max(maxX, x2);
  358. maxY = Math.max(maxY, y2);
  359. });
  360. return [minX, minY, maxX, maxY];
  361. };
  362. export const getResizedElementAbsoluteCoords = (
  363. element: ExcalidrawElement,
  364. nextWidth: number,
  365. nextHeight: number,
  366. ): [number, number, number, number] => {
  367. if (!(isLinearElement(element) || isFreeDrawElement(element))) {
  368. return [
  369. element.x,
  370. element.y,
  371. element.x + nextWidth,
  372. element.y + nextHeight,
  373. ];
  374. }
  375. const points = rescalePoints(
  376. 0,
  377. nextWidth,
  378. rescalePoints(1, nextHeight, element.points),
  379. );
  380. let bounds: [number, number, number, number];
  381. if (isFreeDrawElement(element)) {
  382. // Free Draw
  383. bounds = getBoundsFromPoints(points);
  384. } else {
  385. // Line
  386. const gen = rough.generator();
  387. const curve =
  388. element.strokeSharpness === "sharp"
  389. ? gen.linearPath(
  390. points as [number, number][],
  391. generateRoughOptions(element),
  392. )
  393. : gen.curve(
  394. points as [number, number][],
  395. generateRoughOptions(element),
  396. );
  397. const ops = getCurvePathOps(curve);
  398. bounds = getMinMaxXYFromCurvePathOps(ops);
  399. }
  400. const [minX, minY, maxX, maxY] = bounds;
  401. return [
  402. minX + element.x,
  403. minY + element.y,
  404. maxX + element.x,
  405. maxY + element.y,
  406. ];
  407. };
  408. export const getElementPointsCoords = (
  409. element: ExcalidrawLinearElement,
  410. points: readonly (readonly [number, number])[],
  411. sharpness: ExcalidrawElement["strokeSharpness"],
  412. ): [number, number, number, number] => {
  413. // This might be computationally heavey
  414. const gen = rough.generator();
  415. const curve =
  416. sharpness === "sharp"
  417. ? gen.linearPath(
  418. points as [number, number][],
  419. generateRoughOptions(element),
  420. )
  421. : gen.curve(points as [number, number][], generateRoughOptions(element));
  422. const ops = getCurvePathOps(curve);
  423. const [minX, minY, maxX, maxY] = getMinMaxXYFromCurvePathOps(ops);
  424. return [
  425. minX + element.x,
  426. minY + element.y,
  427. maxX + element.x,
  428. maxY + element.y,
  429. ];
  430. };
  431. export const getClosestElementBounds = (
  432. elements: readonly ExcalidrawElement[],
  433. from: { x: number; y: number },
  434. ): [number, number, number, number] => {
  435. if (!elements.length) {
  436. return [0, 0, 0, 0];
  437. }
  438. let minDistance = Infinity;
  439. let closestElement = elements[0];
  440. elements.forEach((element) => {
  441. const [x1, y1, x2, y2] = getElementBounds(element);
  442. const distance = distance2d((x1 + x2) / 2, (y1 + y2) / 2, from.x, from.y);
  443. if (distance < minDistance) {
  444. minDistance = distance;
  445. closestElement = element;
  446. }
  447. });
  448. return getElementBounds(closestElement);
  449. };