Определение количества пересечений линии с многоугольником

Question

Я уже задавал этот вопрос по обмену стека обработки сигналов, но не получил никаких ответов. Ты моя единственная надежда StackOverflow. Пожалуйста, помогите, спасибо:

Как часть математического эссе, я пишу программу, которая обнаруживает пересечения линии, которая рисуется с вводимой формы.

Например, в форма ниже, многоугольник является входным изображением заданного размера. Луч был нарисован на многоугольнике, начиная с него. Как определить, сколько раз луч пересекает границу многоугольника.

Кроме того, многоугольник всегда является замкнутым многоугольником.

см. Изображение здесь:

Первоначально мне пришла в голову мысль заполнить многоугольник тем же цветом, что и граница (черный). А затем посчитайте, сколько раз луч встретился бы с черным, а затем с белым.

Моя проблема с этим методом заключается в том, что я действительно не знаю, как проследить вдоль линии и проверить каждую точку, и я предполагаю, что это было бы чрезвычайно дорогостоящим процессом для непрерывной проверки по линии.

Я сейчас использую Processing 3, но я могу использовать любое другое программное обеспечение / платформу, кроме MatLab, потому что у меня нет доступа прямо сейчас.

Answer 1

Если у вас есть бесконечная линия, которая определяется точкой P и нормализованным направлением R, и вторая бесконечная линия, которая определяется точкой Q и направлением S, то точка пересечения бесконечных линий X составляет:

alpha ... angle between Q-P and R
beta  ... angle between R and S

gamma  =  180° - alpha - beta

h  =  | Q - P | * sin(alpha)
u  =  h / sin(beta)

t  = | Q - P | * sin(gamma) / sin(beta)

t  =  dot(Q-P, (S.y, -S.x)) / dot(R, (S.y, -S.x))  =  determinant(mat2(Q-P, S)) / determinant(mat2(R, S))
u  =  dot(Q-P, (R.y, -R.x)) / dot(R, (S.y, -S.x))  =  determinant(mat2(Q-P, R)) / determinant(mat2(R, S))

X  =  P + R * t  =  Q + S * u

_{См. также найти точку пересечения двух векторов независимо из направления}

Если у вас есть инин от l1p1 до l1p2 и вторая строка от l2p1 до l2p2, тогда:

P = l1p1
Q = l2p1;
R = normalize(l1p2 - l1p1)
S = normalize(l2p2 - l2p1)

normalize вычисляет Единичный вектор вектора. Длина единичного вектора равна 1.

Поскольку линии не являются бесконечными, необходимо оценить, находится ли точка пересечения на отрезке. Вычислите длину линий и расстояния от начала залога до точки пересечения. Убедитесь, что расстояния (вычисленные с помощью Dot product ) больше> = 0 и <= длина линии. <br>В следующем

len1 = | l1p2 - l1p1 |
len2 = | l2p2 - l2p1 |

distOnL1 = dot(X - P, R);
distOnL2 = dot(X - Q, S);

intersecting = distOnL1 >= 0 AND distOnL1 <= len1 AND distOnL2 >= 0 AND distOnL2 <= len2

Это можно рассчитать с помощью PVector следующим образом:

class TIntersection {
   boolean valid = false;
   PVector point = new PVector(0.0, 0.0);
}

// Intersect 2 endless  lines
// line 1: line segment from `l1p1` to `l1p2`
// line 2: line segment from `l2p1` to `l2p2`
TIntersection Intersect(PVector l1p1, PVector l1p2, PVector l2p1, PVector l2p2) {

    PVector P = l1p1;
    PVector Q = l2p1;
    PVector R = PVector.sub(l1p2, l1p1);
    PVector S = PVector.sub(l2p2, l2p1);
    float   len1 = R.mag();
    float   len2 = S.mag();
    R.normalize();
    S.normalize();

    PVector QP  = PVector.sub(Q, P);
    PVector SNV = new PVector(S.y, -S.x);  
    TIntersection isect = new TIntersection();
    float t =  QP.dot(SNV) / R.dot(SNV); 
    isect.point = PVector.add(P, PVector.mult(R, t));

    if (!Float.isInfinite(isect.point.x) || !Float.isInfinite(isect.point.y)) {
        float distOnL1 = PVector.sub(isect.point, P).dot(R);
        float distOnL2 = PVector.sub(isect.point, Q).dot(S);
        isect.valid = distOnL1 >= 0.0 && distOnL1 <= len1 && distOnL2 >= 0.0 && distOnL2 <= len2; 
    } else {
        isect.valid = false; 
    }
    return isect;
}

Возвращаемое значение функции имеет тип TIntersection. Атрибут valid равен true, если есть пересечение и линии не параллельны. Атрибут point типа PVector является точкой пересечения, если она есть.

---

См. Пример:

<script src="https://cdnjs.cloudflare.com/ajax/libs/processing.js/1.6.6/processing.min.js"></script>
<canvas id="pjs"></canvas>
<script type="application/processing" data-processing-target="pjs">
class TIntersection {
    boolean valid = false;
    PVector point = new PVector(0.0, 0.0);
}
 
// Intersect 2 endless  lines
// line 1: line segment from `l1p1` to `l1p2`
// line 2: line segment from `l2p1` to `l2p2`
TIntersection Intersect(PVector l1p1, PVector l1p2, PVector l2p1, PVector l2p2) {
   
    PVector P = l1p1;
    PVector Q = l2p1;
    PVector R = PVector.sub(l1p2, l1p1);
    PVector S = PVector.sub(l2p2, l2p1);
    float   len1 = R.mag();
    float   len2 = S.mag();
    R.normalize();
    S.normalize();
     
    PVector QP  = PVector.sub(Q, P);
    PVector SNV = new PVector(S.y, -S.x);
     
    TIntersection isect = new TIntersection();
    float t =  QP.dot(SNV) / R.dot(SNV); 
    isect.point = PVector.add(P, PVector.mult(R, t));
     
    //if (!Float.isInfinite(isect.point.x) || !Float.isInfinite(isect.point.y)) {
        float distOnL1 = PVector.sub(isect.point, P).dot(R);
        float distOnL2 = PVector.sub(isect.point, Q).dot(S);
        isect.valid = distOnL1 >= 0.0 && distOnL1 <= len1 && distOnL2 >= 0.0 && distOnL2 <= len2; 
    //} else {
    //    isect.valid = false; 
    //}
    return isect;
}
 
ArrayList<PVector> poly;
PVector[] line_p, move;
 
void setup() {
    size(500,500);
    
    poly = new ArrayList();
    poly.add(new PVector(175, 100));
    poly.add(new PVector(175, 300));
    poly.add(new PVector(200, 300));
    poly.add(new PVector(225, 400));
    poly.add(new PVector(275, 350));
    poly.add(new PVector(275, 200));
    poly.add(new PVector(325, 200));
    poly.add(new PVector(325, 100));
    
    line_p = new PVector[2];
    line_p[0] = new PVector(150, 400);
    line_p[1] = new PVector(380, 100);
    
    move = new PVector[2];
    move[0] = new PVector(random(2)-1, random(2)-1);
    move[1] = new PVector(random(2)-1, random(2)-1);
}

void draw() {
  
    // randomize points
    for (int i=0; i < line_p.length; ++i ) {
        line_p[i] = PVector.add(line_p[i], move[i]);
        if (line_p[i].x < 50 || line_p[i].x > width-50)
            move[i].x *= -1; 
        if (line_p[i].y < 50 || line_p[i].y > height-50)
            move[i].y *= -1;    
        move[i].x = max(-1, min(1, move[i].x+random(0.2)-0.1));
        move[i].y = max(-1, min(1, move[i].y+random(0.2)-0.1));
    }
  
    // clear background
    background(0, 0, 0);
    
    stroke(255);
    fill(255, 0, 0);
    
    // draw line
    line(line_p[0].x, line_p[0].y, line_p[1].x, line_p[1].y);
    
    // draw polygon and intersections
    int intersections = 0;
    for (int i = 0; i < poly.size(); i++) {
        PVector poly_p1 = poly.get(i);
        PVector poly_p2 = poly.get((i+1) %  poly.size());
        
        line(poly_p1.x, poly_p1.y, poly_p2.x, poly_p2.y);
        
        TIntersection x = Intersect(line_p[0], line_p[1], poly_p1, poly_p2);
        if (x.valid) {
            ellipse(x.point.x, x.point.y, 10, 10);
            intersections ++;
        }
    }
    
    // draw intersection count
    fill(255);
    textSize(24);
    text("intersections: " + str(intersections), 20, 40); 
}
</script>

Answer 2

При определенных допущениях вы можете сделать это, не используя много математики для получения приблизительных точек пересечения.

Допущения:

• ваше входное изображение многоугольника нарисовано с линии сглаживания
• вы можете нарисовать линию без сглаживания (или луч)
• толщина линий составляет 1 пиксель

Возьмите изображение многоугольника, назовем это poly. Установите пороговое значение для этого изображения таким образом, чтобы фоновые пиксели были равны 0, а многоугольные пиксели отличны от нуля, скажем, 1.

Создайте пустое изображение (все значения пикселей 0) того же размера, что и poly, давайте назовем его ray. Нарисуйте на этом изображении не сглаживающий луч с ненулевыми значениями пикселей, скажем, 1.

Возьмите сумму или эти два изображения, result = poly + ray. Теперь пересечения должны иметь значение пикселя 2 в изображении result, и вы можете легко извлечь их координаты.

Здесь предполагается, что все изображения имеют один канал.