Re: point projection on polyline

[Juan Pablo Carbajal]

On Wed, Jan 27, 2016 at 5:35 AM, rcharan51 <address@hidden> wrote:

For simplicity just say there's only one poly-line, then i want proj and dist
of all points in the image from the poly-line, so there will be some
4000x5000 points for 1m spacing or 400x500 for 10m spacing.

Yes, projPointOnPolyline is simple and easy to understand. I have to think
of some approach to reduce the # of edges that need to be compared thereby
decreasing the # of iterations in the nested *for* loop.



--
View this message in context: http://octave.1599824.n4.nabble.com/point-projection-on-polyline-tp4673298p4674537.html
Sent from the Octave - General mailing list archive at Nabble.com.

_______________________________________________
Help-octave mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/help-octave

You will need N*m comparisons (N # of points, m # of edges). First thing si to try to use more hardware (try the parallel package if you have multi cores, and replace arrayfun with paraarayfun).

If that is not enough:

You can try to see the polyline at different resolutions _m_ = 1, 2, 3, ..., m and do N*_m_ comparisons and cluster the points according to what edge they project to. When you go to the next level of resolution of the polyline (next _m_) you do not need to do N*_m_ anymore, but a subset (check octrees[1] to get an idea of the kind of algorithm involved). This could improve the complexity of your comparison but it depends on the shape of the polyline, for polylines that look more or less like straight lines the improvement can be substantial.

You can also try to group your points and do the same trick (assuming N >> m). This would be also an octree or something like collision detection in 2D using space hashing [2]

All ideas are basically "divide and conquer", if the sum of the divide steps is faster than the complete problem you gained something, just make sure what you gain is worth the pains.

[1] https://en.wikipedia.org/wiki/Octree

[2] https://conkerjo.wordpress.com/2009/06/13/spatial-hashing-implementation-for-fast-2d-collisions/