Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

pawhan11

Active Participant

09-17-2021 07:29 AM - edited 09-17-2021 07:45 AM

Options

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

Labels:

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

- Tags:
- math

GerdW

Knight of NI

09-17-2021 08:27 AM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

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?

FireFist-Redhawk

Active Participant

09-17-2021 09:15 AM - edited 09-17-2021 09:20 AM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

@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.

Redhawk

Test Engineer at Moog Inc.

Test Engineer at Moog Inc.

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.

alexderjuengere

Active Participant

09-17-2021 12:49 PM - edited 09-17-2021 01:16 PM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

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

natasftw

Active Participant

09-18-2021 01:04 PM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

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.

altenbach

Knight of NI

09-18-2021 04:20 PM - edited 09-18-2021 04:26 PM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

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.)*

altenbach

Knight of NI

09-19-2021 03:02 PM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

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

FireFist-Redhawk

Active Participant

09-20-2021 07:22 AM - edited 09-20-2021 07:48 AM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

@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.

- The first remark didn't seem condescending to me, just pointing out that those lines
*can*be made into a function. The*eight*total lines on the screen. Which are being displayed on two*plots*. And are each fully described using*two points*. If you want to think of it as*two**lines on the screen and eight line segments*, sure. And yes, that is essentially what needs to happen, break the lines down to 8 segments and iterate/check against every other segment for an intersection, as altenbach's solution shows. - Where exactly did you see that what was desired was a "line of best fit to find where the intersections exist"? To me that doesn't even make sense. How does me misreading equate to me assuming the OP isn't as bright as me? And I'm not talking down to anyone either. Just trying to offer advice on a post that, yes, was a bit vague.
- Good job responding to my perceived condescension with 10x more condescension
- Do you come on these forums to critique comments or help people that post their questions? Because in all that, you offered zero actual help/advice to the OP. Again, good job.

Now, moving on to *actually helping the OP, *could you be more specific in what you need?

Redhawk

Test Engineer at Moog Inc.

Test Engineer at Moog Inc.

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.

alexderjuengere

Active Participant

09-20-2021 07:23 AM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

@altenbach wrote:

thank you for this elegant and lean implementation