Weekly Challenge in Raku : Week 101 (Part 2)

Tags:

So for this task I found a neat little trick for calculating if a point is inside a triangle. If you calculate the area of the triangle it should equal the area of the three triangle made of connecting the point with each of the sides.

So I decided it was time to whip out some simple classes and write a mini DSL. Now I'd like to give a caveat with this, I'm using user defined operators which are awesome but also rather slow. Generally I would not advise using them directly in a script but instead putting them in a module that can be precompiled for faster loading.

With this in mind lets write a few tests. I'm creating three new operators p[], v[] and t[] these will create a point, a vector and a triangle object. Here's the tests which should hopefully make some sense :

#| Run tests
multi sub MAIN("test") {
  use Test;
  isa-ok( p[2,3], Point, "Point Creation OK" ); 
  isa-ok( v[p[0,0], p[2,2]], Vector, "Vector Creation OK" );
  isa-ok( t[p[0,0], p[0,3], p[4,0]], Triangle, "Triangle Creation OK" );
  is( v[p[0,0], p[3,4]].len, 5, "Vector Length works" );
  is( t[p[0,0], p[0,3], p[4,0]].area, 6, "Triangle Area works" );
}

Note I've also added a len and area method for the Vector and Triangle as I'm going to need these.

The Point method and operator are simple enough :

class Point {
  has Rat() $.x;
  has Rat() $.y;
}

sub circumfix:<p[ ]>( *@ (Rat() $x, Rat() $y) ) {
  Point.new( :$x, :$y );
}

The Vector object just takes two points and we include the len method (with use of ² which is great).

class Vector {
  has Point $.p1;
  has Point $.p2;

  method len() {
    ( ($.p1.x - $.p2.x)² + ($.p1.y - $.p2.y)² ).sqrt;
  }
}

sub circumfix:<v[ ]>( *@ (Point $p1, Point $p2) ) {
    Vector.new( :$p1, :$p2 );
}

And finally we add the Triangle object, this takes three points and uses Heron's Forumla to calculate the area.

class Triangle {
  has Point $.p1;
  has Point $.p2;
  has Point $.p3;

  method area() {
    my \a = v[$.p1,$.p2].len;
    my \b = v[$.p1,$.p3].len;
    my \c = v[$.p2,$.p3].len;
    my \s = (a + b + c) / 2;
    return ( s * (s - a) * (s - b) * (s - c) ).sqrt;
  }
}

sub circumfix:<t[ ]>( *@ (Point $p1, Point $p2, Point $p3 ) ) {
  Triangle.new( :$p1, :$p2, :$p3 )
}

Ok. So that's the basic tests done. Now I'll add a point-inside method to the Triangle object.

The tests for this (from the challenge).

is( t[p[0,1],p[1,0],p[2,2]].point-inside(p[0,0]), False, "Origin not in Triangle" );
is( t[p[1,1],p[-1,1],p[0,-3]].point-inside(p[0,0]), True, "Origin in Triangle" );
is( t[p[0,1],p[2,0],p[-6,0]].point-inside(p[0,0]), True, "Origin on edge test" );

The point-inside method is quite simple as I've got my DSL in place :

method point-inside( Point $pn ) {
    my $*TOLERANCE = .000001;
    return self.area =~=
    ( t[$pn, $.p1, $.p2].area +
      t[$pn, $.p1, $.p3].area +
      t[$pn, $.p2, $.p3].area );
}

One note in order to get this to work I needed to define a stub Triangle class using class Triangle {...} so I could define the t[] operator as otherwise the Triangle class doesn't know what it means.

Because I'm using Square Roots I'm having to deal with floating point number and approximate equality. I could use a different method with raycasting and vector crossing but I've done this and it works so that's cool.

Last bit make a nice MAIN sub that takes size numbers and runs the check.

#| Does the triangle made from the 6 gives points contain the origin?
multi sub MAIN( Rat() $p1x, Rat() $p1y,
                Rat() $p2x, Rat() $p2y,
                Rat() $p3x, Rat() $p3y ) {
  say t[p[$p1x,$p1y],
        p[$p2x,$p2y],
        p[$p3x,$p3y]].point-inside(p[0,0]) ?? 1 !! 0;   
}

One of the many things I love about Raku is it's ability to easily let you make a language to do what you want. Hopefully work that's being done at the moment will deal with some of the startup costs of user generated operators so we can really play about with them. But until then libraries work just fine. As it is this takes 43 seconds to run on my VM with Raku 2021.12.

If I change the p[], t[] and v[] operators to simple subroutines p(), t(), v() it takes 0.6 seconds... So I guess that's the version I'm going to submit. Anyway, I hope you found this interesting, more soon.

Pages

Other Places