×
INTELLIGENT WORK FORUMS
FOR ENGINEERING PROFESSIONALS

Contact US

Log In

Come Join Us!

Are you an
Engineering professional?
Join Eng-Tips Forums!
  • Talk With Other Members
  • Be Notified Of Responses
    To Your Posts
  • Keyword Search
  • One-Click Access To Your
    Favorite Forums
  • Automated Signatures
    On Your Posts
  • 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.

Students Click Here

Match Index Function - Lines

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.

thread770-434884: Match Index with Tolerances

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.

Mint, interesting - I'll do some further reading from that link.

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.

Reply To This Thread

Posting in the Eng-Tips forums is a member-only feature.

Click Here to join Eng-Tips and talk with other members! Already a Member? Login


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
Design for Additive Manufacturing (DfAM)
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:

Register now while it's still free!

Already a member? Close this window and log in.

Join Us             Close