קביעת יחס הכלה

[iceman90]

מצטער על הכותרת הכללית... יש גבול לכמה שאפשר (וכדאי) לכתוב בשורה אחת.

אני מחפש אלגוריתם/תכנית (בכל שפה עם עדיפות ל cpp) אשר בהנתן פולינום המיוצג ע"י triangle mesh ונקודה (הכל בתלת מימד) תקבע האם הנקודה נמצאת בתוך או מחוץ לפוליגון.

התכנית יכולה להניח שהפוליגון הינו פוליגון פשוט (כלומר לא חותך את עצמו).

אה.. ולמי שרוצה לעזור ולא מכיר את המושג triangle mesh : מדובר בייצוג של פולינום (כאמור) ע"י סדרת משולשים, כאשר כל משולש מיוצג ע"י שלוש נקודות.

תודה מראש.

מטי.

[Boomerang]

נראה לי שאתה מתכוון לפוליגון (מצולע), ולא פולינום.

אתה מניח שהפוליגון הוא מישורי? ואם כן - אז שהנקודה נמצאת על המישור של הפוליגון?

אם לא אז לא מוגדר כ"כ היטב, וההגדרה צריכה להיות משהו כמו "המרחק בין הנקודה לפוליגון קטן מערך (קטן) מסוים".

הדרך לעשות את זה היא למצוא את משוואת המישור, ואם המרחק של הנקודה ממנו באמת קטן מהערך שהגדרת לחפש באיזה משולש הוא נמצא (ע"י מציאת משוואת הישר של כל צלע ובדיקה שהנקודה נמצאת בצד "הנכון" של הישר). אם הפוליגון שלך הוא קמור, ונמצא כולו על ישר אחד, מספיק שתבדוק את הצלעות שלו, ולא צריך לחלק אותו למשולשים.

[iceman90]

פוליגון, צודק טעות שלי.

מישורי ? מה פתאום ? זו בעיה קלה יחסית. אני מדבר על צורה תלת מימדית (כדוגמת ספרה, קוביה, טורוס וכמובן דברים קצת יותר אמורפים).

אני לא מחלק כלום למשולשים, הצורה נתונה ע"י אוסף משולשים שסוגרים צורה תלת מימדית (תחשוב למשל על התוצאה של טריאנגולציה למודל תלת מימדי כלשהו)

מטי.

[Boomerang]

אוקיי, אז אתה לא מדבר על פוליגון, אלא על mesh.

השאלה הבאה היא אם זה mesh סגור, אחרת היחס בפנים/בחוץ לא מוגדר.

אם כן, מספיק שתשלח קרן מהנקודה לכיוון כלשהו, ותספור את מספר הפעמים שאתה חוצה את ה- mesh שלך. אי-זוגי - בפנים, זוגי - בחוץ.

אם ל- faces שלך יש כיוון (כלומר שהן "קיימות" רק בכיוון אחד) אז מספיק לך לבדוק אם הפעם הראשונה שהקרן חוצה את האובייקט היא חוצה face מבפנים החוצה או מהחוץ פנימה.

[iceman90]

אני לא רוצה להשמע כפוי טובה, אבל אתה לא ממש עוזר. כידוע לך, "שלח קרן" היא לא פונקציה ב stdlib. אני מחפש פתרון לבעיה. הmesh סגור (אם כבר אנחנו קטנוניים אז המילה הנכונה היא פאון).

את מה שהצעת אני מכיר ובכל זאת זה לא ממש עוזר (שים לב, אני צריך לממש את הפונציה כולה - נפנופי ידיים מספיקים להסבר אבל לא בשביל לכתוב תכנית)

ושוב, תודה על שאתה מנסה.

מטי.

[Boomerang]

אולי הלינק הזה יעזור?

אחד הרעיונות המרכזיים הוא להשתמש בתיבות חוסמות (אתה מתחיל בתיבה חוסמת של כל הגוף, ומתחיל לחלק אותה עד שאתה מקבל תיבה שכולה נמצאת בתוך הגוף, והנקודה נמצאת בתוכה)