Re: Need code to calculate the Lower Envelope for a set of (non collinear) points.
- To: mathgroup at smc.vnet.net
- Subject: [mg51445] Re: [mg51409] Need code to calculate the Lower Envelope for a set of (non collinear) points.
- From: DrBob <drbob at bigfoot.com>
- Date: Sun, 17 Oct 2004 03:06:28 -0400 (EDT)
- References: <200410160820.EAA23705@smc.vnet.net>
- Reply-to: drbob at bigfoot.com
- Sender: owner-wri-mathgroup at wolfram.com
I think this does it if the data is already sorted: LowerEnvelope[a_]:=Module[{hull=ConvexHull@a}, a[[hull/.{x___,1,y___}:>{1,y,x} /.{x__,Length@a,y___}:>{x,Length@a}]] ] LowerEnvelope@a MultipleListPlot[{%,a},PlotJoined\[Rule]True,PlotStyle\[Rule]{Hue[.6]}] {{4,2},{8,3},{16,5},{44,13},{92,31},{688,269},{992,421},{1000,491}} If the data might NOT be pre-sorted, the function would be: LowerEnvelope[a_] := Module[{data = Sort@a, hull}, hull = ConvexHull@data; data[[hull /. {x___, 1, y___} :> {1, y, x} /. {x__, Length@a, y___} :> {x, Length@a}]] ] Testing with a random reordering of a still gives the same answer: LowerEnvelope[Sort[a, Random[] < 0.5 &]] MultipleListPlot[{%, a}, PlotJoined -> True, PlotStyle -> {Hue[.6]}] {{4, 2}, {8, 3}, {16, 5}, {44, 13}, {92, 31}, {688, 269}, {992, 421}, {1000, 491}} Bobby On Sat, 16 Oct 2004 04:20:45 -0400 (EDT), Gilmar Rodr?guez Pierluissi <gilmar.rodriguez at nwfwmd.state.fl.us> wrote: > Dear Mathematica Solver Group: > > I'm looking for a program to calculate the Lower Envelope > ("LE" for short)for a set of (non-collinear) points on the > plane. Please download the following file containing an > arbitrary set of such points(which I'm calling "A") by > double-clicking the following shortcut: > > http://gilmarlily.netfirms.com/download/A.txt > > You can also down load: > > http://gilmarlily.netfirms.com/download/Lower Envelope.nb > > to evaluate the following steps using Mathematica (version 5): > > If your define your working directory as C:\Temporary, then kindly > evaluate the following Mathematica commands: > > In[1]: A = ReadList["C:\\Temporary\\A.txt", {Number, Number}]; > > Next, plot the set A: > > In[2]: plt1 = ListPlot[A, PlotJoined -> True, PlotStyle -> {Hue[.7]}] > > I can manipulate the program ConvexHull to find the Lower Envelope > for the set A as follows: > > In[3]: << DiscreteMath`ComputationalGeometry` > > In[4]: convexhull = ConvexHull[A] > > The following input gives a picture of the Convex Hull: > > In[5]: plt2 = ListPlot[Table[A[[convexhull[[i]]]], {i, > 1, Length[convexhull]}], PlotJoined -> True, PlotStyle -> {Hue[.6]}] > > Modifying the starting value of index i in In[5] above > (starting at i=96 instead of i=1) gives a picture of the > Lower Envelope of A: > > In[6]:plt3 = ListPlot[Table[A[[convexhull[[i]]]], {i, > 96, Length[convexhull]}], PlotJoined -> True, PlotStyle -> {Hue[.6]}] > > In[7]: Show[plt1, plt3] > > The Lower Envelope of A ("LEA" for short) is given by: > > In[8]: LEA = Table[A[[convexhull[[i]]]], {i, 96, Length[convexhull]}] > > So my question is: How can the code of the ConvexHull program be modified, > to get a program that calculates the LE of a set? > > The following (clumsy)alternative attempt: > > In[9]: LE[B_] := Module[{M}, {L = Length[B]; M = {}; > AppendTo[M, B[[L]]]; {Xg, Yg} = B[[L]]; Do[If[B[[ > L - i + 1]][[2]] < Yg, {{Xg, Yg} = B[[L - > i + 1]], AppendTo[M, B[[L - i + 1]]]}], {i, 1, L - 1}]}; Sort[M]] > > In[10]: LE[A] > > In[11]: plt4 = ListPlot[LE[A], PlotJoined -> True, PlotStyle -> {Hue[.1]}] > > In[12]: Show[plt1, plt4] > > gives me something that is "not even close, and no cigar". > > What I need is an algorithm that gives me the Lower Envelope E of A > as shown in In[8] above. Thank you for your help! > > > > -- DrBob at bigfoot.com www.eclecticdreams.net
- References:
- Need code to calculate the Lower Envelope for a set of (non collinear) points.
- From: gilmar.rodriguez@nwfwmd.state.fl.us (Gilmar Rodr?guez Pierluissi)
- Need code to calculate the Lower Envelope for a set of (non collinear) points.