0

Given two curves by sets of waypoint (with direction). Is there any way to tell if one curve is on the left or right side of another? And if possible, make it fast.

red/green curves: waypoints to be judged. Green: reference line:

img

At first, for each waypoint in the curve, I found its nearest neighbor vector to the other vector. And then find its relative position (left or right). However, if the amount of waypoints is huge, it'll be quite slow. And there are many corner cases. Maybe some algorighms about semiplane will help.

Any idea is welcome, many thanks.

Spektre
  • 49,595
  • 11
  • 110
  • 380
Tian Yafu
  • 1
  • 2
    How do you define being on the left or right? What if a curve surrounds another one, or extends to both left and right of the other one? – Gilles-Philippe Paillé Mar 17 '22 at 14:10
  • you most likely iterate the path in ordered manner so once you find closest point the next one will be very near to it so no need to check whole curve just the near by points ... Also point density is more or less continuous which means distance between found corresponding points will be similar so you can even search near that distance instead of on full range ... Without seeing the code we can only guess how are you computing this and if it is efficient or not ... – Spektre Mar 18 '22 at 07:17
  • You can even do something similar to this [airfoil profile geometry plotting](https://stackoverflow.com/a/25973788/2521214) in bullet #3 ... so cast perpendicular line from your green curve and the intersection red will give you one point from which you cast perpendicular line to red curve and the intersection with green curve will give you next point ... and the corresponding points will be in between consequent point you can use middle for simplicity... – Spektre Mar 18 '22 at 07:25

0 Answers0