-1

enter image description here

Now I have a set of contour points. I have ray L which starts at Pn and has an angle of ALPHA clockwise to the horizontal axis. I want to calculate the length of line which starts at Pn and ends at the point that ray L intersects with the contour, in this case is one point between Pn-2 and Pn-3. So how can I efficently and fast calculate this length?

tonytonov
  • 25,060
  • 16
  • 82
  • 98
user3728326
  • 3
  • 2

2 Answers2

0

You could just compute the intersection of ray L with all line segments consisting of any pair of neighbouring contour points.

Of course you might want to optimize this process by sorting by distance to Pn or whatever. Depending on the countour (concave shape?) there could be multiple intersections, so you have to choose the right one (inner, outer, ...).

Instea of computing the intersection you also could draw the contour and the ray (e.g. using openCV) and find the point of intersection by using logical and.

Community
  • 1
  • 1
Simson
  • 829
  • 6
  • 16
  • Thank you for you advice. I have tried @Ophir Gvirtzer method and it works. Your first hint may be time-consuming. The second one I have tried but found it hard to implement(For every point calculate the angle to point **Pn** and sorting them, then find the one which have the nearest angle to **ALPHA**). The last one seems fast and optimal, but I'm using the MATLAB and I don't know any function can draw a line in an image and then save it. Besides, the coutour point is 8-connected and the drawing line is also 8-connected, so there may be no intersection between them. – user3728326 Jun 13 '14 at 01:46
0

No algorithm can solve this in faster than linear time, since the number of intersections may be linear, and so is the size of the output. I can suggest the following algorithm, which is quite convenient and efficient to implement:

  • transfer the points to a coordinate system x',y' whose center is Pn and x' is parallel to L. (In practice only the y' coordinate needs to be calculated. This requires 2 multiplication and 2 additions per point).
  • now find all the intersecting segments by searching for adjacent indices where the y' coordinates changes signs.
  • Calculate the intersection & length only for these segments
Ophir Gvirtzer
  • 604
  • 4
  • 8