{"id":260,"date":"2026-06-27T20:51:00","date_gmt":"2026-06-27T12:51:00","guid":{"rendered":"https:\/\/geocommunity.vip\/?p=260"},"modified":"2026-06-27T20:51:00","modified_gmt":"2026-06-27T12:51:00","slug":"%e6%9e%84%e5%bb%ba%e4%b8%8d%e8%a7%84%e5%88%99%e4%b8%89%e8%a7%92%e7%bd%91%e8%bf%9b%e8%a1%8c%e7%ad%89%e9%ab%98%e7%ba%bf%e7%9a%84%e8%87%aa%e5%8a%a8%e7%bb%98%e5%88%b6","status":"publish","type":"post","link":"https:\/\/geocommunity.vip\/index.php\/2026\/06\/27\/%e6%9e%84%e5%bb%ba%e4%b8%8d%e8%a7%84%e5%88%99%e4%b8%89%e8%a7%92%e7%bd%91%e8%bf%9b%e8%a1%8c%e7%ad%89%e9%ab%98%e7%ba%bf%e7%9a%84%e8%87%aa%e5%8a%a8%e7%bb%98%e5%88%b6\/","title":{"rendered":"\u6784\u5efa\u4e0d\u89c4\u5219\u4e09\u89d2\u7f51\u8fdb\u884c\u7b49\u9ad8\u7ebf\u7684\u81ea\u52a8\u7ed8\u5236"},"content":{"rendered":"\n

\u4e00\u3001\u7a0b\u5e8f\u6982\u8ff0<\/h1>\n\n\n\n

\u6e90\u7a0b\u5e8f\uff1ahxghuiwn\/tin-contour-generation: Automatic contour line generation based on Triangulated Irregular Network (TIN).<\/a><\/p>\n\n\n\n

\u672c\u7a0b\u5e8f\u57fa\u4e8e PyQt5 \u6784\u5efa GUI \u5e94\u7528\uff0c\u5b9e\u73b0\u4e86\u4ece\u79bb\u6563\u9ad8\u7a0b\u70b9\u6570\u636e\u5230\u7b49\u9ad8\u7ebf\u81ea\u52a8\u7ed8\u5236<\/strong>\u7684\u5b8c\u6574\u6d41\u7a0b\u3002\u6838\u5fc3\u7b97\u6cd5\u5305\u62ec\uff1a\u51f8\u5305\u6784\u5efa\u3001Delaunay \u4e09\u89d2\u5256\u5206\u3001\u7b49\u9ad8\u7ebf\u8ffd\u8e2a\u4e0e\u62fc\u63a5\u3002<\/p>\n\n\n\n

1\u3001\u7b97\u6cd5\u603b\u6d41\u7a0b<\/h2>\n\n\n\n

\u6563\u70b9\u6570\u636e \u2192 \u51f8\u5305\u6784\u5efa(Graham Scan) \u2192 Delaunay\u4e09\u89d2\u7f51(\u9010\u70b9\u63d2\u5165\u6cd5) \u2192 \u7b49\u9ad8\u7ebf\u8ffd\u8e2a \u2192 \u8f93\u51fa\u7ed3\u679c<\/p>\n\n\n\n

2\u3001\u6570\u636e\u683c\u5f0f<\/h2>\n\n\n\n

\u8f93\u5165\u4e3a\u6587\u672c\u6587\u4ef6\uff0c\u6bcf\u884c\u683c\u5f0f\uff1a\u70b9\u53f7, x, y, \u9ad8\u7a0b<\/code><\/p>\n\n\n\n

1, 100.5, 200.3, 15.2\n2, 150.0, 180.7, 18.6<\/code><\/pre>\n\n\n\n
\u4e8c\u3001\u6838\u5fc3\u6570\u636e\u7ed3\u6784<\/h1>\n\n\n\n
1\u3001Point \u7c7b \u2014 \u70b9\u6570\u636e\u5b58\u50a8<\/h2>\n\n\n\n
class Point:\n    def __init__(self, n=None, x=None, y=None, h=None):\n        self.n = n          # \u70b9\u53f7\n        self.x = float(x)   # x\u5750\u6807\n        self.y = float(y)   # y\u5750\u6807\n        self.h = float(h)   # \u9ad8\u7a0b<\/code><\/pre>\n\n\n\n
\u65e0\u8bba\u662f\u539f\u59cb\u6570\u636e\u70b9\u8fd8\u662f\u8ba1\u7b97\u51fa\u7684\u4ea4\u70b9\uff0c\u7edf\u4e00\u4f7f\u7528 Point \u7c7b\u5b58\u50a8\u3002<\/p>\n\n\n\n
\u6240\u6709\u53c2\u6570\u5747\u6709\u9ed8\u8ba4\u503c\u7684\u597d\u5904\u662f\uff1a\u5728\u6784\u9020\u70b9\u5bf9\u8c61\u65f6\uff0c\u67d0\u4e9b\u53c2\u6570\u53ef\u4ee5\u4e0d\u4f20\uff0c\u7075\u6d3b\u6027\u66f4\u9ad8\u3002<\/p>\n\n\n\n
2\u3001Triangle \u7c7b \u2014 \u4e09\u89d2\u5f62\u5b58\u50a8<\/h2>\n\n\n\n
class Triangle:\n    def __init__(self, a, b, c):\n        self.a = a    # \u9876\u70b9A\uff08Point\u5bf9\u8c61\uff09\n        self.b = b    # \u9876\u70b9B\uff08Point\u5bf9\u8c61\uff09\n        self.c = c    # \u9876\u70b9C\uff08Point\u5bf9\u8c61\uff09<\/code><\/pre>\n\n\n\n
\u4e09\u3001\u51f8\u5305\u6784\u5efa<\/h1>\n\n\n\n
1\u3001Graham Scan\u7b97\u6cd5<\/h2>\n\n\n\n
\uff081\uff09\u53c9\u79ef\u51fd\u6570<\/h3>\n\n\n\n
def cross(a, b, c):\n    # \u8ba1\u7b97ab\u548cac\u7684\u53c9\u79ef\uff0c\uff1e0\uff0c\u8868\u793a\u5de6\u62d0\uff0c\u5373ac\u5728ab\u7684\u5de6\u8fb9\n    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)<\/code><\/pre>\n\n\n\n
\uff082\uff09\u8f85\u52a9\u51fd\u6570<\/h3>\n\n\n\n
\u51fd\u6570<\/td>\u4f5c\u7528<\/td><\/tr>
distance2(p1, p2)<\/td>\u8ba1\u7b97\u4e24\u70b9\u8ddd\u79bb\u7684\u5e73\u65b9\uff08\u907f\u514d\u5f00\u65b9\uff09<\/td><\/tr>
angle(p0, p)<\/td>\u8ba1\u7b97 p0 \u5230 p \u7684\u65b9\u5411\u89d2\uff08\u6781\u89d2\uff09<\/td><\/tr>
find_stone(points)<\/td>\u627e y \u6700\u5c0f\u7684\u57fa\u70b9<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
\uff083\uff09Graham Scan \u4e94\u6b65\u6d41\u7a0b<\/h3>\n\n\n\n
1. \u627e\u57fa\u70b9\uff1ay \u6700\u5c0f\u7684\u70b9\u4f5c\u4e3a\u8d77\u59cb\n2. \u53bb\u6389\u57fa\u70b9\uff1a\u5c06\u57fa\u70b9\u4ece\u70b9\u96c6\u4e2d\u79fb\u9664\n3. \u6392\u5e8f\uff1a\u6309\u6781\u89d2\u6392\u5e8f\uff0c\u6781\u89d2\u76f8\u540c\u5219\u6309\u8ddd\u79bb\u6392\u5e8f\n4. \u6784\u5efa\uff1a\u7528\u6808\u7ef4\u62a4\u51f8\u5305\uff0c\u65b0\u70b9\u52a0\u5165\u65f6\u68c0\u67e5\u662f\u5426\u6ee1\u8db3\u5de6\u8f6c\n5. \u5b8c\u6210\uff1a\u6808\u4e2d\u5269\u4f59\u7684\u70b9\u5373\u4e3a\u51f8\u5305\u9876\u70b9<\/code><\/pre>\n\n\n\n
2\u3001\u589e\u91cf\u8fed\u4ee3\u6cd5<\/h2>\n\n\n\n
\uff081\uff09\u6838\u5fc3\u601d\u60f3\uff1a\u4ece\u51f8\u5305\u7684\u521d\u59cb\u56db\u8fb9\u5f62\u51fa\u53d1\uff0c\u9010\u6761\u8fb9\u68c0\u67e5\u5916\u90e8\u662f\u5426\u6709\u66f4\u8fdc\u7684\u70b9\uff0c\u6709\u5219\u63d2\u5165\u3002<\/h3>\n\n\n\n
\uff082\uff09\u6d41\u7a0b<\/h3>\n\n\n\n
1. \u67e5\u627e\u56db\u4e2a\u6781\u503c\u9876\u70b9\uff08\u6700\u5de6\u3001\u6700\u4e0a\u3001\u6700\u53f3\u3001\u6700\u4e0b\uff09\uff0c\u6784\u6210\u521d\u59cb\u51f8\u5305 CH\n2. \u5220\u9664\u8fd9\u56db\u4e2a\u9876\u70b9\uff0c\u5269\u4f59\u70b9\u4f5c\u4e3a\u5019\u9009\u70b9\u96c6\n3. \u4e3b\u5faa\u73af\uff08\u8fed\u4ee3\u601d\u60f3\uff09\uff1a\n   a. \u679a\u4e3e CH \u7684\u6bcf\u4e00\u6761\u8fb9\n   b. \u627e\u5230\u5728\u8fb9\u5de6\u4fa7\uff08\u51f8\u5305\u5916\u4fa7\uff09\u7684\u6240\u6709\u70b9 LP\n   c. \u5982\u679c LP \u4e3a\u7a7a\uff0c\u7ee7\u7eed\u4e0b\u4e00\u6761\u8fb9\n   d. \u5728 LP \u4e2d\u627e\u6700\u8fdc\u70b9 F\uff08\u9762\u79ef\u6700\u5927\uff09\n   e. \u5c06 F \u63d2\u5165\u5230\u5f53\u524d\u8fb9\u4e4b\u540e\u7684\u4f4d\u7f6e\n   f. \u51f8\u5305\u7ed3\u6784\u5df2\u53d8\u5316\uff0ci \u91cd\u7f6e\u4e3a 0\uff0c\u91cd\u65b0\u904d\u5386\u6240\u6709\u8fb9<\/code><\/pre>\n\n\n\n
\uff083\uff09\u4ee3\u7801\u5b9e\u73b0<\/h3>\n\n\n\n
# 1\u3001\u67e5\u627e\u56db\u4e2a\u9876\u70b9\np1 = min(points, key=lambda p: p.x)   # \u6700\u5de6\np2 = max(points, key=lambda p: p.y)   # \u6700\u4e0a\np3 = max(points, key=lambda p: p.x)   # \u6700\u53f3\np4 = min(points, key=lambda p: p.y)   # \u6700\u4e0b\nCH = [p1, p2, p3, p4]                 # \u987a\u65f6\u9488\n\n# 2\u3001\u5220\u9664\u56db\u4e2a\u9876\u70b9\npoints = [p for p in points if p not in CH]\n\n# 3\u3001\u4e3b\u5faa\u73af\ni = 0\nwhile i < len(CH):\n    edge_start = CH[i]\n    edge_end = CH[(i + 1) % len(CH)]\n    # \u627e\u8fb9\u5916\u4fa7\u7684\u70b9\n    LP = [p for p in points if cross(edge_start, edge_end, p) > 0]\n    if not LP:\n        i += 1\n        continue\n    # \u627e\u6700\u8fdc\u70b9\uff08\u9762\u79ef\u6700\u5927\uff09\n    F = max(LP, key=lambda p: area(p))\n    CH.insert(i + 1, F)\n    i = 0  # \u91cd\u65b0\u904d\u5386<\/code><\/pre>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\u56db\u3001Delaunay \u4e09\u89d2\u5256\u5206 \u2014 \u9010\u70b9\u63d2\u5165\u6cd5<\/h1>\n\n\n\n
1\u3001\u8f85\u52a9\u51fd\u6570<\/h2>\n\n\n\n
\uff081\uff09\u70b9\u662f\u5426\u5728\u5916\u63a5\u5706\u5185 \u2014 is_in \u51fd\u6570<\/h3>\n\n\n\n
\uff082\uff09\u516c\u5171\u8fb9\u67e5\u627e \u2014 find_shared_lines \u51fd\u6570<\/h3>\n\n\n\n
2\u3001\u4e09\u89d2\u7f51\u6784\u5efa\u6d41\u7a0b<\/h2>\n\n\n\n
1. \u5220\u9664\u51f8\u5305\u70b9\uff0c\u4fdd\u7559\u5185\u90e8\u79bb\u6563\u70b9\n2. \u521d\u59cb\u5316\uff1a\u53d6\u7b2c\u4e00\u4e2a\u5185\u90e8\u70b9\uff0c\u4e0e\u51f8\u5305\u7684\u6bcf\u6761\u8fb9\u76f8\u8fde\uff0c\u6784\u6210\u521d\u59cb\u4e09\u89d2\u7f51 T1\n3. \u904d\u5386\u5269\u4f59\u5185\u90e8\u70b9\uff0c\u9010\u4e2a\u63d2\u5165\uff1a\n   a. \u627e\u5230\u5305\u542b\u5f85\u63d2\u70b9\u7684\u6240\u6709\u4e09\u89d2\u5f62\uff0c\u79fb\u5165 t2\n   b. \u4ece T1 \u4e2d\u79fb\u9664 t2\n   c. \u627e t2 \u7684\u975e\u516c\u5171\u8fb9\n   d. \u5c06\u975e\u516c\u5171\u8fb9\u7684\u4e24\u7aef\u70b9\u4e0e\u5f85\u63d2\u70b9\u8fde\u63a5\uff0c\u751f\u6210\u65b0\u4e09\u89d2\u5f62\uff0c\u52a0\u5165 T1<\/code><\/pre>\n\n\n\n
3\u3001\u4e09\u79cd\u521d\u59cb\u5316\u65b9\u6cd5\u5bf9\u6bd4<\/h2>\n\n\n\n
\u65b9\u6cd5<\/td>\u63cf\u8ff0<\/td><\/tr>
\u8d85\u7ea7\u4e09\u89d2\u5f62\u6cd5<\/td>\u6784\u9020\u4e00\u4e2a\u5305\u542b\u6240\u6709\u70b9\u7684\u8d85\u7ea7\u4e09\u89d2\u5f62\uff0c\u6700\u540e\u5220\u9664\u4e0e\u8d85\u7ea7\u4e09\u89d2\u5f62\u9876\u70b9\u76f8\u5173\u7684\u4e09\u89d2\u5f62<\/td><\/tr>
\u51f8\u5305\u8fb9\u6cd5\uff08\u672c\u7a0b\u5e8f\u4f7f\u7528\uff09<\/td>\u53d6\u4e00\u4e2a\u5185\u90e8\u70b9\u4e0e\u6240\u6709\u51f8\u5305\u8fb9\u76f8\u8fde\uff0c\u66f4\u76f4\u89c2<\/td><\/tr>
\u521d\u59cb\u77e9\u5f62<\/td>\u6784\u9020\u4e00\u4e2a\u5305\u542b\u6240\u6709\u70b9\u7684\u6700\u5c0f\u5916\u5305\u77e9\u5f62\uff08\u6216\u521d\u59cb\u5305\u56f4\u77e9\u5f62\uff09\uff0c\u4f5c\u4e3a\u521d\u59cb\u533a\u57df\uff0c\u518d\u5728\u5176\u57fa\u7840\u4e0a\u9010\u6b65\u7ec6\u5206\u751f\u6210\u4e09\u89d2\u7f51<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\u56db\u3001\u7b49\u9ad8\u7ebf\u6784\u5efa<\/h1>\n\n\n\n
\u5148\u786e\u5b9a\u7b49\u9ad8\u7ebf\u7684\u9ad8\u7a0b\u8303\u56f4\uff0c\u7136\u540e\u904d\u5386\u6bcf\u4e2a\u9ad8\u5ea6 h \u7684\u7b49\u9ad8\u7ebf\u3002\u5bf9\u4e8e\u9ad8\u5ea6\u4e3a h \u7684\u7b49\u9ad8\u7ebf\uff1a<\/p>\n\n\n\n
    \n
  1. \u901a\u8fc7 triangle_contour_segments \u51fd\u6570\uff0c\u627e\u5230\u5176\u4e0e\u6240\u6709 Delaunay \u4e09\u89d2\u7f51\u7684\u4ea4\u70b9\u7ebf\u6bb5<\/li>\n\n\n\n
  2. \u901a\u8fc7 build_contours_from_segments \u8fdb\u884c\u62fc\u63a5\u4e3a\u4e00\u6761\u5b8c\u6574\u7684\u7b49\u9ad8\u7ebf<\/li>\n<\/ol>\n\n\n\n
    build_contours_from_segments \u51fd\u6570\u7684\u6d41\u7a0b\uff1a<\/p>\n\n\n\n
      \n
    • \u7ebf\u6bb5\u53bb\u91cd\uff1a\u76f8\u90bb\u4e09\u89d2\u5f62\u5171\u4eab\u8fb9\u4f1a\u4ea7\u751f\u91cd\u590d\u7ebf\u6bb5\uff0c\u901a\u8fc7 point_key \u8f6c\u5143\u7ec4\u8fdb\u884c\u53bb\u91cd<\/li>\n\n\n\n
    • \u5efa\u7acb\u90bb\u63a5\u56fe\uff1a\u5c06\u53bb\u91cd\u540e\u7684\u7ebf\u6bb5\u8f6c\u4e3a\u70b9\u7684\u90bb\u63a5\u5173\u7cfb\uff08\u540c\u4e00\u4e2a\u90bb\u63a5\u56fe\u7684\u70b9\uff0c\u9ad8\u5ea6\u76f8\u540c\uff09<\/li>\n\n\n\n
    • \u4e24\u8f6e\u7b49\u9ad8\u7ebf\u8ffd\u8e2a\uff1a\n
        \n
      • \u7b2c\u4e00\u8f6e\uff1a\u4ece\u5ea6\u6570=1 \u7684\u7aef\u70b9\u51fa\u53d1\uff0c\u8ffd\u8e2a\u5f00\u653e\u7b49\u9ad8\u7ebf<\/li>\n\n\n\n
      • \u7b2c\u4e8c\u8f6e\uff1a\u4ece\u5269\u4f59\u672a\u8d70\u8fb9\u51fa\u53d1\uff0c\u8ffd\u8e2a\u95ed\u5408\u7b49\u9ad8\u7ebf<\/li>\n<\/ul>\n<\/li>\n\n\n\n
      • \u6700\u7ec8\u628a\u7ed3\u679c\u6574\u5408\u5230\u4e00\u8d77<\/li>\n<\/ul>\n\n\n\n
        \u90bb\u63a5\u5173\u7cfb\u548c sorted \u6392\u5e8f\u7684\u91cd\u8981\u6027\uff1a \u5404\u4e09\u89d2\u5f62\u72ec\u7acb\u8ba1\u7b97\u51fa\u7684\u4ea4\u70b9\u7ebf\u6bb5\u662f\u96f6\u6563\u7684\uff0c\u7ebf\u6bb5\u4e4b\u95f4\u6ca1\u6709\u76f4\u63a5\u7684\u8fde\u63a5\u5173\u7cfb\u3002\u90bb\u63a5\u56fe\u7684\u4f5c\u7528\u662f\u5c06\u8fd9\u4e9b\u96f6\u6563\u7ebf\u6bb5\u7684\u8282\u70b9\u5bf9\u5e94\u4e0a\u2014\u2014\u901a\u8fc7 point_key \u56db\u820d\u4e94\u5165\u540e\u8f6c\u4e3a\u5143\u7ec4\uff0c\u518d\u7528 sorted \u6392\u5e8f\u4fdd\u8bc1\u65b9\u5411\u65e0\u5173\uff08A\u2192B \u548c B\u2192A \u5f97\u5230\u76f8\u540c\u7684 key\uff09\uff0c\u4ece\u800c\u6b63\u786e\u8bc6\u522b\u54ea\u4e9b\u70b9\u5171\u4eab\u540c\u4e00\u6761\u8fb9\u3002\u53ea\u6709\u8282\u70b9\u80fd\u591f\u5bf9\u5e94\u4e0a\uff0c\u624d\u80fd\u4ece\u96f6\u6563\u7ebf\u6bb5\u4e2d”\u8d70”\u51fa\u4e00\u6761\u5b8c\u6574\u7684\u7b49\u9ad8\u7ebf\u3002<\/p>\n\n\n\n
        \"\"<\/figure>\n","protected":false},"excerpt":{"rendered":"
        \u4e00\u3001\u7a0b\u5e8f\u6982\u8ff0 \u6e90\u7a0b\u5e8f\uff1ahxghuiwn\/tin-c …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5,7],"tags":[],"class_list":["post-260","post","type-post","status-publish","format-standard","hentry","category-gis","category-7"],"_links":{"self":[{"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/posts\/260","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/comments?post=260"}],"version-history":[{"count":1,"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/posts\/260\/revisions"}],"predecessor-version":[{"id":265,"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/posts\/260\/revisions\/265"}],"wp:attachment":[{"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/media?parent=260"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/categories?post=260"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/tags?post=260"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}