LinuxQuestions.org
Latest LQ Deal: Latest LQ Deals
Home Forums Tutorials Articles Register
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 09-05-2012, 07:13 PM   #1
jlinkels
LQ Guru
 
Registered: Oct 2003
Location: Bonaire, Leeuwarden
Distribution: Debian /Jessie/Stretch/Sid, Linux Mint DE
Posts: 5,195

Rep: Reputation: 1043Reputation: 1043Reputation: 1043Reputation: 1043Reputation: 1043Reputation: 1043Reputation: 1043Reputation: 1043
Fit rectangle in sine curve


I have a top half of a sine curve. Height and period are known. Hence I know the area below the sine curve.

Now I want to fit a rectangle below this curve with the same area, which fits as well as possible.

In the attachment I have drawn three different solutions. One rectangle is too low and too wide, one is too high and too narrow and the middle one fits just right.

To my feeling, the best fit rectangle is the one where the areas outside the rectangle or outside the sine are as small as possible. At least for this application I am writing the areas should be minimal.

Note that in all three examples the red area equals the green area. That is by definition as the rectangle area is equal to the sine area.

Now how can I analytically determine what is the best fitting rectangle?

jlinkels
Attached Thumbnails
Click image for larger version

Name:	sine_fit.png
Views:	28
Size:	88.8 KB
ID:	10581  
 
Old 09-05-2012, 07:42 PM   #2
suicidaleggroll
LQ Guru
 
Registered: Nov 2010
Location: Colorado
Distribution: OpenSUSE, CentOS
Posts: 5,573

Rep: Reputation: 2142Reputation: 2142Reputation: 2142Reputation: 2142Reputation: 2142Reputation: 2142Reputation: 2142Reputation: 2142Reputation: 2142Reputation: 2142Reputation: 2142
Time to break out the math

Your question is about minimization. I would start by analytically defining the area under the first half of a sine for a standard period of 2*pi and a standard amplitude of 1. This should be easy enough as it's just the integral of sin(x) from 0 to pi, which by definition is 2 (easy ain't it?). Then define the area of the rectangle as h*l=2. Rearrange to get h=2/l. Now you have the height of the rectangle as a function of the length of the rectangle.

At this point, you need to define the area of the rectangle that lies outside the sine (or the area of the sine that lies outside the rectangle...you don't need both, as they're equal, you just need one, I'll leave that part up to you). Once you have an equation for the area of the rectangle that lies outside the sine as a function of h and l, combine it with the h=2/l to get a single equation that gives you the area of the rectangle that lies outside the sine as a function of h. Where the derivative of this equation equals zero will be your minimum (ie: the lowest overlap, the optimum solution). This solution is scaled to a standard amplitude of 1 and a standard period of 2*pi, which you can then scale down linearly with the actual amplitude and period of your sine wave.

Alternatively, you can come up with an equation for the overlap area, take the derivative, and the zero crossing will be the maximum, the point where the overlap is maximized and therefore the area outside the overlap is minimized...same basic approach.

Hope that helps a bit, the only tricky part will be finding the area of the overlap as a function of h and l. I'll keep thinking about this part myself...

Last edited by suicidaleggroll; 09-05-2012 at 07:56 PM. Reason: simplified the approach
 
Old 09-05-2012, 08:03 PM   #3
jlinkels
LQ Guru
 
Registered: Oct 2003
Location: Bonaire, Leeuwarden
Distribution: Debian /Jessie/Stretch/Sid, Linux Mint DE
Posts: 5,195

Original Poster
Rep: Reputation: 1043Reputation: 1043Reputation: 1043Reputation: 1043Reputation: 1043Reputation: 1043Reputation: 1043Reputation: 1043
That is what I thought as well and tried to avoid that.

The area below the sine I could determine analytically just as you did.

The statement that I just had to calculate either the green or the red area because they are equal is something I overlooked. Thank you for that hint.

Calculating the area of the sine above the rectangle should not be too difficult. The height of the rectangle is known, so I have to take the arc sine and integrate between those two angles. But ...errr to put that in a derivable function?

My idea is that this must have been done before. Usually I google for such things but it is very hard to create a search key for that.

jlinkels

Last edited by jlinkels; 09-05-2012 at 08:05 PM.
 
Old 09-05-2012, 08:14 PM   #4
jlinkels
LQ Guru
 
Registered: Oct 2003
Location: Bonaire, Leeuwarden
Distribution: Debian /Jessie/Stretch/Sid, Linux Mint DE
Posts: 5,195

Original Poster
Rep: Reputation: 1043Reputation: 1043Reputation: 1043Reputation: 1043Reputation: 1043Reputation: 1043Reputation: 1043Reputation: 1043
Looking at the pictures again, my gut feeling says that the rectangle must be lower than 1 and narrower than pi() for a standardized sine. Then the two other cases can be exluded and I know I always have two green areas on the sides and one green area on top which are >= 0.

jlinkels
 
Old 09-05-2012, 09:12 PM   #5
suicidaleggroll
LQ Guru
 
Registered: Nov 2010
Location: Colorado
Distribution: OpenSUSE, CentOS
Posts: 5,573

Rep: Reputation: 2142Reputation: 2142Reputation: 2142Reputation: 2142Reputation: 2142Reputation: 2142Reputation: 2142Reputation: 2142Reputation: 2142Reputation: 2142Reputation: 2142
I agree, so the overlap area will be equal to:
integral(sin(x)) from pi/2-l/2 to pi/2+l/2 - integral(sin(x)-h) from asin(h) to pi-asin(h)

The first integral here is the integral of the sin from the start of the rectangle to the end of the rectangle. Then you're subtracting off the area on top which is equal to the integral of the sin minus the height of the rectangle from asin(h) to pi-asin(h).

and thanks to SymCalc on my iPad (I seriously love this app), that is equal to:
2*sin(l/2) - 2*h*asin(h)+2*sqrt(-(h^2)+1)-pi*h

Swapping in l=2/h, you get

area = 2*sin(1/h) - (2*h*asin(h)+2*sqrt(-(h^2)+1)-pi*h)

Again thanks to SymCalc (did I mention I love this app?), the derivative of this equation with respect to h is equal to:
overlap = ((-2*h^2*asin(h)-2*cos(1/h)+pi*h^2)/h^2

Unfortunately I'm having issues with resolving where this equation is equal to zero. Plotting the output of this equation versus h reveals that there are multiple locations where the derivative=0, however there is only one where the value is a maximum. I'm looking into solving it discretely.

Last edited by suicidaleggroll; 09-05-2012 at 09:16 PM.
 
Old 09-06-2012, 01:06 AM   #6
firstfire
Member
 
Registered: Mar 2006
Location: Ekaterinburg, Russia
Distribution: Debian, Ubuntu
Posts: 709

Rep: Reputation: 428Reputation: 428Reputation: 428Reputation: 428Reputation: 428
Hi.

It looks like optimum value for a standard sine is approximately l=2.3266... (width of the rectangle). I did not tested it yet. Let me know if it looks reasonable. I'll try to post derivation here when I return from work. The red area in this case is approximately S=2*0.1318...

Last edited by firstfire; 09-06-2012 at 01:07 AM.
 
Old 09-06-2012, 07:21 AM   #7
salasi
Senior Member
 
Registered: Jul 2007
Location: Directly above centre of the earth, UK
Distribution: SuSE, plus some hopping
Posts: 4,070

Rep: Reputation: 897Reputation: 897Reputation: 897Reputation: 897Reputation: 897Reputation: 897Reputation: 897
It seems to me that you have two (types of) requirements:
  • the analytical one is about equal areas
  • the 'aesthetic' one, which can be stated as the angles (on the sine) at which the vertical lines are placed
If you can state the second one, that then gives you enough info so that you do not have an excess of unknowns. that is, if, for example you could state that 'it looks right' if the edges of the rectangle are at 15 degrees and 165 degrees on the sine (I assume that symmetrical will be more pleasing), then there is a calculable height which fulfils the other condition (equal areas).

(My suspicion is that 15 degrees is a bit on the small side, and that closer to 30 degrees/ 150 degrees will be more pleasing, but your definition of pleasing may well be different from mine.)

So, algorithmically::
  • for a sine, you can calculate an area.
  • For a number of degrees, you know the start and end points of the rectangle (assuming symmetry).
  • Given those start and end points, what height gives you the pre-determined area?

You now have all the information.
 
Old 09-06-2012, 08:31 AM   #8
theNbomr
LQ 5k Club
 
Registered: Aug 2005
Distribution: OpenSuse, Fedora, Redhat, Debian
Posts: 5,399
Blog Entries: 2

Rep: Reputation: 908Reputation: 908Reputation: 908Reputation: 908Reputation: 908Reputation: 908Reputation: 908Reputation: 908
There are a couple or more math oriented forums, where the inhabitants eat this kind of question up. I've used them a few times, and found the help to be very friendly, and as far as I could tell, qualified. I know I ended up with working solutions every time, and got no grief; they actually seemed happy to have a challenge to chew on. As with any Q&A forums, a well formed question helps a lot, and yours looks fine to me.
Sorry I can't recall any exact names, but a Google search for 'math help forums' turned up quite a few plausible hits.

This does seem like an exercise in minimization. My usual strategy for this kind of problem is to model it in a spreadsheet, and once I've discovered the general area where the solution lies, progressively increase the resolution around that area until I've reached a sufficiently precise solution. Not very scientific, but seems practical enough.

--- rod.

Last edited by theNbomr; 09-06-2012 at 08:35 AM.
 
Old 09-06-2012, 09:06 AM   #9
firstfire
Member
 
Registered: Mar 2006
Location: Ekaterinburg, Russia
Distribution: Debian, Ubuntu
Posts: 709

Rep: Reputation: 428Reputation: 428Reputation: 428Reputation: 428Reputation: 428
Hi.

The equation, I ended up with, is equivalent to that of suicidaleggroll, and its solution (using Newton's method) is l_m=2.3266... (h_m=0.8596..) So the idea of derivation should be clear from post #5. I also checked other possible cases, such as when h>1 or l>pi, and neither of them have appropriate solution. If your sine looks like Y = A*sin(2*pi*X/T), where T is its period, then the optimum rectangle width is L=T*l_m/(2*pi) and height is H = A*T/(pi*L).

Hope that helps.

Last edited by firstfire; 09-06-2012 at 09:08 AM.
 
Old 09-06-2012, 10:22 AM   #10
suicidaleggroll
LQ Guru
 
Registered: Nov 2010
Location: Colorado
Distribution: OpenSUSE, CentOS
Posts: 5,573

Rep: Reputation: 2142Reputation: 2142Reputation: 2142Reputation: 2142Reputation: 2142Reputation: 2142Reputation: 2142Reputation: 2142Reputation: 2142Reputation: 2142Reputation: 2142
Quote:
Originally Posted by firstfire View Post
Hi.

The equation, I ended up with, is equivalent to that of suicidaleggroll, and its solution (using Newton's method) is l_m=2.3266... (h_m=0.8596..) So the idea of derivation should be clear from post #5. I also checked other possible cases, such as when h>1 or l>pi, and neither of them have appropriate solution. If your sine looks like Y = A*sin(2*pi*X/T), where T is its period, then the optimum rectangle width is L=T*l_m/(2*pi) and height is H = A*T/(pi*L).

Hope that helps.
I get the same result, h=.8596018... This can of course then be scaled by the amplitude of the sine wave, and l can be scaled by the period.
 
Old 09-06-2012, 11:04 AM   #11
jlinkels
LQ Guru
 
Registered: Oct 2003
Location: Bonaire, Leeuwarden
Distribution: Debian /Jessie/Stretch/Sid, Linux Mint DE
Posts: 5,195

Original Poster
Rep: Reputation: 1043Reputation: 1043Reputation: 1043Reputation: 1043Reputation: 1043Reputation: 1043Reputation: 1043Reputation: 1043
Dear friends,

Thanks a lot for those answers. I will evaluate what you wrote and post back. At this moment I am working against a deadline and will mention the curve as "yet to be determined" in my report.

jlinkels
 
  


Reply



Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
Every text in the GUI is transformed into rectangle Nadeen Spirit Fedora 1 06-11-2012 01:26 PM
Wink recorder and custom rectangle stoppage Linux - Software 0 09-13-2009 01:49 PM
How can I draw a rectangle on XWindows?? deedhnd Linux - Server 2 08-01-2008 02:30 AM
help calculating sine using factorials equation darkangel29 Programming 3 09-29-2007 12:20 PM
java, rectangle size issues. exodist Programming 1 03-13-2004 04:48 PM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 08:12 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration