Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement autoarrange collection when adding a new collection #507

Open
brauliodiez opened this issue Jun 26, 2024 · 1 comment · May be fixed by #509
Open

Implement autoarrange collection when adding a new collection #507

brauliodiez opened this issue Jun 26, 2024 · 1 comment · May be fixed by #509

Comments

@brauliodiez
Copy link
Member

brauliodiez commented Jun 26, 2024

Right now when you click on Add collection the collection is place on the top left corner of the visible area of the canvas, if a blind person tries to add more than one collection they will be place stacked, that's not an accesible approach.

The idea is to implement an algorithm that:

  • Will find for free spots (or at least the ones with less collision area).
  • Will propose a where to place the collection starting in the center of the visible area.
  • Will place next tables following an spiral path.

Once the table is added we should highlight it using some animation just to let the user know where has been placed.

There's an initial POC implemented:

https://github.com/Lemoncode/auto-arrange-playground

And how it works:

autoarrange.mp4

A previous discussion is needed before starting integrating the POC, the steps:

  • Understand the current solution (team start).
  • Adapt it to mongo modeler as is and give it a try.
  • Enhance it and add unit testing once we check that it fits with Mongo Modeler.

Steps to implement this:

  1. In common under common/helper create a subfolder called autorrange-table.

  2. Under that subfolder create a autoarrange-table.model.ts we will slightly update the model (remove color field).

./src/common/autoarrange-table/autoarrange-table.model.ts

export interface Box {
  x: number;
  y: number;
  width: number;
  height: number;
}
  1. Add the util to calculate overlapping etc...

./src/common/autoarrange-table/autoarrange-table.utils.ts

import { Box } from './autoarrange-table.model';

export const getRandomInt = (min: number, max: number): number => {
  return Math.floor(Math.random() * (max - min + 1)) + min;
};

export const isOverlapping = (box1: Box, box2: Box): boolean => {
  return (
    box1.x < box2.x + box2.width &&
    box1.x + box1.width > box2.x &&
    box1.y < box2.y + box2.height &&
    box1.y + box1.height > box2.y
  );
};

export const calculateCollisionArea = (box1: Box, box2: Box): number => {
  const xOverlap = Math.max(
    0,
    Math.min(box1.x + box1.width, box2.x + box2.width) -
      Math.max(box1.x, box2.x)
  );
  const yOverlap = Math.max(
    0,
    Math.min(box1.y + box1.height, box2.y + box2.height) -
      Math.max(box1.y, box2.y)
  );
  return xOverlap * yOverlap;
};

And create the main file:

./src/common/autoarrange-table/index.ts

import { Box, Size } from "../model";
import { calculateCollisionArea, isOverlapping } from "./canvas.utils";

function* spiralPositions(
  centerX: number,
  centerY: number,
  canvasSize: Size
): Generator<[number, number]> {
  let x = 0,
    y = 0,
    dx = 0,
    dy = -1;
  for (let i = 0; i < Math.max(canvasSize.width, canvasSize.height) ** 2; i++) {
    if (
      -canvasSize.width / 2 < x &&
      x < canvasSize.width / 2 &&
      -canvasSize.height / 2 < y &&
      y < canvasSize.height / 2
    ) {
      yield [centerX + x, centerY + y];
    }
    if (x === y || (x < 0 && x === -y) || (x > 0 && x === 1 - y)) {
      [dx, dy] = [-dy, dx];
    }
    x += dx;
    y += dy;
  }
}

export function findFreePositionOrMinCollision(
  boxes: Box[],
  newBoxSize: Size,
  canvasSize: Size
): Box | null {
  const centerX = Math.floor(canvasSize.width / 2);
  const centerY = Math.floor(canvasSize.height / 2);
  let minCollisionBox: Box | null = null;
  let minCollisionArea = Infinity;

  for (const [x, y] of spiralPositions(centerX, centerY, canvasSize)) {
    const newBox = {
      x,
      y,
      width: newBoxSize.width,
      height: newBoxSize.height,
      // TODO: we will remove this once we get rid of the poc
      // and integrate this into the main app
      color: "orange",
    };
    if (
      x >= 0 &&
      y >= 0 &&
      x + newBoxSize.width <= canvasSize.width &&
      y + newBoxSize.height <= canvasSize.height
    ) {
      let collisionArea = 0;
      let isFree = true;

      for (const existingBox of boxes) {
        if (isOverlapping(newBox, existingBox)) {
          isFree = false;
          collisionArea += calculateCollisionArea(newBox, existingBox);
        }
      }

      if (isFree) {
        return newBox;
      }

      if (collisionArea < minCollisionArea) {
        minCollisionArea = collisionArea;
        minCollisionBox = newBox;
      }
    }
  }

  if (minCollisionBox !== null) {
    return minCollisionBox;
  }
  // TODO: if no free position is found, return a random one
  return null;
}

Now on the Add table handler let's use the findFreePositionOrMinCollision, to add a new collection, things to take into consideration:

  • Let's map all the tables from TableVm to Box (just create a mapper), to take into account we will have to calculate the fullsize of each table (witdth and height) and add a margin e.g. 40px.
  • Then call findFreePositionOrMinCollision passing the box collection and the current view size ( canvasViewSettings.scrollPosition.x, canvasViewSettings.scrollPosition.y, and the current subview with the width and height of the part that is shown.
  • Add some transition or animation to highlight the table temporarily once is created

Check that the approach is working, then we will do a second iteration (refactor the code, add unit testing etc...)

@Ivanruii
Copy link
Collaborator

Ivanruii commented Jul 8, 2024

I have added a commit in the feature/#507-implement-autoarrange branch implementing autoarrange collection. I will add some animation to highlight the table once created. After that I will create the pull request linking this issue.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
2 participants