當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

多边形裁剪(Polygon Clipping) 1

發(fā)布時(shí)間：2023/12/8 编程问答 36 豆豆

生活随笔收集整理的這篇文章主要介紹了多边形裁剪(Polygon Clipping) 1 小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

原文地址:?https://sean.cm/a/polygon-clipping-pt1

Greiner-Hormann裁剪算法無法處理重合線。?所以我研究并寫了另一篇適用于所有多邊形的文章。

在此處閱讀后續(xù)內(nèi)容：多邊形裁剪（第 2 部分）

問題

首先, 讓我們定義問題,

假設(shè)您有兩個(gè)多邊形，每個(gè)多邊形都以 2D 形式存在

var poly1 = [ // red[ 181, 270 ],[ 85, 418 ],[ 171, 477 ],[ 491, 365 ],[ 218, 381 ],[ 458, 260 ] ]; var poly2 = [ // blue[ 474, 488 ],[ 659, 363 ],[ 255, 283 ],[ 56, 340 ],[ 284, 488 ],[ 371, 342 ] ];

?奇偶規(guī)則

多邊形遵循奇偶規(guī)則來確定一個(gè)點(diǎn)是否被視為區(qū)域“內(nèi)部”。

基本規(guī)則是想象您正在用一條水平線上從左到右掃描。每次越過邊緣時(shí)，都會(huì)在外部和內(nèi)部之間切換。

?那么：給定這兩個(gè)多邊形，我們?nèi)绾斡?jì)算不同的布爾運(yùn)算？

基本理念

?首先，讓我們定義一些基本的規(guī)則.

順時(shí)針vs逆時(shí)針(Forward vs. Backward Movement)

如果我們坐在多邊形的任何一點(diǎn)上，我們總是可以向前一個(gè)點(diǎn)或者后一個(gè)點(diǎn)移動(dòng)

順時(shí)針只是意味著沿箭頭方向移動(dòng)，逆時(shí)針則相反

?插入點(diǎn)

?在處理過程中，我們需要在多邊形中插入點(diǎn)。只要我們對(duì)如何插入它們很聰明，它就不會(huì)改變多邊形的形狀:

交叉點(diǎn)

識(shí)別和分類交叉點(diǎn)是算法中的魔法.

如果您考慮一下，我們將執(zhí)行的每個(gè)操作（交集、聯(lián)合、差異）都會(huì)產(chǎn)生一個(gè)包含多邊形之間所有交點(diǎn)的多邊形

?我們不關(guān)心同一多邊形內(nèi)的交叉點(diǎn).

另外：如果你想象我們正沿著一個(gè)多邊形行走并遇到一個(gè)十字路口，我們有3個(gè)選擇.

1.?保持在同一個(gè)多邊形上（這是毫無意義的)

2.?切換多邊形，開始順時(shí)針移動(dòng)

3.?切換多邊形，并開始逆時(shí)針移動(dòng)

因此，如果我們能夠智能地選擇在每個(gè)交叉路口的方向，我們就可以追蹤到正確的結(jié)果形狀.

交叉點(diǎn)示例

想象一下, 我們想象一下，我們正在追蹤兩個(gè)多邊形合并union的結(jié)果.

在每個(gè)交叉點(diǎn)，我們都希望朝著最終形狀繼續(xù)增長的方向移動(dòng).

我們可以這樣做:

我們也可以在相反的方向得到相同的結(jié)果:

關(guān)于所有四個(gè)決定，我們可以說哪些是正確的?

在每個(gè)交叉點(diǎn)，我們總是朝著遠(yuǎn)離我們離開的多邊形的方向前進(jìn).

因此，例如，如果我們沿著 Blue 行駛，然后遇到一個(gè)十字路口，我們應(yīng)該繼續(xù)沿著 Red 向遠(yuǎn)離Blue的方向行使.

會(huì)有什么不同？這是Red-Blue(從Red中減去Blue區(qū)域):

?而在另一個(gè)方向:

對(duì)此我們能說什么?

當(dāng)從紅色切換到藍(lán)色時(shí)，我們進(jìn)入紅色。當(dāng)從藍(lán)色切換到紅色時(shí)，我們遠(yuǎn)離紅色.

所以我們有兩個(gè)基本的決定:

1. 當(dāng)從紅色切換到藍(lán)色時(shí)，我們是進(jìn)入還是遠(yuǎn)離紅色?

2.當(dāng)從藍(lán)色切換到紅色時(shí)，我們是進(jìn)入還是遠(yuǎn)離藍(lán)色？

對(duì)于聯(lián)合(union)來說, 答案總是離開.?但是對(duì)于Red-Blue(Red減Blue)，我們想要進(jìn)入紅色，?遠(yuǎn)離藍(lán)色。如果你玩玩，你會(huì)注意到交叉(intersection?)意味著總是進(jìn)入你要離開的

這給了我們下邊的表

OperatorInto Red?Into Blue?

聯(lián)合(Union)	False	False
Red減Blue(Red - Blue)	True	False
Blue減Red(Blue - Red)	False	True
交叉(Intersection)	True	True

交叉入口/ 交叉出口

我們不知道如何進(jìn)入或離開——我們只知道沿著多邊形順時(shí)針,逆時(shí)針移動(dòng)。我們?nèi)绾伟褍烧咄馄饋?

如果我們?cè)谝粋€(gè)交點(diǎn)的兩邊取兩個(gè)點(diǎn)，并測(cè)試它們是否在另一個(gè)多邊形內(nèi)，我們可以保證一個(gè)點(diǎn)在外面，一個(gè)點(diǎn)在里面:

如果第一個(gè)點(diǎn)在外面，那么我們可以認(rèn)為這條線是通過交點(diǎn)進(jìn)入多邊形的。如果第一個(gè)點(diǎn)在內(nèi)，則該線通過交點(diǎn)離開多邊形.

所以，我們真的只需要將每個(gè)交叉點(diǎn)標(biāo)記為交叉入口/ 交叉出口

當(dāng)我們沿著一條路徑行駛時(shí)，每個(gè)路口都會(huì)切換我們是在里面還是外面。它必須.

因此，我們只需要計(jì)算第一個(gè)點(diǎn)是否在另一個(gè)多邊形內(nèi)部。如果是，那么第一個(gè)交叉點(diǎn)是一個(gè)交叉出口——否則第一個(gè)交叉點(diǎn)是一個(gè)交叉入口.

而且由于路徑上的每個(gè)交叉點(diǎn)都在entry和exit之間切換，我們不必繼續(xù)測(cè)試點(diǎn)是在內(nèi)部還是外部（這很昂貴).

表現(xiàn)

最后，重要的是要認(rèn)識(shí)到交叉點(diǎn)是相對(duì)于多邊形的交叉入口或交叉出口.

這意味著每個(gè)交叉點(diǎn)有四種可能性.

?白色代表進(jìn)入，黑色代表退出。左半球?yàn)榧t色，右半球?yàn)樗{(lán)色

?實(shí)際上，對(duì)于每個(gè)交點(diǎn)，我們將在每個(gè)多邊形中插入一個(gè)點(diǎn)。所以每個(gè)交點(diǎn)會(huì)有兩個(gè)點(diǎn)，一個(gè)存儲(chǔ)在每個(gè)多邊形中。每個(gè)點(diǎn)都會(huì)跟蹤它是進(jìn)入還是退出.

現(xiàn)在我們準(zhǔn)備好代碼啦.

步驟1. 將多邊形轉(zhuǎn)換為鏈表

雙鏈表對(duì)于這個(gè)算法來說是一個(gè)有用的多邊形表示，因?yàn)槲覀儗⑼瑫r(shí)插入點(diǎn)和遍歷。通過使用雙鏈表，我們不必?fù)?dān)心插入會(huì)破壞遍歷.

我們還需要跟蹤一個(gè)點(diǎn)是否是一個(gè)交點(diǎn)，所以我們可以從false這里初始化它開始:

步驟2. 計(jì)算并插入交叉點(diǎn)

接下來，我們需要遍歷每個(gè)邊組合，看看它們是否相交。如果它們確實(shí)彼此相交，那么我們需要在多邊形中插入交點(diǎn).

線交點(diǎn)

首先，我們需要一個(gè)輔助函數(shù)來計(jì)算兩條線的交點(diǎn):

function LinesIntersect(a0, a1, b0, b1){var adx = a1[0] - a0[0];var ady = a1[1] - a0[1];var bdx = b1[0] - b0[0];var bdy = b1[1] - b0[1];var axb = adx * bdy - ady * bdx;var ret = {cross: axb,alongA: Infinity,alongB: Infinity,point: [Infinity, Infinity]};if (axb === 0)return ret;var dx = a0[0] - b0[0];var dy = a0[1] - b0[1];ret.alongA = (bdx * dy - bdy * dx) / axb;ret.alongB = (adx * dy - ady * dx) / axb;ret.point = [a0[0] + ret.alongA * adx,a0[1] + ret.alongA * ady];return ret; }

它計(jì)算兩條線的交點(diǎn)，并返回每條線上的交點(diǎn)“沿”多遠(yuǎn)。因此，例如，如果alongA是0.75，那么交集發(fā)生在從a0到的75% 處a1.?

這些值是重要的，因?yàn)樗麄兛赡苁秦?fù)數(shù)或大于1，因此，如果兩條線實(shí)際相交，我們需要測(cè)試alongA和alongB0和1（不含）之間.

下一個(gè)非交點(diǎn)

由于我們將在我們的鏈表中插入交點(diǎn)，所以有一個(gè)幫助函數(shù)來查找下一個(gè)非交點(diǎn).

function NextNonIntersection(node){do{node = node.next;} while (node.intersection);return node; }

每個(gè)邊組合(Edge Pair)

現(xiàn)在我們可以編寫迭代每個(gè)邊組合的代碼:

var root1 = UpgradePolygon(poly1); var root2 = UpgradePolygon(poly2);var here1 = root1; var here2 = root2; do{do{//// TODO: test intersection between:// here1 -> NextNonIntersection(here1) and// here2 -> NextNonIntersection(here2)//here2 = NextNonIntersection(here2);} while (here2 !== root2);here1 = NextNonIntersection(here1); } while (here1 !== root1);

交叉點(diǎn)測(cè)試

給定兩個(gè)節(jié)點(diǎn)，我們可以測(cè)試交集:

var next1 = NextNonIntersection(here1); var next2 = NextNonIntersection(here2);var i = LinesIntersect(here1.point, next1.point,here2.point, next2.point );if (i.alongA > 0 && i.alongA < 1 &&i.alongB > 0 && i.alongB < 1){//// TODO: insert intersection points in both polygons at// the correct location, referencing each other// }

插入交叉點(diǎn)

最后，如果兩條邊相交，那么我們要在兩個(gè)非交點(diǎn)之間插入我們的交叉點(diǎn).

為了將它插入正確的位置，我們必須跟蹤alongA和alongB值以確保如果兩個(gè)交點(diǎn)在同一條邊上，它們以正確的順序插入.

我們將要?jiǎng)?chuàng)建兩個(gè)節(jié)點(diǎn)，一個(gè)用于每個(gè)多邊形——但這些節(jié)點(diǎn)應(yīng)該相互指向，以便我們稍后在遇到交叉點(diǎn)時(shí)可以在多邊形之間“跳躍”

var node1 = {point: i.point,intersection: true,next: null,prev: null,dist: i.alongA,friend: null }; var node2 = {point: i.point,intersection: true,next: null,prev: null,dist: i.alongB,friend: null };// point the nodes at each other node1.friend = node2; node2.friend = node1;var inext, iprev;// find insertion between here1 and next1, based on dist inext = here1.next; while (inext !== next1 && inext.dist < node1.dist)inext = inext.next; iprev = inext.prev;// insert node1 between iprev and inext inext.prev = node1; node1.next = inext; node1.prev = iprev; iprev.next = node1;// find insertion between here2 and next2, based on dist inext = here2.next; while (inext !== next2 && inext.dist < node2.dist)inext = inext.next; iprev = inext.prev;// insert node2 between iprev and inext inext.prev = node2; node2.next = inext; node2.prev = iprev; iprev.next = node2;

步驟3. 計(jì)算交叉入口/交叉出口

我們知道交叉口在進(jìn)入和退出之間交替。但是第一個(gè)交叉點(diǎn)是什么？是入口還是出口.

簡(jiǎn)單：如果多邊形的第一個(gè)點(diǎn)在另一個(gè)多邊形內(nèi)，那么第一個(gè)交點(diǎn)必須是出口.

但是，計(jì)算一個(gè)點(diǎn)是否在多邊形內(nèi)部實(shí)際上有點(diǎn)復(fù)雜.

點(diǎn)在多邊形內(nèi)

PointInPolygon通過計(jì)算水平線相交的邊數(shù)來工作。水平線從(-Infinity, y)到(x, y)。它只關(guān)心交叉點(diǎn)的數(shù)量是奇數(shù)還是偶數(shù)。它基于光線投射。

交替進(jìn)入/退出

現(xiàn)在我們可以輕松計(jì)算出一個(gè)交叉點(diǎn)是入口還是出口:

步驟4. 生成結(jié)果

我們已經(jīng)走了很長一段路！這是我們到目前為止所擁有的.

我們已經(jīng)計(jì)算并插入了交點(diǎn)，并將它們標(biāo)記為每個(gè)多邊形的入口或出口.

現(xiàn)在是有趣的部分！

從哪里開始

?我們從哪里開始追蹤結(jié)果？我們不能只選擇一個(gè)隨機(jī)點(diǎn)，因?yàn)橛行c(diǎn)實(shí)際上可以從結(jié)果中完全刪除.

由于所有操作都包括每個(gè)交集，我們應(yīng)該從尋找未處理的交集開始.

我們添加到最終結(jié)果中的每個(gè)交點(diǎn)，我們都標(biāo)記為已處理.

然后，我們只是繼續(xù)跟蹤，直到我們不再有任何交集需要處理.

var result = []; var isect = root1; var into = [intoBlue, intoRed]; // explained below while (true){do{if (isect.intersection && !isect.processed)break;isect = isect.next;} while (isect !== root1);if (isect === root1)break;//// TODO: process isect// }

?轉(zhuǎn)向哪個(gè)方向

最后，我們來到了癥結(jié)所在:

當(dāng)我們遇到十字路口時(shí)，我們?cè)趺粗涝撏膫€(gè)方向轉(zhuǎn)彎?

讓我們來推理一下：

Is Entry?Move Into?Move Forward?

True	True	True
True	False	False
False	True	False
False	False	True

因此，如果，我們應(yīng)該繼續(xù)前進(jìn)isEntry === intoPoly

由于我們所在的多邊形來回切換，我們只需通過將intoBlue和存儲(chǔ)intoRed在into列表中來使我們的決策動(dòng)態(tài)化，并將?其curpoly用作索引．

var curpoly = 0; var clipped = [];var here = isect; do{// mark intersection as processedhere.processed = true;here.friend.processed = true;var moveForward = here.isEntry === into[curpoly];do{clipped.push(here.point);if (moveForward)here = here.next;elsehere = here.prev;} while (!here.intersection);// we've hit the next intersection so switch polygonshere = here.friend;curpoly = 1 - curpoly; } while (!here.processed);result.push(clipped);

沒有交叉點(diǎn)

如果沒有交叉點(diǎn)？

我們的結(jié)果集將是空的……這可能是正確的，也可能是錯(cuò)誤的——這取決于操作．

一個(gè)簡(jiǎn)單的檢查就足以修復(fù)它：

if (result.length <= 0){if (is1in2 === intoBlue)result.push(poly1);if (is2in1 === intoRed)result.push(poly2); }

演示

單擊此處啟動(dòng)演示！

?您可以拖動(dòng)每個(gè)多邊形的點(diǎn)，并通過單擊按鈕切換操作。

?附錄：限制

抱歉，這個(gè)算法有一個(gè)嚴(yán)重的局限性：

您不能擁有完美重疊的點(diǎn)或邊．

如果你仔細(xì)想想，這是有道理的：整個(gè)算法都是基于交叉點(diǎn)的思想．

如果點(diǎn)或邊直接重疊，那么您就不會(huì)得到那種好的跳躍效果．

最初的論文建議稍微“擾亂”點(diǎn)，這樣線條就不會(huì)完全重疊。我最初認(rèn)為這是一個(gè)小調(diào)整，不會(huì)有有問題．

但是，我錯(cuò)了．

擾動(dòng)點(diǎn)會(huì)破壞數(shù)據(jù)——因此可能很重要的源數(shù)據(jù)的屬性（例如，平滑邊緣）變得無效．

幸運(yùn)的是我研究了另一種處理一切的算法，并寫了一篇后續(xù)文章

此處閱讀后續(xù)內(nèi)容：多邊形裁剪（第 2 部分）

總結(jié)

以上是生活随笔為你收集整理的多边形裁剪(Polygon Clipping) 1的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

上一篇： MSP432 FPU与DSP测试
下一篇：移动互联网应用开发概览