Match Index Function - Lines

[Trenno]

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

thread770-434884

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?

 

[sticksandtriangles]

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

 

[MintJulep]

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/slope-of-a-line-in-3d-coordinate-system

 

[IDS]

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/

 

[Trenno]

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.

 

[IDS]

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

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/