#spatial #gis #geospatial #transit #networking

anime

Approximate Network Matching, Integration, and Enrichment

3 releases

new 0.1.2 Dec 20, 2024
0.1.1 Dec 20, 2024
0.1.0 Dec 20, 2024

#270 in Geospatial

42 downloads per month

MIT/Apache

23KB
286 lines

Approximate Network Matching, Integration, and Enrichment

The algorithm works like this:

Let A and B be two vectors of LineSring, Vec<LineString>. Let i refer to the index position of a LineString in A and let j refer to the index position of B. For each LineString in A or B, let the index of the component line be k where Aik is a Line.

  • Initialize an empty R* Tree $Tree_A$
  • Initialize an empty R* Tree $Tree_B$
  • Initialize an empty BTreeMap<usize, Vec<(usize, f64)>>
  • define a distance threshold DT
  • define an angle threshold AT
for i in A:
  for k in i:
    calculate the slope of Aik
    insert Aik with a tuple of (i, slope_Aik) into Tree_A

for j in B:
  for k in j:
    calculate the slope of Bjk
    expand the AABB of Bjk in the x and y direction by DT
    insert Bjk with a tuple of (j, slope_Bjk)
  • Locate intersection candidates between A and B
  • for each candidate pair, extract the slopes of Aik and Bjk
  • calculate the angle of each slope using atan(slope)
  • if the absolute difference between the angles of the slope is less than or equal to the slope, continue
  • calculate the overlap in domain and range
  • if there is overlap in domain and range, continue
  • let d be the distance between lines Aik and Bjk
  • if the distance between Aik and Bjk is less than DT, continue
  • if the angle of Ai is less than or equal to 45
    • calculate the overlap in the x dimension between Aik and Bjk
    • if there is overlap in the x-dimension
      • solve for y in the line defined by Aik based on xmin and xmax
      • calculate the length of the line segment defined by (xmin, y1) and (xmax, y2)
      • insert i into the BTreeMap if it does not exist
        • append (j, d) to the value vector if j does not exist
        • if j is in the value vector, add d to the f64 value
  • else if the angle of Ai is greater than 45 degrees
    • calculate the overlap in the y dimension between Aik and Bjk
    • if there is overlap in the y-dimension`
      • solve for x in the line defined by Aik based on ymin and ymax
      • calculate the length of the line segment defined by (x1, ymin) and (x2, ymax)
      • insert i into the BTreeMap if it does not exist
        • append (j, d) to the value vector if j does not exist
        • if j is in the value vector, add d to the f64 value

Dependencies

~7.5MB
~116K SLoC