×
INTELLIGENT WORK FORUMS
FOR ENGINEERING PROFESSIONALS

Are you an
Engineering professional?
Join Eng-Tips Forums!
• Talk With Other Members
• Be Notified Of Responses
• Keyword Search
Favorite Forums
• Automated Signatures
• Best Of All, It's Free!

*Eng-Tips's functionality depends on members receiving e-mail. By joining you are opting in to receive e-mail.

#### Posting Guidelines

Promoting, selling, recruiting, coursework and thesis posting is forbidden.

# Match Index Function - Lines

## Match Index Function - Lines

(OP)
I'd previously started a thread to match a set of points to another set of master points.

Extending this functionality a little further, I'd like to develop a routine to match/map/cross reference a trial set of lines to another set of master lines. These lines are within the 3D space and are primarily defined by their start and end points (X,Y,Z). I've done a little research on various nearest-neighbour searching.

A few items to note:

- The data sets will probably never contain more than 5000 lines. So I think a linear distance based approach shouldn't being too computationally demanding. Perhaps I'm wrong?
- The data set will be fairly unorganised in terms of the start and end points. For example the start point in the trial set of points may actually be the end point in the master set of points.
- I highly doubt there will be exact matches and therefore I'll need to introduce a tolerance.
- Is there a way I measure how close/parallel a particular line is to another line? I'll use this to keep a record of how close the matches ended up.
- This will most likely be done within MS Excel.

Does anybody have any suggestions of the most robust way of tackling this problem?

### RE: Match Index Function - Lines

I'd be interested in tackling this problem (albeit I do not have the matching set problem that you are trying to tackle).

I think a lot of the principles learned through this exercise could help me try to tackle my problem I have been wanting to get around to (trying to find distance between almost parallel lines within some tolerance).

I'd most likely be trying to do this in python but I am sure that we can run ideas past each other to find solutions.

I will probably have some free time in the middle of this week to get some thoughts on paper (or website in this case).

A differing train of thought on how to tackle(not sure how well it would work):
1. Calculate midpoint of all lines
2. Calculate vector direction of all lines
3. If both midpoint and vector direction are within x tolerance of the main list; the lines match?

S&T

### RE: Match Index Function - Lines

If you have end points them you have equations for the line segments.

There is an analytical solution.

Although it might be easier to work with projections onto planes first.

Starting point. https://math.stackexchange.com/questions/799783/sl...

### RE: Match Index Function - Lines

Hi Trenno,

Could you clarify what you want to check?

Are the trial and master lines to be returned if:

They are the same line (within tolerance)?
They are coincident over some length?
They intersect?
Something else?

Doug Jenkins
Interactive Design Services
http://newtonexcelbach.wordpress.com/

### RE: Match Index Function - Lines

(OP)
Sticks, that's a good idea about the midpoint... It would also be relatively easy to implement. I'll have a look into it.

Doug, the goal of this exercise is to map the same line, but knowing they will never be in the exact same spot. I know most of the lines should be captured by the tolerance and if not it's a good warning to the user to check that particular line manually.

### RE: Match Index Function - Lines

I have modified Skip's code from the other thread for MatchPoint and MatchLine functions:

#### CODE -->

Function MatchPoint(MatchRange As Variant, MasterRange As Variant, Optional Tol As Double = 0.1)
Dim Numrows As Long, NumCols As Long, TolSq As Double
Dim DistSq As Double, row As Long, col As Long

MatchRange = MatchRange.Value2
MasterRange = MasterRange.Value2
Numrows = UBound(MasterRange)
NumCols = UBound(MasterRange, 2)
TolSq = Tol ^ 2

For row = 1 To Numrows
DistSq = 0
For col = 1 To NumCols
DistSq = (MasterRange(row, col) - MatchRange(1, col)) ^ 2 + DistSq
Next col
If DistSq < TolSq Then Exit For
Next row

If row <= Numrows Then
MatchPoint = row
Else
MatchPoint = CVErr(xlErrNA)
End If
End Function

Function MatchLine(End1 As Variant, End2 As Variant, MasterEnd1 As Variant, MasterEnd2 As Variant, Optional Tol As Double = 0.1)
Dim Numrows As Long, NumCols As Long, TolSq As Double
Dim DistSq As Double, row As Long, col As Long

End1 = End1.Value2
End2 = End2.Value2
MasterEnd1 = MasterEnd1.Value2
MasterEnd2 = MasterEnd2.Value2
Numrows = UBound(MasterEnd1)
NumCols = UBound(MasterEnd1, 2)
TolSq = Tol ^ 2

For row = 1 To Numrows
DistSq = 0
For col = 1 To NumCols
DistSq = (MasterEnd1(row, col) - End1(1, col)) ^ 2 + DistSq
Next col
If DistSq < TolSq Then
DistSq = 0
For col = 1 To NumCols
DistSq = (MasterEnd2(row, col) - End2(1, col)) ^ 2 + DistSq
Next col
If DistSq < TolSq Then
MatchLine = row
Exit Function
End If
End If
Next row

MatchLine = CVErr(xlErrNA)
End Function 

The MatchLine function searches for a matching point at end 1, then checks if the other end matches. This assumes that all the lines are specified in the same direction. If you swap End1 and End2 it won't find the match.

The MatchPoint function is essentially the same as Skip's function, just changed to suit my preferred style.

Both functions will work with 2 or 3 dimensions (or more) and return the matching row number, rather than a string.

Doug Jenkins
Interactive Design Services
http://newtonexcelbach.wordpress.com/

#### Red Flag This Post

Please let us know here why this post is inappropriate. Reasons such as off-topic, duplicates, flames, illegal, vulgar, or students posting their homework.

#### Red Flag Submitted

Thank you for helping keep Eng-Tips Forums free from inappropriate posts.
The Eng-Tips staff will check this out and take appropriate action.

#### Resources

Low-Volume Rapid Injection Molding With 3D Printed Molds
Learn methods and guidelines for using stereolithography (SLA) 3D printed molds in the injection molding process to lower costs and lead time. Discover how this hybrid manufacturing process enables on-demand mold fabrication to quickly produce small batches of thermoplastic parts. Download Now
Examine how the principles of DfAM upend many of the long-standing rules around manufacturability - allowing engineers and designers to place a partâ€™s function at the center of their design considerations. Download Now
Taking Control of Engineering Documents
This ebook covers tips for creating and managing workflows, security best practices and protection of intellectual property, Cloud vs. on-premise software solutions, CAD file management, compliance, and more. Download Now

Close Box

# Join Eng-Tips® Today!

Join your peers on the Internet's largest technical engineering professional community.
It's easy to join and it's free.

Here's Why Members Love Eng-Tips Forums:

• Talk To Other Members
• Notification Of Responses To Questions
• Favorite Forums One Click Access
• Keyword Search Of All Posts, And More...

Register now while it's still free!