Generate non intersecting line segments within a polygon

Awaiting user input

天 景

• January 19, 2024 03:00

Hi,

Expect to generate a line segment within the polygon that does not intersect with its boundaries (the polygon may be non convex). I tried to build a constraint model using geometric methods, given the starting coordinate point, and added cross product constraints between internal and boundary line segments to control non intersection with various polygon boundaries. However, in reality, I was unable to obtain the expected results. I would like to receive some suggestions for model building. Thank you very much.

0

• 

  Mario Ruthmair

  Gurobi Staff

  • January 29, 2024 13:32

  Hi,

  What exactly is the optimization problem that you want to solve?
  Are you working in a continuous space or is the 2D plane discretized?

  Best regards,
  Mario

  0
• 

  天 景

  • January 30, 2024 02:14

  

  

  

  Hi Mario,
          I expect to construct a continuous 2D shape as the boundary.The original problem can be abstracted as specifying the starting point coordinates and the number of inflection points in a given region, generating a fixed total length line scheme (not intersecting with the boundary of the region). For example, A (1, 5), B (1, 1), C (7, 1), and D (7, 5) in the figure are the outer contours, with the specified points E (1.5, 2) and F (6, 4.5), and the number of inflection points set to 1. Find the coordinates of point G so that the length sum is 6, that is, EF+GF=6. At present, I am trying to build an overall model but have not achieved the effect of not intersecting with the regional boundary, which is why I have simplified it. So simplify the problem and try to generate a line segment within the region that does not intersect with the boundary of the region. Building models using geometric schemes (reference https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/) .The picture shows the vector cross product model I built，However, the expected results have not been achieved yet, so I would like to seek your help. Thank you very much.

  

  

  0
• 

  Mario Ruthmair

  Gurobi Staff

  • February 05, 2024 12:25

  This seems to be a tough (but interesting!) problem. So, what exactly is the issue that you observe? How do you put the pieces together in a model?

  I see your inner_multiply() function. It seems you are expanding the formula for the orientation. Usually, it is recommended to use as few quadratic terms as possible in the model. So it might be better to introduce helper variables for the coordinate differences and multiply those instead.

  The orientation formula gives you a continuous value. The sign of the value tells you the orientation. So, how do you use this value in the rest of the model? How do you combine the conditions?

  There is a lot to do to use the orientation value in a model that should find a non-intersecting line. Could you send us the mathematical model you have so far?

  0

Please sign in to leave a comment.