コミット: d803d6f195accd635e33c76a2ad3eb7e027cd016 - mmath (git)

Mercury Geometry and Math Library

コミットメタ情報

• リビジョン: d803d6f195accd635e33c76a2ad3eb7e027cd016 (tree)
• 日時: 2022-03-27 05:18:10
• 作者: AlaskanEmily <emily@alas...>
• コミッター: AlaskanEmily

ログメッセージ

Fix point_inside for triangles, add 2D cross-product to vector2

変更サマリ

• modified: geometry.segment.m
• modified: geometry2d.m
• modified: vector.vector2.m

差分

--- a/geometry.segment.m
+++ b/geometry.segment.m
@@ -43,7 +43,7 @@
 
 %------------------------------------------------------------------------------%
 
-:- type side ---> left ; right ; collinear.
+:- type side ---> left ; right ; colinear.
 
 %------------------------------------------------------------------------------%
 
@@ -82,6 +82,7 @@
 %==============================================================================%
 
 :- import_module float.
+:- import_module vector.vector2.
 
 %------------------------------------------------------------------------------%
 
@@ -101,7 +102,20 @@ as_tuple(S, {S ^ p1,  S ^ p2}).
 
 %------------------------------------------------------------------------------%
 % TODO!
-side(_, _) = collinear.
+
+side(segment(A, B), C) = Side :-
+    Cross = vector.vector2.cross(B - A, C - A),
+    ( if
+        Cross > float.epsilon
+    then
+        Side = left
+    else if
+        Cross < -float.epsilon
+    then
+        Side = right
+    else
+        Side = colinear
+    ).
 
 %------------------------------------------------------------------------------%
 

--- a/geometry2d.m
+++ b/geometry2d.m
@@ -224,6 +224,8 @@
 :- use_module math.
 :- import_module float.
 
+:- use_module geometry.
+:- use_module geometry.segment.
 :- use_module multi_math.
 :- import_module vector.vector2.
 
@@ -674,32 +676,31 @@ point_to_vector(geometry2d.point(X, Y)) = vector.vector2.vector(X, Y).
         Y = min(min(Y1, Y2), Y3),
         W = max(max(X1, X2), X3) - X,
         H = max(max(Y1, Y2), Y3) - Y),
-    (point_inside(Triangle, point(PX, PY)) :-
-        triangle_segments(Triangle, S1, S2, S3),
+    (point_inside(triangle(X1, Y1, X2, Y2, X3, Y3), point(PX, PY)) :-
+        % Find the side of the point for each segment
+        Pos = vector.vector2.vector(PX, PY),
+        Vector1 = vector.vector2.vector(X1, Y1),
+        Vector2 = vector.vector2.vector(X2, Y2),
+        Vector3 = vector.vector2.vector(X3, Y3),
+        Segment1 = geometry.segment.segment(Vector1, Vector2),
+        Segment2 = geometry.segment.segment(Vector2, Vector3),
+        Segment3 = geometry.segment.segment(Vector3, Vector1),
         
-        bounding_box(Triangle) = Bounds,
-        segment(Bounds ^ rect_x - 1.0, PY, PX, PY) = TestSegment,
+        Side1 = geometry.segment.side(Segment1, Pos),
+        Side2 = geometry.segment.side(Segment2, Pos),
+        Side3 = geometry.segment.side(Segment3, Pos),
         
-        % I tried my best to use existential term instantiation to express an
-        % exclusive-or disjunction. It didn't work.
-        % So I'm sorry. I should have done more.
-        ( collide_segments(TestSegment, S1, _) <=> not (
-                collide_segments(TestSegment, S2, _)
-            ;
-                collide_segments(TestSegment, S3, _)
-            )
-        ),
-        ( collide_segments(TestSegment, S2, _) <=> not (
-                collide_segments(TestSegment, S1, _)
-            ;
-                collide_segments(TestSegment, S3, _)
-            )
-        ),
-        ( collide_segments(TestSegment, S3, _) <=> not (
-                collide_segments(TestSegment, S1, _)
-            ;
-                collide_segments(TestSegment, S2, _)
-            )
+        % Either the point must be colinear, or we must be on the same side of
+        % all three segments.
+        (
+            Side1 = geometry.segment.colinear
+        ;
+            Side2 = geometry.segment.colinear
+        ;
+            Side3 = geometry.segment.colinear
+        ;
+            Side1 = Side2,
+            Side2 = Side3
         )
     ),
     (translate(Point, TriangleIn, TriangleOut) :-

--- a/vector.vector2.m
+++ b/vector.vector2.m
@@ -26,6 +26,10 @@
 
 %------------------------------------------------------------------------------%
 
+:- func cross(vector2, vector2) = float.
+
+%------------------------------------------------------------------------------%
+
 :- func (vector2::in) + (vector2::in) = (vector2::uo) is det.
 :- func (vector2::in) - (vector2::in) = (vector2::uo) is det.
 :- func (vector2::in) * (vector2::in) = (vector2::uo) is det.
@@ -117,6 +121,10 @@ get_y(V) = V ^ y.
 
 %------------------------------------------------------------------------------%
 
+cross(vector(X1, Y1), vector(X2, Y2)) = (X1 * Y2) - (Y1 * X2).
+
+%------------------------------------------------------------------------------%
+
 (vector(X1, Y1)) + (vector(X2, Y2)) = (vector(X1+X2, Y1+Y2)).
 (vector(X1, Y1)) - (vector(X2, Y2)) = (vector(X1-X2, Y1-Y2)).
 (vector(X1, Y1)) * (vector(X2, Y2)) = (vector(X1*X2, Y1*Y2)).