Intersections

[DanPatterson]

While working on a half-tribute to one of my favorite bands.  I was amazed at the number of turns involved in a seemingly small dataset.  I could also imagine some poor roadie planning a route, or the delivery person navigating them one focusing on one at a time.

So on to AC/

• twenty junction points, (first and last)
• twelve intersections
• six T-junctions, six four-segment junctions

I already published the code to get the intersections and renumber the points so that you can identify geometry intersections.  The attached shows the logic of getting the intersections

The logic is:

• Get a dictionary of point connections (pnt_connections)
  • 3 segment connections ( two, 3x3 sliding windows)
  • 4 segment connections ( three, 4x3 sliding windows)
  • 5+  .... (it gets really ugly but the pattern code can be generated easily)
• Produce sliding triplets of points (start, center, end)
• Calculate the angle of the triplet
• Classify it as
  • right-turn, -1
  • left-turn or  1
  • straight sequence  0
• each entry is now    (start, center, end, value) with a more verbose example in the function header below.

def turns(frto, _CP_):
    """Classify overlay points by the angle formed by moving triplets.

    Parameters
    ----------
    frto : array_like
        The from-to pairs of the segment ids from the overlapping polygons.
    _CP_ : array
        The x-y coordinates of the resultant polygon.  The point ids have been
        renumbered and redundant points removed.

    Notes
    -----
    The approach uses the ideas from `_is_turn` from `np_geom_hlp`.

       _is_turn(p0, p1=None, p2=None, tol=1e-6)  imported above
       -1 : right
        0 : straight
        1 : left

    turns_arr::

        st - start point id
        c  - center point id
        en - end point id
        v  - turn value as above
                st   c  en  val
        array([[ 1,  0, 10,  1],
               [ 1,  0, 19,  0],
               [10,  0, 19,  1],
               [10,  0,  1, -1],
               [19,  0,  1,  0],
               [19,  0, 10, -1],
               [ 2,  3,  4,  0],
               [ 2,  3,  8, -1],
               [ 4,  3,  8,  1],
               [ 4,  3,  2,  0] .... snip

    """
    # for testing use (p02, c02)  2025-01-26
    #
    # use a dictionary to create the associated segments
    d = pnt_connections(frto, as_dict=True, keep_size=2, exclude=None,
                        bidirectional=True)
    #
    out = []
    for a, b in d.items():
        if len(b) == 3:
            b0, b1, b2 = b
            sl = [[b0, a, b1], [b0, a, b2],
                  [b1, a, b2], [b1, a, b0],
                  [b2, a, b0], [b2, a, b1]]
            out.extend(sl)
        elif len(b) == 4:
            b0, b1, b2, b3 = b
            sl = [[b0, a, b1], [b0, a, b2], [b0, a, b3],
                  [b1, a, b2], [b1, a, b3], [b1, a, b0],
                  [b2, a, b3], [b2, a, b0], [b2, a, b1],
                  [b3, a, b0], [b3, a, b1], [b3, a, b2]]
            out.extend(sl)
    zz = np.array(out)
    tol = 1e-6
    x0y0x1y1x2y2 = _CP_[zz].reshape((-1, 6))
    x0, y0, x1, y1, x2, y2 = x0y0x1y1x2y2.T
    # (x1_x0 * y3_y2) - (y1_y0 * x3_x2) + 0.0
    v = (x1 - x0) * (y2 - y0) - (y1 - y0) * (x2 - x0)
    tmp = np.where(np.abs(v) < tol, 0., v)
    final = np.int32(np.sign(tmp))
    rgt_arr = zz[final == -1]
    lft_arr = zz[final == 1]
    strg_arr = zz[final == 0]
    turns_arr = np.concatenate((zz, final[:, None]), axis=1)
    return rgt_arr, lft_arr, strg_arr, turns_arr

Four arrays are returned representing the id values forming

• right turns (rgt_arr),
• left turns (lft_arr),
• straight segments (strg_arr) and a final
• all turns array (turns_arr)

which contains all three with a forth column identifying the turn type (-1, 0, 1 )

Full code for these functions can be found npg_bool_ops.py 

More generally geometry related NumPy Geometry 

I will leave more on geometry trivia to subsequent post concluding with the remainder of the band tribute.