Мирослав обнови решението на 18.11.2018 22:02 (преди 9 месеца)
+package main
+
+import (
+ "math"
+
+ "github.com/fmi/go-homework/geom"
+)
+
+const eps float64 = 1e-6
+
+type Triangle struct {
+ a, b, c geom.Vector
+}
+
+func NewTriangle(a, b, c geom.Vector) Triangle {
+ return Triangle{a: a, b: b, c: c}
+}
+
+func (t Triangle) Intersect(ray geom.Ray) bool {
+ normal := t.getNormal()
+ n := dot(normal, ray.Direction)
+ if math.Abs(n) < eps {
+ // ray is parallel to the plane
+ return false
+ }
+
+ origDist := dot(normal, t.a)
+ correction := -(dot(normal, ray.Origin) + origDist) / n
+ if correction < 0 {
+ // ray either starts before the triangle with positive, or
+ // behind the triangle with negative direction
+ return false
+ }
+
+ intersectionPoint := sum(ray.Origin, vecXnum(ray.Direction, correction))
+ return t.checkIntersectionPoint(intersectionPoint, normal)
+}
+
+func (t Triangle) getNormal() geom.Vector {
+ ba, ca := diff(t.b, t.a), diff(t.c, t.a)
+ return cross(ba, ca)
+}
+
+func (t Triangle) checkIntersectionPoint(point, planeNormal geom.Vector) bool {
+ ba := diff(t.b, t.a)
+ pa := diff(point, t.a)
+ if dot(planeNormal, cross(ba, pa)) < 0 {
+ return false
+ }
+ ac := diff(t.a, t.c)
+ pc := diff(point, t.c)
+ if dot(planeNormal, cross(ac, pc)) < 0 {
+ return false
+ }
+ cb := diff(t.c, t.b)
+ pb := diff(point, t.b)
+ if dot(planeNormal, cross(cb, pb)) < 0 {
+ return false
+ }
+ return true
+}
+
+type Quad struct {
+ a, b, c, d geom.Vector
+}
+
+func NewQuad(a, b, c, d geom.Vector) Quad {
+ return Quad{a: a, b: b, c: c, d: d}
+}
+
+func (q Quad) Intersect(ray geom.Ray) bool {
+ // all four points will be in the same plane, so
+ // plane normal could be obtained from one of the triangles
+ t := NewTriangle(q.a, q.b, q.c)
+ normal := t.getNormal()
+ n := dot(normal, ray.Direction)
+ if math.Abs(n) < eps {
+ // ray is parallel to the plane
+ return false
+ }
+
+ origDist := dot(normal, t.a)
+ correction := -(dot(normal, ray.Origin) + origDist) / n
+ if correction < 0 {
+ // ray either starts before the quad with positive, or
+ // behind the quad with negative direction
+ return false
+ }
+
+ intersectionPoint := sum(ray.Origin, vecXnum(ray.Direction, correction))
+ return q.checkIntersectionPoint(intersectionPoint, normal)
+}
+
+func (q Quad) checkIntersectionPoint(point, planeNormal geom.Vector) bool {
+ ba := diff(q.b, q.a)
+ pa := diff(point, q.a)
+ if dot(planeNormal, cross(ba, pa)) < 0 {
+ return false
+ }
+ ac := diff(q.a, q.c)
+ pc := diff(point, q.c)
+ if dot(planeNormal, cross(ac, pc)) < 0 {
+ return false
+ }
+ cd := diff(q.c, q.d)
+ pd := diff(point, q.d)
+ if dot(planeNormal, cross(cd, pd)) < 0 {
+ return false
+ }
+ db := diff(q.d, q.b)
+ pb := diff(point, q.b)
+ if dot(planeNormal, cross(db, pb)) < 0 {
+ return false
+ }
+ return true
+}
+
+type Sphere struct {
+ origin geom.Vector
+ r float64
+}
+
+func NewSphere(origin geom.Vector, r float64) Sphere {
+ return Sphere{origin: origin, r: r}
+}
+
+func (s Sphere) Intersect(ray geom.Ray) bool {
+ delta := diff(s.origin, ray.Origin)
+ rayOriginHeight := dot(delta, ray.Direction)
rayOriginHeight е особено име :D
Но всъщност пиша защото ми се струва, че тук си приел ray.Direction за единичен вектор.
+ d2 := dot(delta, delta) - rayOriginHeight*rayOriginHeight
+ if d2 > s.r {
+ return false
+ }
+ intersectHeight := math.Sqrt(s.r - d2)
+ firstIntersection, secondIntersection := rayOriginHeight-intersectHeight, rayOriginHeight+intersectHeight
+ return firstIntersection >= 0 || secondIntersection >= 0
+}
+
+func sum(a, b geom.Vector) geom.Vector {
+ return geom.NewVector(a.X+b.X, a.Y+b.Y, a.Z+b.Z)
+}
+
+func diff(a, b geom.Vector) geom.Vector {
+ return geom.NewVector(a.X-b.X, a.Y-b.Y, a.Z-b.Z)
+}
+
+func vecXnum(a geom.Vector, n float64) geom.Vector {
+ return geom.NewVector(a.X*n, a.Y*n, a.Z*n)
+}
+
+func cross(a, b geom.Vector) geom.Vector {
+ return geom.NewVector(a.Y*b.Z-a.Z*b.Y, a.Z*b.X-a.X*b.Z, a.X*b.Y-a.Y*b.X)
+}
+
+func dot(a, b geom.Vector) float64 {
+ return a.X*b.X + a.Y*b.Y + a.Z*b.Z
+}
Can I assume that in the Quad case, the sides would always be BA, AC, CD and DB ? The current solution works with this assumption. I would generalise it for both 2d figures if that's the case.
Бих ти препоръчал да си напишеш няколко теста и да видиш дали всяка фигура работа. А не да разчиташ на sample теста.
А за да ти отговоря на оригиналния въпрос - точките ще са в ред. По часовниковата стрелка или обратно, но винаги в ред.
T.e. контурът се затваря по път a-b-c-d? В моето решение за четириъгълника съм приел, че са в стандартното положение на всеки учебник по математика :Д (a-c-d-b)
Не си спомням какво правят в учебниците по математика. Но ако вземеш молив работещ в 3D пространството и чертаеш линии от точка до точка в същия ред, в който са дадени на конструктор функцията, ще имаш четириъгълник.