[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.


   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
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

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


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 :-)
> Could you please avoid  top-posting, and instead use interleaved style
> <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>

More information about the Tutor mailing list