Check è un punto (x,y) si trova tra due punti disegnati su una linea retta

Ho tracciato una linea tra due punti A(x,y)-B(x,y)
Ora ho un terzo punto C(x,y). Io voglio sapere che se C si trova sulla linea che viene tracciata tra A e B.
Voglio farlo in linguaggio java. Ho trovato un paio di risposte simili a questo. Ma, un po ‘ tutti i problemi e nessuno è perfetto.

  • Si potrebbe provare a creare un Line2D oggetto che rappresenta Un & B e l’uso contains metodo
  • y=mx+b. Trovare l’equazione della linea contiene A e B, e poi vedere se C(x,y) soddisfa l’equazione?
  • questo è quello che ho cercato, ma cosa fare quando il x2 e x1 sono le stesse float ratio = (y2 – y1) / (x2 – x1); Quindi: larghezza = x2 – x1; for(int i = 0; i < larghezza; i++) { float x = x1 + i; float y = y1 + (rapporto * i); punti.add(new Point(x,y)); }
  • puoi spiegare un po ‘ di più, io non sono bravo con la matematica. Come fare ?
  • mathsisfun.com/algebra/line-equation-2points.html o la risposta da @SeniorJD.
  • user2061477, qualsiasi soluzione che fa (solo) con gradienti fallire miseramente per linee verticali, come la sfumatura che tende a infinito. La risposta da @MrROY consentirà di bypassare questi problemi.
  • Si prega di dare un’occhiata a questa (vecchia) [COSÌ thread][1] [1]: stackoverflow.com/questions/328107/…
  • contiene restituisce sempre false per line2D

 

6 Replies
  1. 70
    if (distance(A, C) + distance(B, C) == distance(A, B))
        return true; //C is on the line.
    return false;    //C is not on the line.

    o solo:

    return distance(A, C) + distance(B, C) == distance(A, B);

    Il modo in cui funziona è piuttosto semplice. Se C si trova sul AB line, si otterrà il seguente scenario:

    A-C------B

    e, indipendentemente dal luogo in cui si trova su quella linea, dist(AC) + dist(CB) == dist(AB). In ogni altro caso, il triangolo di qualche descrizione e ‘dist(AC) + dist(CB) > dist(AB)’:

    A-----B
     \   /
      \ /
       C

    Infatti, funziona anche se C si trova sul estrapolate linea:

    C---A-------B

    a condizione che le distanze sono tenuti unsigned. La distanza dist(AB) può essere calcolato come:

      ___________________________
     /           2              2
    V (A.x - B.x)  + (A.y - B.y)

    Tenere a mente i limiti intrinseci (precisione limitata) di operazioni in virgola mobile. È possibile che potrebbe essere necessario optare per un “abbastanza vicino” test (ad esempio, meno di una parte per milione di errore) per garantire il corretto funzionamento dell’uguaglianza.

    • Il "(" preso dopo if previsto
    • Ciò presuppone che la linea è equi-distanti da A e B. ad esempio, passa tra la metà di A e B, non attraverso di essa.
    • se intendi il punto (C) è equidistante, no. L’uguaglianza terrà se il punto si trova di ovunque in linea. Se non è sulla linea, allora si avrebbe una situazione di distanze (formando un triangolo).
    • Questa soluzione potrebbe essere meglio per errore di gestione. ad esempio, se la differenza di distanza è meno di un pixel, C può essere visualizzato sulla linea A-B.
    • C’è qualcosa di sbagliato con i calcoli perché distance(C, A) = 3, distance(C, B) = 10 e distance(A, B) = 13.
  2. 9

    ATTENZIONE! Matematica-solo!

    Check è un punto (x,y) si trova tra due punti disegnati su una linea retta

    Si può provare questa formula. Metti il tuo A(x1, y1) e B(x2, y2) coordinate formula, quindi si otterrà qualcosa di simile

    y = k*x + b; //k and b - numbers

    Quindi, di tutti i punti che soddisfano questa equazione, si trovano sulla linea.
    Per verificare che C(x, y) è tra A(x1, y1) e B(x2, y2), controllare questo: (x1<x<x2 && y1<y<y2) || (x1>x>x2 && y1>y>y2).

    Esempio

    A(2,3) B(6,5)

    L’equazione della linea:

    (y - 3)/(5 - 3) = (x - 2)/(6 - 2)
    (y - 3)/2 = (x - 2)/4
    4*(y - 3) = 2*(x - 2)
    4y - 12 = 2x - 4
    4y = 2x + 8
    y = 1/2 * x + 2; //equation of line. k = 1/2, b = 2;

    Verificare se C(4,4) si trova su questa linea.

    2<4<6 & 3<4<5 //C between A and B

    Ora mettete C coordinate di equazione:

    4 = 1/2 * 4 + 2
    4 = 2 + 2 //equal, C is on line AB

    PS: come @paxdiablo scritto, è necessario controllare se la linea è orizzontale o verticale prima di eseguire il calcolo. Basta controllare

    y1 == y2 || x1 == x2
    • qual è lo scopo di y = k*x + b; // k e b – i numeri di quello che è il valore di k e b ?
    • Dipende da A e B di coordinate.
    • Non provate a farlo a casa se le linee può essere orizzontale o verticale 🙂
    • funziona per linee orizzontali e verticali così 😉
    • Davvero? Qual è la k valore per (1,0) per (1,2) 🙂 O basta collegare quei due coords nel tuo metodo: (x-1)/(1-1) sta per provocare (e Java) molto dolore e stridore di denti. Non è un non risposta, ma è necessario rilevare e correggere per le infinite sfumature di prima.
    • +∞. Ma ricordate che per linee orizzontali e verticali non c’è più dipendenza lineare. Non c’è dipendenza a tutti 🙂 è facile da controllare prima di eseguire il calcolo.
    • Questo ha funzionato perfettamente per me. Molto semplice, perché la spiegazione matematica. L’algoritmo è quindi molto semplice. Funziona per tutti gli stili di una linea. Anche quando C non è all’interno di Un & B allora funziona!
    • Abbiamo qualche soluzione più veloce se dobbiamo cercare il punto nel dire 25-30 righe?
    • Credo che se si (x1 - x2)(y - y1) == (y1 - y2)(x - x1), non è necessario fare un orizzontale o verticale controllare prima. Ovviamente i controlli sono per evitare di dividere per zero, ma questo non soffre di questo.
    • Tuttavia, la verifica dei limiti è necessario per linee orizzontali e verticali.

  3. 7

    Credo che la cosa più semplice è

    //is BC inline with AC or visa-versa
    public static boolean inLine(Point A, Point B, Point C) {
       //if AC is vertical
       if (A.x == C.x) return B.x == C.x;
       //if AC is horizontal
       if (A.y == C.y) return B.y == C.y;
       //match the gradients
       return (A.x - C.x)*(A.y - C.y) == (C.x - B.x)*(C.y - B.y);
    }

    Può calcolare il gradiente prendendo la differenza nei valori di x diviso per la differenza nei valori di y.

    Nota: c’è un test diverso per vedere se C viene visualizzato sulla linea tra A e B se si disegna su uno schermo. Matematica presuppone che A, B, C sono infinitamente piccoli punti. In realtà molto piccole all’interno di rappresentazione di errore.

    • Questo è lo stesso problema come SeniorJD risposta. La pendenza di una linea verticale è infinito (o, più correttamente, indefinita, ma tende verso l’infinito).
    • Non di divisione per 0, ma io non sono questo risolve il problema.
    • Per linee verticali o orizzontali, linee, questo test (da sé) restituisce true se la punto ha lo stesso valore di x per linee verticali, o valore di y per linee orizzontali, indipendentemente dal fatto o meno il punto è che tra i punti finali della linea.
    • Questo codice superato tutti i miei test di unità e \o/.
    • Piuttosto banale, ma non i commenti se AC è orizzontale e AC è verticali essere scambiati in giro?, vale a dire, AC sarà VERTICALE, quando A. x == x C.
  4. 2

    Le risposte di cui sopra sono inutilmente complicate. Il più semplice è il seguente.

    1. se (x-x1)/(x2-x1) = (y-y1)/(y2-y1) = alfa (una costante), allora il punto C(x,y) si trovano sulla linea tra pts 1 & 2.

    2. Se alfa < 0.0, quindi C è esterno al punto 1.

    3. Se alfa > 1.0, poi C è esterno al punto 2.
    4. Infine se alfa = [0,1.0], poi C è interno al 1 & 2.

    Spero che questa risposta aiuta.

    • se tutti i punti dell’asse x, come si fa questo lavoro
  5. 1

    Un modo semplice per fare che, credo, sarebbe il controllo dell’angolo formato da 3 punti.
    Se l’angolo ACB è di 180 gradi (o vicino ad esso,a seconda di come preciso che si desidera essere) allora il punto C è tra A e B.

  6. 0

    Credo che tutti i metodi qui hanno un’insidia, in quanto non si tratta di errori di arrotondamento nel modo più rigoroso possibile. Fondamentalmente i metodi descritti vi dirà se il vostro punto è abbastanza vicino alla linea utilizzando qualche semplice algoritmo e che sarà più o meno preciso.

    Perché la precisione è importante? Perché il problema presentato da op. Per un programma di computer non c’è nessuna tale cosa come un punto su una linea, c’è un solo punto all’interno di un epsilon di una linea e la cosa che epsilon è, deve essere documentata.

    Andiamo a illustrare il problema. Utilizzando la distanza algoritmo di confronto:

    Diciamo un segmento che va da (0, 0) e (0, 2000), stiamo usando galleggia nella nostra applicazione (che sono intorno a 7 cifre decimali di precisione) e noi verificare se un punto (1E-6, 1000) è in linea o non.

    La distanza da entrambe le estremità del segmento, il punto è 1000.0000000005 o 1000 + 5E-10, e, pertanto, la differenza con l’aggiunta di distanza e il punto è di circa 1E-9. Ma nessuno di questi valori possono essere memorizzati su un carro con sufficiente precission e il metodo restituirà true.

    Se usiamo un metodo più preciso, come calcolare la distanza di un punto più vicino della linea, restituisce un valore float che ha una precisione sufficiente per memorizzare e abbiamo potuto ritornare false a seconda dell’accettabile epsilon.

    Ho usato galleggia nell’esempio, ma lo stesso vale per qualsiasi tipo a virgola mobile come ad esempio il doppio.

    Una soluzione è usare BigDecimal e il metodo che si desidera se incorrere in termini di prestazioni e colpo di memoria non è un problema.

    Un metodo più preciso rispetto a confrontare le distanze per la floating points, e, cosa più importante, costantemente preciso, anche se ad un elevato costo computazionale, è il calcolo della distanza dal punto più vicino della linea.

    Distanza più breve tra un punto e un segmento di linea

    Sembra che io stia spaccando i capelli, ma ho avuto a che fare con questo problema prima. È un problema quando il concatenamento operazioni geometriche. Se non hai il controllo che tipo di precission perdita che hai a che fare con, alla fine, è difficile bug che ti costringe a ragionare rigorosamente il codice per risolverli.

Lascia un commento