2

I receive the following points as an input:

Point A(200 ; 400)
Point B(400 ; 400)
Point C(400 ; 200)
Point D(600 ; 200)
Point E(700 ; 500)
Point F(500 ; 700)
Point G(200 ; 600)

These points are forming the segments AB, BC, CD, DE, EF, FG and GA, to be drawn that way:

Base image

Now I've been tasked to write an automatic scaling algorithm, based on the closest numbers determining the real segment's length:

Second image

As I have to decide the constraints on my own, I've just decided to do the best to keep the angles intact. First, I determine the longest segment in order to establish a scale (for i.e. "labelled length 6" = 250px, then labelled length 1 ~= 41.7).

Then I process the next segment shorter, rescale it from it's center, and apply the same vector translation to its neighboor.

This is the best output I can get right now:

Expected output

But that method would end up in an infinite loop, or being really inaccurate in other cases, especially when the lines were handdrawn and not perfectly straight.

Are there well known algorithms to solve that situation ? I don't have any clue where to start while searching into some geometry libraries such as GEOS, libigl, ...

Axel Isouard
  • 1,498
  • 1
  • 24
  • 38
  • 2
    I'm not sure I understand. What exactly is the expected output? Isn't scaling simply multiplying all segments by a constant factor? If that's the case, then you translate all points by say `-Point A` coordinates (i.e. you move to local coordinates), then you multiply all points by constant C and finally you translate back by `+Point A` coordinates (i.e. you move back to global coordinates). If you want your scaling to be centered at some other point than `Point A` then just pick one. Arithmetic mean of all points is a valid choice as well. Either way you need to know where's the center. – freakish Apr 20 '20 at 11:49
  • 1
    I don't see how this can work if you preserve angles. For example: take a square and rescale opposite sides to resp 6 and 3. – Botje Apr 20 '20 at 12:48
  • @freakish let's say that someone was drawing a floorplan, then didn't have enough space on the sheet of paper to draw a rectangle, forcing themselves to draw a square. All they can do is just define the segment's length by labelling it. Here's a simple example of what is expected and already achieved, and of course, I don't have to handle the case when all segments are labelled: https://imgur.com/a/A4y1N63 – Axel Isouard Apr 20 '20 at 15:46
  • @Botje hello, please see above (only able to notify one person a time) – Axel Isouard Apr 20 '20 at 15:46

1 Answers1

1

Very hard problem if you dig deep into it. Naive scaling by multiplying by a constant is out of question as that changes the shape, angles etc ...

For enlarging and shrinking a polygons are best techniques using shifting sides inwards/outwards in perpendicular direction and repair the join points afterwards. But beware its very hard problem here some basics:

Your problem on top of this adds unknown side lengths. Very similar to paper box cutting SW techniques (but much simpler). So from mine point of view you should:

  1. encode your polygon in polar encoding

    so instead of just cartesian use also polar lines. Polygon is encoded as set of connected lines (loop). Each line needs this info:

    float angle;
float length;
int flag;
float x0,y0,x1,y1; // computed endpoints for rendering

    the angle can be computed by atan2(y1-y0,x1-x0) and length is obvious sqrt((x1-x0)^2+(y1-y0)^2). The flag can store which of the values are final (measured).

  2. set measured values

    so change the lengths of sides you know and set their flags accordingly

  3. recompute the endpoints again

    line[i].x0=line[i-1].x1;
line[i].y0=line[i-1].y1;
line[i].x1=line[i].lengths*cos(line[i].angle);
line[i].y1=line[i].lengths*sin(line[i].angle);

    where x0,y0 of the first line will be the origin of your polygon. In order to compute a line the previous segment must be computed and all of the values of actual line must be set. So compute all the lines you can and stop when no more lines can be computed.

    If you have no info about position from previous line you should flag that as floating position and chose some blindly (like (0,0)).

  4. fitting

    there will be bunch of uncomputed lines (with unset real lengths/angles). if line before and after is computed you can simply use theirs x0,y0,x1,y1

    if you computed a line and the next one is flagged as floating recompute it and all its followers until uncomputed or the same line is hit.

    the real problem will be the set of connected uncomputed lines. for those you can scale by multiplying by a constant + translate or change the length of first and last line until they join the computed parts. Depends on what properties of the shape you want to preserve.

As yo can see its not an easy task and there will be most likely some edge cases I forgot to handle.

The scalable paper box geometry is based on scaling equations. Each of the dimension of line is defined by a string instead of a number and also it can use polar and cartesian (switchable) representation of lines. The string can hold number, predefined size constant or equation. This way by changing just a few coefficients (usually height,width,depth, paper thickness of the box) the whole shape rescales without any fitting needed. But creating such geometry is not an easy task. There are SW for Box Making machines (cutting and scrimbing/embsing plotters) like BoxMaker but those usually need the expensive machine connected to run and are not for free use.

If you want to go this way instead you would need to implement expression evaluation see:

Spektre
  • 49,595
  • 11
  • 110
  • 380