Metapost: union test of two paths
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
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
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
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
Hi Taco, many thanks for your effort! I'm just having a look at your code. Kind regards 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
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
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
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
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
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
participants (3)
-
Alan BRASLAU -
Marco -
Taco Hoekwater