¿Todos los algoritmos para la geometría computacional?

Supongamos el vector bidimensional P = (x1, y1), Q = (x2, y2).

Entonces la resta de vectores se define como: P-Q = (x1-x2, y1-y2).

Obviamente tiene la propiedad de P-Q =-(Q-P)

A menos que se especifique lo contrario, todos los puntos siguientes se consideran vectores, y la resta de dos puntos es resta de vectores;< /p >

2. Producto cruzado del vector

Supongamos el vector P = (x1, y1), Q = (x2, y2).

Entonces el producto vectorial vectorial se define como: P × Q = x1*y2-x2*y1, y el resultado es un escalar.

Obviamente, tiene la propiedad de P × Q =-(Q × P) P × (-Q) =-(P × Q).

A menos que se especifique lo contrario, todos los puntos siguientes se consideran vectores y el producto de los puntos se considera un producto vectorial cruzado;

Propiedades importantes de los productos cruzados:

& gtSi P × Q > 0, entonces P está en el sentido de las agujas del reloj de Q.

& gtSi p × q

& gtSi P × Q = 0, entonces P y Q son líneas * * *, pero pueden tener la misma dirección o la dirección opuesta.

3. El punto de juicio está en el segmento de recta.

Establece el punto en q y el segmento de recta en P1P2. La base para juzgar el punto q en este segmento de línea es:

(Q-P1) × (P2-P1) = 0, Q está en un rectángulo con P1 y P2 como vértices diagonales.

4. Determina si dos segmentos de recta se cruzan.

Determinamos si dos segmentos de recta se cruzan en dos pasos:

(1). Prueba de repulsión rápida

Sea R el rectángulo con diagonal P1P2. El rectángulo. con diagonales Q1Q2 es t. Si

r y t no se cruzan, obviamente los dos segmentos de recta no se cruzan;

(2). Si dos segmentos de línea se cruzan, deben cruzarse, como se muestra en la Figura 1. En la Figura 1, se extiende P1P2.

Q1Q2, entonces los vectores (P1-Q1) y (P2-Q1) se ubican a ambos lados del vector (Q2-Q1), es decir,

(p 1 -q 1)×( Q2-q 1)*(P2-q 1)×(Q2-q 1)<0

La fórmula anterior se puede reescribir como

( p 1-q 1) ×(Q2-q 1)*(Q2-q 1)×(P2-q 1)>0

Cuando (P1-Q1)×(Q2-q 1) = 0, explica (p 1-q 1) y (Q2-Q1)*** *Estas dos líneas.

Pero debido a que pasó la prueba de eliminación rápida, P1 debe estar en el segmento de línea Q1Q2 de manera similar,

(Q2-Q1) ×(P2-Q1) = 0 significa que P2; debe estar en el segmento de línea en Q1Q2.

Entonces, la base para juzgar que P1P2 abarca Q1Q2 es:

(p 1-q 1)×(Q2-q 1)*(Q2-q 1)×(P2- q 1 )≥0

De manera similar, la base para juzgar si Q1Q2 abarca P1P2 es:

(q 1-p 1)×(P2-p 1)*(P2-p 1) ×(Q2-p 1)≥0

En este punto, el problema de determinar si los segmentos de línea se cruzan está completamente resuelto.

5. Determina si el segmento de recta y la recta se cruzan.

Si el segmento de línea P1P2 intersecta a la línea recta Q1Q2, entonces P1P2 abarca Q1Q2, es decir:

(p 1-q 1)×(Q2-q 1)*(Q2-q 1 )×(P2-q 1)≥0

6 Determina si el rectángulo contiene puntos.

Solo necesitas determinar si la abscisa y la ordenada del punto están intercaladas entre los lados izquierdo y derecho y los lados superior e inferior del rectángulo.

6. Determina si los segmentos de línea, polilíneas y polígonos están dentro del rectángulo.

Debido a que el rectángulo es un conjunto convexo, solo necesitas determinar si todos los puntos finales están dentro del rectángulo.

7. Determina si el rectángulo está dentro del rectángulo.

Simplemente compare los bordes izquierdo y derecho con los bordes superior e inferior.

8. Determina si el círculo está dentro del rectángulo.

La condición necesaria y suficiente para un círculo en un rectángulo es que el centro del círculo esté dentro del rectángulo, y el radio del círculo sea menor o igual a la distancia desde el centro del círculo. a los cuatro lados del rectángulo.

El valor mínimo de la distancia.

9. Determinar si un punto está en un polígono.

Con el punto P como punto final, haz que la luz L vaya hacia la izquierda. Como el polígono está acotado, debe haber muchos extremos izquierdos del rayo l.

Fuera del polígono, considere moverse de izquierda a derecha a lo largo de L desde el infinito para encontrar la primera intersección del polígono.

, entró en el interior del polígono, encontró la segunda intersección, abandonó el polígono,...

Es fácil ver que cuando la intersección número c de L y el polígono es un número impar, cuando P está en un polígono, es un número par.

p está fuera del polígono.

Pero hay algunas circunstancias especiales a considerar. Si l cruza los vértices de un polígono, en algunos casos, el punto de intersección solo se puede contar como uno. En algunos casos, no es necesario contar el punto de intersección (simplemente haga un dibujo usted mismo si l y el polígono <); /p>

Superpuestas en un lado, este lado debe ignorarse. En aras de la uniformidad, estamos calculando la intersección del rayo L y el polígono en la intersección de las formas, 1 sin tener en cuenta los lados horizontales del polígono 2; Para el vértice de un polígono que se cruza con L

En el caso de la intersección, si el vértice es el vértice con la ordenada más grande en el borde al que pertenece, cuéntelo, de lo contrario ignórelo;

3. Para el caso en que P está en el borde de un polígono, se puede juzgar directamente que P pertenece a una polilínea. A partir de esto, se obtiene el pseudocódigo del algoritmo

de la siguiente manera:

1. Contar ←0;

2. a la izquierda Haz un rayo L;

3 a cada lado del polígono.

4. Si P está en el borde, hazlo

5 Luego devuelve verdadero

6. > 7. Entonces, si un punto final de s está en L y es el punto final con la ordenada más grande entre los dos puntos finales de s.

9. Luego cuenta ← cuenta + 1

10. De lo contrario, si s y l se cruzan

11.

12. Si el módulo de recuento 2 = 1

13. Entonces devuelve verdadero

14. De lo contrario, devuelve falso

El método para crear el rayo L es. : La ordenada de P' es la misma que P, y la abscisa es infinito positivo (un infinito positivo grande)

Número), entonces p y p' determinan el rayo l. La complejidad de este algoritmo es. En) .

10. Determina si el segmento de recta está dentro del polígono.

Una condición necesaria para que un segmento de línea esté dentro de un polígono es que ambos puntos finales del segmento de línea estén dentro del polígono

Si un segmento de línea intersecta un borde del polígono ( dos segmentos de línea se cruzan significa que dos segmentos de línea se cruzan y el punto de intersección no está en los dos segmentos de línea)

Puntos finales), porque los lados izquierdo y derecho de los lados del polígono pertenecen a partes diferentes dentro y fuera el polígono, por lo que debe haber segmentos de línea.

Parte del mismo está fuera del polígono. Entonces obtenemos la segunda condición necesaria para los segmentos de línea en polígonos: segmentos de línea y polígonos.

Todos los lados de una forma no están inscritos;

La intersección de un segmento de línea y un polígono en ambos extremos del segmento de línea no afecta si el segmento de línea está dentro del polígono, pero; si un polígono

Cuando un vértice intersecta un segmento de línea, es necesario determinar si el segmento de línea entre dos puntos de intersección adyacentes contiene el interior del polígono.

Entonces, primero podemos encontrar los vértices de todos los polígonos que intersecan el segmento de línea y luego ordenarlos según las coordenadas X-Y. De esta manera,

Dos puntos adyacentes son dos adyacentes. puntos de intersección en el segmento de recta. Si el punto medio de dos puntos adyacentes cualesquiera también está dentro del polígono,

el segmento de línea debe estar dentro del polígono. La prueba es la siguiente:

Proposición 1:

Si el punto medio P' del segmento de recta y los dos puntos de intersección adyacentes P1 y P2 del polígono también están dentro del polígono, luego tome el valor entre el valor P1 y P2.

Todos los puntos están dentro de un polígono.

Demostración:

Supongamos que hay un punto entre P1 y P2 que no está dentro del polígono, sea q, entre P1 y P', porque es un polígono.

La forma es una curva cerrada, por lo que su interior y exterior están acotados, mientras que P1 pertenece al interior del polígono y Q pertenece al exterior del polígono.

P' pertenece al interior del multilateralismo, P1-Q-P' es completamente continuo, por lo que P1Q y QP' deben cruzar el límite del polígono, por lo

La distancia entre p1 y p' es al menos Hay dos intersecciones, lo que contradice que P1P2 sea adyacente entre sí.

Esta propuesta se mantiene. Certificado de finalización

La inferencia se puede extraer directamente de la Proposición 1:

Corolario 2:

Supongamos que los puntos de intersección del polígono y el segmento de línea PQ son P1, P2,... Secuencia PN, donde Pi y Pi+1 son dos puntos de intersección adyacentes, y el segmento de recta

Las condiciones necesarias y suficientes para que PQ esté dentro del polígono son: P, Q están dentro del polígono y para I = 1, 2, ..., N-1, Pi, Pi+1. El punto medio de

también está dentro del polígono.

En la programación real, no es necesario calcular todas las intersecciones. Primero, determine si el segmento de línea y el borde del polígono se cruzan.

Si un segmento de línea interseca un borde del polígono, entonces el segmento de línea debe estar fuera del polígono; si cada segmento de línea intersecta el polígono

Si ningún borde se cruza, entonces la línea segmento y el polígono. El punto de intersección debe ser un punto final de un segmento de línea o un vértice de un polígono.

Basta con juzgar si el punto está en el segmento de recta.

En este punto, obtenemos el siguiente algoritmo:

1. Los puntos finales de PQ al final de la línea if no están todos dentro del polígono.

2. Luego devuelve falso

3. El conjunto de puntos se inicializa para que esté vacío

4.

5. El punto final del segmento de línea DOIF está en s.

6. Luego agregue el punto final al pointSet

7. Si s está en la línea PQ, es el punto final de else.

8. Luego agregue el punto final a pointSet

9. Else Si s cruza la línea PQ// en este momento, se puede determinar que se cruzan.

10. Luego devuelve falso

11 Ordena los puntos en el conjunto de puntos según las coordenadas X-Y, con la coordenada X más pequeña al frente.

Para puntos con la misma coordenada X, el que tiene la coordenada Y más pequeña viene primero;

12 Para el conjunto de puntos [i], cada dos puntos adyacentes en el conjunto de puntos [i+1]. Puntos

13. Si el conjunto de puntos [i], el punto medio del conjunto de puntos [i+1] no está dentro del polígono.

14. Luego devuelve falso

15. Devuelve verdadero

La complejidad de este algoritmo también es O (n). Porque el número de puntos de intersección es ciertamente mucho menor que el número de vértices de un polígono.

n, por lo que la complejidad es como mucho una constante y casi insignificante.

11. Asegúrate de que la polilínea esté dentro del polígono.

Simplemente determina si cada segmento de la polilínea está dentro del polígono. Supongamos que una polilínea tiene m segmentos de línea y un polígono tiene n segmentos de línea.

Vértice, la complejidad es O(m*n).

12. Determina si el polígono está dentro del polígono.

Simplemente determina si cada lado del polígono está dentro del polígono. Determine si un polígono con m vértices no lo es. En un polígono con n vértices, la complejidad es O (m*n).

13. Determina si el rectángulo está dentro del polígono.

Convierte el rectángulo en un polígono y luego determina si está dentro del polígono.

14. Determina si el círculo está dentro del polígono.

Siempre que se calcule la distancia más corta desde el centro del círculo a cada lado del polígono, si la distancia es mayor o igual al radio del círculo, el círculo es

dentro del polígono. El algoritmo para calcular la distancia más corta desde el centro de un círculo a cada lado de un polígono se describe más adelante.

15. Determina si el punto está dentro del círculo.

Calcula la distancia desde el centro del círculo hasta el punto. Si es menor o igual que el radio, el punto está dentro del círculo.

16. Determinar si un segmento de línea, polilínea, rectángulo o polígono está dentro de un círculo.

Debido a que el círculo es un conjunto convexo, solo necesitas determinar si cada vértice está dentro del círculo.

17. Determina si el círculo está dentro del círculo.

Supongamos que los dos círculos son O1 y O2, y los radios son r1 y r2 respectivamente. Es necesario determinar si el O2 está dentro del O1.

Primero compare los tamaños de r1 y r2.

, si r1 < R2, O2 no puede estar en o 1; en caso contrario, si la distancia entre los dos centros es mayor que r1-r2, O2 no existe.

Dentro de O1; de lo contrario, O2 está dentro del rango de O1.

18. Calcula el punto más cercano de un punto a un segmento de recta.

Si el segmento de recta es paralelo al eje X (eje Y), entonces el punto de intersección es el Perpendicular a la recta donde se ubica el segmento de recta, y el pie vertical es muy tolerante.

Se obtiene fácilmente y luego calcula el pie vertical. Si el pie vertical está en línea recta, regresa al pie vertical; de lo contrario, regresa al punto final cerca del pie vertical.

Punto;

Si el segmento de recta no es paralelo al eje X o al eje Y, la pendiente existe y no es 0. Supongamos que los dos extremos del segmento de recta son

Pt1 y pt2, y la pendiente es:

k = (pt2.y - pt1.y)/(pt2 . x- pt 1 . x);

La ecuación lineal es:

y = k *(x-pt 1 . x)+pt 1 . la pendiente de su línea vertical es -1 /k,

La ecuación vertical es:

y = (-1/k) * (x punto x) + punto y

Dos soluciones simultáneas de ecuación lineal;

x =(k^2 * pt 1 . x+k *(punto . y-pt 1 . y)+punto . x)/(k ^2+1)

y = k *(x-pt 1 . Si no, se calculan ambos puntos finales.

Distancia al pie vertical, seleccione el punto final más cercano al pie vertical al que desea regresar.

19. Calcula el punto más cercano desde un punto a una polilínea, rectángulo o polígono.

Simplemente calcula el punto más cercano desde el punto a cada segmento de línea, registra la distancia más cercana y toma. el punto con la distancia más pequeña.

Sí.

20. Calcula la distancia más cercana de un punto a un círculo.

Si el punto está en el centro del círculo, se devuelve UNDEFINED.

Conecta el punto P y el centro de O. Si PO es paralelo al eje X, calcula el punto más cercano en función de si P está a la izquierda o a la derecha de O.

La abscisa es centerPoint.x-radius o centerPoint.x+radius, como se muestra en la Figura 4 (a);

Si PO es paralelo al eje y, entonces de acuerdo con to p in o Arriba o abajo para calcular la ordenada del punto más cercano.

CenterPoint.y+radius o centerPoint.y-radius, como se muestra en la Figura 4 (b).

Si PO no es paralelo a los ejes xey, entonces la pendiente de PO existe y no es 0, como se muestra en la Figura 4(c). En este momento, la pendiente de la recta PO

es

k = (P.y - O.y)/ (P.x - O.x)

La ecuación de la recta PO es:

y = k * ( x - P.x) + P.y

Supongamos que la ecuación del círculo es:

(x - O.x ) ^2 + ( y - O.y ) ^2 = r ^2,

La intersección de la recta PO y el círculo se puede resolver combinando dos ecuaciones y tomando la intersección cerca del punto P.

21. Calcula el punto de intersección de los segmentos de las dos * * * rectas.

Para los segmentos de las dos * * * rectas, la relación posicional entre ellas es como se muestra en Situación de la figura 5.

Los dos segmentos de línea en la Figura 5(a) no tienen intersección; los dos segmentos de línea en las Figuras 5(b) y 5(d) tienen una distancia focal infinita;

Hay una intersección entre los dos segmentos de línea. Sea la línea 1 el segmento de línea más largo y la línea 2 el segmento de línea más corto.

Si la línea 1 contiene los dos puntos finales de la línea 2, es la situación en la Figura 5 (d). Los dos segmentos de línea tienen infinitos puntos de intersección, como por ejemplo

Si la línea 1 solo contiene; línea 2, entonces si un punto final de la fila 1 es igual al punto final contenido en la fila 1.

El punto final de la línea 2 es la situación en la Figura 5 (c). En este momento, solo hay una intersección entre los dos segmentos de línea;

En el caso de la Figura 5(c), los dos segmentos de línea también tienen infinitos puntos de intersección; si la fila 1 no contiene ningún punto final de la fila 2,

Esta es la Figura 5. (a) En este caso, los dos segmentos de recta no tienen intersección.

22. Calcular el punto de intersección de un segmento de recta o una recta y un segmento de recta.

Supongamos que un segmento de recta es L0 = P1P2, y otro segmento de recta o recta es L1 = Q1Q2. Los cálculos son L0 y L1.

La intersección.

1. Primero determine si L0 y L1 se cruzan (el método se analizó anteriormente). Si no se cruzan, no hay intersección.

En caso contrario deberá existir una intersección entre L0 y L1. Consideramos tanto a L0 como a L1 como líneas rectas.

2. Si P1 y P2 tienen la misma abscisa, es decir, L0 es paralela al eje Y.

a) Si L1 también es paralela al eje y,

1 Si la ordenada de P1 es la misma que la ordenada de Q1, significa que L0 y L1*. ** líneas, si L1 es líneas rectas, entonces tienen.

Intersecciones infinitas, si L1 es un segmento de línea, se pueden encontrar mediante el algoritmo de "calcular la intersección de dos * * * segmentos de línea".

El punto de intersección (este método se ha comentado anteriormente);

2. De lo contrario, L0 y L1 son paralelas y no tienen intersección;

b) Si L1 no es paralela al eje y, la abscisa de la intersección es P1, que se puede calcular sustituyéndola en la línea lineal ecuación de L1.

Calcule la ordenada de la intersección;

3 Si las abscisas de P1 y P2 son diferentes, pero las abscisas de Q1 y Q2 son iguales, es decir, L1 es paralela. al eje Y, entonces la intersección es horizontal.

La coordenada de abscisa de Q1 se puede sustituir en la ecuación lineal de L0 para calcular la ordenada de la intersección

4 Si P1 y P2 tienen la misma ordenada, es decir, L0 es paralelo al eje X.

a) Si L1 también es paralela al eje x,

1 Si la abscisa de P1 es la misma que la abscisa de Q1, significa L0 y L1*. ** líneas, si L1 es una línea recta, entonces.

Hay infinitas intersecciones. Si L1 es un segmento de línea, se puede encontrar mediante el algoritmo de "calcular la intersección de dos * * * segmentos de línea".

Su intersección (este método se ha comentado en el artículo anterior);

2. De lo contrario, L0 y L1 son paralelas y no tienen intersección;

b) Si L1 no es paralela al eje X, la ordenada de la intersección es la ordenada de P1, que se puede calcular sustituyéndola en la ecuación lineal de L1.

Calcule la abscisa de la intersección;

5 Si las ordenadas de P1 y P2 son diferentes, pero las ordenadas de Q1 y Q2 son iguales, es decir, L1 es paralela. al eje X, luego la ordenada de la coordenada de intersección.

Es la ordenada de Q1. Sustituyéndola en la ecuación lineal de L0 para calcular la abscisa del punto de intersección

6. L0 existe y no es cero.

a) Calcular la pendiente K0 de L0 y la pendiente k 1 de L1

b) Si K1 = K2;

1. Si Q1 está en L0, significa que si L1 es una línea recta, entonces las líneas L0 y L1*** * tienen infinitos puntos de intersección, si es L1.

Si se trata de un segmento de línea, puede utilizar el algoritmo de "calcular la intersección de dos * * * segmentos de línea" para encontrar su intersección (este método se utiliza en

como mencionado anteriormente);

Dos. Si Q1 no está en L0, entonces L0 y L1 son paralelos y no tienen intersección.

c) Se puede resolver el punto de intersección de dos ecuaciones simultáneas en línea recta.

Nota: Este algoritmo no es complicado, pero debe discutirse claramente caso por caso, especialmente cuando hay dos segmentos de línea.

Debe considerarse por separado, por lo que el algoritmo para encontrar dos * * * segmentos de línea se escribirá por separado en el artículo anterior. Además, desde el principio,

primero use el producto vectorial vectorial para determinar si el segmento de línea se cruza con el segmento de línea (o línea recta). Si el resultado es una intersección, entonces sigue el segmento de línea.

Esta superficie puede tratar todos los segmentos de línea como líneas rectas.

23. Encuentra el punto de intersección de un segmento de recta o recta con una polilínea, rectángulo o polígono.

Encuentra los puntos de intersección con cada lado respectivamente.

24. Encuentra el punto de intersección del segmento de recta o recta y la circunferencia.

Supongamos que el centro del círculo es O, el radio del centro es R y los dos puntos de la recta (o segmento de recta) L son P1 y P2.

1. Si L es un segmento de línea y P1 y P2 están incluidos en el círculo O, de lo contrario no hay intersección, continúe con el siguiente paso.

2. Si l es paralelo al eje y,

a) Calcula la distancia dis desde el centro del círculo hasta l

b) Si dis > R, entonces l y los círculos no tienen intersección;

c) Usando el teorema de Pitágoras, se pueden obtener las coordenadas de los dos puntos de intersección, como se muestra en la Figura 6(a), pero se debe prestar atención; pagado a la fase de L y el círculo.

Situación tangencial

3. Si L es paralelo al eje X no es paralelo al eje Y, entonces podemos encontrar la pendiente k de L y luego enumerarla. la ecuación punto-pendiente de L.

, y la ecuación del círculo puede resolver inmediatamente los dos puntos de intersección de ly el círculo.

5 Si L es un segmento de línea, debes determinar si se encuentran los puntos de intersección; en 2, 3 y 4 pertenecen a este El rango del segmento de línea.