       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.
>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] ====

```

• Prev by Date: Re: Mathematica and PPP
• Next by Date: ArcTan[-Cotan[theta]]
• Previous by thread: Re: programming competition
• Next by thread: Re: programming competition