09-17-2021 07:29 AM - edited 09-17-2021 07:45 AM
We have 2 arrays of x,y coordinates, we do not have equations
What is the best way to find intersections in 2d plots?
Seems that brute force would be to interpolate it and then compute distance between each point within 2 arrays
09-17-2021 08:27 AM
Hi pawhan,
@pawhan11 wrote:
What is the best way to find intersections in 2d plots?
Seems that brute force would be to interpolate it and then compute distance between each point within 2 arrays
Brute force atleast is the simple way to go…
Which points do you want to find programmatically? Only intersections of the white and red - or also red vs. red?
09-17-2021 09:15 AM - edited 09-17-2021 09:20 AM
@pawhan11 wrote:
We have 2 arrays of x,y coordinates, we do not have equations
What is the best way to find intersections in 2d plots?
Seems that brute force would be to interpolate it and then compute distance between each point within 2 arrays
Brush up on your algebra. If you have two points, then you absolutely have an equation. You just need to solve for it. Not sure if that's what you meant by "interpolate it", when I think linear interpolation I think many points and a "line of best fit", not finding the exact solution for a line given two points. That's just semantics though. Anyway...
Luckily, good ole Wikipedia has a formula to find the intersection of two lines which are both given by two points. Once you put this into a form that LabVIEW can use, all that's left is to make an array of (x1, y1, x2, y2) which make up each one your lines and iterate through it, checking each line against every other line for an intersection, assuming you want every single intersection. I believe that parallel lines will end up getting you into a divide by 0 situation, so you'll have to account for that.
Edit: since they're segments and not infinite lines, you'll also have to check the intersection point to make sure that Px lies between x1 and x2 and that Py lies between y1 and y2.
Saying "Thanks that fixed it" or "Thanks that answers my question" and not giving a Kudo or Marked Solution, is like telling your waiter they did a great job and not leaving a tip. Please, tip your waiters.
09-17-2021 12:49 PM - edited 09-17-2021 01:16 PM
for convex polygons, there exits:
https://zone.ni.com/reference/en-XX/help/371361R-01/gmath/convex_poly_inter/
edit: which is probably not going to work for your example
09-18-2021 01:04 PM
Brush up on your algebra. If you have two points, then you absolutely have an equation. You just need to solve for it.
These are some of the most frustrating posts that I see posted here. Starting off with a condescending remark doesn't help. It looks even worse when you realize you read "2 arrays" and interpreted "2 points." That's not what we have here. The OP has two lines being held in arrays of points. From what we're shown, there are at least 5 and 6 points in these two lines, respectively. Unless you plan for the OP to split each segment in the two lines and create a separate equation for each, this mention isn't really applicable.
Not sure if that's what you meant by "interpolate it", when I think linear interpolation I think many points and a "line of best fit", not finding the exact solution for a line given two points. That's just semantics though. Anyway...
What you think when you hear interpolation is exactly what's being discussed here. We have many points and the OP is wanting a line of best fit to find where the intersections exist. Only you are discussing finding an exact solution for a line given two points. It isn't semantics. It's you misreading, assuming the OP isn't as bright as you, and talking down to them. That should stop.
Luckily, good ole Wikipedia has a formula to find the intersection of two lines which are both given by two points.
Unfortunately, we aren't working with any lines given by two points. In the future, it'll help to take a moment to make sure you understand the question before rushing in to let everyone see how smart you are. It'll help you to avoid the condescending jabs to start your posts and then help to avoid a lengthy post that makes it apparent you didn't understand the original post. Both will be beneficial to you and the community as a whole.
09-18-2021 04:20 PM - edited 09-18-2021 04:26 PM
Any two adjacent points form a line segment, so with N points in set A and and M point in set B, we have N-1 line segments in A and each needs to be tested with the M-1 segments from set B. For each of these tests, you can calculate the intersection given the four points involved. (Depending on how smart the code is, you might need to eliminate duplicates, e.g. if a point of B falls exactly on a line segment of A, it could be counted twice. Similarly, if the same point is shared by A and B, you need to account for that.)
(Unfortunately, the OP did not attach a VI with some default data as shown in the picture. It is much more likely that somebody will provide a quick general solution if we don't have to start from scratch and type in all these array values.)
09-19-2021 03:02 PM
It is typically much easier to represent points/lines in xy as complex values. Here's a quick solution that seems to work for you dataset. (I am sure a final solution probably needs to have additional validations due to the limitations of floating point math).
See if you fully understand every detail and try to recreate it (Since you seem to like pictures better, I am not attaching VIs at this time. It is trivial to convert your arrays of points to complex arrays). The subVI basically implements the algorithm described in my link above)
09-20-2021 07:22 AM - edited 09-20-2021 07:48 AM
@natasftw wrote:
Brush up on your algebra. If you have two points, then you absolutely have an equation. You just need to solve for it.
These are some of the most frustrating posts that I see posted here. Starting off with a condescending remark doesn't help. It looks even worse when you realize you read "2 arrays" and interpreted "2 points." That's not what we have here. The OP has two lines being held in arrays of points. From what we're shown, there are at least 5 and 6 points in these two lines, respectively. Unless you plan for the OP to split each segment in the two lines and create a separate equation for each, this mention isn't really applicable.
Not sure if that's what you meant by "interpolate it", when I think linear interpolation I think many points and a "line of best fit", not finding the exact solution for a line given two points. That's just semantics though. Anyway...
What you think when you hear interpolation is exactly what's being discussed here. We have many points and the OP is wanting a line of best fit to find where the intersections exist. Only you are discussing finding an exact solution for a line given two points. It isn't semantics. It's you misreading, assuming the OP isn't as bright as you, and talking down to them. That should stop.
Luckily, good ole Wikipedia has a formula to find the intersection of two lines which are both given by two points.
Unfortunately, we aren't working with any lines given by two points. In the future, it'll help to take a moment to make sure you understand the question before rushing in to let everyone see how smart you are. It'll help you to avoid the condescending jabs to start your posts and then help to avoid a lengthy post that makes it apparent you didn't understand the original post. Both will be beneficial to you and the community as a whole.
Now, moving on to actually helping the OP, could you be more specific in what you need?
Saying "Thanks that fixed it" or "Thanks that answers my question" and not giving a Kudo or Marked Solution, is like telling your waiter they did a great job and not leaving a tip. Please, tip your waiters.
09-20-2021 07:23 AM
@altenbach wrote:
thank you for this elegant and lean implementation