[Tutor] Python & algorithms (Lang line simplification algorithm)

Laura Kauria lacation at gmail.com
Tue Apr 15 08:51:38 CEST 2014

```Okay I'll try. What the main job is to do an algorithm which simples a
line. Algorithm deletes points which are unnecessary accurate according to
tolerance distance user gives.

>> I started by converting the pseudocode I had to python.

Pseudocode:

1. function lang(PointList[], Tolerance)
2. key=0
3. endP= PointList.length-1
4. do {
5. endP= PointList.length-1
6. if (key+1 != endP) // If there are intermediate points
7. line= new Line( PointList[key], PointList[endP])
8. /* Find the point with the furthest perpendicular distance */
9. maxIndex= key+1
10. maxD= perpendicularDistance(line, PointList[maxIndex])
11. for (i=maxIndex+1; i<endP; i++)
12. d= perpendicularDistance(line, PointList[i])
13. if (d > maxD)
14. maxIndex=i
15. maxD=d
16. if (maxD > Tolerance)
17. endP--;
18. else
19. for (i=key+1; i<endP; i++)
20. PointList.remove(i)
21. key= endP
22. } while ( endP != PointList.length-1 )
23. end

>> Still I have problems with perpendicular distance and creating a line
>> with python.

What I mean by creating a line is what Alan answered "checking
distances/intersections
etc only requires the math model." I need the mathematical model not a
picture/graph. I'll try move forward with Bens suggestion of ‘math’ module
which probably help me with both mathematical line model between two points
and its distance between the intermediate points.
> <URL:http://docs.python.org/3/library/math.html#trigonometric-functions>.

Here is a picture of the lang algorithm, where you can see distance of
interest by purple
http://psimpl.sourceforge.net/lang.html.

I'll ask later if I can't get this work.

Cheers!

2014-04-15 3:23 GMT+03:00 Ben Finney <ben+python at benfinney.id.au>:

> Laura Kauria <lacation at gmail.com> writes:
>
> > Thanks a lot for all the help! I got the courage to start at least..
>
> Congratulations! Courage is a necessary ingredient when starting :-)
>
> <URL:https://en.wikipedia.org/wiki/Posting_style#Interleaved_style> for
> your replies, so the conversation is in a natural order.
>
> > I started by converting the pseudocode I had to python.
>
> If it's short and simple, please post it here so we can discuss it in
> context.
>
> > Still I have problems with perpendicular distance and creating a line
> > with python.
> > I need to create a line between two points and then check what is the
> > distance between a line and intermediate points which were between lines
> > start and end point. If someone could help me with this? I could not
> > understand can I do this without math library or not?
>
> The ‘math’ module in the standard library has trigonometric functions
> <URL:http://docs.python.org/3/library/math.html#trigonometric-functions>.
> If you have co-ordinate data and know how to use trigonometry, then
> those functions will do what you expect.
>
> --
>  \        “If I melt dry ice, can I swim without getting wet?” —Steven |
>   `\                                                            Wright |
> _o__)                                                                  |
> Ben Finney
>
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> To unsubscribe or change subscription options:
> https://mail.python.org/mailman/listinfo/tutor
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20140415/53de77e3/attachment.html>
```