خوارزمية جيل مرتفع؟

Question

كنت أتطلع حول الإنترنت ولم أتمكن من العثور على خوارزمية مثالية لهذه المشكلة بالذات:

لدى عملائنا مجموعة من النقاط والوزن إلى جانب كل نقطة كما يتضح من هذه الصورة:

النقاط المرجحة http://chakrit.net/files/stackoverflow/so_heightmap_points.png.

منها، لدينا برنامج نظم المعلومات الجغرافية التي يمكن أن تولد "مرتفعات" أو نوع من بيانات التضاريس من هذه النقاط وقيم وزنها ولكن لدينا بالقرب من ألف نقطة من البيانات وأنها ستتغير مع مرور الوقت، ونود أن قم بإنشاء أدواتنا الخاصة لتوليد هذه المرتفعات.

حتى الآن، حاولت حساب الوزن لكل بكسل من مسافةها إلى أقرب نقطة بيانات مع Sqrt((x1 - x2) ^ 2 + (y1 - y2) ^ 2) وتطبيق عامل الوزن والمسافة حسب لون نقطة البيانات لإنتاج لون التدرج الناتج لهذا بكسل معين:

النتيجة المرتفع http://chakrit.net/files/stackoverflow/so_heightmap_result.png.

يمكنك أن ترى أنه لا تزال هناك مشاكل مع تكوين معينة من نقاط البيانات وتنتج الخوارزمية في بعض الأحيان صورة مضللة إلى حد ما عندما يكون هناك الكثير من نقاط البيانات. يجب أن تبدو النتيجة المثالية مثل علامة القطع وأقل مثل مضلع.

فيما يلي صورة مثال واحدة من مقالة Wikipedia حول صعود التدرج الذي يدل على النتيجة التي أريدها:

الجبال http://chakrit.net/files/stackoverflow/so_gradient_dents.png.

خوارزمية صعود التدرج ليس اهتمامي. ما أنا مهتم هي الخوارزمية لحساب الوظيفة الأصلية في تلك الصورة في المقام الأول، قدمت نقاط البيانات مع الأوزان.

أنا لم أحاط أي فئة في الرياضيات الطوبولوجية، ولكن يمكنني القيام ببعض التفاضل والتكامل. أعتقد أنني قد أفتقد شيئا ما وفقدت إلى حد ما في ما يجب أن أكتب في مربع بحث Google.

أحتاج إلى بعض المؤشرات.

شكرا!

Answer 1

ما تبحث عنه هو الاستيفاء السطحي.

بعض المنتجات موجودة للقيام بذلك (هنا واحد)

يمكن بعد ذلك استجواب الوظيفة الناتجة / SPLINE / البناء الرياضي الآخر عند الدقة المطلوبة لتزويد خريطة الارتفاع.

وظيفة الاستيفاء الخاص بك

Sqrt((x1 - x2) ^ 2 + (y1 - y2) ^ 2) 

مشابه ل عكس المسافة المرجحة الأساليب إلا أنك تقوم بتطبيق مرشح تعسفي وتخلص العديد من نقاط البيانات الأخرى.

تعتمد معظم هذه التقنيات على عدد معقول من العينات والسلوك "يشبه التضاريس" الذي يدعم القيم.

أقترح استخدام الوزن كعينة الارتفاع ومحاولة طريقة Simpard Shepard في الرابط الثاني (لا تصفية أي بكسل لبدء التشغيل) من خلال أخذ نسبة مساهمة نقاط العينة في قيمة الارتفاع الكلي عند نقطة الاستيفاء التي يمكنك مزجها ألوان العينات في تلك النسب لألوان النقطة أيضا. استخدم الشدة (تتحدث تقريبا الرماد الرمادي في مساحة RGB البسيطة) لعرض الارتفاع أو إضافة خطوط كونتور باللون الأسود مثل الصورة المثال.

Answer 2

هذه المشكلة ليست سهلة كما تبدو على السطح. مشكلتك هي أن كلا الجانبين من حدود منطقتين بحاجة إلى أن يكون لها نفس الارتفاع، وهو ما يقوله، يتم تحديد ارتفاع بكسل معين بأكثر من أقرب جار واحد فقط.

إذا فهمت ذلك بشكل صحيح، فأنت بحاجة إلى خيارين على الأقل (وقطعة ثالثة من Jargon).

للقيام بذلك بشكل صحيح، تحتاج إلى كسر الطائرة إلى voronoi tesselation..

من المحتمل أنك تريد استخدام KD-Tree. لمساعدتك في العثور على أقرب جار. بدلا من تناول O (n ^ 2)، سيؤدي ذلك إلى رفع الأمر إلى O (N) (n)) (الفائدة الإضافية هي أن مرحلة توليد منطقة Voronoi الخاصة بك ستكون سريعة بما يكفي في التنمية للعمل في مرحلة حساب الارتفاع).

الآن بعد أن تمتلك خريطة فهرسة 2-D لكل نقطة إلى أقرب جارها الأول، تحتاج إلى المشي عبر كل X، Y نقطة على الخريطة وحساب ارتفاعها.

للقيام بذلك لنقطة معينة X، Y، احصل أولا على أقرب جارته وأمسك به في قائمة، ثم جمع جميع المناطق المتجاورة على مخطط Voronoi. طريقة سهلة هي استخدام ملء الفيضانات للعثور على كل النقاط في المنطقة، ثم انظر حول الحدود وجمع الهويات الأخرى.

باستخدام هذه القائمة من جميع أقرب جيران، لديك الآن تسديدة في الاستيفاء بشكل صحيح! (انظر إجابات أخرى لخطط الاستيفاء).

Answer 3

لقد طلبت للحصول على معلومات عن الخوارزميات لاستيفاء 2-D للبيانات غير النظامية، وهي منطقة معقدة تماما. منذ أن تقول أن لديك ArcGIS، أنا ننصح بشدة لك لالتقاط تلقائيا في ArcGIS باستخدام مدمج الميزات للحسابات التلقائية. أنا متأكد من أن ستكون اسهل بكثير من كتابة خوارزمية الاستيفاء الخاصة بك. لقد قمت ببعض أتمتة ArcGIS، إنها واضحة إلى حد ما.

إذا قمت بكتابة كود الاستيفاء الخاص بك - أنصحك بعدم ذلك - أول شيء هو اختيار الخوارزمية المناسبة لأن هناك العديد من كل منها بإجراءات إيجابية وبعديها. فيما يلي بعض النصائح التي سيدت من المساعدة لأداة الاستيفاء الممتازة متصفح (الذي راجع للشغل يمكن أيضا أن يكون أيضا تلقائيا بسهولة). هناك المزيد من الخوارزميات، هذه هي فقط تلك التي جربتها.

• kriging. هي واحدة من الأساليب الأكثر مرونة وهي مفيدة للبكاء تقريبا أي نوع من مجموعة البيانات. مع معظم مجموعات البيانات، Kriging مع Variogram الخطي الافتراضي فعال للغاية. بشكل عام، كنا نوصي كثيرا بهذه الطريقة. Kriging هي طريقة الشبكة الافتراضية لأنها تنشئ خريطة جيدة لمعظم مجموعات البيانات. لمجموعات بيانات أكبر، يمكن أن تكون Kriging بطيئة إلى حد ما. يمكن kriging استقراء قيم الشبكة خارج نطاق Z بياناتك.
• ربط المسافة العكسية سريع ولكن لديه الميل إلى توليد أنماط "عين الثور" من ملامح متحدة المركز حول نقاط البيانات. عكس المسافة إلى السلطة لا يستكشف قيم z تتجاوز نطاق البيانات. من السهل تنفيذ خوارزمية لتراجع عن بعد عكسية ولكن ستكون إبطاءا.
• التثليث مع الاستيفاء الخطي سريع. عند استخدام مجموعات بيانات صغيرة، يولد التثليح مع الاستيفاء الخطي وجوه ثلاثية مميزة بين نقاط البيانات. التثليث مع الاستيفاء الخطي لا يستكشف قيم Z تتجاوز نطاق البيانات.
• طريقة Shephard يشبه المسافة معكوسة إلى قوة ولكنه لا يميل إلى توليد أنماط "عين الثور"، خاصة عندما يتم استخدام عامل تجانس. طريقة شيبرد يمكن أن استقراء القيم خارج نطاق Z بياناتك.

لتنفيذ الخوارزميات: يمكنك تجربة Googling، أو اتبع الروابط في بعض الإجابات الأخرى. هناك بعض حزم نظم المعلومات الجغرافية مفتوحة المصدر التي تشمل الاستيفاء، لذلك ربما يمكنك استخراج الخوارزميات منها إذا كنت تحب Potholing من خلال C ++. أو هذا الكتاب بقلم ديفيد واتسون يعتبر كلاسيكيا، على الرغم من أن القراءة صعبة وعينة رمز هو السباغيتي الأساسية !! ولكن من ما أسمعه، إنه الأفضل. إذا كان أي شخص آخر على تجاوز سعة مكدس يعرف بشكل أفضل، فالرجاء تصحيح لي لأنني لا أصدق ذلك أيضا.

Answer 4

kriging. هي واحدة من أساليب الوزن الثقيل للقيام بذلك، خاصة في مجال نظم المعلومات الجغرافية. لديها العديد من الخصائص الرياضية لطيفة - الجانب السلبي هو أنه قد يكون بطيئا اعتمادا على variogram..

إذا كنت تريد شيئا أكثر بساطة، فهناك العديد من إجراءات الاستيفاء التي تتعامل مع هذا بشكل جيد للغاية. إذا كنت تستطيع الحصول على نسخة من نسخة من الوصفات العددية, ، مكرسة الفصل 3 لشرح العديد من المتغيرات للاستيفاء، ويشمل أمثلة التعليمات البرمجية وأوصاف خصائصها الوظيفية.

Answer 5

هي الخوارزمية لحساب الوظيفة الأصلية في تلك الصورة في المقام الأول، قدمت نقاط البيانات مع الأوزان.

انه ممكن. إذا بدأت مع نقاط واحدة، فسوف ينتهي الأمر دائما بالدوائر، ولكن إذا كنت تقوم بوزن Datapooints وأخذ ذلك في الاعتبار، فيمكنك إسراف الدوائر في أبيضا كما في الصورة ..

السبب في إنهاء المضلعات هو أنك تستخدم وظيفة منفصلة في حسابك - أولا يمكنك العثور على أقرب لون، ثم تحدد اللون.

يجب أن تنظر بدلا من ذلك إلى خوارزميات التدرج التي تقوم بتعيين لون للنقطة المستندة إلى المسافة والوزن من Datapooints الثلاثة التي أرفق تلك النقطة في مثلث.

خوارزمية التدرج

ذلك يعتمد على ما تحاول عرضه. الخوارزمية المبسطة سيكون:

لكل بكسل:

• ابحث عن النقاط الثلاث التي تشكل أصغر مثلث تحيط بهذا بكسل

• اضبط هذه النقطة على اللون (نظام لون HSV) الذي يتأثر بكل من الوزن والمسافة لكل Datapoint:

  pixel.color = datapoint[1].weight * distance(pixel, datapoint[1]) * datapoint[1].color + datapoint[2].weight * distance(pixel, datapoint[2]) * datapoint[2].color + datapoint[3].weight * distance(pixel, datapoint[3]) * datapoint[3].color

أنا أستخدم + هنا، ولكن تحتاج إلى تحديد خوارزمية "المتوسط" مناسبة للتطبيق الخاص بك.

-Adam.

Answer 6

يبدو أن الاستيفاء السطحي مشكلة صعبة ورياضية. آخر، أرخص وسيلة للقيام بذلك هي:

For each pixel:
For each point:
pixel.addWeight(weight(point, pixel))

def addWeight(w):
totalweight += w
numberofweights += 1
weight = totalweight / numberofweights

مثال وظيفة الوزن:

def weight(point, pixel):
return point.weight * 1/(1 + sqrt((point.x - pixel.x)^2 + (point.y - pixel.y)^2))

إنه نهج القوة الغاشمة تماما، لكنه بسيط.

Answer 7

نفذت شيئا كهذا في Winamp Avs منذ فترة. يستخدم نهج نوع "Metaballs" من حساب المسافة العكسية المربعة (لتجنب SQRT للسرعة) من كل نقطة بيانات، مما يؤدي إلى توجيهه (على سبيل المثال إلى 1.0)، وأخذ مجموع المسافات لكل نقطة في الشبكة 2D. هذا سوف يعطي خريطة اللون / الارتفاع بسلاسة.

إذا كنت ترغب في النظر إلى التعليمات البرمجية، في الإعداد المسبق "Glowy" J10 AVS Pack..

تحرير: مجرد النظر إليه أضفت بعض الجاز الأخرى لجعلها تبدو أجمل، الجزء الأكثر أهمية هو:

d1=s/(sqr(px1-rx)+sqr(py1-ry));
d2=s/(sqr(px2-rx)+sqr(py2-ry));
d3=s/(sqr(px3-rx)+sqr(py3-ry));
d4=s/(sqr(px4-rx)+sqr(py4-ry));
d5=s/(sqr(px5-rx)+sqr(py5-ry));
d6=s/(sqr(px6-rx)+sqr(py6-ry));
d=d1+d2+d3+d4+d5+d6;

الذي يأخذ المبلغ ل 6 نقاط. كل شيء آخر تم القيام به في قيم الإخراج الحمراء والأخضر والأزرق هو جعلها تبدو أجمل. 6 نقاط ليست كبيرة ولكن في الاعتبار في الاعتبار أنني كنت أحاول جعل هذا يعمل في الوقت الحقيقي على شبكة 320x200 على آلة 400 ميجا هرتز عندما كان جديدا (الذي يفعل عند ~ 20fps). :)

استبدال الأحمر =، الأخضر = والأزرق = ... خطوط مع الأحمر = D؛ إلخ ... لمعرفة ما أعنيه. كل شيء يذهب بعيدا وأنت تركت مع صورة Greyscale بسلاسة النيطات حول نقاط البيانات.

تحرير آخر: نسيت أن أقول "S" هو الوزن المشترك لجميع النقاط، مما يؤدي إلى تغييره لكل واحد يعطي الأوزان الفردية لكل نقطة، مثل D1 = 2 / (...) و D2 = 1 / (.. .) من شأنه أن يعطي D1 ضعف ارتفاع في وسطه كما D2. قد ترغب أيضا في تخفيف التعبير في الأسفل مع شيء مثل D1 = 2 / Max (...، 1.0) لتنعيم قمم النقاط بحيث لا تبلغ ذروتها في اللانهاية في الوسط. :)

آسف لوجود الفوضى للإجابة ... اعتقدت أن نشر مثال التعليمات البرمجية سيكون جيدا بما فيه الكفاية ولكن على التفتيش الرمز الخاص بي مربك ويصعب قراءته. :(

Answer 8

أعلم أن هذا سؤال قديم للغاية، لكنني تعثرت عبره أثناء محاولة حل مشكلة مماثلة.

هناك مشروع مفتوح المصدر يسمى سوروفيت هذا ينفذ بالضبط هذا النوع من الوظائف.

Answer 9

كنت تبحث عن شيء الخلاط المكالمات "metaballs" (مقالة ويكيبيديا مع روابط, مثال). أعتقد أنه من هذا الطريق:

الكائنات الخاصة بك هي المخاريط التي عصا من الأرض. إنهم جميعا بارابولا ويخبر الوزن إلى أي مدى يتصارعون من الأرض. بدلا من ذلك، اجعلها كلها نفس الارتفاع وضبط "التسطيح" من الباربولا وفقا لذلك، لذا فإن الوزن الكبير يجعل مخروطا واسعا في حين أن وزن منخفض يجعله حادا. ربما حتى كلاهما إلى حد ما.

أقترح أن تنفذ هذا ونرى كيف تبدو.

بعد ذلك، تحتاج إلى تعليق قطعة قماش أو ورقة مطاطية على النتيجة. ستمتد القماش بمقدار معين وسيعطل بشكل عام بسبب الجاذبية. المخاريط تبقيه.

طالما أنك قريب من مركز مخروطي، فإن إحداثيات Z هي مجرد موقف على سطح المخروط. وأنت تغادر مركز المخروط، تبدأ الجاذبية في الانسحاب وتأثير المخاريط الأخرى.