다각형 계산 영역이 일치하지 않습니다

Question

인 voronoi_finite_polygons_2d(vor, radius=None) 함수를 사용하고있었습니다.

centroid of each voronoi cell을 표시하도록 수정하고 싶습니다. 일부 중도가 왜 잘못 표시되는지 디버깅합니다 (녹색 아치가 잡초에서 중도 방식으로 벗어남을 참조하십시오). 첫 번째 오류 : 일부 계산에서는 정점을 시계 반대 방향 또는 전체 시계 반대 방향으로 처리하지 못했습니다.

일부 점수가 올바르게 정렬되지 않는 이유는 확실하지 않지만 조사하기 전에 다른 예외를 발견했습니다.

시계 방향이나 반 시계 방향으로 가면 같은 영역 (반대 기호)을 가져야합니다. 간단한 예를 들어 보겠습니다. 그러나 임의의 다각형을 만들면/약간/다른 결과를 얻습니다.

import numpy as np 
import matplotlib.pyplot as plt 
from scipy.spatial import Voronoi 
import random 
import math 

def measure_polygon(vertices): 
    xs = vertices[:,0] 
    ys = vertices[:,1] 
    xs = np.append(xs,xs[0]) 
    ys = np.append(ys,ys[0]) 

    #https://en.wikipedia.org/wiki/Centroid#Centroid_of_polygon 
    area = sum(xs[i]*(ys[i+1]-ys[i-1]) for i in range(0, len(xs)-1))/2.0 
    centroid_x = sum((xs[i]+xs[i+1])*(xs[i]*ys[i+1] - xs[i+1]*ys[i]) for i in range(0, len(xs)-1))/(6.0*area) 
    centroid_y = sum((ys[i]+ys[i+1])*(xs[i]*ys[i+1] - xs[i+1]*ys[i]) for i in range(0, len(xs)-1))/(6.0*area) 

    return (area, (centroid_x, centroid_y)) 

첫 번째 예제는 처리 순서 (cw 또는 ccw)에 관계없이 동일한 영역과 중심을 기대합니다.

d = [[0.0 , 0.0], [1.0,3.0],[ 5.0,3.0],[ 4.0 , 0.0] ] 
print len(d) 

defects = [] 
defects.append([d[0], d[1], d[2], d[3]]) 
defects.append([d[3], d[2], d[1], d[0]]) 

for v in defects: 
    print measure_polygon(np.array(v)) 

간단한 평행 사변형 출력 :

4 
(1280.4882517358433, (-36.609159411740798, 7.5961622623413145)) 
(-1278.8546083623708, (-36.655924939495335, 7.6058658049196115)) 

:

4 
(-12.0, (2.5, 1.5)) 
(12.0, (2.5, 1.5)) 

하지만 지금은 (즉, 거의 삼각형)

#original list of vertices 
d = [[-148.35290745 , -1.95467472], [-124.93580616 , -2.09420039],[ -0.58281373, 1.32530292],[ 8.77020932 , 22.79390931] ] 
print len(d) 

defects = [] 
#cw 
defects.append([d[0], d[2], d[3], d[1]]) 
#ccw 
defects.append([d[1], d[3], d[2], d[0]]) 

for v in defects: 
    print measure_polygon(np.array(v)) 

나에게 이상한 출력을 제공합니다이 4 각형보고

영역이 다릅니다. 그리고 지역이 다른 경우, centroid는 다를 것입니다. 영역의 불일치 (1280 대 1278)가 너무 커서 부동 소수점 올림을 의심하지 않습니다. 하지만 그 외에는 왜 이것이 작동하지 않는 가설이 없어졌습니다.

===============================

나는 목록 - 내 .... 오류를 발견 y-1 및 y + 1 표기법을 사용하기위한 해독/색인 생성 해킹 (half-worked) 방식으로 깨졌습니다. 올바른 루틴은 다음과 같다 :

def measure_polygon(vertices): 
    xs = vertices[:,0] 
    ys = vertices[:,1] 

    #the first and last elements are for +1 -1 to work at end of range 
    xs = vertices[-1:,0] 
    xs = np.append(xs,vertices[:,0]) 
    xs = np.append(xs,vertices[:1,0]) 

    ys = vertices[-1:,1] 
    ys = np.append(ys,vertices[:,1]) 
    ys = np.append(ys,vertices[:1,1]) 

    #for i in range(1, len(xs)-1): 
    # print ("digesting x, y+1, y-1 points: {0}/{1}/{2}".format(xs[i], ys[i+1], ys[i-1])) 

    #https://en.wikipedia.org/wiki/Centroid#Centroid_of_polygon 
    area = sum(xs[i]*(ys[i+1]-ys[i-1]) for i in range(1, len(xs)-1))/2.0 
    centroid_x = sum((xs[i]+xs[i+1])*(xs[i]*ys[i+1] - xs[i+1]*ys[i]) for i in range(1, len(xs)-1))/(6.0*area) 
    centroid_y = sum((ys[i]+ys[i+1])*(xs[i]*ys[i+1] - xs[i+1]*ys[i]) for i in range(1, len(xs)-1))/(6.0*area) 

    return (area, (centroid_x, centroid_y)) 

이제 NaN이의 예를 잘 작동합니다 : 첫 번째와 마지막 포인트는 그래서 자기 폐쇄해야

number of vertices: 5 
(-30.0, (7.166666666666667, 7.6111111111111107)) 
(30.0, (7.166666666666667, 7.6111111111111107)) 

Answer 1

다각형 :

#NaN Example 
d = [[3.0 , 4], [5.0,11],[ 12.0,8],[ 9.0 , 5],[5,6] ] 
print "number of vertices: {0}".format(len(d)) 

defects = [] 
defects.append([d[0], d[1], d[2], d[3], d[4] ]) 
defects.append([ d[4], d[3], d[2], d[1], d[0]]) 

for v in defects: 
    print measure_polygon(np.array(v)) 

결과를 같은. 이것은 꽤 표준입니다. Shoelace 수식 (https://en.m.wikipedia.org/wiki/Shoelace_formula )을 일반 좌표와 함께 사용할 수 있지만 복제 된 마지막 점이 누락 된 데이터 집합을 얻으면 계산을 더 쉽게 만듭니다. 다음 좌표 (참조에서 정의)로 정의 된 구멍이없는 다각형을 고려하십시오. 첫 번째와 마지막 요점은 동일합니다 ...그들은 당신이 다시 첫 번째 점을 추가하여, 동일한 처리 하였다 이제 다각형을

roll area 30.0 
slice area30.0 

를 산출

x = np.array([3,5,12,9,5,3]) # wikipedia 
y= np.array([4,11,8,5,6,4]) 
a = np.array(list(zip(x,y))) 
area1 = 0.5*np.abs(np.dot(x, np.roll(y, 1))-np.dot(y, np.roll(x, 1))) 
area2 =0.5*np.abs(np.dot(x[1:], y[:-1])-np.dot(y[1:], x[:-1])) 
print("\nroll area {}\nslice area{}".format(area1, area2)) 

(예를 들어 구멍 다각형) 다중 다각형에 대한 정렬 오류를 얻을 수없는 경우

x = np.array([-148.35290745, -124.93580616, -0.58281373, 8.77029032, -148.35290745]) 
y = np.array([-1.95467472, -2.09420039, 1.32530292, 22.79390931, -1.95467472]) 
roll area 1619.5826480482792 
slice area 1619.5826480482792 

영역 결과는 다르지만 einsum을 사용하는 세 번째 방법을 사용하여 확인했습니다. 스크립트의 일부는 다음과 같습니다.

def ein_area(a, b=None): 
    """Area calculation, using einsum. 
    :Requires: 
    :-------- 
    : a - either a 2D+ array of coordinates or an array of x values 
    : b - if a < 2D, then the y values need to be supplied 
    : Outer rings are ordered clockwise, inner holes are counter-clockwise 
    :Notes: 
    : x => array([ 0.000, 0.000, 10.000, 10.000, 0.000]) .... OR .... 
    : t = x.reshape((1,) + x.shape) 
    :  array([[ 0.000, 0.000, 10.000, 10.000, 0.000]]) .... OR .... 
    : u = np.atleast_2d(x) 
    :  array([[ 0.000, 0.000, 10.000, 10.000, 0.000]]) .... OR .... 
    : v = x[None, :] 
    :  array([[ 0.000, 0.000, 10.000, 10.000, 0.000]]) 
    """ 
    a = np.array(a) 
    if b is None: 
     xs = a[..., 0] 
     ys = a[..., 1] 
    else: 
     xs, ys = a, b 
    x0 = np.atleast_2d(xs[..., 1:]) 
    y0 = np.atleast_2d(ys[..., :-1]) 
    x1 = np.atleast_2d(xs[..., :-1]) 
    y1 = np.atleast_2d(ys[..., 1:]) 
    e0 = np.einsum('...ij,...ij->...i', x0, y0) 
    e1 = np.einsum('...ij,...ij->...i', x1, y1) 
    area = abs(np.sum((e0 - e1)*0.5)) 
    return area 

그러나 대부분 슬라이싱/롤링 방식을 기반으로합니다. 폴리곤 목록에서 누락되었지만 가정 된 마지막 점을 포함하여 결과를 확인할 수 있는지 확인합니다.

Answer 2

그 이유는 마지막 점이 누락 되었기 때문입니다. 첫 번째 것과 거의 같을 수 있습니다. 다각형은 회로 여야합니다.

데이터베이스는 일반적으로 데이터베이스가 첫 번째 것과 같기 때문에 데이터베이스를 생략합니다.