Metapost: union test of two paths

Metapost: union test of two paths

[Marco]

Hi,

two arbitrary paths are given. A small path and a larger path, both cycled.
How to find out if the smaller path lies completely »inside« the larger path? 

If this is too complicated, it might help if I can find out if a given point
lies inside a given cycled path.

I hope it's understandable what I want to achieve.

Marco


___________________________________________________________________________________
If your question is of interest to others as well, please add an entry to the Wiki!

maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context
webpage  : http://www.pragma-ade.nl / http://tex.aanhet.net
archive  : http://foundry.supelec.fr/projects/contextrev/
wiki     : http://contextgarden.net
___________________________________________________________________________________

Re: Metapost: union test of two paths

[Taco Hoekwater]

On 07/02/2010 07:01 PM, Marco wrote:
> Hi,
>
> two arbitrary paths are given. A small path and a larger path, both cycled.
> How to find out if the smaller path lies completely »inside« the larger path?

That is hard. The main problem is the word 'arbitrary'. An arbitrary
path does not even have to enclose anything:

   path p; p = origin--(100,100)--cycle;

> If this is too complicated, it might help if I can find out if a given point
> lies inside a given cycled path.

Even this is fairly tricky. Some important questions are:

* do your arbitrary paths selfintersect?
* are your arbitrary paths convex or concave?
* is a point *on* the path in or out?
* do you want to use nonzero or even-odd filling rules?

Best wishes,
Taco
___________________________________________________________________________________
If your question is of interest to others as well, please add an entry to the Wiki!

maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context
webpage  : http://www.pragma-ade.nl / http://tex.aanhet.net
archive  : http://foundry.supelec.fr/projects/contextrev/
wiki     : http://contextgarden.net
___________________________________________________________________________________

Re: Metapost: union test of two paths

[Taco Hoekwater]

[-- Attachment #1: Type: text/plain, Size: 678 bytes --]

On 07/03/2010 10:03 AM, Taco Hoekwater wrote:
>
>> If this is too complicated, it might help if I can find out if a given
>> point lies inside a given cycled path.
>
> Even this is fairly tricky. Some important questions are:

I thought this was a neat thing to try to write a macro for. Attached
is a test file that defines a macro inside() that takes two arguments:
a point and a cyclic path. It returns true if the point lies inside
that path, in most cases. There are lots of problems with it;
what happens to a point actually on the curve is basically undefined,
and self-intersects sometimes make it fail in interesting ways.

Anyway, perhaps it helps.

Best wishes,
Taco

[-- Attachment #2: inside.mp --]
[-- Type: text/plain, Size: 1783 bytes --]


def inside(expr j, p) =
  begingroup
  save n;
  hide(
  save done, L, P, t, bottom, top;
  boolean done;
  path L,P;
  numeric t[];
  pair bottom, top;
  bottom = llcorner p;
  top = urcorner p;
  P := p;
  n := 0;
  if (xpart j <= xpart bottom) or (xpart j >= xpart top) 
    or (ypart j <= ypart bottom) or (ypart j >= ypart top):
  else:
    L := j--(xpart j, ((ypart bottom)-100));
    done := false;
    forever:
     (t[n],whatever) = L intersectiontimes P;
      if (t[n]<0) and (n>0) :  % find upward match
        P := reverse P;
        numeric t[];
        L := j--(xpart j, ((ypart bottom)-100));
        forever:
          (t[n],whatever) = L intersectiontimes P;
          exitif t[n]<0;
          L := subpath (t[n]+epsilon, length L) of L;
          n := n + 1;
        endfor;
        done := true;
      fi
      exitif done;
      L := subpath (t[n]+epsilon,length L) of L;
      n := n + 1;
    endfor; 
  fi )
if (n>1) and (not odd n): true else: false fi
endgroup
enddef;

beginfig(1);
path P;
% P:= (fullcircle scaled 20) shifted (20,20);
% P:= (0,10){down}..(10,10){up} .. (30,10){down} .. (20,10){up}..cycle;
% P := unitsquare scaled 10 rotated 30 shifted (20,10);
% P := (10,10){down}..(30,10){up} .. (0,10){down} .. (20,10){up}..cycle;
P := (0,10){down}..(10,0){right}..(30,5){up}..
    (20,10){up}..(30,15){up}..(20,20){left}..cycle;
draw P withcolor red;

nx := 100;
ny := 100;
pair endgrid;
endgrid := (30,30);
pickup pencircle xscaled (xpart endgrid/nx) yscaled (ypart endgrid/ny);
pair J;

for k = 1 upto nx:
 for l = 1 upto ny:
  J := (k/nx*xpart endgrid,l/ny*ypart endgrid);
  if inside(J,P):
     drawdot J withcolor green;
  else:
     drawdot J withcolor blue;
  fi
 endfor;
endfor;
currentpicture := currentpicture scaled 10;

endfig;
end.




[-- Attachment #3: Type: text/plain, Size: 486 bytes --]

___________________________________________________________________________________
If your question is of interest to others as well, please add an entry to the Wiki!

maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context
webpage  : http://www.pragma-ade.nl / http://tex.aanhet.net
archive  : http://foundry.supelec.fr/projects/contextrev/
wiki     : http://contextgarden.net
___________________________________________________________________________________

Re: Metapost: union test of two paths

[Alan BRASLAU]

On Saturday 03 July 2010 10:03:32 Taco Hoekwater wrote:
> On 07/02/2010 07:01 PM, Marco wrote:
> > Hi,
> > 
> > two arbitrary paths are given. A small path and a larger path, both
> > cycled. How to find out if the smaller path lies completely »inside« the
> > larger path?
> 
> That is hard. The main problem is the word 'arbitrary'. An arbitrary
> path does not even have to enclose anything:
> 
>    path p; p = origin--(100,100)--cycle;
> 
> > If this is too complicated, it might help if I can find out if a given
> > point lies inside a given cycled path.
> 
> Even this is fairly tricky. Some important questions are:
> 
> * do your arbitrary paths selfintersect?
> * are your arbitrary paths convex or concave?
> * is a point *on* the path in or out?
> * do you want to use nonzero or even-odd filling rules?
> 
> Best wishes,
> Taco

OK, this is off-topic (and not very useful as an answer)...
but is something to think about:

``posito tendendum esse a puncto ad punctum, licet nihil ultra iter 
determinat, via eligetur maxime facilis seu brevissima;''

Leibniz: De rerum originatione radicali, 1697

``suppose that we are to go from one point to another, without being directed 
to follow a particular path, the path chosen will be the easiest or the 
shortest one;''


So, in a Cartesian space, if the energy cost of a kink is low, than
>    path p; p := origin--(100,100)--cycle;
should be a straight line running back on itself.
Indeed, this is what metapost produces.

Now try p := origin..(100,100)..cycle;

Alan
___________________________________________________________________________________
If your question is of interest to others as well, please add an entry to the Wiki!

maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context
webpage  : http://www.pragma-ade.nl / http://tex.aanhet.net
archive  : http://foundry.supelec.fr/projects/contextrev/
wiki     : http://contextgarden.net
___________________________________________________________________________________

Re: Metapost: union test of two paths

[Taco Hoekwater]

[-- Attachment #1: Type: text/plain, Size: 880 bytes --]

On 07/03/2010 12:19 PM, Taco Hoekwater wrote:
> On 07/03/2010 10:03 AM, Taco Hoekwater wrote:
>>
>>> If this is too complicated, it might help if I can find out if a given
>>> point lies inside a given cycled path.
>>
>> Even this is fairly tricky. Some important questions are:
>
> I thought this was a neat thing to try to write a macro for. Attached
> is a test file that defines a macro inside() that takes two arguments:
> a point and a cyclic path. It returns true if the point lies inside
> that path, in most cases. There are lots of problems with it;
> what happens to a point actually on the curve is basically undefined,
> and self-intersects sometimes make it fail in interesting ways.

Here is a somewhat smarter version of the same macro. This one
seems ok at first glance (extensive testing will probably show
border cases that are not covered).

Best wishes,
Taco

[-- Attachment #2: inside2.mp --]
[-- Type: text/plain, Size: 1782 bytes --]


def inside(expr j, p) =
  begingroup
  save n;
  hide(
  save L, P, t, tt,bottom, top;
  boolean abort;
  path L,P;
  pair bottom, top;
  bottom = llcorner p;
  top = urcorner p;
  P := p;
  n := 0;
  if (xpart j <= xpart bottom) or (xpart j >= xpart top) 
    or (ypart j <= ypart bottom) or (ypart j >= ypart top):
  else:
    P := subpath (epsilon,(length P)) of P;
    L := j--(xpart j, -infinity);
    forever:
      t := xpart (P intersectiontimes L);
      exitif t<0;
      tt := t;
      forever:
        exitif t<0;
        exitif not (xpart direction t of P = 0);
 	L := L shifted (-epsilon,0); 
        t := xpart (P intersectiontimes L);
        exitif t<0;
        if t<tt: 
   	  L := L shifted (3epsilon,0); 
          t := xpart (P intersectiontimes L);
        fi
      endfor
      exitif t < 0;
      n := n + 1;
      P := subpath (t+epsilon,(length P)) of P;
    endfor; 
  fi )
if (n>0) and (odd n): true else: false fi
endgroup
enddef;

beginfig(1);
path P;
 P:= (fullcircle scaled 20) shifted (20,20);
 P:= (0,10){down}..(10,10){up} .. (30,10){down} .. (20,10){up}..cycle;
 P := ((0,0)--(10,0)--(10,10)--(0,10)--cycle) rotated 130 shifted (20,10);
% P := (10,10){down}..(30,10){up} .. (0,10){down} .. (20,10){up}..cycle;
% P := ((25,10){down}..(10,0){right}..(30,5){up}..
%   (20,10){up}..(30,15){up}..(20,20){left}..cycle) shifted (0,5);

nx := 50;
ny := 40;
pair endgrid;
endgrid := (40,30);
pickup pencircle xscaled (xpart endgrid/nx) yscaled (ypart endgrid/ny);
pair J;

for k = 1 upto nx:
 for l = 1 upto ny:
  J := (k/nx*xpart endgrid,l/ny*ypart endgrid);
  if inside(J,P):
     drawdot J withcolor green;
  else:
     drawdot J withcolor blue;
  fi
 endfor;
endfor;
draw P withcolor red;
currentpicture := currentpicture scaled 10;

endfig;
end.




[-- Attachment #3: Type: text/plain, Size: 486 bytes --]

___________________________________________________________________________________
If your question is of interest to others as well, please add an entry to the Wiki!

maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context
webpage  : http://www.pragma-ade.nl / http://tex.aanhet.net
archive  : http://foundry.supelec.fr/projects/contextrev/
wiki     : http://contextgarden.net
___________________________________________________________________________________

Re: Metapost: union test of two paths

[Taco Hoekwater]

On 07/03/2010 12:33 PM, Alan BRASLAU wrote:
>
>
> So, in a Cartesian space, if the energy cost of a kink is low, than
>>     path p; p := origin--(100,100)--cycle;
> should be a straight line running back on itself.
> Indeed, this is what metapost produces.
>
> Now try p := origin..(100,100)..cycle;

The .. operator makes the cost of a kink infinity.

Best wishes,
Taco
___________________________________________________________________________________
If your question is of interest to others as well, please add an entry to the Wiki!

maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context
webpage  : http://www.pragma-ade.nl / http://tex.aanhet.net
archive  : http://foundry.supelec.fr/projects/contextrev/
wiki     : http://contextgarden.net
___________________________________________________________________________________

Re: Metapost: union test of two paths

[Marco]

Hi Taco,

many thanks for your effort! I'm just having a look at your code.

Kind regards
Marco


___________________________________________________________________________________
If your question is of interest to others as well, please add an entry to the Wiki!

maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context
webpage  : http://www.pragma-ade.nl / http://tex.aanhet.net
archive  : http://foundry.supelec.fr/projects/contextrev/
wiki     : http://contextgarden.net
___________________________________________________________________________________

Re: Metapost: union test of two paths

[Marco]

Hi Taco!

> That is hard. The main problem is the word 'arbitrary'.
Sorry, I was too general. The paths are a outline of a relatively
simple shape (so border cases should rarely occur) with area >0k, not
selfintersecting.

> * is a point *on* the path in or out?
It doesn't matter in my case.

> This one seems ok at first glance (extensive testing will probably
> show border cases that are not covered).
I did run some tests. It works like a charm, exactly the way I expect.
Thank you very much for this piece of code. If I got it right, your
basic idea is to count the times the point inside the boundingbox
crosses the border of the shape. And the subpath stuff results of the
fact that intersectionpoint/times returns only one intersection even if
there are more. Very smart.


I'm grateful for your support.

Kind regards
Marco


___________________________________________________________________________________
If your question is of interest to others as well, please add an entry to the Wiki!

maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context
webpage  : http://www.pragma-ade.nl / http://tex.aanhet.net
archive  : http://foundry.supelec.fr/projects/contextrev/
wiki     : http://contextgarden.net
___________________________________________________________________________________

Re: Metapost: union test of two paths

[Taco Hoekwater]

On 07/04/2010 01:11 AM, Marco wrote:
> Hi Taco!
>
>> That is hard. The main problem is the word 'arbitrary'.
> Sorry, I was too general. The paths are a outline of a relatively
> simple shape (so border cases should rarely occur) with area>0k, not
> selfintersecting.

That helps. First test whether the paths insersect, that is easy.
If they do insersect, they may still be touching each other only.
Still, perhaps that is good enough (depends on what you want to do).

But if they do not intersect, then you know for sure that either one
is inside the other, or they are totally disjunct. In the fully
overlapping case, the boundingboxes of the two paths will most
likely likewise overlap perfectly, and that could be good enough
for you.

Alternatively, if you are certain that both the paths are convex
hulls, then just testing for the boundingboxes could be good enough
in practice.

When the two paths P and Q touch at time A, you could test whether the
two  points that are time(A+epsilon) and time(A-epsilon) are both
inside() both paths.

But the hardest thing with doing all this in metapost is that you
cannot trust metaposts results in the mathematical sense: rounding
errors creep in easily in the internal routines, which is one the
problems I hope to solve with metapost 2.

Best wishes,
Taco
___________________________________________________________________________________
If your question is of interest to others as well, please add an entry to the Wiki!

maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context
webpage  : http://www.pragma-ade.nl / http://tex.aanhet.net
archive  : http://foundry.supelec.fr/projects/contextrev/
wiki     : http://contextgarden.net
___________________________________________________________________________________

Re: Metapost: union test of two paths

[Marco]

Thanks for the hints.

> But the hardest thing with doing all this in metapost is that you
> cannot trust metaposts results in the mathematical sense: rounding
> errors creep in easily in the internal routines, which is one the
> problems I hope to solve with metapost 2.
When is MP2 expected to be released? Is there a timeline or alike?

Kind regards
Marco


___________________________________________________________________________________
If your question is of interest to others as well, please add an entry to the Wiki!

maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context
webpage  : http://www.pragma-ade.nl / http://tex.aanhet.net
archive  : http://foundry.supelec.fr/projects/contextrev/
wiki     : http://contextgarden.net
___________________________________________________________________________________

Re: Metapost: union test of two paths

[Taco Hoekwater]

On 07/04/2010 10:09 AM, Marco wrote:
> Thanks for the hints.
>
>> But the hardest thing with doing all this in metapost is that you
>> cannot trust metaposts results in the mathematical sense: rounding
>> errors creep in easily in the internal routines, which is one the
>> problems I hope to solve with metapost 2.
> When is MP2 expected to be released? Is there a timeline or alike?

End of this summer, I hope. But I am constantly juggling between
mp|luatex|context and commercial work, so deadlines are far from
fixed.

Best wishes,
Tacfo

___________________________________________________________________________________
If your question is of interest to others as well, please add an entry to the Wiki!

maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context
webpage  : http://www.pragma-ade.nl / http://tex.aanhet.net
archive  : http://foundry.supelec.fr/projects/contextrev/
wiki     : http://contextgarden.net
___________________________________________________________________________________