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?
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?
Talk To Other Members
RE: Match Index Function - Lines
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):
S&T
RE: Match Index Function - Lines
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
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
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
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 FunctionThe 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/