לאיזה כיוון יתגלגל הכדור? ..........

[שחר בן צור]

לאיזה כיוון יתגלגל הכדור? ............/images/Emo180.gif

שלום לכולם! לצורך פיתוח משחק מחשב כלשהו עלי לפתור חידה/בעייה מסויימת שעל פניה נראיית דיי פשוטה, אבל בינתיים לא הצלחתי להגיע לפתרון. ברשותי דיסקה עגולה שעליה אפשר למקם 8 מוטות תמיכה שווים באורכם. המוטות מפוזרים בצורה סימטרית על פני היקף הדיסקה (אני יודע שבציור זה לא ממש סימטרי וגם לא ממוקם בצורה מדוייקת) כלומר כל 45 מעלות. אני מניח מעל המוטות כדור, באופן סימטרי כך שמרכז הכובד שלו ממוקם בדיוק מעל מרכז הדיסקית, ועלי לדעת לאיזה כיוון יתגלגל הכדור כאשר רק חלק מהמוטות מוצבים במקומם, לדוגמה - 1 - אם רק מוטות 1, 3, 5, 7 מוצבים במקומם, ברור שהכדור ישמור על שיווי משקל ולא יזוז ברגע שהנחתי אותו מלמעלה. 2 - אם רק מוטות 8, 1, 2 מוצבים, ברור שהכדור יתגלגל כלפי מטה לכיוונו של מוט מספר 5 (שכאמור אינו מוצב במקומו). כלומר כל אחד מ 8 המוטות יכול להיות ממוקם על הדיסקית או לא, זאת אומרת שיש סה"כ 256 מצבים אפשריים (2 בחזקת 8). איך אני יכול לדעת בדרך חישובית פשוטה, באילו מצבים הכדור ישאר יציב, ובאילו מצבים של המוטות הוא יתגלגל, והכי חשוב לאיזה כיוון

אשמח מאד אם למישהו יש פתרון מתמטי פשוט (או אלגוֹריתם) לבעייה הזו. תודה רבה מראש

שחר.

 

[Rus Almighty]

אם מרכז מסה בתוך השטח של המוטות אז יש שיווי

משקל, כלומר הכדור יפול כאשר שטח של המוטות לא מכסה את מרכז הכדור

 

[שחר בן צור]

זה קצת קשה במחשבית.......

אני צריך להסביר את זה איכשהו למחשב.... מה שנקרא בעברית אלגוריתם...... ולהתחיל לחשב שטחים של מצולעים ולבדוק את מרכז הכדור בתוך או מחוץ למצולע זה קצת מסובך...... אין שיטה פשוטה יותר? 1. הציעו לי בפורום אחד להשתמש בחישוב ווקטורים כדי לדעת לאיזה כיוון הכדור יפול, אבל לא הבנתי איך בדיוק לחשב את זה..... 2. "אם המרחק בין כל עמוד קיים לא עולה על ארבעה קטעים, אז הכדור לא יפול. אם אחד המרחקים בין כל עמוד קיים עולה על ארבעה קטעים, אז הכדור יפול בכיוון ניצב לישר שתואר בתגובתי הקודמת (הוא יתגלגל לכיוון ניצב לישר שנוצר בין שתי הנקודות הרחוקות ביותר זו מזו [למשל במקרה שקיימים עמודים 1,2,4 אז הכדור יתגלגל לכיוון ניצב לישר 1,4] לפחות ככה נראה לי אינטואיטיבית)" מה אתם אומרים? הפתרון השני נשמע לי מאד פשוט, השאלה היא אם הכלל הזה נכון לכל אחד מ 256 המצבים האפשריים כאן...... תודה.

 

[Rus Almighty]

?? מה זה קטעים שאתה מתאר??

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

 

[Rus Almighty]

חידוד קטן

בפעם השנייה שרשמתי נקודות התכוונתי לעמודים

 

[Rus Almighty]

נא לא להתייחס לפתרון השני

הוא לא מנוסח נכון

קשה לחשוב בצורה תקינה מאוחר

 

[שחר בן צור]

טוב, תודה, ומה על הפתרון שרשמתי למטה? יעבוד?

 

[Rus Almighty]

אני לא הבנתי כלכך את הרעיון שכתבת

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

 

[nvrmnd]

לא כזה קשה

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

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy) { int i, j, c = 0; for (i = 0, j = nvert-1; i < nvert; j = i++) { if ( ((verty>testy) != (verty[j]>testy)) && (testx < (vertx[j]-vertx) * (testy-verty) / (verty[j]-verty) + vertx) ) c = !c; } return c; }​

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

 

[שחר בן צור]

תודה רבה!

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

 

[nvrmnd]

אגב, לקחתי את זה מפה

http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html יש שם עוד הסברים. הפתרון שנתנו לך בפורום מתמתיקה הרבה יותר פשוט, אבל אם תרצה לשנות את המבנה של השאלה שלך, אולי תצטרך גם את הקטע של הנקודה והפוליגונים

 

[Rus Almighty]

השאלה אם אפשר לפשט את זה כי

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

 

[שחר בן צור]

האם זה יכול להיות פתרון? התלבטות....

מניחים את הדיסקה על מערכת צירים X, Y כך שמרכז הדיסקית ממוקם בדיוק על ראשית הצירים, כלומר בנקודה 0, 0. לאחר מכן אני מוצאים את ההיטלים של כל מוט שאינו ממוקם על הדיסקית - לדוגמה מוט 3 יתן 2 בציר X ו 0 בציר Y. לאחר מכן אני מסכם את כל ההייטלים בציר X, ואת כל אלו של ציר Y, וכיוון החץ שהם נותנים ביחד יתן לי את כיוון נפילת הכדור? האם זה פתרון נכון? תודה.

 

[שחר בן צור]

טעות, פתרון שגוי ../images/Emo10.gif

לפי השיטה הזו גם אם רק מוט אחד יהיה חסר אז הכדור יפול, וברור שזה לא נכון.....

 

[שחר בן צור]

../images/Emo26.gif ../images/Emo26.gif ../images/Emo26.gif ../images/Emo26.gif ../images/Emo26.gif ../images/Emo26.gif

 

[שחר בן צור]

הנה הבעייה האמיתית שעלי לפתור........ ../images/Emo41.gif

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

בקוטר מסויים (נגיד בקוטר של 20 פיקסלים לצורך הדוגמה) ולבדוק לאן הוא יתגלגל עד מצב של עצירה. אני לא מעוניין להתחשב בנתונים כגון התנופה שהכדור צבר או אנרציה, כלומר במקום הראשון ששם הכדור מגיע לשיווי משקל אני רוצה שהוא יעצור. נתונה לי הנקודה בה הונח הכדור (לדוגמה פיסקל 80 על 95) ועלי לקבל בתור תשובה סופית את הנקודה בה הכדור נעצר והגיע לשיווי משקל. לפתור את הבעייה הזו עם כדור זה יכול להיות שזה מסובך מדי, לכן אם לא תהייה ברירה אני מוכן "להתפשר" (רק אם אין ברירה) וללכת על פתרון מקורב, לדוגמה להניח שבמקום כדור מניחים דיסקית (שנמצאת תמיד במצב מאוזן) שהקוטר שלה מייצג את הקוטר של הכדור, או להתייחס רק לכמה נקודות מייצגות על הכדור ולהזניח את שאר המעטפת שלו, לדוגמה להסתכל על 3 טבעות מייצגות החל מהחצי התחתון של הכדור וכלפי מעלה (טבעות קטנה, בינונית מעליה, וטבעת גדולה מעליה בקוטר של הכדור) ובכל טבעת להתייחס ל 8 פיסקלים שמפוזרים בצורה שווה על הטבעת (כמו בשאלה המקורית ששאלתי קןדם) ואז לחשב את הכוחות המשותפים שמפעילה הקרקע על כל הנקודות יחד, כדי להחליט לאן הכדור יתגלגל (מקווה שההסבר מובן.....) בקיצור איך פותרים את זה? חישובי וקטורים? סיכום של ההייטלים (הכוחות) בציר X ובציר Y כדי להסיק את כיוון ההתקדמות של הכדור? אם זה הכיוון לפתרון --> איך מבצעים חישוב כזה? אני מעדיף את הפתרון הפשוט ביותר, כמה שפחות להסתבך אם אפשר.... אשמח מאד לקבל כל עזרה או עיצות בנושא, תודה מראש

 

[Rus Almighty]

המשטח של "חלק" או "חד"

יש לך נקדות גבוהות בפתאומיות או כל נקודה נמצאת קרוב לנקודות השכנות?

 

[שחר בן צור]

באופן עקרוני כל מצב אפשרי

למרות שאני משתדל לספק משטח כמה שיותר חלק בלי חיספוס או קפיצות פתאומיות. אבל אני רוצה לקחת בחשבון כל מצב אפשרי.

 

[Rus Almighty]

כי אתה צריך לחשב גרדיאנט ואם המשטח "חלק"

אז ניתן לעשות אלגוריטם יותר פשוט

 

[Rus Almighty]

למקרה של חלק

הפרש של שתי נקודות שכנות על ציר X והפרש של שתי נקודות שכנות על ציר (כפרשי גובהה)Y יהיו מספיק טובים כדי לקבוע את התאוצה של הכדור.