Graph tips

by 管理人

今日はグラフの幾何学的特性などに触れます。以下の一部をコードを書いて作図します。

孤立最近接対（Reciprocal Pair）:RP
最近傍グラフ（Nearest Neighbor Graph） :NNG
最小木（Minimum Spanning Tree）:MST
相対近傍グラフ（Relative Neghborhood Graph）：RNG
ガブリエルグラフ（Gabriel Graph）：GG
ドローネ網（Delaunay Triangle）：DT

以下 Rhino-Python (editpythonscript) でのコード
指定範囲内（x: 0~100, t: 0~100）にランダムな点を生成

import rhinoscriptsyntax as rs
import Rhino.Geometry as rg
import math
import random
import sys

pts = []
for i in range(100):
    x = random.uniform(0,100)
    y = random.uniform(0,100)
    pos = rg.Point3d(x,y,0)
    pt = rs.AddPoint(pos)
    pts.append(pt)

全グラフ（配列ブラケットアクセス）

objs = []
for i in range(len(pts)-1):
    for j in range(i+1,len(pts)):
        if pts[i] != pts[j]:
            l = rs.AddLine(pts[i], pts[j])
            objs.append(l)

全グラフ（配列ラムダ文）

for p in pts:
    for q in pts:
        if p != q:
            rs.AddLine(p,q)
rs.Command('_seldup')
rs.Command('_delete')

Nearest Neighbor Graph NNG
もっとも近い点同士を結ぶ

objs = []
for p1 in pts:
    nearlestdist = sys.float_info.max
    nearlest = None
    for p2 in pts:
        if p1 != p2:
            dist = rs.Distance(p1, p2)
            if dist < nearlestdist:
                nearlestdist = dist
                nearlest = p2
    if(nearlest!=None):
        l = rs.AddLine(p1, nearlest)
        objs.append(l)

Minimum Spanning Tree: MST (最小木)
全ての点（ノード）を最小限のエッジで接続する。全ての点(ノード）が参加しているグラフ（ネットワーク）で、エッジの総長さがもっとも短いもの。下記はプリム法（グラフに接続済みのノードグループと未接続のノードグループに分け、2つのグループ間のもっとも近いノード同士を接続していく）

objs = []
#Minimum Spanning Tree: MST
ptsA = []
ptsB = list(pts)
ptsA.append(pts[0])
ptsB.remove(pts[0])
 
while 1:
    shortestlen = sys.float_info.max
    stA = None
    stB = None
    for p1 in ptsA:
        for p2 in ptsB:
            dist = rs.Distance(p1,p2)
            if shortestlen > dist:
                shortestlen = dist
                stA = p1
                stB = p2
    if shortestlen > 0:
        l = rs.AddLine(stA,stB)
        objs.append(l)
    ptsA.append(stB)
    ptsB.remove(stB)
    if len(ptsB) == 0:
        break

Relative Neighborhood Graph RNG
点群から2点を取り出し、その2点間の距離を半径とする円を2点それぞれから描画し、その両方の円に他の点が一つも無い場合、その2点を結ぶ

objs = []
for p1 in pts:
    for p2 in pts:
        if p1 != p2:
            dist0 = rs.Distance(p1,p2)
            nopoints = True
            for p3 in pts:
                if p3 != p1 and p3 != p1:
                    dist1 = rs.Distance(p1,p3)
                    dist2 = rs.Distance(p2,p3)
                    if dist1 < dist0 and dist2 < dist0:
                        nopoints = False
                        break
            if nopoints:
                l = rs.AddLine(p1,p2)
                objs.append(l)

Gabriel Graph　GG
点群から2点を取り出し、その2点間の距離を直径とする円を2点の中点に描画し、その円内に他の点が一つも無い場合、その2点を結ぶ

objs = []
#Gabriel Graph:GG
for p1 in pts:
    for p2 in pts:
        if p1 != p2:
            mp = (rs.PointCoordinates(p1)+rs.PointCoordinates(p2)) / 2.
            r = rs.Distance(p1,p2) / 2.
            if r > 0:
                nopoints = True
                for p3 in pts:
                    if p3 != p1 and p3 != p2:
                        dist = rs.Distance(p3,mp)
                        if dist < r :
                            nopoints = False
                            break
                if nopoints and r > 0:
                    l = rs.AddLine(p1,p2)
                    objs.append(l)

Delaunay Triangle: DT
ドローネ網、3点（ノード）を取り出し、その3点（ノード）を通る円内にその3点以外の点（ノード）が存在しないときにその3点（ノード）を3つのエッジでつなぐ
ボロノイ・ダイアグラムと双対関係

objs = []
for i in range(0,len(pts) - 2):
    p1 = pts[i]
    for j in range(i+1,len(pts) - 1):
        p2 = pts[j]
        for k in range(j+1,len(pts) - 0):
            p3 = pts[k]
            pos1 = rs.PointCoordinates(p1)
            pos2 = rs.PointCoordinates(p2)
            pos3 = rs.PointCoordinates(p3)
            c = rg.Circle(pos1,pos2,pos3)
            cp = c.Center
            r = c.Radius
            if r > 0:
                nopoint = True
                for p4 in pts:
                    if p4 != p1 and p4 != p2 and p4 != p3:
                        dist = rs.Distance(cp,p4)
                        if dist < r:
                            nopoint = False
                            break
                if nopoint == True:
                    l = rs.AddLine(p1,p2)
                    objs.append(l)
                    l = rs.AddLine(p1,p3)
                    objs.append(l)
                    l = rs.AddLine(p2,p3)
                    objs.append(l)

下記はghpythonlibを使った簡易な描き方(Delaunay Triangle: DT)

import ghpythonlib.components as ghp

result = ghp.DelaunayEdges(pts)
edges = result[1]
for e in edges:
    if e.Length &amp;gt; 0:
        rs.AddLine(e.From,e.To)

Comments are closed.