ある点(x,y)が多角形の内部にあるかどうかを判定するアルゴリズム

ある点(x,y)が多角形の内部にあるかどうかを判定するアルゴリズム
An algorithm to determine if a point (x, y) is inside a polygon

ある点(x,y)が多角形の内部にあるかどうかを判定する
判定のアルゴリズムは以下3ステップ

・判定対象としたい多角形の、最も大きいx座標を求める(xp)。
・判定対象とした点から、x軸並行で上記で求めたxpまでの線分を作成する(lxp)
・線分lxpと多角形を構成するエッジとの交点の数をカウントする(cross num)。
 →交点の数が・・
  奇数なら、点(x,y)は多角形の内部にある。
  偶数なら、点(x,y)は多角形の外部にある。

polygon max x coordinate
cross count

It is judged whether or not a certain point (x, y) is inside the polygon
The algorithm of the judgment consists of three steps

· Find the largest x coordinate of the polygon you want to judge (xp).
· Create a line segment up to xp obtained in parallel on the x axis from the point to be judged (lxp)
· Count the number of intersection points between the line segment lxp and the edge constituting the polygon (cross num).
→ Number of intersection points
If it is odd, the point (x, y) is inside the polygon.
If it is an even number, the point (x, y) is outside the polygon.

ボロノイ図を使いポリゴン図形の中に中心線を引く

make center line at polygons , using voronoi.

ポリゴンを構成する頂点列から、ポリゴン内に中心線を生成する。中心線の生成にはボロノイ図を用いる。入力としたポリゴン内の長いエッジに対しては細分化を行い、ボロノイ図を生成。生成したボロノイ図を構成するエッジの内、ポリゴン内にあるもののみを抽出すると、そのエッジはポリゴンの中心線のような形状となる。
generate center line in the polygon from the vertex sequence constituting the polygon. at generate we use voronoi diagrams . For long edges in the input polygon, subdivide it and generate Voronoi diagram. When extracting only those in the polygon out of the edges constituting the generated Voronoi diagram, the edge has a shape like the center line of the polygon.

なお、今回扱うポリゴン頂点列のフォーマットしては下記の様なものとしてある。ポリゴンが複数ある場合は、下記を一つのテキストファイルに複数記述することで複数ポリゴンを表現できる。
The format of the polygon vertex sequence handled this time is as follows. If there are multiple polygons, you can express multiple polygons by describing the following in one text file.

XY .. 固定(fixed)
point num .. ポリゴンを形成する頂点数
      (number of vertives forming a polygon)
x1 y1 .. 頂点1つを表すX-Y座標。
    (XY coordinates representing one vertex)


■頂点座標指定のイメージ図(format sample image)
polygon points format sample

最初に生成する中心線の結果画像を示す。青色がポリゴン図形、白線がボロノイ図、緑線が中心線となる。
At first, show results image of the center line generated. Blue is a polygon figure, a white line is a Voronoi diagram, and a green line is a center line.
005_c_inpol_vol_pnt.png

入力としたポリゴン頂点を表すテキストファイルは下記
the input polygon vertex text is as follow URL.
http://hello-python.com/imgs/201901/point_list

■sample code

polygonを形成する頂点列からボロノイ図を作成する

テキスト形式で保存された、polygonを形成する頂点列から、ボロノイ図を作成する。初めに入力とする座標データ、次に生成結果の画像(入力図形のダンプや、結果のボロノイ図)、最後に使用したコードを示す。

Create a Voronoi diagram from a vertex sequence that forms a polygon, saved in text format. The first coordinate data input, the resulting image (input figure dump, result Voronoi diagram), and the last used code are shown.

■input point list(x-y coodinate)
-125.458 131.465
-125.474 135.003
-122.966 135.026
-122.974 132.982
-123.492 132.974
-123.516 134.484
-124.011 134.492
-123.988 133.981
-124.515 133.981
-124.491 133.454
-125.026 133.477
-125.018 131.968
-124.459 131.992
-124.53 132.99
-124.019 132.982
-123.98 132.518
-122.769 132.503
-122.785 135.482
-125.513 135.522
-125.521 135.986
-119.97 135.986
-119.947 133.477
-120.442 133.485
-120.442 131.496
-121.527 131.473
-121.535 133.485
-121 133.485
-121.016 134.468
-120.505 134.468
-120.497 135.506
-121.511 135.506
-121.488 133.981
-122.006 133.981
-121.999 131.512
-125.458 131.465

■output picture
001_pattern_contour.png(input pattern)
001_pattern_contour.png

002_point_marker.png(after split long edge points)
002_point_marker.png

003_delaunay_traiangle.png
003_delaunay_traiangle.png

004_voronoi.png
004_voronoi.png



■sample code



上記の関数では、頂点列で表すPolygon図形を構成するエッジのうち、任意の長さ以上のエッジに対して分割し頂点を増やすことを行う
In the above function, divide the edges of arbitrary length out of the edges constituting the polygon figure represented by the vertex sequence and increase the number of vertices.input first argument is ndarray(xy point list),second is split length. If distance between two points constituting an edge far than this length, add new point at between two point, and split long edge.



上記の関数では、生成するボロノイ図の画像データのに合わせて、頂点列の座標を変換(倍率変換)している。2つ目引数に指定した値が生成画像の横幅となる。戻り値は配列となっており、一つ目は変換結果のndarray,2つ目は画像の高さ。
In the above function, the coordinates of the vertex sequence are converted (magnification conversion) in accordance with the image data of the generated Voronoi diagram. The value specified for the second argument is the width of the generated image.The return value is an array, the first is the ndarray of the conversion result, the second is the height of the image.

頂点列で表すPolygonを構成する長いエッジに対しエッジ分割し、頂点を追加する。

頂点列で表すPolygon図形を構成するエッジのうち、任意の長さ以上のエッジに対して分割し頂点を増やす処理。

Process of dividing vertices of arbitrary length and increasing vertex among edges constituting Polygon figure represented by vertex sequence.

(results sample picture)
@red points : Polygon points
@blue pattern : Filled polygon
before
before split edge
after
after split edge

(results split edge)
original_points
[[237.894 0. ]
[130.554 105.408]
[ 43.748 0.626]
[ 0. 42.589]
[129.559 189. ]
[280. 42.589]
[237.894 0. ]]

after split points
[[237.894 0. ]
[184.224 52.704 ]
[130.554 105.408 ]
[ 87.151 53.017 ]
[ 43.748 0.626 ]
[ 0. 42.589 ]
[ 64.7795 115.7945 ]
[129.559 189. ]
[179.706 140.19633333]
[229.853 91.39266667]
[280. 42.589 ]
[237.894 0. ]]

sample code

■polygon_points.txt
237.894 0.000
130.554 105.408
43.748 0.626
0.000 42.589
129.559 189.000
280.000 42.589
237.894 0.000

Add x-y vertex coordinates to empty numpy.ndarray

頂点座標を空のnumpy.ndarrayに追加する操作。
よくやるのでメモ。

—(sample code)—–

—(exec result)—–
[[-126 133]
[-126 131]
[-117 131]
[-117 134]]

—(memo)—-
initialize ndarray for x-y point list.
at first array is empty(no entry) and add_type is [x,y].
so initialize parameter is (0,2).

if append for ndarray, append element must ndarray.
we use only 1 axis, so axis = 0(axis memo)