יש פונקציה כזאתי?

לא שאני מכיר אבל הינה נוסחה פשוטה לחישוב שטח של פוליגן (בעזרת דטרמיננטה):

http://mathworld.wolfram.com/PolygonArea.html

מה זה דטרמיננטה ואני לא ממש מבין מה הולך שמה..

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

הנה שני אלגוריתמים שמצאתי שמחשבים את השטח של פוליגון:

// area2D_Polygon(): computes the area of a 2D polygon
//  Input: int n = the number of vertices in the polygon
//      Point* V = an array of n+2 vertices
//            with V[n]=V[0] and V[n+1]=V[1]
//  Return: the (float) area of the polygon
float
area2D_Polygon( int n, Point* V )
{
  float area = 0;
  int  i, j, k;   // indices

  for (i=1, j=2, k=0; i<=n; i++, j++, k++) {
    area += V[i].x * (V[j].y - V[k].y);
  }
  return area / 2.0;
}

int area = 0;
int N = lengthof(p);
//We will triangulate the polygon
//into triangles with points p[0],p[i],p[i+1]

for(int i = 1; i+1<N; i++){
  int x1 = p[i][0] - p[0][0];
  int y1 = p[i][1] - p[0][1];
  int x2 = p[i+1][0] - p[0][0];
  int y2 = p[i+1][1] - p[0][1];
  int cross = x1*y2 - x2*y1;
  area += cross;
}
return abs(cross/2.0);

מקורות:

http://geometryalgorithms.com/Archive/algorithm_0101/

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry1

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

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

מה שאתה צריך לעשות זה לברר מה הדרישות:

1) האם כל הפוליגונים מישוריים? (כלומר דו מימדיים)

2) האם יש פוליגונים שחותכים את עצמם?

3) האם כל הפוליגונים קמורים (convex)?

בהתאם לתשובות לשאלות אלה, תוכל למצוא אלגוריתם מתאים.

כל הפוליגונים דו מימדיים.

יש פוליגונים שחותכים את עצמם.

הפוליגונים יכולים להיות גם קעורים.

מישהו יודע איזשהוא אלגוריתם למציאת שטח לזה?

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

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

עבור פוליגונים פשוטים אך קעורים, הנוסחאות שהוצגו קודם יפעלו: http://local.wasp.uwa.edu.au/~pbourke/geometry/polyarea/

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

לדוגמא, אם תחשוב על פנטגרם, האם השטח כולל את כל החלקים הפנימיים או לא?

בכל מקרה הבעיה היא לא פשוטה.

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

ניסיתי את הנוסחה הראשונה שקובי נתן עם שינויים (יש בעיות עם שטח שלילי וכו' - זה מסודר) ..וזה עובד דיי בסדר..

בפוליגונים שחותכים את עצמם זה גם פועל?

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

מוזר, זה לא אמור. אם יש חורים או איזורים כפולים אז זה עלול לחשב את השטח שלהם פעמיים.

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

ממ אני אבדוק את זה בהזדמנות כרגע אני יותר לחוץ לפתור דברים אחרים..

יש לי עוד בעיה..

יש לי מערך של נקודות שבירה שנשמר כל פעם ואחרי שאני משתמש בו פעם אחת אני משתמש בו שוב ודורס את מה שיש בו.

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

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

ממש, אבל _ממש_ לא הבנתי כלום.

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

ככה במהלך כל התוכנית אני מקבל הרבה מערכים כאלה.

אני צריך לשמור את כולם במערך דו מימדי .

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

מקווה שהבנת..

ומה אתה עושה איתם אחר כך?

בכל מקרה, דרך נוחה היא עם אחד מה container-ים של ה STL. ככה לא תצרך לנהל את הזכרון בעצמך - יותר נוח ועם פחות מקום לטעויות מצידך.

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

אם אתה כן צריך, תשתמש ב vector .