Live Page

Description

In many papers about the Facility Layout Problem (FLP), including my master thesis titled Optimization of Production Layouts in Multi-Floor Industrial Buildings, the applied algorithms mostly consider simple rectangular block layout properties. However, real-world production buildings are often times far more nuanced, with reserved areas, structural constraints, like pillars, and other obstacles, that block the placement of facilities. In the future, designers require an easy-to-use tool to design complex 2D properties that include no-placement zones. PropertyDraw is a proof-of-concept web app written in Svelte that allows designers to quickly draw up complex block properties that can be exported and used as input for future algorithms.

Core features

• Add and remove rectangles to form complex axis-aligned grid-based polygons via simple clicks
• Manually add rectangles via the dialog window
• Adjust the grid resolution for bigger sketches
• Download your property in the commonly used CAD format .dxf

Technologies used

• Svelte 5 (TypeScript)
• Vite
• tailwindcss
• dxf-write
• nanoid

Reflection

It turns out that merging multiple polygons is a non-trivial task. To solve this problem, I have implemented a sweep-line algorithm from scratch. This tutorial gave me an idea but contains errors and confusing figures. The trial-and-error approach was my main modus operandi. The initial complexity of the project was very high and decreased over time. For instance, explicitly modelling the edges was redundant, once I sorted the vertices for each outline in a clockwise order. Vertices have IDs. To me UUIDs seemed overkill, as I only needed identifiers that would most likely not collide, not extended cryptographic features. So, I ended up using the Nano ID package, which generates small and tidy IDs of a specified size. Generally, the Canvas API is rich in features, but mapping the internal state to the canvas was challenging.

Data Flow

graph LR;
  
  A0-->A-->B-->|Yes| C-->D-->|Yes| E-->F-->G-->H-->I-->J-->K-->Z_1
  B-->|No| Z_1
  D-->|No| Z_1
  A0@{ shape: circle, label: "Start" }
  A@{ shape: lean-r, label: "User added new rectangle" }
  B@{ shape: diamond, label: "Valid rectangle (i.e. has area > 0)?" }
  C["Convert to outline (i.e. vertices)"]
  D@{ shape: diamond, label: "Valid operation (i.e. no kissing vertices)?" }
  E["Convert outlines to (potentially) overlapping rectangles"]
  F["Execute Sweep Line algorithm"]
  G["Sort vertices CW and group into separate outlines"]
  H["Prune unnecessary vertices"]
  I["Classify outlines into 'Additive' and 'Subtractive'"]
  J["Return computed outlines"]
  K["Update state in Svelte page"]
  Z_1@{ shape: dbl-circ, label: "Stop" }

How AI was used

As with all personal coding projects that have no sharp deadline, I wanted the experience to be mainly about learning and improving my coding skills, especially in algorithmics. Consequently, I limited my use of generative AI tools to brainstorming and validating different trains of thought.

Because there were very limited entry-level resources on the Internet about geometric Sweep Line algorithms available, I used ChatGPT 5 for evaluating different approaches to the core outline merging algorithm. I also consulted with ChatGPT when it came to dealing with certain edge cases, like for identifying the "kissing vertex" edge case, that would result in "non-manifold" topology.

What I have learned

• Taming the Canvas API
• Nano ID package
• Svelte 5 features
• Leveraging the JavaScript debugger in Firefox
• Various algorithms
  • Sweep Line algorithm
  • Vertex pruning logic
  • Outline classification logic

Features that could be added

• Canvas Zoom/Pan
• Hotkey support (currently only Esc aborts rectangle drawing)
• Left click for additive, right click for subtractive instead of UI buttons
• Settings: Different units that can be shown as a post-fix of the coordinates (e.g. cm)
• Memory: Store sketch in cookies to make it persistent between page refreshs/reopens
• Import/Export: Import sketch from previous file to resume work later