Самый быстрый способ удалить дубликаты точек на краях многоугольника?

Question

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

type 
    TPoint = array [1 .. 2] of Integer; 
    TPointArray = array of TPoint; 

Точки на краях, приведены в часовой стрелке порядке, и я хочу, чтобы удалить промежуточные точки (отмеченные красным цветом).

Например, при любых непрерывных трех точках A, B, C, если B находится точно на линии между A и C, тогда B можно безопасно удалить.

Как я могу сделать это быстро и эффективно?

Мой Psedu-код:

procedure RemovePoints(var pt: TPointArray); 
var 
    i, j, sz, k, u: integer; 
    xoffset, yoffset: integer; 
begin 
    sz := High(pt); 
    i := 0; 
    while (True) do 
    begin 
    Inc(i); 
    // points represent array index, so can't be negative, 
    // we use -1 to mark deletion 
    if (pt[i][1] = -1) then continue; 
    if (i = 0) then 
    begin 
     break; // finish a loop 
    end; 
    j := i + 1; 
    if (j > sz) then 
    begin 
     j := 0; 
    end; 
    k := j + 1; 
    if (k > sz) then 
    begin 
     k := 0; 
    end; 
    if ((pt[i][1] - pt[j][1] = pt[j][1] - pt[k][1]) and ((pt[i][2] - pt[j][2] = pt[j][2] - pt[k][2]))) then 
    begin 
     // remove pt[j]; 
     pt[j][1] := -1; 
    end; 
    end; 
    // TODO: shrink the array to remove deleted points 
end; 

Answer 1

Прогулка по списку и рассмотрят тройки соседних точек р, д и г. определите векторы, направленные вперед pq и qr и проверьте, являются ли они коллинеарными. Если да, и если они обращены в одном направлении, отметьте точку для удаления.

На второй проход отфильтруйте отмеченные точки.

Два вектора коллинеарны, если их поперечное произведение является нулевым вектором. Перекрестное произведение векторов в плоскости имеет только одну компоненту, перпендикулярную этой плоскости. Так проверьте:

pq.x * qr.y - pq.y * qr.x == 0 

Если вы хотите, чтобы убедиться, что вы не удалить острые точки в попрошайничать, проверьте, является ли положительное скалярное произведение вектора:

pq.x * qr.x + pq.y * qr.y > 0 

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

Вот решение, которое использует вашу номенклатуру и типы. Он отслеживает, какие узлы удаляются в отдельном массиве. (Вы не можете пометить координаты с фиктивными значениями, потому что вы все еще нужны координаты нетронутыми, когда вы определяете, следует ли удалить следующий узел.)

procedure RemovePoints(var pt: TPointArray); 
Var i, j: Integer; 
    p, q, r: TPoint; 
    ax, ay: Integer; 
    bx, by: Integer; 
    del: Array of Boolean; 

begin 
    if Length(pt) > 2 then begin 
    SetLength(del, Length(pt)); 
    for i := 0 to Length(pt) - 1 do del[i] := False; 

    j := Length(pt) - 1; 
    p := pt[j - 1]; 
    q := pt[j]; 

    for i := 0 to Length(pt) - 1 do begin 
     r := pt[i]; 

     ax := q[1] - p[1]; 
     ay := q[2] - p[2]; 
     bx := r[1] - q[1]; 
     by := r[2] - q[2]; 

     if (ax*by - ay*bx = 0) and (ax*bx + ay*by > 0) then del[j] := True; 

     p := q; 
     q := r; 
     j := i; 
    end; 

    j := 0; 
    for i := 0 to Length(pt) - 1 do begin 
     if not del[i] then begin 
     pt[j] := pt[i]; 
     inc(j); 
     end; 
    end; 

    SetLength(pt, j); 
    end; 
end; 

Answer 2

Мы уже знаем, что мы можем полностью определить линию, используя наклон -перечислить уравнение. Это означает, что мы можем также однозначно определить линию с использованием наклона и одной точки, через которую проходит эта линия.

Начиная с первой точки в вашем списке точек многоугольника, вычислите наклон линии, проходящей через первую и следующую точки. Это первое значение наклона для вас. Сохраните это значение как currentSlope. Создайте newPointList для хранения новых точек ребер.Следующая:

1. Итерация через все точки, начиная с третьей точки;
2. Если наклон второй и третьей точки такое же, как currentSlope
   1. Это означает, вторую точку находится на той же линии, что и первый и третий, так что пропустить эту точку
   2. continue петлю идущие назад к шагу 1 .
3. Если наклон второй и третьей точки отличается от currentSlope
   1. это означает, что край определяется сначала вторая точка отличается от края, определяемого второй и третьей точками.
   2. Сохраните первую и вторую точку в newPointList и обновите значение currentSlope наклон между второй и третьей точками.

Когда итерация закончится, newPointList будет содержать только вершины вашего многоугольника.