پرش به محتویات

مساحت جهت‌دار مثلث

با داشتن سه نقطه $p_1$، $p_2$ و $p_3$، مساحت جهت‌دار (علامت‌دار) مثلثی که توسط آن‌ها تشکیل می‌شود را محاسبه کنید. علامت مساحت به این صورت تعیین می‌شود: تصور کنید در صفحه در نقطه $p_1$ ایستاده‌اید و رو به $p_2$ هستید. به سمت $p_2$ حرکت می‌کنید و اگر $p_3$ در سمت راست شما باشد (در این صورت می‌گوییم این سه بردار «ساعتگرد» می‌چرخند)، علامت مساحت منفی است، در غیر این صورت مثبت است. اگر سه نقطه هم‌خط باشند، مساحت صفر است.

با استفاده از این مساحت علامت‌دار، می‌توانیم هم مساحت معمولی بدون علامت (به عنوان قدر مطلق مساحت علامت‌دار) را به دست آوریم و هم تعیین کنیم که نقاط به ترتیب مشخص‌شده ساعتگرد یا پادساعتگرد قرار دارند (که برای مثال، در الگوریتم‌های پوش محدب (convex hull) مفید است).

محاسبه

می‌توانیم از این واقعیت استفاده کنیم که دترمینان یک ماتریس $2\times 2$ برابر با مساحت علامت‌دار متوازی‌الاضلاعی است که توسط بردارهای ستونی (یا سطری) ماتریس ساخته می‌شود. این مشابه تعریف ضرب خارجی در فضای دوبعدی است (ببینید هندسه‌ی پایه). با تقسیم این مساحت بر دو، مساحت مثلث مورد نظر خود را به دست می‌آوریم. ما از بردارهای $\vec{p_1p_2}$ و $\vec{p_2p_3}$ به عنوان بردارهای ستونی استفاده کرده و دترمینان $2\times 2$ را محاسبه می‌کنیم:

$$2S=\left|\begin{matrix}x_2-x_1 & x_3-x_2\\y_2-y_1 & y_3-y_2\end{matrix}\right|=(x_2-x_1)(y_3-y_2)-(x_3-x_2)(y_2-y_1)$$

پیاده‌سازی

int signed_area_parallelogram(point2d p1, point2d p2, point2d p3) {
    return cross(p2 - p1, p3 - p2);
}

double triangle_area(point2d p1, point2d p2, point2d p3) {
    return abs(signed_area_parallelogram(p1, p2, p3)) / 2.0;
}

bool clockwise(point2d p1, point2d p2, point2d p3) {
    return signed_area_parallelogram(p1, p2, p3) < 0;
}

bool counter_clockwise(point2d p1, point2d p2, point2d p3) {
    return signed_area_parallelogram(p1, p2, p3) > 0;
}

مسائل تمرینی