1
$\begingroup$

I have some heavy calculations that essentially takes a point in the plane as input and gives an integer as output. Points in the same region gives the same integer (think about the regions as pieces in a jigsaw (every point in completed puzzle belongs to a specific jigsaw piece), the boundaries being simple, closed curves). I've made a very simple algorithm that first finds a boundary by finding the integers of two neighboring corners of my search rectangle and divides and conquers its way to find a boundary (to within a predefined accuracy). So I find a random boundary in O(log(width)) time, where width is the width of my search rectangle. Now my naive approach is then to sort of take small steps in a circle around that point until the number changes, record that point and repeat. The problem is checking a points number is really expensive (NP-hard) and even worse my algorithm misses forkings in the boundaries. All I can find online is image processing algorithms like floodfill, where checking a point is cheap. Does algorithms like this exist? Or do you have any good ideas to make one?

$\endgroup$
  • 2
    $\begingroup$ 1. NP-hard? You sure? Sounds dubious. 2. I don't understand exactly what the problem is. Can you give a clearer statement of the problem statement? Can you give a clearer description of your algorithm and a small example of an input where it produces the wrong answer? My guess is: there's a function $f$ where, given integer coordinates $(x,y)$, $f(x,y)$ outputs the color of the point at $(x,y)$; you have a way to compute $f$, but it's very slow; the task is: given a single point $(x_0,y_0)$, find the boundary of the connected region containing $(x_0,y_0)$. Is that it? $\endgroup$ – D.W. Jul 16 '15 at 22:50
  • 1
    $\begingroup$ If that's right, what's your definition of "connected region"? Do you count points that are diagonally adjacent as adjacent/connected? Is it right that you only care about integer points, or is this a continuous problem on the full real plane? If the latter, what do you know about the shape that the boundary can take? If it can be a truly arbitrary curve, this is almost certainly unsolvable. Do you know that perhaps the boundary can be well-approximated by a cubic spline, or anything like that? Do you know that the pieces are convex? Can you give pictures of example instances? $\endgroup$ – D.W. Jul 16 '15 at 22:52
  • 2
    $\begingroup$ Welcome to Computer Science Stack Exchange. I know little of your topic, but maybe you should improve and structure the p[resentation of your question. This big block of text is kind of overwhelming. Do your closed curves intersect so that 2 curves make 3 or 4 regions. Can one be inside another? The same region give only one integer, but can two distinct regions give the same integer? In other words, is the integer characteristic of one region? Your search rectangle is the only part of the plane you are analyzing? Or can it move? And you do not seem to say what result you are looking for. $\endgroup$ – babou Jul 16 '15 at 23:04
  • $\begingroup$ The boundaries lie in the full real plane (but a good bitmap algorithms is ok). The boundaries I've traced so far seem well-approximated by cubic-splines. Regions are not convex. The point to integer function f(x,y) is indeed NP-hard, I haven't asked about this problem, because I know it to be NP-complete. My question is about efficient boundary tracing. I have uploaded tracings here: imgur.com/a/nCiRU $\endgroup$ – Lars Holm Jensen Jul 16 '15 at 23:39
  • $\begingroup$ To babou: The tracing algorithm does not need to consider regions inside other regions, only the boundaries connected to other boundaries. Two distinct regions never have the same integer. My search rectangle is static. The result I'm looking for is a full trace of the web of all the connected boundaries with a predefined resolution. $\endgroup$ – Lars Holm Jensen Jul 16 '15 at 23:39