3
$\begingroup$

Now we have a compact closed simple smooth curve in $\Bbb R^2$ and the curve's bounding box is known. But the curve is given implicitly by a signed distance function $f(x, y)$. Note that we don't have a global formula for $f(x, y)$, but we can sample $f(x, y)$ at arbitrary points.

definition of signed distance function can be found here

The question is: Given a point $P$, how can we find all the points on the curve whose tangent line pass through $P$. Can you give me an algorithm for this process?

Here is an illustration.

enter image description here

Points on the red curve whose tangent line pass through $P$ are $A, B, C, D$.

$\endgroup$
4
  • $\begingroup$ what is the parametrization of that red circuit? $\endgroup$
    – janmarqz
    Jul 12, 2022 at 15:50
  • $\begingroup$ @janmarqz : We don't know its parametrization, but only the signed distance function. $\endgroup$
    – Andy
    Jul 13, 2022 at 6:48
  • $\begingroup$ did you see that, locally, around the marked points, you can parametrize the curve as an arc of a circle? $\endgroup$
    – janmarqz
    Jul 13, 2022 at 15:19
  • $\begingroup$ @janmarqz : Yes, we can do that by the implicit function theorem. But I think that tracing all points on the curve is must if we want to find all the points meeting requirements in the question. $\endgroup$
    – Andy
    Jul 14, 2022 at 1:51

1 Answer 1

1
$\begingroup$

Ideas too long for a comment.

You are assuming that the signed distance function actually calculates the distance to a smooth curve (since topologically that curve it its own boundary). If I read the linked definition correctly, the signed difference function will always be nonnegative (since the curve as a set has empty interior and is all boundary).

Sample the bounding box until you find a point where the distance function is 0 (or within $\epsilon$ of $0$). Then by sampling near that point for more points on the curve you can essentially trace out the curve as a sequence of close together points at distance near $0$.

With that data you can calculate slopes of short secants and look for lines that pass through $P$.

Whether this is numerically stable or efficient depends on the complexity of the curve. You will have trouble if it's self intersecting.

$\endgroup$
2
  • $\begingroup$ So if we want to get all the points meeting above conditions, we need to check every point on the curve in the tracing process? $\endgroup$
    – Andy
    Jul 11, 2022 at 15:44
  • $\begingroup$ I think so. You might be able to find points $A$ and $D$ by rotating a line through $P$ and finding out where it first and last meets the curve. The intermediate tangents would be harder to pin down. And an inflection point is possible too. $\endgroup$ Jul 11, 2022 at 15:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .