x86汇编Gift Wrapping算法出错求助：循环异常与结果混乱

Let's break down the critical bugs in your code that are causing infinite loops and incorrect convex hull results—your hunch about the cross product was spot-on, plus there are a few other key issues to address:

Core Issues Identified #

1. Incorrect Cross Product Calculation & Logic Reversal #

Your cross product uses the wrong vector combinations and has inverted conditional logic:

• You calculated (Q-I) × (I-P) instead of the required (PQ) × (PI) (where PQ = Q-P and PI = I-P) to determine relative point positions.
• Your condition jl notcandidate skips updating the candidate when the cross product is negative, but the correct logic is: a positive cross product means point I is to the left of PQ, so we should update the candidate to I.

2. Bad Initial Candidate Setup #

You initialized the candidate rcx to the current point rax (P itself), which leads to invalid zero-vector cross product calculations on the first iteration.

3. Missing Collinear Point Handling #

When points are collinear (cross product = 0), you didn't check which point is farther from P—this leads to choosing incorrect convex hull vertices.

4. Unhandled Self-Comparison #

You didn't skip comparing the current point P to itself during the point traversal, which wastes cycles and can introduce edge-case errors.

Corrected Assembly Code (Jarvis March Section) #

Here's the fixed core algorithm, with comments explaining each change:

extern printf

global main

%DEFINE NUM_POINTS 20
%DEFINE MAX_X 255
%DEFINE MAX_Y 255

section .data
fmt_printf: db "Added index: %d", 10, 0 ; Add missing printf format string

section .bss
coordx: resw NUM_POINTS
coordy: resw NUM_POINTS
enveloppe: resw NUM_POINTS
sizeEnveloppe: resb 1
randnum: resw 1
minpoint: resw 1

section .text
main:
; --- [Point generation code remains unchanged] ---

; Trouver le point le plus à gauche
mov rbx, 0
mov word[minpoint], bx
inc rbx
minAlgo:
    movzx rcx, word[minpoint]
    movzx rax, word[coordx+rcx*2]
    cmp ax, word[coordx+rbx*2]
    jb lower
    mov rax, rbx
    mov word[minpoint], ax
lower:
    inc rbx
    cmp rbx, NUM_POINTS
    jb minAlgo

; Marche de Jarvis
; rax = Point actuel (P)
; rbx = Index actuel de l'enveloppe
; rcx = Candidat pour le prochain point (Q)
movzx rax, word[minpoint]
mov rbx, 0
; Initialize Q to a point different from P
mov rcx, 0
cmp cx, ax
je init_next_candidate
jmp jarvis_start
init_next_candidate:
mov rcx, 1
jarvis_start:
jarvis:
    ; Ajouter le point actuel à l'enveloppe
    mov word[enveloppe+rbx*2], ax
    
    ; Debug print (optional)
    push rax
    mov rdi, fmt_printf
    mov si, word[enveloppe+rbx*2]
    mov rax, 0
    call printf
    pop rax

    inc rbx
    mov rdx, rax ; Save current P in rdx for the entire traversal

    ; Parcourir tous les points pour trouver le prochain Q
    mov rbx, 0
parcoursPoints:
    cmp bx, dx ; Skip comparing P to itself
    je skip_current_point

    ; Calculate correct cross product
    mov r8w, word[coordx+rdx*2]   ; xP
    mov r9w, word[coordy+rdx*2]   ; yP
    mov r10w, word[coordx+rcx*2]  ; xQ
    mov r11w, word[coordy+rcx*2]  ; yQ
    mov r12w, word[coordx+rbx*2]  ; xI
    mov r13w, word[coordy+rbx*2]  ; yI

    ; Vectors PQ = Q-P, PI = I-P
    sub r10w, r8w
    sub r11w, r9w
    sub r12w, r8w
    sub r13w, r9w

    ; Cross product: PQ × PI = (xQ-xP)*(yI-yP) - (yQ-yP)*(xI-xP)
    movzx rax, r10w
    imul rax, r13w
    movzx rsi, r11w
    imul rsi, r12w
    sub rax, rsi ; rax holds the cross product value

    cmp rax, 0
    jg update_candidate ; Positive cross product: I is left of PQ → update Q to I
    je check_distance ; Collinear points: pick the farther one
    jmp skip_current_point

check_distance:
    ; Compare squared distances to avoid floating-point ops
    ; PQ² = (xQ-xP)² + (yQ-yP)²
    movzx rax, r10w
    imul rax, rax
    movzx rsi, r11w
    imul rsi, rsi
    add rax, rsi

    ; PI² = (xI-xP)² + (yI-yP)²
    movzx rdi, r12w
    imul rdi, rdi
    movzx r8, r13w
    imul r8, r8
    add rdi, r8

    cmp rdi, rax
    jg update_candidate ; I is farther than Q → update Q to I
    jmp skip_current_point

update_candidate:
    mov rcx, rbx ; Set Q to current I

skip_current_point:
    inc rbx
    cmp rbx, NUM_POINTS
    jb parcoursPoints

    ; Update P to the new candidate Q for next iteration
    mov rax, rcx

    ; Terminate when we return to the starting point
    cmp ax, word[enveloppe]
    jne jarvis

; Update the convex hull size
mov byte[sizeEnveloppe], bl

; Clean exit
mov    rax, 60         
mov    rdi, 0
syscall

ret

Key Fixes Explained #

1. Correct Cross Product:
   • Uses vectors PQ (from P to candidate Q) and PI (from P to current point I) to calculate the cross product. A positive value means I is positioned counterclockwise from PQ, so we update the candidate.
2. Valid Initial Candidate:
   • Ensures the first candidate Q is not the same as the starting point P, avoiding invalid zero-vector calculations.
3. Collinear Point Handling:
   • Compares squared distances (to avoid slow square root operations) when points are collinear, selecting the farthest point from P to maintain correct convex hull vertices.
4. Skip Self-Comparison:
   • Skips checking the current point P against itself, preventing unnecessary computations and edge-case errors.
5. Missing Format String:
   • Added the fmt_printf definition in .data to fix crashes from invalid printf calls.

内容的提问来源于stack exchange，提问作者Chachoune963