Re: programming competition
- To: mathgroup at smc.vnet.net
- Subject: [mg4890] Re: programming competition
- From: espen.haslund at fys.uio.no (Espen Haslund)
- Date: Fri, 4 Oct 1996 00:17:31 -0400
- Organization: Universitet i Oslo
- Sender: owner-wri-mathgroup at wolfram.com
In article <52664j$8dh at dragonfly.wolfram.com>, xah at best.com says...
>
>This is a programming problem I recently encountered. The problem has the
>attraction of being a programming competition type. I post the problem and
my
>solution here and hope someone will enjoy and maybe come out with other
solutions.
>
>Problem:
>Suppose you have a ordered list {p1, p2, ... , pn} where points has the
form
>{x,y}. You want to modify the list so any neighboring points will have a
distance
>less or equal to a given value maxLength. You do this by adding points in
between
>points. For example, suppose p3 and p4 has length greater than maxLength.
Your new
>list should then be
>{p1, p2, p3, newP1, newP2,..., newPm, p4, p5, ... , pn} where
>newP1, ...newPm lies on the line p3 p4.
>
>
>linearInterpolate::usage = "
>linearInterpolate[{p1,p2,...}, maxLength ] returns
>{P1,P2,...} such that the length between neighboring points
>P[i], P[i+1] is less or equal to maxLength.
>Newly created points lies on a line between old points";
>
Hi, Xah:
I want to enter two functions to your competition. As pointed out by
Bob Hall your function gives the points in a different order than what
you specify (I guess this is not important to your applications). However
I do not encounter the divide by zero problem mentioned by Bob Hall.
(can it be machine dependent ??)
My first entry is a straight forward Do loop approach. All the clever stuff
in it, is stolen from you. Also, thanks a lot to Daniel Lichtblau for his
resent informative article.
linearInterpolateEH1[ li_List, maxLength_ ]:=
Module[{res={}, p1, p2, n},
Do[
{p1, p2} = li[[{i, i+1}]];
n = Max[Ceiling[Sqrt[#.#]&[N[p2-p1]]/maxLength],1];
res = {res,Table[p1+(p2-p1)j,{j,0,1-.5/n,1./n}]},
{i, 1, Length[li]-1}];
Partition[Flatten[{res, Last[li]}],2]
]
My second entry is basically the same thing with the Do loop replaced with
a Table. This makes it slightly more compact and faster, but in my opinion
it is more difficult to read and debug.
linearInterpolateEH2[ li_List, maxLength_ ]:=
Module[{p1, p2, n},
Append[Join @@ Table[{p1, p2} = li[[{i, i+1}]];
n = Max[Ceiling[Sqrt[#.#]&[N[p2-p1]]/maxLength],1];
Table[p1+(p2-p1)j,{j,0,1-.5/n,1./n}],
{i,1,Length[li]-1}], Last[li] ]
]
Bellow are some timings where I also quote Bob Halls solution,
"insertPoints". I think my functions are of linear order in both
length (li) and resolution (1/maxLength). I suspect yours
to be of second order in the length. Bobs function interpolates with
not equidistant points so it's result can not be directly compared
with the other results.
li = Join[ {{0,0},{1,1}},
Table[{i,1}, {i,1,2,1/5}],
{{2,1}, {3,3}}
];
IN:
Sort[linearInterpolate[li, 0.2] ] ==
Sort[linearInterpolateEH1[li, 0.2] ] ==
Sort[linearInterpolateEH2[li, 0.2] ]
OUT:
True
IN:
li = Table[{i,i},{i,100}];
IN:
Map[First, {
Timing[linearInterpolate[li, 0.1] ],
Timing[insertPoints[li, 0.1] ],
Timing[linearInterpolateEH1[li, 0.1] ],
Timing[linearInterpolateEH2[li, 0.1] ]}]
OUT:
{6.15 Second, 5.16 Second, 4.95 Second, 4.89 Second}
IN:
li = Table[{i,i},{i,1000}];
IN:
Map[First, {
Timing[linearInterpolate[li, 1] ],
Timing[insertPoints[li, 1] ],
Timing[linearInterpolateEH1[li, 1] ],
Timing[linearInterpolateEH2[li, 1] ]}]
OUT:
{39.61 Second, 11.04 Second, 13.07 Second, 12.8 Second}
Greetings
-Espen
==== [MESSAGE SEPARATOR] ====