Need code to calculate the Lower Envelope for a set of (non collinear) points.
- To: mathgroup at smc.vnet.net
- Subject: [mg51409] Need code to calculate the Lower Envelope for a set of (non collinear) points.
- From: gilmar.rodriguez at nwfwmd.state.fl.us (Gilmar Rodr?guez Pierluissi)
- Date: Sat, 16 Oct 2004 04:20:45 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
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!
- Follow-Ups:
- Re: Need code to calculate the Lower Envelope for a set of (non collinear) points.
- From: DrBob <drbob@bigfoot.com>
- Re: Need code to calculate the Lower Envelope for a set of (non collinear) points.