javascript - How can I rotate a square to minimize the distance between each point and four arbitrary points?

Question

I have been trying to follow this article: https://andersource.dev/2020/11/06/organic-grid.html

Specifically, the appendix. But my understanding of calculus and its notation is limited.

So I tried also to understand and adapt/rewrite the source code: https://raw.githubusercontent.com/andersource/andersource.github.io/master/assets/organic-grid/index.js

But it uses some libraries I'm unfamiliar with and I want to work from first principles.

Here is a simple example containing my code (all relevant code is in the rotateSquareToFitQuad function)

https://editor.p5js.org/marcusround/sketches/5jckZCCw-

[edit: this example has since been updated with the fix provided by andersource below] But the resulting square seems to have an almost random rotation so I must have made some error in adapting the code.

My goal is to minimise the total length of the four lines connecting each pair of vertices.

question from:https://stackoverflow.com/questions/65640869/how-can-i-rotate-a-square-to-minimize-the-distance-between-each-point-and-four-a

Answer 1

Your implementation of the math is correct. The culprit in this case is the notorious mismatch between the "up" direction of the y-axis between mathematics and many graphics utilities; this affects the "clockwise" assumption of the mathematical formulation in the article.

In your implementation you define the quadrants like this:

const quadrants = [
    [-1, -1], // TL
    [1, -1],  // TR
    [1, 1],   // BR
    [-1, 1],  // BL
  ]

This indeed renders the vertices in clockwise orientation, but results in counter-clockwise computation mathematically.

Replacing that with the following definition:

  const quadrants = [
    [-1, -1],
    [-1, 1],
    [1, 1],
    [1, -1],
  ]

Results in proper solutions (albeit counter-clockwise rendering of the vertices and shifted correspondences between the "fitted" square and the original vertices).

(An alternative solution is to re-derive the math in a "down is y-positive" system but that's probably an overkill.)