python geometry processing#1

              ห่างหายจากการเขียนถึง python ซะนานวันนี้ขอเขียนถึงหน่อย อย่างที่เคยกล่าวมาในตอนต้นผมเองเชื่อว่า python เป็นภาษาหนึ่งที่เหมาะกับการเรียนวิชา gis programming สำหรับท่านที่อยากนำไปใช้ในการพัฒนาโปรแกรมจริงๆ ไม่ใช่แค่เน้นที่การ interface ทั่วไป เนื่องจากทั่วไปการวิชา spatialdata model,  spatialdata hadle หรือวิชาอื่นๆที่เกี่ยวข้องกับ geometry processing มักจะต้องมีการเขียนโปรแกรม พิสูจน์ algorithm  สำหรับผมเองโชคดีที่ตอนเรียนถูกบังคับให้ทำเยอะ เขียนแม้กระทั่งฟังก์ชั่นสำหรับ zoom-in zoom-rectang มันเลยทำให้เราค่อนข้างเข้าใจใน algorithm ต่างๆได้ดีกว่าการอ่านอย่างเดียว แต่ก็ติดปัญหาตรงที่ว่าสมัยเรียนใช้ vb กับ VC++ ซึ่งค่อนข้างใหญ่เกินไป วันนี้ผมเลยอยากจะมาแนะนำ python ครับ

             python ภาษาที่ใช้ได้ง่ายและก็เล็กคล่องแคล่ว ลงก็ไม่เปลื้องทรัพยากรของเครื่องมากนัก โม้มาเยอะลองดูตัวอย่างง่ายๆกันดีกว่า ผมนำ code ตัวอย่างเกี่ยวกับ feature simplify ด้วย Douglas-Peucker algorithm
 โดยจะทำการ generalize ข้อมูลเส้นที่เป็น set ของจุด เขียนโค้ดง่ายๆดังนี้ครับ

 # เรียก class math มาใช้
import math 

##สร้าง  simplify point function
def simplify_points (pts, tolerance):
    anchor  = 0
    floater = len(pts) – 1
    stack   = []
    keep    = set()

    stack.append((anchor, floater)) 
    while stack:
        anchor, floater = stack.pop()
     
        # initialize line segment
        if pts[floater] != pts[anchor]:
            anchorX = float(pts[floater][0] – pts[anchor][0])
            anchorY = float(pts[floater][1] – pts[anchor][1])
            seg_len = math.sqrt(anchorX ** 2 + anchorY ** 2)
            # get the unit vector
            anchorX /= seg_len
            anchorY /= seg_len
        else:
            anchorX = anchorY = seg_len = 0.0
   
        # inner loop:
        max_dist = 0.0
        farthest = anchor + 1
        for i in range(anchor + 1, floater):
            dist_to_seg = 0.0
            # compare to anchor
            vecX = float(pts[i][0] – pts[anchor][0])
            vecY = float(pts[i][1] – pts[anchor][1])
            seg_len = math.sqrt( vecX ** 2 + vecY ** 2 )
            # dot product:
            proj = vecX * anchorX + vecY * anchorY
            if proj < 0.0:
                dist_to_seg = seg_len
            else:
                # compare to floater
                vecX = float(pts[i][0] – pts[floater][0])
                vecY = float(pts[i][1] – pts[floater][1])
                seg_len = math.sqrt( vecX ** 2 + vecY ** 2 )
                # dot product:
                proj = vecX * (-anchorX) + vecY * (-anchorY)
                if proj < 0.0:
                    dist_to_seg = seg_len
                else:  # calculate perpendicular distance to line (pythagorean theorem):
                    dist_to_seg = math.sqrt(abs(seg_len ** 2 – proj ** 2))
                if max_dist < dist_to_seg:
                    max_dist = dist_to_seg
                    farthest = i

        if max_dist <= tolerance: # use line segment
            keep.add(anchor)
            keep.add(floater)
        else:
            stack.append((anchor, farthest))
            stack.append((farthest, floater))

    keep = list(keep)
    keep.sort()
    return [pts[i] for i in keep]

if __name__ == “__main__”:
    import doctest
    doctest.testmod()
   

ทดลองใช้งานนะครับ

>>> line = [(0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,1),(0,0)]   # set of point
>>> simplify_points(line, 1.0)   # call function
[(0, 0), (2, 0), (2, 2), (0, 2), (0, 0)]  # result

 

เข้าไปอ่านรายละเอียดของ algorithm ได้ที่

http://www.geog.ubc.ca/courses/klink/gis.notes/ncgia/u48.html

http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm

Advertisements

One thought on “python geometry processing#1

Add yours

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s

บลอกที่ WordPress.com .

Up ↑

%d bloggers like this: