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

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

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

Rus Almighty

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

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

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

Rus Almighty

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

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

Rus Almighty

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

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

Rus Almighty

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

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

nvrmnd

New member
לא כזה קשה

האם נקודה היא בתוך מצולע היא בעיה ידוע במדעי המחשב, וככזאת יש לה אלגוריתמים ידועים. חפש בגוגל הנה סתם משהו שמצאתי (כתוב ב 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; }

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

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

Rus Almighty

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

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

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

לפי השיטה הזו גם אם רק מוט אחד יהיה חסר אז הכדור יפול, וברור שזה לא נכון.....
 
הנה הבעייה האמיתית שעלי לפתור........ ../images/Emo41.gif

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

Rus Almighty

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

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

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

Rus Almighty

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

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

Rus Almighty

New member
למקרה של חלק

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