Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.theory > #39369

Re: Fiting squares under a curve.

Show all headers | View raw

On Wednesday, 15 September 2021 at 22:33:21 UTC+1, Ben Bacarisse wrote:
> Malcolm McLean <malcolm.ar...@gmail.com> writes: 
> 
> > On Wednesday, 15 September 2021 at 15:17:39 UTC+1, Ben Bacarisse wrote: 
> >> Malcolm McLean <malcolm.ar...@gmail.com> writes: 
> >> 
> >> > Maybe there's enough theoretical content here to justify a post to 
> >> > comp.theory, though it's largely a practical problem. 
> >> > 
> >> > I have an image made up of a frieze of square cells. I can add cells 
> >> > at will to the left or the rich (within reason). I want to fit it to a 
> >> > wall with a curved top, retaining the aspect ratio as much as 
> >> > possible. So small cells in low parts of the wall, large cells in high 
> >> > parts. 
> >> > 
> >> > The flat top case is easy. The cell width is given by the height of 
> >> > the wall to make a square. It is then rounded to make a whole number 
> >> > of cells. As long as the wall is longer than it is high, the worst 
> >> > case is a 150% scaling in the x direction. Normally the wall is much 
> >> > longer than high, and distortion is negligible. 
> >> > 
> >> > However I want to allow a curved top. So the cells are no longer of 
> >> > the same height, in fact they are quads with two right angles at the 
> >> > bottom and a sloping top. The stright line function of the cell tops 
> >> > approximates the wall top curve. 
> >> > 
> >> > if we consider the solution to be a set of points in x along the wall 
> >> > representing cells, and the midpints the boundaries of cells, then we 
> >> > need to minimise the function 
> >> > 
> >> > sum over each cell : integral of wall function from cell x low to cell 
> >> > x high minus (cell x high - cell x low) squared. 
> >> > 
> >> > Is there a fast way of doing this? 
> >> It might be useful to know why I didn't comment before in 
> >> comp.programming: I didn't understand what the constraints are. 
> >> 
> >> You can add cells to some already given strip of cells but what is "with 
> >> reason"? Can you add cells from some restricted set, or can you choose 
> >> everything about the cells you add? Can you choose anything about the 
> >> initial frieze? 
> >> 
> > The user specifies the contents of the cell, which can be any image. In fact 
> > it's a vector image. I then construct a frieze from the cell by adding as many 
> > cells as are needed to make up the length of the wall (in the flat top case). 
> > Often the images will have geometry which joins. So two adjoining cells must 
> > have a common edge of the same height. I was planning to make the cells 
> > into quads with two ritch angles at the bottom and a slanted top to accommodate 
> > this requirement. 
> > I can add as many cells as I want to the frieze, until I overload the capacity of the 
> > various systems to handle the geometry. Which means about a hundred cells 
> > would be a limit. There's also no point in having a very tiny cell. The end user can't 
> > see sub-pixel geometry, it's waste of resources calculating it. 
> >> 
> >> You can scale something. It is the function to be fitted or the frieze 
> >> of cells? Scaling implies an origin. What is that origin and/or can 
> >> the scaling be accompanied by a translation making the origin 
> >> unimportant? 
> >> 
> > I can't scale the wall to the end user. But of course I can scale intermediates, 
> > for instance to trivially transform the rectangular cell problem into the square 
> > cell problem by strething or contracting the wall. Each cell is small square 
> > image. I was thinking of simply scaling the whole cell by a factor, but of course 
> > this isn't strictly correct - internally different regions of the cell have different 
> > scales because the wall is not flat over the cell. I'm hoping this won't matter 
> > too much visually. 
> > 
> >> Do you have any extra information about the function? For example, is 
> >> it everywhere continuous and maybe even smooth? 
> >> 
> > The function was chosen to be as close as possible to an existing industry- 
> > standard "variable width profile" which we can manipulate, but the equations 
> > are not public. The user enters "width points" and drags them out and slides 
> > them, and the profile interpolates. I ended up using quintic interpolation, 
> > with special cases for when two width points are at identical x positions. 
> > So you can create steps and straight line sections, but normally the 
> > function is continuous and smooth for its entire length. (I can also 
> > restrict the function as a last resort, I coded it and have control of it, but 
> > then it would no longer be as similar to the function in the industry- 
> > standard tool).
> I'm sorry but I can't work out what the optimisation problem is from 
> this description. Also, the problem is described in domain-specific 
> jargon which makes it hard for outsiders. 
> 
OK, lets try a more formal approach.

We have a function f(x) which is defined over x = 0.0 to1.0, and is always non-negative.

We have a set of values x_0 ... x_N, in ascending order. x_0 = 0.0, x_N = 1.0. These
define N-1 non-overlapping intervals.

The integral f(x) from x=0 to x = 1.0 is known to be less than 1.0.

The optimisation problem is to define the set of points such that the sum

for each interval 

| integral f(x) from x_i to x_i+1 - (x_i+1 - x_i)^2 |

is at a minimum.

Additionally, an interval cannot be less than delta_min, which will be 1 pixel, so usually
between 0.01 and 0.001, because the range x = 0 - 1.0 will generally span 100 to 1000
pixels. 

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Fiting squares under a curve. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-09-15 06:59 -0700
  Re: Fiting squares under a curve. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-15 15:17 +0100
    Re: Fiting squares under a curve. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-09-15 08:06 -0700
      Re: Fiting squares under a curve. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-15 22:33 +0100
        Re: Fiting squares under a curve. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-09-15 15:01 -0700
          Re: Fiting squares under a curve. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-16 00:33 +0100
            Re: Fiting squares under a curve. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-09-17 03:25 -0700
              Re: Fiting squares under a curve. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-17 14:22 +0100
                Re: Fiting squares under a curve. Andy Walker <anw@cuboid.co.uk> - 2021-09-17 16:25 +0100
                Re: Fiting squares under a curve. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-17 20:59 +0100
                Re: Fiting squares under a curve. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-09-23 02:14 -0700

csiph-web