Author Topic: point in triangle  (Read 10256 times)

0 Members and 1 Guest are viewing this topic.

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 7096
  • AKA Daniel
point in triangle
« on: December 22, 2009, 08:23:41 AM »
Code: [Select]
 static void ArxPntInTri_getit(void)
  {
    ads_point ads_testpnt;
    AcGePoint3d a,b,c,p;
  
    if(acedGetPoint(NULL,_T("\nPick Point to test: "),ads_testpnt) != RTNORM)
    {
      PRNTERR
      return;
    }

    p = asPnt3d(ads_testpnt);
    AcDbDatabase* pDb = acdbHostApplicationServices()->workingDatabase();
    AcDbBlockTableRecordPointer pBlockTableRecord(pDb->currentSpaceId(),kForRead);
    TRYRETVOID (pBlockTableRecord.openStatus());
    AcDbBlockTableRecordIterator* pIter;
    TRYRETVOID (pBlockTableRecord->newIterator( pIter ))
    
    for (pIter->start();!pIter->done();pIter->step())
    {
      AcDbObjectId entId;
      TRYMSG(pIter->getEntityId(entId));
      AcDbEntityPointer pEnt(entId,AcDb::kForRead);
      AcDbFace* pFace = AcDbFace::cast(pEnt);
      if(pFace)
      {
        TRYMSG(pFace->getVertexAt(0,a));
        TRYMSG(pFace->getVertexAt(1,b));
        TRYMSG(pFace->getVertexAt(2,c));

        if(isInTriangle(AcGePoint2d(a.x,a.y),AcGePoint2d(b.x,b.y),
                        AcGePoint2d(c.x,c.y),AcGePoint2d(p.x,p.y)))
        {
          TRYMSG(pFace->upgradeOpen());
          TRYMSG(pFace->setColorIndex(1));
        }
      }
    }
    delete pIter;
  }

  //http://www.blackpawn.com/texts/pointinpoly/default.html
  static bool isInTriangle(const AcGePoint2d &a,
                                 const AcGePoint2d &b,
                                 const AcGePoint2d &c,
                                 const AcGePoint2d &p)
  {
    AcGeVector2d v0 = c-a;
    AcGeVector2d v1 = b-a;
    AcGeVector2d v2 = p-a;
    double  dot00 = v0.dotProduct(v0);
    double  dot01 = v0.dotProduct(v1);
    double  dot02 = v0.dotProduct(v2);
    double  dot11 = v1.dotProduct(v1);
    double  dot12 = v1.dotProduct(v2);
    double invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
    double  u = (dot11 * dot02 - dot01 * dot12) * invDenom;
    double  v = (dot00 * dot12 - dot01 * dot02) * invDenom;
    return (u > 0) && (v > 0) && (u + v < 1);
  }

fixed leak
« Last Edit: February 06, 2010, 04:04:28 AM by Daniel »
Retired

MickD

  • Gator
  • Posts: 3498
  • (x-in)->[process]->(y-out)
Re: point in triangle
« Reply #1 on: December 22, 2009, 03:31:06 PM »
Nice and neat Dan!
As you are only passing in x & y coord's the function relies on the face not being perp to world I'm guessing, maybe a test is requied? or is that covered by a fuzz factor?

You have quite a few macros going there, care to share :)
You don't see too many macros in C++ as it's percieved to not be 'pure' but they can sure save a lot of typing ;)
Forth is like the Tao: it is a Way, and is realized when followed.
Its fragility is its strength; its simplicity is its direction - Michael Ham

"First, solve the problem. Then, write the code." John Johnson

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 7096
  • AKA Daniel
Re: point in triangle
« Reply #2 on: December 22, 2009, 06:02:27 PM »
You're Right! I had a request to write a routine that would find the triangle that enclosed a point. Since the Delaunay triangle algorithm that create the triangles only used X & Y to calculate the circumcircle, I thought I would only use X & Y.. or is my thinking flawed?   :|

It's the same Macros from this thread  http://www.theswamp.org/index.php?topic=28170.0
I know, I know Bjarne Stroustrup would have a Danish meatball, but I can't tell you how many times these little gems of saved me from digging through tons of code to find a bug.  8-)

Code: [Select]
//returns ES
#define TRYRETES(statement)    { Acad::ErrorStatus st = (statement); if (st != Acad::eOk){\
  acutPrintf(_T("\nError: Line %ld [%s]\nIn function %s"),\
  __LINE__, acadErrorStatusText(st),_T(__FUNCTION__)); return st;}}

// returns void
#define TRYRETVOID(statement)  { Acad::ErrorStatus st = (statement); if (st != Acad::eOk){\
  acutPrintf(_T("\nError: Line %ld [%s]\nIn function %s"),\
  __LINE__, acadErrorStatusText(st),_T(__FUNCTION__)); return;}}

// only prints es message
#define TRYMSG(statement)      { Acad::ErrorStatus st = (statement); if (st != Acad::eOk){\
  acutPrintf(_T("\nError: Line %ld [%s]\nIn function %s"),\
  __LINE__, acadErrorStatusText(st),_T(__FUNCTION__));}}

#define PRNTERR acutPrintf(_T("\nFail %s,Line %ld: ") ,_T(__FUNCTION__), __LINE__ );
Retired

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: point in triangle
« Reply #3 on: December 22, 2009, 06:31:43 PM »
OT a little.

Dan,
In your Capture.png : there is an area bottom left which is NOT triangulated. ??

appears to have 3 boundarys missing
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

--> Donate to theSwamp<--

MickD

  • Gator
  • Posts: 3498
  • (x-in)->[process]->(y-out)
Re: point in triangle
« Reply #4 on: December 22, 2009, 06:46:46 PM »
Thanks for the macros, almost forgot that thread :)

...I thought I would only use X & Y.. or is my thinking flawed?   :|

It should be fine as long as you are working in world coord's (world ucs) but even then I would do a check for colinear edges just in case. Take topology for example, you could encounter a shear cliff face which may be perpendicular to world. A slim chance but you never know :)

Forth is like the Tao: it is a Way, and is realized when followed.
Its fragility is its strength; its simplicity is its direction - Michael Ham

"First, solve the problem. Then, write the code." John Johnson

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 7096
  • AKA Daniel
Re: point in triangle
« Reply #5 on: December 22, 2009, 08:27:52 PM »
OT a little.

Dan,
In your Capture.png : there is an area bottom left which is NOT triangulated. ??

appears to have 3 boundarys missing

That's my goof, I had erased those. :whistle:
Retired

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 7096
  • AKA Daniel
Re: point in triangle
« Reply #6 on: December 22, 2009, 08:47:17 PM »
Thanks for the macros, almost forgot that thread :)

You're welcome, I guess I should have removed the macros before I posted, I normally do.

It should be fine as long as you are working in world coord's (world ucs) but even then I would do a check for colinear edges just in case. Take topology for example, you could encounter a shear cliff face which may be perpendicular to world. A slim chance but you never know :)


Ah good point.  :-)
Retired

frtfff

  • Bull Frog
  • Posts: 229
Re: point in triangle
« Reply #7 on: December 22, 2009, 08:51:07 PM »
Crazy code.How do you know this ?

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 7096
  • AKA Daniel
Re: point in triangle
« Reply #8 on: December 22, 2009, 09:03:04 PM »
Crazy code.How do you know this ?

Cause I'm a wild and crazy guy  :laugh:

Retired

pkohut

  • Guest
Re: point in triangle
« Reply #9 on: February 05, 2010, 05:26:26 PM »
It's the same Macros from this thread  http://www.theswamp.org/index.php?topic=28170.0
I know, I know Bjarne Stroustrup would have a Danish meatball, but I can't tell you how many times these little gems of saved me from digging through tons of code to find a bug.  8-)

I'm in the "Don't like macros" camp.  Whenever your thinking of writing a macro for compile time
substitution you'd probably be better served making it an inline function.

Beside the issues that Stroustrup, Meyers, Schildt, and company mention, you can not easily
debug function macros or step into them while debugging.

Also, there are 3 macros defined, TRYRETES, TRYRETVOID, and TRYMSG.  Each is basically
the same (the second and third are).  To avoid any mental gymnastics, I'd suggest just
settling on one, that being the first.  Because the macro is inlined, the return st in the first
macro will simply be compiled away or become a simple register modification.

Inline function alternative -
Code: [Select]
inline Acad::ErrorStatus EsCheck(Acad::ErrorStatus es)
{
  if(es != Acad::eOk) {
    acutPrintf(_T("\nError: Line %ld [%s]\nIn function %s"),
            __LINE__, acadErrorStatusText(es), _T(__FUNCTION__));
  }
  return es;
}


It's Alive!

  • Retired
  • Needs a day job
  • Posts: 7096
  • AKA Daniel
Re: point in triangle
« Reply #10 on: February 05, 2010, 06:34:07 PM »
Hi Paul,

I was thinking about changing those to inline functions, but I had the impression that they behaved differently.
Question, Will your example actually return out of the function? Or just return  another copy of an error status?
My goal is to test and if the test fails, print a message then exit the function. (without using exceptions)
Retired

pkohut

  • Guest
Re: point in triangle
« Reply #11 on: February 05, 2010, 07:39:32 PM »
They do behave differently, more to the point, the inlined function behaves as
expected.  Macros on the otherhand can have wierd side effects that can be
hard to track down.

It will return a copy of the error status.  Since Acad::ErrorStatus is an enum it
will be just a simple move of an int to a register making the value immediatedly
ready for the next operation, if it's needed.

I tested a few different implementation since I last posted and came up with
this one.  Overall it's better than the other because the print function is not
inlined, and you get encapsulation for free.  Also free is its size, because there
is no member data.

If you turn on "Assembler output" -> "Assembly with source code", you can look
at the generated code.  It's pretty interesting what a little tweek in the code
will do at build time.

Code: [Select]
struct EsChecker
{
    static Acad::ErrorStatus op(Acad::ErrorStatus es)
    {
        if(es != Acad::eOk) {
            EsPrint(es);
        }
        return es;
    }

    __declspec(noinline) static void EsPrint(Acad::ErrorStatus es)
    {
        acutPrintf(_T("\nError: Line %ld [%s]\nIn function %s"),
            __LINE__, acadErrorStatusText(es), _T(__FUNCTION__));
    }
};
Useage:
Code: [Select]
EsChecker::op(pDb->getFilename(pcszFilename));

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 7096
  • AKA Daniel
Re: point in triangle
« Reply #12 on: February 05, 2010, 07:47:25 PM »
But then I would need to test the error status again if I wanted to return out of the function on != eOk right?
Retired

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 7096
  • AKA Daniel
Re: point in triangle
« Reply #13 on: February 05, 2010, 08:05:49 PM »
I want to break out of the function when es != eOk.

in this example, the macro returns out of the function and prints an error message. When they are nested it performs a kind of stack trace.

I haven't tried, but the expansion of __FUNCTION__  elsewhere, might not give me  correct info.



« Last Edit: February 05, 2010, 08:16:19 PM by Daniel »
Retired

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 7096
  • AKA Daniel
Re: point in triangle
« Reply #14 on: February 05, 2010, 08:15:47 PM »
I guess I could just start using exceptions to unwind the stack. I was just following along with the ARX style and the macros saved typing..

What's your opinion on exceptions? I read that compilers refuse to unroll loops that are in a try catch
Retired