Skip to main content

Generate non intersecting line segments within a polygon

Awaiting user input



  • Mario Ruthmair
    Gurobi Staff Gurobi Staff


    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,

  • 天 景
    First Comment
    First Question

    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 .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.

  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    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?


Please sign in to leave a comment.