Hộp giới hạn 2D của một ngành?

Question

Tôi đã googled cho đến khi tôi là màu xanh vào mặt, và trừ khi tôi đang thiếu một cái gì đó thực sự rõ ràng, tôi không thể tìm thấy bất kỳ thuật toán để tính toán các hộp bounding của một khu vực 2D.

Cho điểm trung tâm của vòng tròn bao quanh, bán kính và góc của phạm vi của ngành, thuật toán tốt nhất để tính hình chữ nhật bao quanh trục của khu vực đó là gì?

Answer 1

• Tạo những điểm sau đây:
  • trung tâm của vòng tròn
  • Các vị trí của hai bán kính trên đường tròn
  • Các điểm trên vòng tròn cho mỗi góc giữa hai chia bởi 90 ^o (tối đa 4 điểm)
• Tính min và max x và y so với các điểm trên. Đây là hộp giới hạn của bạn

Answer 2

Tôi sẽ thuật lại câu trả lời của yairchu để nó rõ ràng hơn (với tôi, dù sao).

Bỏ qua tọa độ trung tâm ngay bây giờ và vẽ vòng tròn tại điểm gốc. Thuyết phục chính bạn về những điều sau:

1. Bất kỳ nơi nào cung tròn giao nhau với trục sẽ là tối đa hoặc tối thiểu.
2. Nếu cung không cắt một trục, thì tâm sẽ là một góc của hình chữ nhật bao quanh, và đây là trường hợp duy nhất khi nó được hiển thị.
3. Điểm cực duy nhất có thể có khác của ngành để xem xét là điểm cuối của bán kính.

Bây giờ bạn có tối đa 4 + 1 + 2 điểm để tìm. Tìm max và min của các tọa độ đó để vẽ hình chữ nhật.

Hình chữ nhật dễ dàng được dịch sang vòng tròn ban đầu bằng cách thêm tọa độ của tâm của vòng tròn ban đầu vào tọa độ của hình chữ nhật.

Answer 3

Trước hết tôi xin lỗi nếu tôi phạm sai lầm khi viết nhưng tiếng Anh không phải là ngôn ngữ đầu tiên của tôi, tiếng Tây Ban Nha thực sự là!

Tôi gặp sự cố này và tôi nghĩ mình đã tìm được giải pháp hiệu quả.

Trước hết chúng ta hãy xem một hình ảnh về tình hình

Vì vậy, chúng ta có một hình elip (thực sự là một vòng tròn) và hai điểm (C, D) mà chỉ ra khu vực của chúng tôi. Chúng tôi cũng có trung tâm của vòng tròn của chúng tôi (B) và góc của Arc alpha.

Bây giờ, trong trường hợp này, tôi chuyển nó qua 360º trên porpouse để xem nó có hoạt động hay không.

Giả sử alpha -> -251.1º (tiêu cực gây ra theo chiều kim đồng hồ), cho phép biến đổi thành giá trị dương 360º - 251.1º = 108.9º bây giờ mục tiêu của chúng tôi là tìm góc chia của góc đó để chúng tôi có thể tìm điểm tối đa cho hộp giới hạn (E in hình ảnh), thực tế như bạn có thể đã nhận ra, chiều dài của đoạn BE bằng bán kính của vòng tròn nhưng chúng ta phải có góc để có tọa độ thực tế của điểm E.

Vì vậy, 108.9º/2 -> 54.45º bây giờ chúng tôi có góc.

Để tìm tọa độ của E chúng ta sử dụng tọa độ cực để

x = r * Cos(theta) 
y = r * Sin(theta) 

chúng tôi có r và theta vì vậy chúng tôi có thể tính toán x và y

trong ví dụ của tôi r = 2.82 ... (trên thực tế đó là irational nhưng tôi mất hai chữ số thập phân đầu tiên là vấn đề dễ dàng)

Chúng tôi biết bán kính đầu tiên của chúng tôi là 87.1º vì vậy theta sẽ là 87.1 - 54.45º -> 32.65º

chúng ta biết * theta * được 32.65º vì vậy hãy làm một số toán

x = 2.82 * Cos(32.65º) -> 2.37552 
y = 2.82 * Sin(32.65º) -> 1.52213 

Bây giờ chúng ta cần phải điều chỉnh các giá trị đến trung tâm thực tế của các vòng tròn để

x = x + centerX 
y = y + centerY 

Trong ví dụ này, vòng tròn được đặt tại (1.86, 4.24)

x -> 4.23552 
y -> 5.76213 

Ở giai đoạn này, chúng tôi nên sử dụng một số phép tính. Chúng ta biết rằng một trong các cạnh của hộp giới hạn sẽ là một tiếp tuyến của vòng cung đi qua điểm mà chúng ta vừa tính toán, cho phép tìm ra đường tiếp tuyến đó (đường màu đỏ).

Chúng tôi biết rằng đường tiếp tuyến đi qua điểm (4.23, 5.76) của chúng tôi bây giờ chúng ta cần độ dốc.

Như bạn có thể thấy, độ dốc giống với độ dốc của đường cong đi qua bán kính của chúng ta nên chúng ta phải tìm độ dốc đó.

Để thực hiện điều đó, chúng ta cần có tọa độ của bán kính của chúng ta (chuyển đổi nhanh thành tọa độ cartess từ tọa độ cực).

x = r * Cos(theta) 
y = r * Sin(theta) 

Vì vậy

p0 = (centerX + 2.82 * Cos(87.1º), centerY + 2.82 * Sin(87.1º)) 
p1 = (centerX + 2.82 * Cos(-21.8º), centerY + 2.82 * Sin(-21.8º)) 

(21.8º là góc đo chiều kim đồng hồ từ trục ngang vào bán kính đó là bên dưới nó và vì vậy tôi đặt nó tiêu cực)

p0 (2, 7.06) 
p1 (4.48, 3.19) 

bây giờ hãy tìm độ dốc:

m = (y - y0)/(x - x0) 
... 
m = (3.19 - 7.06)/(4.48-2) = -3.87/2.48 = -1.56048 
... 
m = -1.56 

có độ dốc chúng ta cần phải tính toán phương trình cho các tiếp tuyến, về cơ bản là một rect với một độ dốc đã được biết đến (m = -1.56) mà đi qua một điểm đã biết (E -> (4.23, 5.76))

Vì vậy, chúng tôi có Y = mx + b nơi m = -1.56, y = 5.76 và x = 4.23 nên b phải

b = 5.76 - (-1.56) * 4.23 = 12.36 

Bây giờ chúng ta có phương trình hoàn chỉnh cho tiếp tuyến của chúng tôi ->Y = -1.56X + 12.36 Tất cả chúng ta phải biết là dự án điểm C và D qua đó rect.

Chúng ta cần các phương trình cho các hình chữ nhật CH và DI vì vậy hãy tính toán 'em

Hãy bắt đầu với CH:

Chúng ta biết (từ phương trình của tanget) mà vector hướng của chúng tôi là (1.56, 1)

Chúng ta cần tìm một đường cắt xuyên qua điểm C -> (2, 7.06)

(x - 2)/1.56 = (y - 7.06)/1 

Thực hiện một số đại số ->y = 0.64x + 5.78

Chúng tôi biết có phương trình cho trực tiếp CH chúng ta phải tính điểm H.

chúng ta phải giải quyết một hệ thống tuyến tính như sau

y = -1.56x + 12.36 
y = 1.56x + 5.78 

Giải quyết này, chúng ta sẽ tìm thấy điểm H (3, 7.69)

Chúng ta cần phải làm tương tự với các rect DI vì vậy hãy làm điều đó

Vectơ hướng của chúng tôi là (1.56, 1) một lần nữa

D -> (4.48, 3.19) 

(x - 4.48)/1.56 = (y -3.19)/1 

Làm một số đại số ->y = 0.64x + 0.32

Cho phép giải quyết các hệ thống tuyến tính

y = -1.56x + 12.36 
y = 0.64x + 0.32 

I (5.47, 3.82) 

Ở giai đoạn này, chúng tôi đã có bốn điểm mà làm cho hộp Bounding của chúng tôi ->C, H, D , I

Chỉ trong trường hợp bạn don không biết hoặc nhớ cách giải quyết hệ thống tuyến tính bằng ngôn ngữ lập trình, tôi sẽ cung cấp cho bạn một ví dụ nhỏ

Đó là đại số thuần túy

Hãy nói rằng chúng ta có hệ thống sau

Ax + By = C 
Dx + Ey = F 

sau đó

Dx = F - Ey 
x = (F - Ey)/D 
x = F/D - (E/D)y 

thay thế vào phương trình khác

A(F/D - (E/D)y) + By = C 
AF/D - (AE/D)y + By = C 
(AE/D)y + By = C - AF/D 
y(-AE/D + B) = C - AF/D 
y = (C - AF/D)/(-AE/D + B) 
    = ((CD - AF)/D)/((-AE + BD)/D)) 

nên

y = (CD - AF)/(BD - AE) 

và cho x chúng tôi làm như vậy

Dx = F - Ey 
Dx - F = -Ey 
Ey = F - Dx 
y = F/E - (D/E)x 

thay thế vào phương trình khác

Ax + B(F/E - (D/E)x) = C 
Ax + (BF/E - (DB/E)x) = C 
Ax - (DB/E)x = C - BF/E 
x (A-(DB/E)) = C - BF/E 
x = (C - BF/E)/(A-(DB/E)) 
    = ((CE - BF)/E)/((AE-DB)/E) 

x = (CE - BF)/(AE - DB) 

Tôi xin lỗi vì phạm vi của câu trả lời của tôi, nhưng tôi có nghĩa là càng rõ ràng càng tốt và vì thế, tôi đã làm cho nó gần như từng bước.