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

[Laura Kauria]

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:
http://web.cs.sunyit.edu/~poissad/projects/Curve/about_algorithms/lang


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