[問題] 紙面上折線的判斷

[yin0416 (鉛筆)]

開發平台(Platform): (Ex: Win10, Linux, ...) 

Mac、Win10

編譯器(Ex: GCC, clang, VC++...)+目標環境(跟開發平台不同的話需列出)

Xcode、DeV C++

問題(Question)：

想請教一下我目前遭遇到的問題，

用一群處於平面上的粒子，且為有序排列，當作一張紙，

再以電腦模擬揉紙的過程，我得到了這粒子在三維空間中的位置，

現在要判斷它的折線，想得到折線的長短分佈，

請問有適合的演算法可以處理這個問題嗎？

謝謝！

餵入的資料(Input)：

1  0  0  0    // 第一行是粒子編號，再來是空間中 X、Y、Z 的位置
2  1  0  0
3  2  0  0

預期的正確結果(Expected Output)：

2 256   // 第一行是折線的長度，然後是這種長度折線的數量
3 200
4 168
5 98
6 7

補充說明(Supplement)：

目前還沒想到怎麼寫這個程式，不知道有沒有適合的演算法～～謝謝！

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.114.127.104
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1479265800.A.D58.html
推 friendever: 有點看不懂@@y
推 firejox: 對每個粒子判斷跟相臨的粒子的凹凸性
→ yin0416: 我是說，我目前已經得到紙被揉過的結果了，它記錄的型式
→ firejox: 我猜
→ yin0416: 是每個粒子的位置。我想得到折線的分佈結果～～
→ firejox: 可以知道原先相臨的粒子有哪些嗎？
→ yin0416: 可以知道！
→ yin0416: Sorry 剛才在查別的網頁，想看看有沒有對這個問題的程式
→ yin0416: 所以忘了要回應～～
推 firejox: 那以一個粒子為中心按照順序掃周圍的粒子 ，判斷四個點
→ firejox: 是否為平面，不是的話就可以找出折線
→ yin0416: 嗯，但如何得到折線的長度呢？
→ yin0416: 實際上，應該不會有完全的平面，因為它會扭曲～～
→ yin0416: 所以我應該訂個標準，看看彎曲多大的程度視為有折線～～
推 firejox: 把斜率相同且相臨的線段合成就能找出折線了
→ yin0416: 謝謝，我再試試看！