geometry > 中心からの線と交わるstar shape(星形)のedgeを探す > geometry_lineintersect_180415 v0.3 | find_rayCrossing_starShapedEged_180417 v0.3

```txt:動作環境
GeForce GTX 1070 (8GB)
ASRock Z170M Pro4S [Intel Z170chipset]
Ubuntu 16.04.4 LTS desktop amd64
TensorFlow v1.7.0
cuDNN v5.1 for Linux
CUDA v8.0
Python 3.5.2
IPython 6.0.0 -- An enhanced Interactive Python.
gcc (Ubuntu 5.4.0-6ubuntu1~16.04.4) 5.4.0 20160609
GNU bash, version 4.3.48(1)-release (x86_64-pc-linux-gnu)
scipy v0.19.1
geopandas v0.3.0
MATLAB R2017b (Home Edition)
ADDA v.1.3b6
gnustep-gui-runtime v0.24.0-3.1
PyMieScatt v1.7.0
```

- find_rayCrossing_starShapedEged_180417
    - v0.1: [geometry > 中心からの線と交わるstar shape(星形)のedgeを探す > find_rayCrossing_starShapedEged_180417 v0.1](https://qiita.com/7of9/items/7ddef458743dc8351fa8)
    - 前回: [geometry > 中心からの線と交わるstar shape(星形)のedgeを探す > find_rayCrossing_starShapedEged_180417 v0.2](geometry > 中心からの線と交わるstar shape(星形)のedgeを探す > find_rayCrossing_starShapedEged_180417 v0.2)
- geometry_lineintersect_180415
    - v0.1, v0.2: [geometry > numpy > 二線分（有限長さ）の交差判定 > 無限長さの二線分の交点を使った判定 > geometry_lineintersect_180415.py v0.1, v0.2](https://qiita.com/7of9/items/c4ade7dfa3f09cf1be49)
- geometry_starShaped_180428 
    - v0.1: [geometry > numpy > star shaped (星形) の頂点座標と辺の情報(頂点インデックスのペア)を得る > v0.5 取得コードと確認用描画コード](https://qiita.com/7of9/items/34143b5af773ab0280b0#_reference-8fa89e0b4d6ebdf92985)

### 処理概要

- 星形の中心からrayを飛ばす
- rayが交差する星形の辺を見つける


find_rayCrossing_starShapedEged_180417: v0.2では実際に交差していない辺まで拾うという問題があった。
使用しているgeometry_lineintersect_180415側の修正が必要だった。

### geometry_lineintersect_180415 > v0.3


線分Aと線分Bについて、線分Aの長さのみ有限としていた。
線分Bの長さも有限とするように`is_intersected()`の処理を見なおした。

[比較用の旧v0.2はこちら](https://qiita.com/7of9/items/c4ade7dfa3f09cf1be49)

```geometry_lineintersect_180415.py
import numpy as np
import sys

'''
v0.3 Apr. 28, 2018
  - is_intersected() takes into account [limited line length]
v0.2 Apr. 15, 2018
  - add Test_intersect()
  - add is_intersected()
  - add is_inside_of_lineA()
v0.1 Apr. 15, 2018
  - add get_intersection_point_unlimited_length()
'''


def get_intersection_point_unlimited_length(a1, a2, b1, b2):
    # Reference
    # https://stackoverflow.com/questions/3252194/numpy-and-line-intersections
    # answered Nov 16 '16 at 16:55
    # user1248490
    '''
    Find intersect points assuming lines have unlimited lengths
    '''
    T = np.array([[0, -1], [1, 0]])
    da = np.atleast_2d(a2 - a1)
    db = np.atleast_2d(b2 - b1)
    dp = np.atleast_2d(a1 - b1)
    dap = np.dot(da, T)
    denom = np.sum(dap * db, axis=1)
    num = np.sum(dap * dp, axis=1)
    return np.atleast_2d(num / denom).T * db + b1


def is_inside_of_lineA(a1, a2, intersect):
    wrk = a1 - a2
    da1a2 = np.sqrt(wrk[0]**2 + wrk[1]**2)
    wrk = a1 - intersect
    d1 = np.sqrt(wrk[0]**2 + wrk[1]**2)
    wrk = intersect - a2
    d2 = np.sqrt(wrk[0]**2 + wrk[1]**2)
    return (abs(da1a2 - (d1+d2)) < sys.float_info.epsilon)


def is_intersected(a1, a2, b1, b2):
    its = get_intersection_point_unlimited_length(a1, a2, b1, b2)  # its: intersect
    res = is_inside_of_lineA(a1, a2, its[0])  # [0] only 1 element
    if not res:
        return False
    res = is_inside_of_lineA(b1, b2, its[0])  # [0] only 1 element
    return res


def Test_intersect():
    # case 1 (intersection)
    a1 = np.array([-1, 0])
    a2 = np.array([1, 0])
    b1 = np.array([0, 1])
    b2 = np.array([0, -1])
    res = is_intersected(a1, a2, b1, b2)  # its: intersect
    print(res)  # True

    # case 2 (no intersection)
    a1 = np.array([-1, 0])
    a2 = np.array([1, 0])
    b1 = np.array([0, 1])
    b2 = np.array([3, 0])
    res = is_intersected(a1, a2, b1, b2)  # its: intersect
    print(res)

    # case 3 (no intersection)
    a1 = np.array([-2, 0])
    a2 = np.array([1, 0])
    b1 = np.array([0, 1])
    b2 = np.array([-3, 0])
    res = is_intersected(a1, a2, b1, b2)  # its: intersect
    print(res)

    # case 4 (no intersection)
    a1 = np.array([0.5, 0])
    a2 = np.array([1, 0])
    b1 = np.array([0, 1])
    b2 = np.array([0, -1])
    res = is_intersected(a1, a2, b1, b2)  # its: intersect
    print(res)

```

### find_rayCrossing_starShapedEged_180417 v0.3

[geometry > 中心からの線と交わるstar shape(星形)のedgeを探す > find_rayCrossing_starShapedEged_180417 v0.2](https://qiita.com/7of9/items/b3e3964ebb78bc390a34)
と何も変わらない。

変わったのはimportしているgeometry_lineintersect_180415のバージョンが上がっていること。

バージョンのコメントに追加した。

```py:find_rayCrossing_starShapedEged_180417.ipynb
%matplotlib inline

import numpy as np
import matplotlib.pyplot as plt
from pylab import rcParams
from itertools import combinations
import geometry_starShaped_180428 as GSS
import geometry_lineintersect_180415 as GLI

'''
v0.3 Apr. 28, 2018
  - import geometry_starShaped_180428 (v0.3)
v0.2 Apr. 28, 2018
  - exclude vertices pairs not included in the output from [geometry_starShaped_180428]
  - import geometry_starShaped_180428 (v0.2)
  - remove: import geometry_starShaped_180415
v0.1 Apr. 17, 2018
  - check the crossing
      + import [geometry_lineintersect_180415]
  - define the ray from the center
    + draw the ray
    + add [xs_ray], [ys_ray]
    + add [theta_deg]
  - add idxs_seq[], combs[]
  - import [combinations]
  - branched from [geometry_starShaped_180414.ipynb]
'''

rcParams['figure.figsize'] = 14, 7
rcParams['figure.dpi'] = 110

# 1. obtain star shaped points
RAD_INNER = 5
RAD_OUTER = 10
xs_str, ys_str, edgeidx = GSS.get_starShaped(RAD_INNER, RAD_OUTER)

# 2. obtain combinations of points
idxs_seq = range(len(xs_str))  # sequential indices to obtain combinations
combs = []  # combinations to obtain all the edges
for acomb in combinations(idxs_seq, 2):
    combs += [acomb]
print(combs)

# 3. define the ray from the center
theta_deg = 0.0  # [deg] 0 for rightward direction, 90 for downward direction
radius = RAD_OUTER * 1.1  # 1.1 to cross the outmost edge
xs_ray, ys_ray = [0.0], [0.0]  # center
xs_ray += [radius * np.cos(np.deg2rad(theta_deg))]  # outmost
ys_ray += [radius * np.sin(np.deg2rad(theta_deg))]  # outmost
print(xs_ray, ys_ray)

fig = plt.figure()

ax1 = fig.add_subplot(1, 2, 1)
ax1.scatter(xs_str, ys_str)
ax1.set_xlabel('x')
ax1.set_ylabel('y')
ax1.plot(xs_ray, ys_ray)
ax1.grid(True)

# 4. find crossing edges
a1 = np.array([xs_ray[0], ys_ray[0]])
a2 = np.array([xs_ray[1], ys_ray[1]])
for aidx in combs:
    #print(aidx, edgeidx)
    if list(aidx) not in edgeidx:
        continue
    b1 = np.array([xs_str[aidx[0]], ys_str[aidx[0]]])
    b2 = np.array([xs_str[aidx[1]], ys_str[aidx[1]]])
    res = GLI.is_intersected(a1, a2, b1, b2)
    if res:
        xs_draw = [b1[0], b2[0]]
        ys_draw = [b1[1], b2[1]]
        ax1.plot(xs_draw, ys_draw)


fig.tight_layout()

```

![qiita.png](https://qiita-image-store.s3.amazonaws.com/0/32870/644aad62-57de-f5cd-163b-732592cacdb4.png)