vdmedragon's blog

A little geometry
By vdmedragon, 15 years ago, In English
Condition to verify if a point C in a segment [A,B]

(C.x-A.x)*(A.y-B.y)=(C.y-A.y)*(A.x-B.x) (1)

min(A.x,B.x) <= C.x <= max(A.x,B.x) (2)
min(A.y,B.y) <= C.y <= max(A.y,B.y) (3)

I forget to check (2),(3); only remember 1. (AC if i remember)

vihrov: Another way: if we have a segment AB and a point C, then C is in AB iff AC + CB = AB.

Condition to check angle (AB,AC) <= 90.
- Using AB*AB+AC*AC>BC*BC
- Using atan2 : it may lead to error of precision (I found it during contest).

dAFTc0d3r: Easier way to check sign of cos

( AB, BC ) = | AB | * | BC | * cos( angleABC )

| AB | * | BC |  > 0 

So sign cos( angleABC ) = sign ( AB, BC ) = AB.x * BC.x + AB.y * BC.y




  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
15 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Another way: if we have a segment AB and a point C, then C is in AB iff AC + CB = AB.
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Don't do that, that leads to precision loss.
    → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Why does it? AC is not multiplication, it is the length of the segment.
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It had better been multiplication :)

        Suppose that segment lies on X axis and point is offset from segment by small value 'eps'. When one finds AC using

        sqrt(dx^2+dy^2)

        following occurs

        sqrt (large_value^2 + eps^2)

        → Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Right, I also forgot to check 2 and 3. Fixing that got me AC. Check your "Talks" btw, I sent you a message a week ago.
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Easier way to check sign of cos

( AB, BC ) = | AB | * | BC | * cos( angleABC )

| AB | * | BC |  > 0

So sign cos( angleABC ) = sign ( AB, BC ) = AB.x * BC.x + AB.y * BC.y
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
My daftdcode for solving first problem (don't write like this!):

bool belongs_good( point A, otr o )
{
    double tx, ty;
    bool uncalcx = false, uncalcy = false;

    if ( o.A.x == o.B.x )
        uncalcx = true;
    else
        tx = double( A.x - o.A.x ) / ( o.B.x - o.A.x );

    if ( o.A.y == o.B.y )
        uncalcy = true;
    else
        ty = double( A.y - o.A.y ) / ( o.B.y - o.A.y );

    if ( uncalcx )
        tx = ty;

    if ( uncalcy )
        ty = tx;

    return ( tx == ty && tx >= 0 && tx <= 1 );
}

P.S.: In problem B I use
return ( tx == ty && tx >= 0.2 && tx <= 0.8 );
because of 1/4 condition.
→ Reply