Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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>